rsagen.c (1486B)
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 }