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