| rsc | cfa37a7 | 2004-04-10 18:53:55 +0000 | [diff] [blame] | 1 | .TH PRIME 3 |
| 2 | .SH NAME |
| 3 | genprime, gensafeprime, genstrongprime, DSAprimes, probably_prime, smallprimetest \- prime number generation |
| 4 | .SH SYNOPSIS |
| 5 | .B #include <u.h> |
| 6 | .br |
| 7 | .B #include <libc.h> |
| 8 | .br |
| 9 | .B #include <mp.h> |
| 10 | .br |
| 11 | .B #include <libsec.h> |
| 12 | .PP |
| 13 | .B |
| 14 | int smallprimetest(mpint *p) |
| 15 | .PP |
| 16 | .B |
| 17 | int probably_prime(mpint *p, int nrep) |
| 18 | .PP |
| 19 | .B |
| 20 | void genprime(mpint *p, int n, int nrep) |
| 21 | .PP |
| 22 | .B |
| 23 | void gensafeprime(mpint *p, mpint *alpha, int n, int accuracy) |
| 24 | .PP |
| 25 | .B |
| 26 | void genstrongprime(mpint *p, int n, int nrep) |
| 27 | .PP |
| 28 | .B |
| 29 | void DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen]) |
| 30 | .SH DESCRIPTION |
| 31 | .PP |
| 32 | Public key algorithms abound in prime numbers. The following routines |
| 33 | generate primes or test numbers for primality. |
| 34 | .PP |
| 35 | .I Smallprimetest |
| 36 | checks for divisibility by the first 10000 primes. It returns 0 |
| 37 | if |
| 38 | .I p |
| 39 | is not divisible by the primes and \-1 if it is. |
| 40 | .PP |
| 41 | .I Probably_prime |
| 42 | uses the Miller-Rabin test to test |
| 43 | .IR p . |
| 44 | It returns non-zero if |
| 45 | .I P |
| 46 | is probably prime. The probability of it not being prime is |
| 47 | 1/4**\fInrep\fR. |
| 48 | .PP |
| 49 | .I Genprime |
| 50 | generates a random |
| 51 | .I n |
| 52 | bit prime. Since it uses the Miller-Rabin test, |
| 53 | .I nrep |
| 54 | is the repetition count passed to |
| 55 | .IR probably_prime . |
| 56 | .I Gensafegprime |
| 57 | generates an |
| 58 | .IR n -bit |
| 59 | prime |
| 60 | .I p |
| 61 | and a generator |
| 62 | .I alpha |
| 63 | of the multiplicative group of integers mod \fIp\fR; |
| 64 | there is a prime \fIq\fR such that \fIp-1=2*q\fR. |
| 65 | .I Genstrongprime |
| 66 | generates a prime, |
| 67 | .IR p , |
| 68 | with the following properties: |
| 69 | .IP \- |
| 70 | (\fIp\fR-1)/2 is prime. Therefore |
| 71 | .IR p -1 |
| 72 | has a large prime factor, |
| 73 | .IR p '. |
| 74 | .IP \- |
| 75 | .IR p '-1 |
| 76 | has a large prime factor |
| 77 | .IP \- |
| 78 | .IR p +1 |
| 79 | has a large prime factor |
| 80 | .PP |
| 81 | .I DSAprimes |
| 82 | generates two primes, |
| 83 | .I q |
| 84 | and |
| 85 | .IR p, |
| 86 | using the NIST recommended algorithm for DSA primes. |
| 87 | .I q |
| 88 | divides |
| 89 | .IR p -1. |
| 90 | The random seed used is also returned, so that skeptics |
| 91 | can later confirm the computation. Be patient; this is a |
| 92 | slow algorithm. |
| 93 | .SH SOURCE |
| rsc | b5fdffe | 2004-04-19 19:22:56 +0000 | [diff] [blame] | 94 | .B /usr/local/plan9/src/libsec |
| rsc | cfa37a7 | 2004-04-10 18:53:55 +0000 | [diff] [blame] | 95 | .SH SEE ALSO |
| rsc | bf8a59f | 2004-04-11 03:42:27 +0000 | [diff] [blame] | 96 | .IR aes (3) |
| 97 | .IR blowfish (3), |
| 98 | .IR des (3), |
| 99 | .IR elgamal (3), |
| 100 | .IR rsa (3), |
