1 cfa37a7b 2004-04-10 devnull .TH PRIME 3
  2 cfa37a7b 2004-04-10 devnull .SH NAME
  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>
  6 cfa37a7b 2004-04-10 devnull .br
  7 cfa37a7b 2004-04-10 devnull .B #include <libc.h>
  8 cfa37a7b 2004-04-10 devnull .br
  9 cfa37a7b 2004-04-10 devnull .B #include <mp.h>
 10 cfa37a7b 2004-04-10 devnull .br
 11 cfa37a7b 2004-04-10 devnull .B #include <libsec.h>
 12 cfa37a7b 2004-04-10 devnull .PP
 13 cfa37a7b 2004-04-10 devnull .B
 14 cfa37a7b 2004-04-10 devnull int	smallprimetest(mpint *p)
 15 cfa37a7b 2004-04-10 devnull .PP
 16 cfa37a7b 2004-04-10 devnull .B
 17 cfa37a7b 2004-04-10 devnull int	probably_prime(mpint *p, int nrep)
 18 cfa37a7b 2004-04-10 devnull .PP
 19 cfa37a7b 2004-04-10 devnull .B
 20 cfa37a7b 2004-04-10 devnull void	genprime(mpint *p, int n, int nrep)
 21 cfa37a7b 2004-04-10 devnull .PP
 22 cfa37a7b 2004-04-10 devnull .B
 23 cfa37a7b 2004-04-10 devnull void	gensafeprime(mpint *p, mpint *alpha, int n, int accuracy)
 24 cfa37a7b 2004-04-10 devnull .PP
 25 cfa37a7b 2004-04-10 devnull .B
 26 cfa37a7b 2004-04-10 devnull void	genstrongprime(mpint *p, int n, int nrep)
 27 cfa37a7b 2004-04-10 devnull .PP
 28 cfa37a7b 2004-04-10 devnull .B
 29 cfa37a7b 2004-04-10 devnull void	DSAprimes(mpint *q, mpint *p, uchar seed[SHA1dlen])
 30 cfa37a7b 2004-04-10 devnull .SH DESCRIPTION
 31 cfa37a7b 2004-04-10 devnull .PP
 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.
 34 cfa37a7b 2004-04-10 devnull .PP
 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
 37 cfa37a7b 2004-04-10 devnull if
 38 cfa37a7b 2004-04-10 devnull .I p
 39 cfa37a7b 2004-04-10 devnull is not divisible by the primes and \-1 if it is.
 40 cfa37a7b 2004-04-10 devnull .PP
 41 cfa37a7b 2004-04-10 devnull .I Probably_prime
 42 cfa37a7b 2004-04-10 devnull uses the Miller-Rabin test to test
 43 cfa37a7b 2004-04-10 devnull .IR p .
 44 cfa37a7b 2004-04-10 devnull It returns non-zero if
 45 cfa37a7b 2004-04-10 devnull .I P
 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.
 48 cfa37a7b 2004-04-10 devnull .PP
 49 cfa37a7b 2004-04-10 devnull .I Genprime
 50 cfa37a7b 2004-04-10 devnull generates a random
 51 cfa37a7b 2004-04-10 devnull .I n
 52 cfa37a7b 2004-04-10 devnull bit prime.  Since it uses the Miller-Rabin test,
 53 cfa37a7b 2004-04-10 devnull .I nrep
 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
 59 cfa37a7b 2004-04-10 devnull prime
 60 cfa37a7b 2004-04-10 devnull .I p
 61 cfa37a7b 2004-04-10 devnull and a generator
 62 cfa37a7b 2004-04-10 devnull .I alpha
 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,
 67 cfa37a7b 2004-04-10 devnull .IR p ,
 68 cfa37a7b 2004-04-10 devnull with the following properties:
 69 cfa37a7b 2004-04-10 devnull .IP \-
 70 cfa37a7b 2004-04-10 devnull (\fIp\fR-1)/2 is prime.  Therefore
 71 cfa37a7b 2004-04-10 devnull .IR p -1
 72 cfa37a7b 2004-04-10 devnull has a large prime factor,
 73 cfa37a7b 2004-04-10 devnull .IR p '.
 74 cfa37a7b 2004-04-10 devnull .IP \-
 75 cfa37a7b 2004-04-10 devnull .IR p '-1
 76 cfa37a7b 2004-04-10 devnull has a large prime factor
 77 cfa37a7b 2004-04-10 devnull .IP \-
 78 cfa37a7b 2004-04-10 devnull .IR p +1
 79 cfa37a7b 2004-04-10 devnull has a large prime factor
 80 cfa37a7b 2004-04-10 devnull .PP
 81 cfa37a7b 2004-04-10 devnull .I DSAprimes
 82 cfa37a7b 2004-04-10 devnull generates two primes,
 83 cfa37a7b 2004-04-10 devnull .I q
 84 cfa37a7b 2004-04-10 devnull and
 85 cfa37a7b 2004-04-10 devnull .IR p,
 86 cfa37a7b 2004-04-10 devnull using the NIST recommended algorithm for DSA primes.
 87 cfa37a7b 2004-04-10 devnull .I q
 88 cfa37a7b 2004-04-10 devnull divides
 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 d32deab1 2020-08-16 rsc .MR aes (3)
 97 d32deab1 2020-08-16 rsc .MR blowfish (3) ,
 98 d32deab1 2020-08-16 rsc .MR des (3) ,
 99 d32deab1 2020-08-16 rsc .MR elgamal (3) ,
100 d32deab1 2020-08-16 rsc .MR rsa (3) ,