180ee5cbfSDavid du Colombier #include "os.h" 280ee5cbfSDavid du Colombier #include <mp.h> 380ee5cbfSDavid du Colombier #include <libsec.h> 480ee5cbfSDavid du Colombier 580ee5cbfSDavid du Colombier RSApriv* 680ee5cbfSDavid du Colombier rsagen(int nlen, int elen, int rounds) 780ee5cbfSDavid du Colombier { 880ee5cbfSDavid du Colombier mpint *p, *q, *e, *d, *phi, *n, *t1, *t2, *kp, *kq, *c2; 980ee5cbfSDavid du Colombier RSApriv *rsa; 1080ee5cbfSDavid du Colombier 1180ee5cbfSDavid du Colombier p = mpnew(nlen/2); 1280ee5cbfSDavid du Colombier q = mpnew(nlen/2); 1380ee5cbfSDavid du Colombier n = mpnew(nlen); 1480ee5cbfSDavid du Colombier e = mpnew(elen); 1580ee5cbfSDavid du Colombier d = mpnew(0); 1680ee5cbfSDavid du Colombier phi = mpnew(nlen); 1780ee5cbfSDavid du Colombier 1880ee5cbfSDavid du Colombier // create the prime factors and euclid's function 1980ee5cbfSDavid du Colombier genstrongprime(p, nlen/2, rounds); 2080ee5cbfSDavid du Colombier genstrongprime(q, nlen - mpsignif(p) + 1, rounds); 2180ee5cbfSDavid du Colombier mpmul(p, q, n); 2280ee5cbfSDavid du Colombier mpsub(p, mpone, e); 2380ee5cbfSDavid du Colombier mpsub(q, mpone, d); 2480ee5cbfSDavid du Colombier mpmul(e, d, phi); 2580ee5cbfSDavid du Colombier 2680ee5cbfSDavid du Colombier // find an e relatively prime to phi 2780ee5cbfSDavid du Colombier t1 = mpnew(0); 2880ee5cbfSDavid du Colombier t2 = mpnew(0); 29*39734e7eSDavid du Colombier mprand(elen, genrandom, e); 3080ee5cbfSDavid du Colombier for(;;){ 31*39734e7eSDavid du Colombier mpextendedgcd(e, phi, t1, d, t2); 32*39734e7eSDavid du Colombier if(mpcmp(t1, mpone) == 0) 3380ee5cbfSDavid du Colombier break; 3480ee5cbfSDavid du Colombier mpadd(mpone, e, e); 3580ee5cbfSDavid du Colombier } 3680ee5cbfSDavid du Colombier mpfree(t1); 3780ee5cbfSDavid du Colombier mpfree(t2); 3880ee5cbfSDavid du Colombier 3980ee5cbfSDavid du Colombier // compute chinese remainder coefficient 4080ee5cbfSDavid du Colombier c2 = mpnew(0); 4180ee5cbfSDavid du Colombier mpinvert(p, q, c2); 4280ee5cbfSDavid du Colombier 4380ee5cbfSDavid du Colombier // for crt a**k mod p == (a**(k mod p-1)) mod p 4480ee5cbfSDavid du Colombier kq = mpnew(0); 4580ee5cbfSDavid du Colombier kp = mpnew(0); 4680ee5cbfSDavid du Colombier mpsub(p, mpone, phi); 4780ee5cbfSDavid du Colombier mpmod(d, phi, kp); 4880ee5cbfSDavid du Colombier mpsub(q, mpone, phi); 4980ee5cbfSDavid du Colombier mpmod(d, phi, kq); 5080ee5cbfSDavid du Colombier 5180ee5cbfSDavid du Colombier rsa = rsaprivalloc(); 5280ee5cbfSDavid du Colombier rsa->pub.ek = e; 5380ee5cbfSDavid du Colombier rsa->pub.n = n; 5480ee5cbfSDavid du Colombier rsa->dk = d; 5580ee5cbfSDavid du Colombier rsa->kp = kp; 5680ee5cbfSDavid du Colombier rsa->kq = kq; 5780ee5cbfSDavid du Colombier rsa->p = p; 5880ee5cbfSDavid du Colombier rsa->q = q; 5980ee5cbfSDavid du Colombier rsa->c2 = c2; 6080ee5cbfSDavid du Colombier 6180ee5cbfSDavid du Colombier mpfree(phi); 6280ee5cbfSDavid du Colombier 6380ee5cbfSDavid du Colombier return rsa; 6480ee5cbfSDavid du Colombier } 65