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 /* find a prime p of length n and a generator alpha of Z^*_p */
 6 cbeb0b26 2006-04-01 devnull /* Alg 4.86 Menezes et al () Handbook, p.164 */
 7 0fc65b37 2004-03-21 devnull void
 8 0fc65b37 2004-03-21 devnull gensafeprime(mpint *p, mpint *alpha, int n, int accuracy)
 9 0fc65b37 2004-03-21 devnull {
10 0fc65b37 2004-03-21 devnull 	mpint *q, *b;
11 0fc65b37 2004-03-21 devnull 
12 0fc65b37 2004-03-21 devnull 	q = mpnew(n-1);
13 0fc65b37 2004-03-21 devnull 	while(1){
14 0fc65b37 2004-03-21 devnull 		genprime(q, n-1, accuracy);
15 0fc65b37 2004-03-21 devnull 		mpleft(q, 1, p);
16 cbeb0b26 2006-04-01 devnull 		mpadd(p, mpone, p); /* p = 2*q+1 */
17 0fc65b37 2004-03-21 devnull 		if(probably_prime(p, accuracy))
18 0fc65b37 2004-03-21 devnull 			break;
19 0fc65b37 2004-03-21 devnull 	}
20 cbeb0b26 2006-04-01 devnull 	/* now find a generator alpha of the multiplicative */
21 cbeb0b26 2006-04-01 devnull 	/* group Z*_p of order p-1=2q */
22 0fc65b37 2004-03-21 devnull 	b = mpnew(0);
23 0fc65b37 2004-03-21 devnull 	while(1){
24 0fc65b37 2004-03-21 devnull 		mprand(n, genrandom, alpha);
25 0fc65b37 2004-03-21 devnull 		mpmod(alpha, p, alpha);
26 0fc65b37 2004-03-21 devnull 		mpmul(alpha, alpha, b);
27 0fc65b37 2004-03-21 devnull 		mpmod(b, p, b);
28 0fc65b37 2004-03-21 devnull 		if(mpcmp(b, mpone) == 0)
29 0fc65b37 2004-03-21 devnull 			continue;
30 0fc65b37 2004-03-21 devnull 		mpexp(alpha, q, p, b);
31 0fc65b37 2004-03-21 devnull 		if(mpcmp(b, mpone) != 0)
32 0fc65b37 2004-03-21 devnull 			break;
33 0fc65b37 2004-03-21 devnull 	}
34 0fc65b37 2004-03-21 devnull 	mpfree(b);
35 0fc65b37 2004-03-21 devnull 	mpfree(q);
36 0fc65b37 2004-03-21 devnull }