sys/src/libsec/port/gensafeprime.c

   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 }