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