diff options
author | rsc <devnull@localhost> | 2004-03-21 14:04:56 +0000 |
---|---|---|
committer | rsc <devnull@localhost> | 2004-03-21 14:04:56 +0000 |
commit | 0fc65b37a1e7585ca2347bf61dcb8bc3a6b146a4 (patch) | |
tree | dd9189a823998f494082adb769451f12be056566 /src/libsec/port/gensafeprime.c | |
parent | 768206abfcf505fb034a0151bf263bc0b1f2380c (diff) | |
download | plan9port-0fc65b37a1e7585ca2347bf61dcb8bc3a6b146a4.tar.gz plan9port-0fc65b37a1e7585ca2347bf61dcb8bc3a6b146a4.tar.bz2 plan9port-0fc65b37a1e7585ca2347bf61dcb8bc3a6b146a4.zip |
Add most of libsec.
Diffstat (limited to 'src/libsec/port/gensafeprime.c')
-rw-r--r-- | src/libsec/port/gensafeprime.c | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/src/libsec/port/gensafeprime.c b/src/libsec/port/gensafeprime.c new file mode 100644 index 00000000..e95c94c9 --- /dev/null +++ b/src/libsec/port/gensafeprime.c @@ -0,0 +1,36 @@ +#include "os.h" +#include <mp.h> +#include <libsec.h> + +// find a prime p of length n and a generator alpha of Z^*_p +// Alg 4.86 Menezes et al () Handbook, p.164 +void +gensafeprime(mpint *p, mpint *alpha, int n, int accuracy) +{ + mpint *q, *b; + + q = mpnew(n-1); + while(1){ + genprime(q, n-1, accuracy); + mpleft(q, 1, p); + mpadd(p, mpone, p); // p = 2*q+1 + if(probably_prime(p, accuracy)) + break; + } + // now find a generator alpha of the multiplicative + // group Z*_p of order p-1=2q + b = mpnew(0); + while(1){ + mprand(n, genrandom, alpha); + mpmod(alpha, p, alpha); + mpmul(alpha, alpha, b); + mpmod(b, p, b); + if(mpcmp(b, mpone) == 0) + continue; + mpexp(alpha, q, p, b); + if(mpcmp(b, mpone) != 0) + break; + } + mpfree(b); + mpfree(q); +} |