crypt.tex

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

Currently Yarrow (yarrow\_desc), RC4 (rc4\_desc) and the secure RNG (sprng\_desc) are provided as PRNGs within the 
library.  

RC4 is provided with a PRNG interface because it is a stream cipher and not well suited for the symmetric block cipher
interface.  You provide the key for RC4 via the rc4\_add\_entropy() function.  By calling rc4\_ready() the key will be used
to setup the RC4 state for encryption or decryption.  The rc4\_read() function has been modified from RC4 since it will 
XOR the output of the RC4 keystream generator against the input buffer you provide.  The following snippet will demonstrate
how to encrypt a buffer with RC4:

\begin{small}
\begin{verbatim}
#include <mycrypt.h>
int main(void)
{
   prng_state prng;
   unsigned char buf[32];
   int errno;

   if ((errno = rc4_start(&prng)) != CRYPT_OK) {
      printf("RC4 init error: %s\n", error_to_string(errno));
      exit(-1);
   }

   /* use ``key'' as the key */
   if ((errno = rc4_add_entropy("key", 3, &prng)) != CRYPT_OK) {
      printf("RC4 add entropy error: %s\n", error_to_string(errno));
      exit(-1);
   }

   /* setup RC4 for use */
   if ((errno = rc4_ready(&prng)) != CRYPT_OK) {
      printf("RC4 ready error: %s\n", error_to_string(errno));
      exit(-1);
   }

   /* encrypt buffer */
   strcpy(buf,"hello world");
   if (rc4_read(buf, 11, &prng) != 11) {
      printf("RC4 read error\n");
      exit(-1);
   }
   return 0;
}   
\end{verbatim}
\end{small}
To decrypt you have to do the exact same steps.  

\section{The Secure RNG}
\index{Secure RNG}
An RNG is related to a PRNG except that it doesn't expand a smaller seed to get the data.  They generate their random bits
by performing some computation on fresh input bits.  Possibly the hardest thing to get correctly in a cryptosystem is the 
PRNG.  Computers are deterministic beasts that try hard not to stray from pre-determined paths.  That makes gathering 
entropy needed to seed the PRNG a hard task.  

There is one small function that may help on certain platforms:
\index{rng\_get\_bytes()}
\begin{verbatim}
unsigned long rng_get_bytes(unsigned char *buf, unsigned long len, 
                  void (*callback)(void));
\end{verbatim}

Which will try one of three methods of getting random data.  The first is to open the popular ``/dev/random'' device which 
on most *NIX platforms provides cryptographic random bits\footnote{This device is available in Windows through the Cygwin compiler suite.  It emulates ``/dev/random'' via the Microsoft CSP.}.  
The second method is to try the Microsoft Cryptographic Service Provider and read the RNG.  The third method is an ANSI C 
clock drift method that is also somewhat popular but gives bits of lower entropy.  The ``callback'' parameter is a pointer to a function that returns void.  Its used when the slower ANSI C RNG must be 
used so the calling application can still work.  This is useful since the ANSI C RNG has a throughput of three 
bytes a second.  The callback pointer may be set to {\bf NULL} to avoid using it if you don't want to.  The function 
returns the number of bytes actually read from any RNG source.  There is a function to help setup a PRNG as well:
\index{rng\_make\_prng()}
\begin{verbatim}
int rng_make_prng(int bits, int wprng, prng_state *prng, 
                  void (*callback)(void));
\end{verbatim}
This will try to setup the prng with a state of at least ``bits'' of entropy.  The ``callback'' parameter works much like
the callback in ``rng\_get\_bytes()''.  It is highly recommended that you use this function to setup your PRNGs unless you have a
platform where the RNG doesn't work well.  Example usage of this function is given below.

\begin{small}
\begin{verbatim}
#include <mycrypt.h>
int main(void)
{
   ecc_key mykey;
   prng_state prng;
   int errno;

   /* register yarrow */
   if (register_prng(&yarrow_desc) == -1) {
      printf("Error registering Yarrow\n");
      return -1;
   }

   /* setup the PRNG */
   if ((errno = rng_make_prng(128, find_prng("yarrow"), &prng, NULL)) != CRYPT_OK) {
      printf("Error setting up PRNG, %s\n", error_to_string(errno));
      return -1;
   }

   /* make a 192-bit ECC key */
   if ((errno = ecc_make_key(&prng, find_prng("yarrow"), 24, &mykey)) != CRYPT_OK) {
      printf("Error making key: %s\n", error_to_string(errno));
      return -1;
   }
   return 0;
}
\end{verbatim}
\end{small}

\subsection{The Secure PRNG Interface}
It is possible to access the secure RNG through the PRNG interface and in turn use it within dependent functions such
as the PK API.  This simplifies the cryptosystem on platforms where the secure RNG is fast.  The secure PRNG never 
requires to be started, that is you need not call the start, add\_entropy or ready functions.  For example, consider
the previous example using this PRNG.

\begin{small}
\begin{verbatim}
#include <mycrypt.h>
int main(void)
{
   ecc_key mykey;
   int errno;

   /* register SPRNG */
   if (register_prng(&sprng_desc) == -1) {
      printf("Error registering SPRNG\n");
      return -1;
   }

   /* make a 192-bit ECC key */
   if ((errno = ecc_make_key(NULL, find_prng("sprng"), 24, &mykey)) != CRYPT_OK) {
      printf("Error making key: %s\n", error_to_string(errno));
      return -1;
   }
   return 0;
}
\end{verbatim}
\end{small}

\chapter{RSA Routines}

\section{Background}

RSA is a public key algorithm that is based on the inability to find the ``e-th'' root modulo a composite of unknown 
factorization.  Normally the difficulty of breaking RSA is associated with the integer factoring problem but they are
not strictly equivalent.

The system begins with with two primes $p$ and $q$ and their product $N = pq$.  The order or ``Euler totient'' of the
multiplicative sub-group formed modulo $N$ is given as $\phi(N) = (p - 1)(q - 1)$ which can be reduced to 
$\mbox{lcm}(p - 1, q - 1)$.  The public key consists of the composite $N$ and some integer $e$ such that 
$\mbox{gcd}(e, \phi(N)) = 1$.  The private key consists of the composite $N$ and the inverse of $e$ modulo $\phi(N)$ 
often simply denoted as $de \equiv 1\mbox{ }(\mbox{mod }\phi(N))$.

A person who wants to encrypt with your public key simply forms an integer (the plaintext) $M$ such that 
$1 < M < N-2$ and computes the ciphertext $C = M^e\mbox{ }(\mbox{mod }N)$.  Since finding the inverse exponent $d$
given only $N$ and $e$ appears to be intractable only the owner of the private key can decrypt the ciphertext and compute
$C^d \equiv \left (M^e \right)^d \equiv M^1 \equiv M\mbox{ }(\mbox{mod }N)$.  Similarly the owner of the private key 
can sign a message by ``decrypting'' it.  Others can verify it by ``encrypting'' it.  

Currently RSA is a difficult system to cryptanalyze provided that both primes are large and not close to each other.  
Ideally $e$ should be larger than $100$ to prevent direct analysis.  For example, if $e$ is three and you do not pad
the plaintext to be encrypted than it is possible that $M^3 < N$ in which case finding the cube-root would be trivial.  
The most often suggested value for $e$ is $65537$ since it is large enough to make such attacks impossible and also well 
designed for fast exponentiation (requires 16 squarings and one multiplication).

It is important to pad the input to RSA since it has particular mathematical structure.  For instance  
$M_1^dM_2^d = (M_1M_2)^d$ which can be used to forge a signature.  Suppose $M_3 = M_1M_2$ is a message you want
to have a forged signature for.  Simply get the signatures for $M_1$ and $M_2$ on their own and multiply the result
together.  Similar tricks can be used to deduce plaintexts from ciphertexts.  It is important not only to sign 
the hash of documents only but also to pad the inputs with data to remove such structure.  

\section{Core Functions}

For RSA routines a single ``rsa\_key'' structure is used.  To make a new RSA key call:
\index{rsa\_make\_key()}
\begin{verbatim}
int rsa_make_key(prng_state *prng, 
                 int wprng, int size, 
                 long e, rsa_key *key);
\end{verbatim}

Where ``wprng'' is the index into the PRNG descriptor array.  ``size'' is the size in bytes of the RSA modulus desired.
``e'' is the encryption exponent desired, typical values are 3, 17, 257 and 65537.  I suggest you stick with 65537 since its big
enough to prevent trivial math attacks and not super slow.  ``key'' is where the key is placed.  All keys must be at 
least 128 bytes and no more than 512 bytes in size (that is from 1024 to 4096 bits).

Note that the ``rsa\_make\_key()'' function allocates memory at runtime when you make the key.  Make sure to call 
``rsa\_free()'' (see below) when you are finished with the key.  If ``rsa\_make\_key()'' fails it will automatically 
free the ram allocated itself.

There are three types of RSA keys.  The types are {\bf PK\_PRIVATE\_OPTIMIZED}, {\bf PK\_PRIVATE} and {\bf PK\_PUBLIC}.  The first
two are private keys where the ``optimized'' type uses the Chinese Remainder Theorem to speed up decryption/signatures.  By 
default all new keys are of the ``optimized'' type.  The non-optimized private type is provided for backwards compatibility
as well as to save space since the optimized key requires about four times as much memory.

To do raw work with the RSA function call:
\index{rsa\_exptmod()}
\begin{verbatim}
int rsa_exptmod(const unsigned char *in, unsigned long inlen, 
                unsigned char *out, unsigned long *outlen, 
                int which, rsa_key *key);
\end{verbatim}
This loads the bignum from ``in'' as a big endian word, raises it to either ``e'' or ``d'' and stores the result
in ``out'' and the size of the result in ``outlen''. ``which'' is set to {\bf PK\_PUBLIC} to use ``e'' 
(i.e. for encryption/verifying) and set to {\bf PK\_PRIVATE} to use ``d'' as the exponent (i.e. for decrypting/signing).

\section{Packet Routines}
The remaining RSA functions are non-standard but should (to the best of my knowledge) be secure if used correctly.  To
encrypt a buffer of memory in a hybrid fashion call:
\index{rsa\_encrypt()}
\begin{verbatim}
int rsa_encrypt(const unsigned char *in, unsigned long len, 
                unsigned char *out, unsigned long *outlen,
                prng_state *prng, int wprng, int cipher, 
                rsa_key *key);
\end{verbatim}
This will encrypt the message with the cipher specified by ``cipher'' under a random key made by a PRNG specified by
``wprng'' and RSA encrypt the symmetric key with ``key''.  This stores all the relevant information in ``out'' and sets
the length in ``outlen''.  You must ensure that ``outlen'' is set to the buffer size before calling this.  

The rsa\_encrypt() function will use up to a 256-bit symmetric key (limited by the max key length of the cipher being
used).  To decrypt packets made by this routine call:
\index{rsa\_decrypt()}
\begin{verbatim}
int rsa_decrypt(const unsigned char *in, unsigned long len, 
                unsigned char *out, unsigned long *outlen, 
                rsa_key *key);
\end{verbatim}
Which works akin to rsa\_encrypt().  ``in'' is the ciphertext and ``out'' is where the plaintext will be stored.  Similarly
to sign/verify there are:
\index{rsa\_sign()} \index{rsa\_verify()}
\begin{verbatim}
int rsa_sign(const unsigned char *in, unsigned long inlen, 
                   unsigned char *out, unsigned long *outlen, 
                   int hash, rsa_key *key);

int rsa_verify(const unsigned char *sig,
               const unsigned char *msg, 
               unsigned long inlen, int *stat, 
               rsa_key *key);
\end{verbatim}

The verify function sets ``stat'' to 1 if it passes or to 0 if it fails.  The ``sig'' parameter is the output of the
rsa\_sign() function and ``msg'' is the original msg that was signed.  An important fact to note is that with
the padding scheme used in ``rsa\_sign()'' you cannot use the SHA-384 or SHA-512 hash function with 1024 bit
RSA keys.  This is because the padding makes the values too large to fit in the space allowed.  You can use SHA-384
with 1160 and above bit RSA keys.  You can use SHA-512 with 1544 and above bit RSA keys.

There are related functions to sign and verify hashes.
\begin{verbatim}
int rsa_sign_hash(const unsigned char *in,  unsigned long inlen, 
                        unsigned char *out, unsigned long *outlen, 
                        rsa_key *key);

int rsa_verify_hash(const unsigned char *sig, const unsigned char *hash,
                          int *stat, rsa_key *key);
\end{verbatim}
Which works just like the two previous functions except the data is not hashed before being signed.

There are times where you may want to encrypt a message to multiple recipients via RSA public keys.  The simplest way to
accomplish this is to make up your own symmetric key and then RSA encrypt the symmetric key using all of the recipients
public keys.  To facilitate this task two functions\footnote{Donated by Clay Culver.} are available:
\begin{verbatim}
int rsa_encrypt_key(const unsigned char *inkey, unsigned long inlen,
                          unsigned char *outkey, unsigned long *outlen,
                          prng_state *prng, int wprng, rsa_key *key);

int rsa_decrypt_key(const unsigned char *in, unsigned char *outkey, 
                          unsigned long *keylen, rsa_key *key);
\end{verbatim}

The ``rsa\_encrypt\_key()'' function accepts a symmetric key (limited to 32 bytes) as input in ``inkey''.  ``inlen''
is the size of the input key in bytes.  The function will then ``rsa\_pad()'' the key and encrypt it using the RSA
algorithm.  It will store the result in ``outkey'' along with the length in ``outlen''.  The ``rsa\_decrypt\_key()'' function
performs the opposite.  The ``in'' variable is where the RSA packet goes and it will store the original symmetric key in
the ``outkey'' variable along with its length in ``keylen''.

To import/export RSA keys as a memory buffer (e.g. to store them to disk) call:
\begin{verbatim}
int rsa_export(unsigned char *out, unsigned long *outlen, 
               int type, rsa_key *key);

int rsa_import(const unsigned char *in, rsa_key *key);
\end{verbatim}

The ``type'' parameter is {\bf PK\_PUBLIC}, {\bf PK\_PRIVATE} or {\bf PK\_PRIVATE\_OPTIMIZED} to export either a public or 
private key.  The latter type will export a key with the optimized parameters.  To free the memory used by an RSA key call:
\index{rsa\_free()}
\begin{verbatim}
void rsa_free(rsa_