1 cfa37a7b 2004-04-10 devnull .TH PRIME 3
3 cfa37a7b 2004-04-10 devnull genprime, gensafeprime, genstrongprime, DSAprimes, probably_prime, smallprimetest \- prime number generation
4 cfa37a7b 2004-04-10 devnull .SH SYNOPSIS
5 cfa37a7b 2004-04-10 devnull .B #include <u.h>
7 cfa37a7b 2004-04-10 devnull .B #include <libc.h>
9 cfa37a7b 2004-04-10 devnull .B #include <mp.h>
11 cfa37a7b 2004-04-10 devnull .B #include <libsec.h>
14 cfa37a7b 2004-04-10 devnull int smallprimetest(mpint *p)
17 cfa37a7b 2004-04-10 devnull int probably_prime(mpint *p, int nrep)
20 cfa37a7b 2004-04-10 devnull void genprime(mpint *p, int n, int nrep)
23 cfa37a7b 2004-04-10 devnull void gensafeprime(mpint *p, mpint *alpha, int n, int accuracy)
26 cfa37a7b 2004-04-10 devnull void genstrongprime(mpint *p, int n, int nrep)
29 cfa37a7b 2004-04-10 devnull void DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen])
30 cfa37a7b 2004-04-10 devnull .SH DESCRIPTION
32 cfa37a7b 2004-04-10 devnull Public key algorithms abound in prime numbers. The following routines
33 cfa37a7b 2004-04-10 devnull generate primes or test numbers for primality.
35 cfa37a7b 2004-04-10 devnull .I Smallprimetest
36 cfa37a7b 2004-04-10 devnull checks for divisibility by the first 10000 primes. It returns 0
39 cfa37a7b 2004-04-10 devnull is not divisible by the primes and \-1 if it is.
41 cfa37a7b 2004-04-10 devnull .I Probably_prime
42 cfa37a7b 2004-04-10 devnull uses the Miller-Rabin test to test
44 cfa37a7b 2004-04-10 devnull It returns non-zero if
46 cfa37a7b 2004-04-10 devnull is probably prime. The probability of it not being prime is
47 cfa37a7b 2004-04-10 devnull 1/4**\fInrep\fR.
49 cfa37a7b 2004-04-10 devnull .I Genprime
50 cfa37a7b 2004-04-10 devnull generates a random
52 cfa37a7b 2004-04-10 devnull bit prime. Since it uses the Miller-Rabin test,
54 cfa37a7b 2004-04-10 devnull is the repetition count passed to
55 cfa37a7b 2004-04-10 devnull .IR probably_prime .
56 cfa37a7b 2004-04-10 devnull .I Gensafegprime
57 cfa37a7b 2004-04-10 devnull generates an
58 cfa37a7b 2004-04-10 devnull .IR n -bit
61 cfa37a7b 2004-04-10 devnull and a generator
63 cfa37a7b 2004-04-10 devnull of the multiplicative group of integers mod \fIp\fR;
64 cfa37a7b 2004-04-10 devnull there is a prime \fIq\fR such that \fIp-1=2*q\fR.
65 cfa37a7b 2004-04-10 devnull .I Genstrongprime
66 cfa37a7b 2004-04-10 devnull generates a prime,
68 cfa37a7b 2004-04-10 devnull with the following properties:
70 cfa37a7b 2004-04-10 devnull (\fIp\fR-1)/2 is prime. Therefore
72 cfa37a7b 2004-04-10 devnull has a large prime factor,
75 cfa37a7b 2004-04-10 devnull .IR p '-1
76 cfa37a7b 2004-04-10 devnull has a large prime factor
79 cfa37a7b 2004-04-10 devnull has a large prime factor
81 cfa37a7b 2004-04-10 devnull .I DSAprimes
82 cfa37a7b 2004-04-10 devnull generates two primes,
86 cfa37a7b 2004-04-10 devnull using the NIST recommended algorithm for DSA primes.
89 cfa37a7b 2004-04-10 devnull .IR p -1.
90 cfa37a7b 2004-04-10 devnull The random seed used is also returned, so that skeptics
91 cfa37a7b 2004-04-10 devnull can later confirm the computation. Be patient; this is a
92 cfa37a7b 2004-04-10 devnull slow algorithm.
93 cfa37a7b 2004-04-10 devnull .SH SOURCE
94 c3674de4 2005-01-11 devnull .B \*9/src/libsec
95 cfa37a7b 2004-04-10 devnull .SH SEE ALSO
96 bf8a59fa 2004-04-11 devnull .IR aes (3)
97 bf8a59fa 2004-04-11 devnull .IR blowfish (3),
98 bf8a59fa 2004-04-11 devnull .IR des (3),
99 bf8a59fa 2004-04-11 devnull .IR elgamal (3),
100 bf8a59fa 2004-04-11 devnull .IR rsa (3),