sys/src/libsec/port/rsagen.c

   1 #include "os.h"
   2 #include <mp.h>
   3 #include <libsec.h>
   4
   5 RSApriv*
   6 rsagen(int nlen, int elen, int rounds)
   7 {
   8         mpint *p, *q, *e, *d, *phi, *n, *t1, *t2, *kp, *kq, *c2;
   9         RSApriv *rsa;
  10
  11         p = mpnew(nlen/2);
  12         q = mpnew(nlen/2);
  13         n = mpnew(nlen);
  14         e = mpnew(elen);
  15         d = mpnew(0);
  16         phi = mpnew(nlen);
  17
  18         // create the prime factors and euclid's function
  19         genprime(p, nlen/2, rounds);
  20         genprime(q, nlen - mpsignif(p) + 1, rounds);
  21         mpmul(p, q, n);
  22         mpsub(p, mpone, e);
  23         mpsub(q, mpone, d);
  24         mpmul(e, d, phi);
  25
  26         // find an e relatively prime to phi
  27         t1 = mpnew(0);
  28         t2 = mpnew(0);
  29         mprand(elen, genrandom, e);
  30         if(mpcmp(e,mptwo) <= 0)
  31                 itomp(3, e);
  32         // See Menezes et al. p.291 "8.8 Note (selecting primes)" for discussion
  33         // of the merits of various choices of primes and exponents.  e=3 is a
  34         // common and recommended exponent, but doesn't necessarily work here
  35         // because we chose strong rather than safe primes.
  36         for(;;){
  37                 mpextendedgcd(e, phi, t1, d, t2);
  38                 if(mpcmp(t1, mpone) == 0)
  39                         break;
  40                 mpadd(mpone, e, e);
  41         }
  42         mpfree(t1);
  43         mpfree(t2);
  44
  45         // compute chinese remainder coefficient
  46         c2 = mpnew(0);
  47         mpinvert(p, q, c2);
  48
  49         // for crt a**k mod p == (a**(k mod p-1)) mod p
  50         kq = mpnew(0);
  51         kp = mpnew(0);
  52         mpsub(p, mpone, phi);
  53         mpmod(d, phi, kp);
  54         mpsub(q, mpone, phi);
  55         mpmod(d, phi, kq);
  56
  57         rsa = rsaprivalloc();
  58         rsa->pub.ek = e;
  59         rsa->pub.n = n;
  60         rsa->dk = d;
  61         rsa->kp = kp;
  62         rsa->kq = kq;
  63         rsa->p = p;
  64         rsa->q = q;
  65         rsa->c2 = c2;
  66
  67         mpfree(phi);
  68
  69         return rsa;
  70 }