Blob
1 #include "os.h"2 #include <mp.h>3 #include <libsec.h>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;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);18 // create the prime factors and euclid's function19 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);26 // find an e relatively prime to phi27 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 discussion33 // of the merits of various choices of primes and exponents. e=3 is a34 // common and recommended exponent, but doesn't necessarily work here35 // 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);45 // compute chinese remainder coefficient46 c2 = mpnew(0);47 mpinvert(p, q, c2);49 // for crt a**k mod p == (a**(k mod p-1)) mod p50 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);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;67 mpfree(phi);69 return rsa;70 }