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
Hrand(uchar * s)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
Hincr(uchar * s)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
DSAprimes(mpint * q,mpint * p,uchar seed[SHA1dlen])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 }
98