dsaprimes.c (1904B)
1 #include "os.h" 2 #include <mp.h> 3 #include <libsec.h> 4 5 /* NIST algorithm for generating DSA primes */ 6 /* Menezes et al (1997) Handbook of Applied Cryptography, p.151 */ 7 /* q is a 160-bit prime; p is a 1024-bit prime; q divides p-1 */ 8 9 /* arithmetic on unsigned ints mod 2**160, represented */ 10 /* as 20-byte, little-endian uchar array */ 11 12 static void 13 Hrand(uchar *s) 14 { 15 uint32 *u = (uint32*)s; 16 *u++ = fastrand(); 17 *u++ = fastrand(); 18 *u++ = fastrand(); 19 *u++ = fastrand(); 20 *u = fastrand(); 21 } 22 23 static void 24 Hincr(uchar *s) 25 { 26 int i; 27 for(i=0; i<20; i++) 28 if(++s[i]!=0) 29 break; 30 } 31 32 /* this can run for quite a while; be patient */ 33 void 34 DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen]) 35 { 36 int i, j, k, n = 6, b = 63; 37 uchar s[SHA1dlen], Hs[SHA1dlen], Hs1[SHA1dlen], sj[SHA1dlen], sjk[SHA1dlen]; 38 mpint *two1023, *mb, *Vk, *W, *X, *q2; 39 40 two1023 = mpnew(1024); 41 mpleft(mpone, 1023, two1023); 42 mb = mpnew(0); 43 mpleft(mpone, b, mb); 44 W = mpnew(1024); 45 Vk = mpnew(1024); 46 X = mpnew(0); 47 q2 = mpnew(0); 48 forever: 49 do{ 50 Hrand(s); 51 memcpy(sj, s, 20); 52 sha1(s, 20, Hs, 0); 53 Hincr(sj); 54 sha1(sj, 20, Hs1, 0); 55 for(i=0; i<20; i++) 56 Hs[i] ^= Hs1[i]; 57 Hs[0] |= 1; 58 Hs[19] |= 0x80; 59 letomp(Hs, 20, q); 60 }while(!probably_prime(q, 18)); 61 if(seed != nil) /* allow skeptics to confirm computation */ 62 memmove(seed, s, SHA1dlen); 63 i = 0; 64 j = 2; 65 Hincr(sj); 66 mpleft(q, 1, q2); 67 while(i<4096){ 68 memcpy(sjk, sj, 20); 69 for(k=0; k <= n; k++){ 70 sha1(sjk, 20, Hs, 0); 71 letomp(Hs, 20, Vk); 72 if(k == n) 73 mpmod(Vk, mb, Vk); 74 mpleft(Vk, 160*k, Vk); 75 mpadd(W, Vk, W); 76 Hincr(sjk); 77 } 78 mpadd(W, two1023, X); 79 mpmod(X, q2, W); 80 mpsub(W, mpone, W); 81 mpsub(X, W, p); 82 if(mpcmp(p, two1023)>=0 && probably_prime(p, 5)) 83 goto done; 84 i += 1; 85 j += n+1; 86 for(k=0; k<n+1; k++) 87 Hincr(sj); 88 } 89 goto forever; 90 done: 91 mpfree(q2); 92 mpfree(X); 93 mpfree(Vk); 94 mpfree(W); 95 mpfree(mb); 96 mpfree(two1023); 97 }