1 #include "os.h"
2 #include <mp.h>
3 #include <libsec.h>
4
5 static void
genrand(mpint * p,int n)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*
rsagen(int nlen,int elen,int rounds)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