home *** CD-ROM | disk | FTP | other *** search
/ PC-Online 1998 February / PCOnline_02_1998.iso / filesbbs / os2 / pgp263.arj / PGP263I.SRC / PGP263II.ZIP / src / rsagen.c < prev    next >
C/C++ Source or Header  |  1995-09-27  |  10KB  |  270 lines
  1. /*    rsagen.c - C source code for RSA public-key key generation routines.
  2.     First version 17 Mar 87
  3.  
  4.         (c) Copyright 1987 by Philip Zimmermann.  All rights reserved.
  5.         The author assumes no liability for damages resulting from the use
  6.         of this software, even if the damage results from defects in this
  7.         software.  No warranty is expressed or implied.
  8.  
  9.     RSA-specific routines follow.  These are the only functions that 
  10.     are specific to the RSA public key cryptosystem.  The other
  11.     multiprecision integer math functions may be used for non-RSA
  12.     applications.  Without these functions that follow, the rest of 
  13.     the software cannot perform the RSA public key algorithm.  
  14.  
  15.     The RSA public key cryptosystem is patented by the Massachusetts
  16.     Institute of Technology (U.S. patent #4,405,829).  This patent does
  17.     not apply outside the USA.  Public Key Partners (PKP) holds the
  18.     exclusive commercial license to sell and sub-license the RSA public
  19.     key cryptosystem.  The author of this software implementation of the
  20.     RSA algorithm is providing this software for educational use only. 
  21.     Licensing this algorithm from PKP is the responsibility of you, the
  22.     user, not Philip Zimmermann, the author of this software.  The author
  23.     assumes no liability for any breach of patent law resulting from the
  24.     unlicensed use of this software by the user.
  25. */
  26.  
  27. #include "mpilib.h"
  28. #include "genprime.h"
  29. #include "rsagen.h"
  30. #include "random.h"
  31. #include "rsaglue.h"
  32.  
  33. #ifdef MACTC5
  34. extern DialogPtr ProgressDialog;
  35. #endif
  36.  
  37. static void derive_rsakeys(unitptr n,unitptr e,unitptr d,
  38.     unitptr p,unitptr q,unitptr u,short ebits);
  39.     /* Given primes p and q, derive RSA key components n, e, d, and u. */
  40.  
  41.  
  42. /* Define some error status returns for RSA keygen... */
  43. #define KEYFAILED -15        /* key failed final test */
  44.  
  45.  
  46. #define swap(p,q)  { unitptr t; t = p;  p = q;  q = t; }
  47.  
  48.  
  49. static void derive_rsakeys(unitptr n, unitptr e, unitptr d,
  50.     unitptr p, unitptr q, unitptr u, short ebits)
  51. /*
  52.  * Given primes p and q, derive RSA key components n, e, d, and u. 
  53.  * The global_precision must have already been set large enough for n.
  54.  * Note that p must be < q.
  55.  * Primes p and q must have been previously generated elsewhere.
  56.  * The bit precision of e will be >= ebits.  The search for a usable
  57.  * exponent e will begin with an ebits-sized number.  The recommended 
  58.  * value for ebits is 5, for efficiency's sake.  This could yield 
  59.  * an e as small as 17.
  60.  */
  61. {
  62.     unit F[MAX_UNIT_PRECISION];
  63.     unitptr ptemp, qtemp, phi, G;     /* scratchpads */
  64.  
  65.     /*    For strong prime generation only, latitude is the amount 
  66.         which the modulus may differ from the desired bit precision.  
  67.         It must be big enough to allow primes to be generated by 
  68.         goodprime reasonably fast. 
  69.     */
  70. #define latitude(bits) (max(min(bits/16,12),4))    /* between 4 and 12 bits */
  71.     
  72.     ptemp = d;    /* use d for temporary scratchpad array */
  73.     qtemp = u;    /* use u for temporary scratchpad array */
  74.     phi = n;    /* use n for temporary scratchpad array */
  75.     G = F;        /* use F for both G and F */
  76.     
  77.     if (mp_compare(p,q) >= 0)    /* ensure that p<q for computing u */
  78.         swap(p,q);        /* swap the pointers p and q */
  79.  
  80.     /*    phi(n) is the Euler totient function of n, or the number of
  81.         positive integers less than n that are relatively prime to n.
  82.         G is the number of "spare key sets" for a given modulus n. 
  83.         The smaller G is, the better.  The smallest G can get is 2. 
  84.     */
  85.     mp_move(ptemp,p); mp_move(qtemp,q);
  86.     mp_dec(ptemp); mp_dec(qtemp);
  87.     mp_mult(phi,ptemp,qtemp);    /*  phi(n) = (p-1)*(q-1)  */
  88.     mp_gcd(G,ptemp,qtemp);        /*  G(n) = gcd(p-1,q-1)  */
  89. #ifdef DEBUG
  90.     if (countbits(G) > 12)        /* G shouldn't get really big. */
  91.         mp_display("\007G = ",G);    /* Worry the user. */
  92. #endif /* DEBUG */
  93.     mp_udiv(ptemp,qtemp,phi,G);    /* F(n) = phi(n)/G(n)  */
  94.     mp_move(F,qtemp);
  95.  
  96.     /*
  97.      * We now have phi and F.  Next, compute e...
  98.      * Strictly speaking, we might get slightly faster results by
  99.      * testing all small prime e's greater than 2 until we hit a 
  100.      * good e.  But we can do just about as well by testing all 
  101.      * odd e's greater than 2.
  102.      * We could begin searching for a candidate e anywhere, perhaps
  103.      * using a random 16-bit starting point value for e, or even
  104.      * larger values.  But the most efficient value for e would be 3, 
  105.      * if it satisfied the gcd test with phi.
  106.      * Parameter ebits specifies the number of significant bits e
  107.      * should have to begin search for a workable e.
  108.      * Make e at least 2 bits long, and no longer than one bit 
  109.      * shorter than the length of phi.
  110.      */
  111.     ebits = min(ebits,countbits(phi)-1);
  112.     if (ebits==0) ebits=5;    /* default is 5 bits long */
  113.     ebits = max(ebits,2);
  114.     mp_init(e,0);
  115.     mp_setbit(e,ebits-1);
  116.     lsunit(e) |= 1;        /* set e candidate's lsb - make it odd */
  117.     mp_dec(e);  mp_dec(e); /* precompensate for preincrements of e */
  118.     do {
  119.         mp_inc(e); mp_inc(e);    /* try odd e's until we get it. */
  120.         mp_gcd(ptemp,e,phi);    /* look for e such that
  121.                        gcd(e,phi(n)) = 1 */
  122.     } while (testne(ptemp,1));
  123.  
  124.     /*    Now we have e.  Next, compute d, then u, then n.
  125.         d is the multiplicative inverse of e, mod F(n).
  126.         u is the multiplicative inverse of p, mod q, if p<q.
  127.         n is the public modulus p*q.
  128.     */
  129.     mp_inv(d,e,F);        /* compute d such that (e*d) mod F(n) = 1 */
  130.     mp_inv(u,p,q);            /* (p*u) mod q = 1, assuming p<q */
  131.     mp_mult(n,p,q);    /*  n = p*q  */
  132.     mp_burn(F);        /* burn the evidence on the stack */
  133. }    /* derive_rsakeys */
  134.  
  135.  
  136. int rsa_keygen(unitptr n, unitptr e, unitptr d,
  137.     unitptr p, unitptr q, unitptr u, short keybits, short ebits)
  138. /*
  139.  * Generate RSA key components p, q, n, e, d, and u. 
  140.  * This routine sets the global_precision appropriate for n,
  141.  * where keybits is desired precision of modulus n.
  142.  * The precision of exponent e will be >= ebits.
  143.  * It will generate a p that is < q.
  144.  * Returns 0 for succcessful keygen, negative status otherwise.
  145.  */
  146. {
  147.     short pbits, qbits;
  148.     boolean too_close_together; /* TRUE iff p and q are too close */
  149.     int status;
  150.     int slop;
  151.  
  152.     /*
  153.      * Don't let keybits get any smaller than 2 units, because    
  154.      * some parts of the math package require at least 2 units 
  155.      * for global_precision.
  156.      * Nor any smaller than the 32 bits of preblocking overhead.
  157.      * Nor any bigger than MAX_BIT_PRECISION - SLOP_BITS.
  158.      * Also, if generating "strong" primes, don't let keybits get
  159.      * any smaller than 64 bits, because of the search latitude.
  160.      */
  161.     slop = max(SLOP_BITS,1); /* allow at least 1 slop bit for sign bit */
  162.     keybits = min(keybits,(MAX_BIT_PRECISION-slop));
  163.     keybits = max(keybits,UNITSIZE*2);
  164.     keybits = max(keybits,32); /* minimum preblocking overhead */
  165. #ifdef STRONGPRIMES
  166.     keybits = max(keybits,64); /* for strong prime search latitude */
  167. #endif    /* STRONGPRIMES */
  168.  
  169.     set_precision(bits2units(keybits + slop));
  170.  
  171.     /*    We will need a series of truly random bits to generate the 
  172.         primes.  We need enough random bits for keybits, plus two 
  173.         random units for combined discarded bit losses in randombits. 
  174.         Since we now know how many random bits we will need,
  175.         this is the place to prefill the pool of random bits. 
  176.     */
  177.     trueRandAccum(keybits+2*UNITSIZE);
  178.  
  179. #if 0
  180.     /*
  181.      * If you want primes of different lengths ("separation" bits apart),
  182.      * do the following:
  183.      */
  184.     pbits = (keybits-separation)/2;
  185.     qbits = keybits - pbits;
  186. #else
  187.     pbits = keybits/2;
  188.     qbits = keybits - pbits;
  189. #endif
  190.  
  191.     trueRandConsume(pbits); /* "use up" this many bits */
  192.  
  193. #ifdef MACTC5
  194.     ShowWindow(ProgressDialog);
  195.     DrawDialog(ProgressDialog);
  196. #endif
  197.  
  198. #ifdef STRONGPRIMES    /* make a good strong prime for the key */
  199.     status = goodprime(p,pbits,pbits-latitude(pbits));
  200. #else    /* just any random prime will suffice for the key */
  201.     status = randomprime(p,pbits);
  202. #endif    /* else not STRONGPRIMES */
  203.     if (status < 0) 
  204.         return(status);    /* failed to find a suitable prime */
  205.  
  206.     /* We now have prime p.  Now generate q such that q>p... */
  207.  
  208.     qbits = keybits - countbits(p);
  209.  
  210.     trueRandConsume(qbits); /* "use up" this many bits */
  211.     /*    This load of random bits will be stirred and recycled until 
  212.         a good q is generated. */
  213.  
  214.     do {    /* Generate a q until we get one that isn't too close to p. */
  215. #ifdef STRONGPRIMES    /* make a good strong prime for the key */
  216.         status = goodprime(q,qbits,qbits-latitude(qbits));
  217. #else    /* just any random prime will suffice for the key */
  218.         status = randomprime(q,qbits);
  219. #endif    /* else not STRONGPRIMES */
  220.         if (status < 0) 
  221.             return(status);    /* failed to find a suitable prime */
  222.  
  223.         /* Note that at this point we can't be sure that q>p. */
  224.         if (mp_compare(p,q) >= 0) { /* ensure that p<q
  225.                            for computing u */
  226.             mp_move(u,p);
  227.             mp_move(p,q);
  228.             mp_move(q,u);
  229.         }
  230.         /* See if p and q are far enough apart.  Is q-p big enough? */
  231.         mp_move(u,q);    /* use u as scratchpad */
  232.         mp_sub(u,p);    /* compute q-p */
  233.         too_close_together = (countbits(u) < (countbits(q)-7));
  234.  
  235.         /* Keep trying q's until we get one far enough from p... */
  236.     } while (too_close_together);
  237.  
  238.     derive_rsakeys(n,e,d,p,q,u,ebits);
  239.     trueRandFlush();    /* ensure recycled random pool is destroyed */
  240.  
  241.     /* Now test key just to make sure --this had better work! */
  242.     {
  243.         unit C[MAX_UNIT_PRECISION];
  244.         int i;
  245.  
  246. /* Create a dummy signature */
  247.         for (i = 0; i < 16; i++)
  248.             ((byte *)C)[i] = 3*i+7;
  249. /* Encrypt it */
  250.         status = rsa_private_encrypt(C,(byte *)C,16,e,d,p,q,u,n);
  251.         if (status < 0)    /* modexp error? */
  252.             return status;    /* return error status */
  253. /* Extract the signature */
  254.         status = rsa_public_decrypt((byte *)C,C,e,n);
  255.         if (status < 0)    /* modexp error? */
  256.             return status;    /* return error status */
  257. /* Verify that we got the same thing back. */
  258.         if (status != 16)
  259.             return KEYFAILED;
  260.         for (i = 0; i < 16; i++)
  261.             if (((byte *)C)[i] != 3*i+7)
  262.                 return KEYFAILED;
  263.     }
  264.     return 0;    /* normal return */
  265. }    /* rsa_keygen */
  266.  
  267. /****************** End of RSA-specific routines  *******************/
  268.  
  269.  
  270.