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