crypt.tex

NIST推荐的素域上的椭圆曲线

\documentclass{book}
\usepackage{makeidx}
\usepackage{amssymb}
\def\union{\cup}
\def\intersect{\cap}
\def\getsrandom{\stackrel{\rm R}{\gets}}
\def\cross{\times}
\def\cat{\hspace{0.5em} \| \hspace{0.5em}}
\def\catn{$\|$}
\def\divides{\hspace{0.3em} | \hspace{0.3em}}
\def\nequiv{\not\equiv}
\def\approx{\raisebox{0.2ex}{\mbox{\small $\sim$}}}
\def\lcm{{\rm lcm}}
\def\gcd{{\rm gcd}}
\def\log{{\rm log}}
\def\ord{{\rm ord}}
\def\abs{{\mathit abs}}
\def\rep{{\mathit rep}}
\def\mod{{\mathit\ mod\ }}
\renewcommand{\pmod}[1]{\ ({\rm mod\ }{#1})}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\def\Or{{\rm\ or\ }}
\def\And{{\rm\ and\ }}
\def\iff{\hspace{1em}\Longleftrightarrow\hspace{1em}}
\def\implies{\Rightarrow}
\def\undefined{{\rm ``undefined"}}
\def\Proof{\vspace{1ex}\noindent {\bf Proof:}\hspace{1em}}
\let\oldphi\phi
\def\phi{\varphi}
\def\Pr{{\rm Pr}}
\newcommand{\str}[1]{{\mathbf{#1}}}
\def\F{{\mathbb F}}
\def\N{{\mathbb N}}
\def\Z{{\mathbb Z}}
\def\R{{\mathbb R}}
\def\C{{\mathbb C}}
\def\Q{{\mathbb Q}}

\newcommand{\url}[1]{\mbox{$<${#1}$>$}}
\newcommand{\emailaddr}[1]{\mbox{$<${#1}$>$}}
\def\twiddle{\raisebox{0.3ex}{\mbox{\tiny $\sim$}}}

\def\gap{\vspace{0.5ex}}
\makeindex
\begin{document}
\title{A Tiny Crypto Library, \\ LibTomCrypt \\ Version 0.75}
\author{Tom St Denis \\
Algonquin College \\
\\
[e-mail] \\
http://libtomcrypt.iahu.ca \\ \\
Phone: [phone]\\
111 Banning Rd \\
Kanata, Ontario \\
K2L 1C3 \\
Canada 
}
\maketitle
\newpage
\tableofcontents
\chapter{Introduction}
\section{What is the Libtomcrypt?}
Libtomcrypt is a portable ANSI C cryptographic library that supports symmetric ciphers, one-way hashes, 
pseudo-random number generators, public key cryptography (via RSA,DH or ECC/DH) and a plethora of support 
routines.  It is designed to compile out of the box with the GNU C Compiler (GCC) version 2.95.3 (and higher) 
and with MSVC version 6 in win32.

The library is designed so new ciphers/hashes/PRNGs can be added at runtime and the existing API (and helper API functions) will 
be able to use the new designs automatically.  There exist self-check functions for each cipher and hash to ensure that
they compile and execute to the published design specifications.  The library also performs extensive parameter error checking
and will give verbose error messages.

Essentially the library saves the time of having to implement the ciphers, hashes, prngs yourself.  Typically implementing
useful cryptography is an error prone business which means anything that can save considerable time and effort is a good
thing.

\subsection{What the library IS for?}

The library typically serves as a basis for other protocols and message formats.  For example, it should be possible to 
take the RSA routines out of this library, apply the appropriate message padding and get PKCS compliant RSA routines.  
Similarly SSL protocols could be formed on top  of the low-level symmetric cipher functions.  The goal of this package is 
to provide these low level core functions in a robust and easy to use fashion.

The library also serves well as a toolkit for applications where they don't need to be OpenPGP, PKCS, etc. compliant.
Included are fully operational public key routines for encryption, decryption, signature generation and verification.  
These routines are fully portable but are not conformant to any known set of standards.  They are all based on established
number theory and cryptography.  

\subsection{What the library IS NOT for?}

The library is not designed to be in anyway an implementation of the SSL, PKCS or OpenPGP standards.  The library is not 
designed  to be compliant with any known form of API or programming hierarchy.  It is not a port of any other 
library and it is not platform specific (like the MS CSP).  So if you're looking to drop in some buzzword 
compliant crypto this library is not for you.  The library has been written from scratch to provide basic 
functions as well as non-standard higher level functions.  

This is not to say that the library is a ``homebrew'' project.  All of the symmetric ciphers and one-way hash functions
conform to published test vectors.  The public key functions are derived from publicly available material and the majority
of the code has been reviewed by a growing community of developers.

\subsubsection{Why not?}
You may be asking why I didn't choose to go all out and support standards like P1363, PKCS and the whole lot.  The reason
is quite simple too much money gets in the way.  I just recently tried to access the P1363 draft documents and was denied (it 
requires a password).  If people are supposed to support these standards they had better make them more accessible.

\section{Why did I write it?}
You may be wondering, ``Tom, why did you write a crypto library.  I already have one.''.  Well the reason falls into
two categories:
\begin{enumerate}
    \item I am too lazy to figure out someone else's API.  I'd rather invent my own simpler API and use that.
    \item It was (still is) good coding practice.
\end{enumerate}

The idea is that I am not striving to replace OpenSSL or Crypto++ or Cryptlib or etc.  I'm trying to write my 
{\bf own} crypto library and hopefully along the way others will appreciate the work.

With this library all core functions (ciphers, hashes, prngs) have the {\bf exact} same prototype definition.  They all load
and store data in a format independent of the platform.  This means if you encrypt with Blowfish on a PPC it should decrypt
on an x86 with zero problems.  The consistent API also means that if you learn how to use blowfish with my library you 
know how to use Safer+ or RC6 or Serpent or ... as well.  With all of the core functions there are central descriptor tables 
that can be used to make a program automatically pick between ciphers, hashes and PRNGs at runtime.  That means your 
application can support all ciphers/hashes/prngs without changing the source code.

\section{License}

All of the source code except for the following files have been written by the author or donated to the project
under the TDCAL license:

\begin{enumerate}
   \item aes.c
   \item mpi.c
   \item rc2.c
   \item serpent.c
   \item safer.c
\end{enumerate}

``aes.c'' and ``serpent.c'' were written by Brian Gladman ([e-mail]).  They are copyrighted works
but were both granted unrestricted usage in any project (commercial or otherwise).  ``mpi.c'' was written by Michael 
Fromberger ([e-mail]).  Similarly it is copyrighted work but is free for all purposes.  
``rc2.c'' is based on publicly available code that is not attributed to a person from the given source.  ``safer.c'' 
was written by Richard De Moliner ([e-mail]) and is public domain.

The rest of the code was written either by Tom St Denis or contributed to the project under the ``Tom Doesn't Care
About Licenses'' (TDCAL) license.  Essentially this license grants the user unlimited distribution and usage (including
commercial usage).  I assume no risk from usage of the code nor do I guarantee it works as desired or stated.  

\section{Patent Disclosure}

The author (Tom St Denis) is not a patent lawyer so this section is not to be treated as legal advice.  To the best
of the authors knowledge the only patent related issues within the library are the RC5 and RC6 symmetric block ciphers.  
They can be removed from a build by simply commenting out the two appropriate lines in the makefile script.  The rest
of the ciphers and hashes are patent free or under patents that have since expired.

The RC2 and RC4 symmetric ciphers are not under patents but are under trademark regulations.  This means you can use 
the ciphers you just can't advertise that you are doing so.  

\section{Building the library}

To build the library on a GCC equipped platform simply type ``make'' at your command prompt.  It will build the library
file ``libtomcrypt.a''.  

To install the library copy all of the ``.h'' files into your ``\#include'' path and the single libtomcrypt.a file into 
your library path.

With MSVC you can build the library with ``make -f makefile.vc''.  You must use GNU make to build it even with MSVC
due to the limitations of the MS MAKE.

\section{Building against the library}

To build an application against the library you obviously must first compile the library.  However, an important 
step is that the build options you use to build the library must be present when you build your application.  For 
instance if ``RC5'' is defined in the makefile when you built the library then you must ensure ``RC5'' is defined when
you build your application.

The simplest way to work with this library is to take the makefile provided and simply add on your project to it as a 
target (dependent on the library).  That way you can be assured that the library and your application are in sync with
the build options you provide.

\section{Thanks}
I would like to give thanks to the following people (in no particular order) for helping me develop this project:
\begin{enumerate}
   \item Richard van de Laarschot
   \item Richard Heathfield
   \item Ajay K. Agrawal
   \item Brian Gladman
   \item Svante Seleborg
   \item Clay Culver
   \item Jason Klapste
   \item Dobes Vandermeer
   \item Daniel Richards
   \item Wayne Scott
   \item Andrew Tyler
   \item Sky Schulz
\end{enumerate}

\chapter{The Application Programming Interface (API)}
\section{Introduction}
\index{CRYPT\_ERROR} \index{CRYPT\_OK}

In general the API is very simple to memorize and use.  Most of the functions return either {\bf void} or {\bf int}.  Functions
that return {\bf int} will return {\bf CRYPT\_OK} if the function was successful or one of the many error codes 
if it failed.  Certain functions that return int will return $-1$ to indicate an error.  These functions will be explicitly
commented upon.  When a function does return a CRYPT error code it can be translated into a string with

\begin{verbatim}
const char *error_to_string(int errno);
\end{verbatim}

An example of handling an error is:
\begin{verbatim}
void somefunc(void)
{
   int errno;
   
   /* call a cryptographic function */
   if ((errno = some_crypto_function(...)) != CRYPT_OK) {
      printf("A crypto error occured, %s\n", error_to_string(errno));
      /* perform error handling */
   }
   /* continue on if no error occured */
}
\end{verbatim}

There is no initialization routine for the library and for the most part the code is thread safe.  The only thread
related issue is if you use the same symmetric cipher, hash or public key state data in multiple threads.  Normally
that is not an issue.

To include the prototypes for ``LibTomCrypt.a'' into your own program simply include ``mycrypt.h'' like so:
\begin{verbatim}
#include <mycrypt.h>
int main(void) {
    return 0;
}
\end{verbatim}

The header file ``mycrypt.h'' also includes ``stdio.h'', ``string.h'', ``stdlib.h'', ``time.h'', ``ctype.h'' and ``mpi.h''
(the bignum library routines).

\section{Macros}

There are a few helper macros to make the coding process a bit easier.  The first set are related to loading and storing
32/64-bit words in little/big endian format.  The macros are:

\index{STORE32L} \index{STORE64L} \index{LOAD32L} \index{LOAD64L}
\index{STORE32H} \index{STORE64H} \index{LOAD32H} \index{LOAD64H} \index{BSWAP}
\begin{small}
\begin{center}
\begin{tabular}{|c|c|c|}
     \hline STORE32L(x, y) & {\bf unsigned long} x, {\bf unsigned char} *y & $x \to y[0 \ldots 3]$ \\
     \hline STORE64L(x, y) & {\bf unsigned long long} x, {\bf unsigned char} *y & $x \to y[0 \ldots 7]$ \\
     \hline LOAD32L(x, y) & {\bf unsigned long} x, {\bf unsigned char} *y & $y[0 \ldots 3] \to x$ \\
     \hline LOAD64L(x, y) & {\bf unsigned long long} x, {\bf unsigned char} *y & $y[0 \ldots 7] \to x$ \\
     \hline STORE32H(x, y) & {\bf unsigned long} x, {\bf unsigned char} *y & $x \to y[3 \ldots 0]$ \\
     \hline STORE64H(x, y) & {\bf unsigned long long} x, {\bf unsigned char} *y & $x \to y[7 \ldots 0]$ \\
     \hline LOAD32H(x, y) & {\bf unsigned long} x, {\bf unsigned char} *y & $y[3 \ldots 0] \to x$ \\
     \hline LOAD64H(x, y) & {\bf unsigned long long} x, {\bf unsigned char} *y & $y[7 \ldots 0] \to x$ \\
     \hline BSWAP(x) & {\bf unsigned long} x & Swaps the byte order of x. \\
     \hline
\end{tabular}
\end{center}
\end{small}

There are 32-bit cyclic rotations as well:
\index{ROL} \index{ROR}
\begin{center}
\begin{tabular}{|c|c|c|}
     \hline ROL(x, y) & {\bf unsigned long} x, {\bf unsigned long} y & $x << y$ \\
     \hline ROR(x, y) & {\bf unsigned long} x, {\bf unsigned long} y & $x >> y$ \\
     \hline
\end{tabular}
\end{center}

\section{Functions with Variable Length Output}
Certain functions such as (for example) ``rsa\_export()'' give an output that is variable length.  To prevent buffer overflows you
must pass it the length of the buffer\footnote{Extensive error checking is not in place but it will be in future releases so it is a good idea to follow through with these guidelines.} where
the output will be stored.  For example:
\begin{small}
\begin{verbatim}
#include <mycrypt.h>
int main(void) {
    rsa_key key;
    unsigned char buffer[1024];
    unsigned long x;
    int errno;

    /* ... Make up the RSA key somehow */

    /* lets export the key, set x to the size of the output buffer */
    x = sizeof(buffer);