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