Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 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
13 
Hrand(uchar *s)
14 
{
33 7u83 15 
	u32int *u = (u32int*)s;
2 - 16 
	*u++ = fastrand();
17 
	*u++ = fastrand();
18 
	*u++ = fastrand();
19 
	*u++ = fastrand();
20 
	*u = fastrand();
21 
}
22 
 
23 
static void
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
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 
}