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