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 }