Blob
1 #include "os.h"2 #include <mp.h>3 #include <libsec.h>5 // NIST algorithm for generating DSA primes6 // Menezes et al (1997) Handbook of Applied Cryptography, p.1517 // q is a 160-bit prime; p is a 1024-bit prime; q divides p-19 // arithmetic on unsigned ints mod 2**160, represented10 // as 20-byte, little-endian uchar array12 static void13 Hrand(uchar *s)14 {15 ulong *u = (ulong*)s;16 *u++ = fastrand();17 *u++ = fastrand();18 *u++ = fastrand();19 *u++ = fastrand();20 *u = fastrand();21 }23 static void24 Hincr(uchar *s)25 {26 int i;27 for(i=0; i<20; i++)28 if(++s[i]!=0)29 break;30 }32 // this can run for quite a while; be patient33 void34 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;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 computation62 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 }