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 /* Gordon's algorithm for generating a strong prime */
 6 cbeb0b26 2006-04-01 devnull /*	Menezes et al () Handbook, p.150 */
 7 0fc65b37 2004-03-21 devnull void
 8 0fc65b37 2004-03-21 devnull genstrongprime(mpint *p, int n, int accuracy)
 9 0fc65b37 2004-03-21 devnull {
10 0fc65b37 2004-03-21 devnull 	mpint *s, *t, *r, *i;
11 0fc65b37 2004-03-21 devnull 
12 0fc65b37 2004-03-21 devnull 	if(n < 64)
13 0fc65b37 2004-03-21 devnull 		n = 64;
14 0fc65b37 2004-03-21 devnull 
15 0fc65b37 2004-03-21 devnull 	s = mpnew(n/2);
16 0fc65b37 2004-03-21 devnull 	genprime(s, (n/2)-16, accuracy);
17 0fc65b37 2004-03-21 devnull 	t = mpnew(n/2);
18 0fc65b37 2004-03-21 devnull 	genprime(t, n-mpsignif(s)-32, accuracy);
19 0fc65b37 2004-03-21 devnull 
20 cbeb0b26 2006-04-01 devnull 	/* first r = 2it + 1 that's prime */
21 0fc65b37 2004-03-21 devnull 	i = mpnew(16);
22 0fc65b37 2004-03-21 devnull 	r = mpnew(0);
23 0fc65b37 2004-03-21 devnull 	itomp(0x8000, i);
24 cbeb0b26 2006-04-01 devnull 	mpleft(t, 1, t);	/* 2t */
25 cbeb0b26 2006-04-01 devnull 	mpmul(i, t, r);		/* 2it */
26 cbeb0b26 2006-04-01 devnull 	mpadd(r, mpone, r);	/* 2it + 1 */
27 0fc65b37 2004-03-21 devnull 	for(;;){
28 0fc65b37 2004-03-21 devnull 		if(probably_prime(r, 18))
29 0fc65b37 2004-03-21 devnull 			break;
30 cbeb0b26 2006-04-01 devnull 		mpadd(r, t, r);	/* r += 2t */
31 0fc65b37 2004-03-21 devnull 	}
32 0fc65b37 2004-03-21 devnull 
33 cbeb0b26 2006-04-01 devnull 	/* p0 = 2(s**(r-2) mod r)s - 1 */
34 0fc65b37 2004-03-21 devnull 	itomp(2, p);
35 0fc65b37 2004-03-21 devnull 	mpsub(r, p, p);
36 0fc65b37 2004-03-21 devnull 	mpexp(s, p, r, p);
37 0fc65b37 2004-03-21 devnull 	mpmul(s, p, p);
38 0fc65b37 2004-03-21 devnull 	mpleft(p, 1, p);
39 0fc65b37 2004-03-21 devnull 	mpsub(p, mpone, p);
40 0fc65b37 2004-03-21 devnull 
41 cbeb0b26 2006-04-01 devnull 	/* first p = p0 + 2irs that's prime */
42 0fc65b37 2004-03-21 devnull 	itomp(0x8000, i);
43 cbeb0b26 2006-04-01 devnull 	mpleft(r, 1, r);	/* 2r */
44 cbeb0b26 2006-04-01 devnull 	mpmul(r, s, r);		/* 2rs */
45 cbeb0b26 2006-04-01 devnull 	mpmul(r, i, i);		/* 2irs */
46 cbeb0b26 2006-04-01 devnull 	mpadd(p, i, p);		/* p0 + 2irs */
47 0fc65b37 2004-03-21 devnull 	for(;;){
48 0fc65b37 2004-03-21 devnull 		if(probably_prime(p, accuracy))
49 0fc65b37 2004-03-21 devnull 			break;
50 cbeb0b26 2006-04-01 devnull 		mpadd(p, r, p); /* p += 2rs */
51 0fc65b37 2004-03-21 devnull 	}
52 0fc65b37 2004-03-21 devnull 
53 0fc65b37 2004-03-21 devnull 	mpfree(i);
54 0fc65b37 2004-03-21 devnull 	mpfree(s);
55 0fc65b37 2004-03-21 devnull 	mpfree(r);
56 0fc65b37 2004-03-21 devnull 	mpfree(t);
57 0fc65b37 2004-03-21 devnull }