180ee5cbfSDavid du Colombier #include "os.h"
280ee5cbfSDavid du Colombier #include <mp.h>
380ee5cbfSDavid du Colombier #include <libsec.h>
480ee5cbfSDavid du Colombier
580ee5cbfSDavid du Colombier // find a prime p of length n and a generator alpha of Z^*_p
680ee5cbfSDavid du Colombier // Alg 4.86 Menezes et al () Handbook, p.164
780ee5cbfSDavid du Colombier void
gensafeprime(mpint * p,mpint * alpha,int n,int accuracy)880ee5cbfSDavid du Colombier gensafeprime(mpint *p, mpint *alpha, int n, int accuracy)
980ee5cbfSDavid du Colombier {
1080ee5cbfSDavid du Colombier mpint *q, *b;
1180ee5cbfSDavid du Colombier
1280ee5cbfSDavid du Colombier q = mpnew(n-1);
1380ee5cbfSDavid du Colombier while(1){
1480ee5cbfSDavid du Colombier genprime(q, n-1, accuracy);
1580ee5cbfSDavid du Colombier mpleft(q, 1, p);
1680ee5cbfSDavid du Colombier mpadd(p, mpone, p); // p = 2*q+1
1780ee5cbfSDavid du Colombier if(probably_prime(p, accuracy))
1880ee5cbfSDavid du Colombier break;
1980ee5cbfSDavid du Colombier }
209a747e4fSDavid du Colombier // now find a generator alpha of the multiplicative
219a747e4fSDavid du Colombier // group Z*_p of order p-1=2q
2280ee5cbfSDavid du Colombier b = mpnew(0);
2380ee5cbfSDavid du Colombier while(1){
24*3ff48bf5SDavid du Colombier mprand(n, genrandom, alpha);
259a747e4fSDavid du Colombier mpmod(alpha, p, alpha);
2680ee5cbfSDavid du Colombier mpmul(alpha, alpha, b);
279a747e4fSDavid du Colombier mpmod(b, p, b);
2880ee5cbfSDavid du Colombier if(mpcmp(b, mpone) == 0)
2980ee5cbfSDavid du Colombier continue;
3080ee5cbfSDavid du Colombier mpexp(alpha, q, p, b);
3180ee5cbfSDavid du Colombier if(mpcmp(b, mpone) != 0)
3280ee5cbfSDavid du Colombier break;
3380ee5cbfSDavid du Colombier }
3480ee5cbfSDavid du Colombier mpfree(b);
3580ee5cbfSDavid du Colombier mpfree(q);
3680ee5cbfSDavid du Colombier }
37