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