1 #include "os.h" 2 #include <mp.h> 3 #include <libsec.h> 4 5 static void 6 genrand(mpint *p, int n) 7 { 8 mpdigit x; 9 10 // generate n random bits with high set 11 mpbits(p, n); 12 genrandom((uchar*)p->p, (n+7)/8); 13 p->top = (n+Dbits-1)/Dbits; 14 x = 1; 15 x <<= ((n-1)%Dbits); 16 p->p[p->top-1] &= (x-1); 17 p->p[p->top-1] |= x; 18 } 19 20 RSApriv* 21 rsagen(int nlen, int elen, int rounds) 22 { 23 mpint *p, *q, *e, *d, *phi, *n, *t1, *t2, *kp, *kq, *c2; 24 RSApriv *rsa; 25 26 p = mpnew(nlen/2); 27 q = mpnew(nlen/2); 28 n = mpnew(nlen); 29 e = mpnew(elen); 30 d = mpnew(0); 31 phi = mpnew(nlen); 32 33 // create the prime factors and euclid's function 34 genstrongprime(p, nlen/2, rounds); 35 genstrongprime(q, nlen - mpsignif(p) + 1, rounds); 36 mpmul(p, q, n); 37 mpsub(p, mpone, e); 38 mpsub(q, mpone, d); 39 mpmul(e, d, phi); 40 41 // find an e relatively prime to phi 42 t1 = mpnew(0); 43 t2 = mpnew(0); 44 genrand(e, elen); 45 for(;;){ 46 mpextendedgcd(e, phi, d, t1, t2); 47 if(mpcmp(d, mpone) == 0) 48 break; 49 mpadd(mpone, e, e); 50 } 51 mpfree(t1); 52 mpfree(t2); 53 54 // d = e**-1 mod phi 55 mpinvert(e, phi, d); 56 57 // compute chinese remainder coefficient 58 c2 = mpnew(0); 59 mpinvert(p, q, c2); 60 61 // for crt a**k mod p == (a**(k mod p-1)) mod p 62 kq = mpnew(0); 63 kp = mpnew(0); 64 mpsub(p, mpone, phi); 65 mpmod(d, phi, kp); 66 mpsub(q, mpone, phi); 67 mpmod(d, phi, kq); 68 69 rsa = rsaprivalloc(); 70 rsa->pub.ek = e; 71 rsa->pub.n = n; 72 rsa->dk = d; 73 rsa->kp = kp; 74 rsa->kq = kq; 75 rsa->p = p; 76 rsa->q = q; 77 rsa->c2 = c2; 78 79 mpfree(phi); 80 81 return rsa; 82 } 83