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