gensafeprime.c (756B)
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 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 }