secure/lib/libcrypto/man/BN_generate_prime.3

   1 .rn '' }`
   2 ''' $RCSfile$$Revision$$Date$
   3 '''
   4 ''' $Log$
   5 '''
   6 .de Sh
   7 .br
   8 .if t .Sp
   9 .ne 5
  10 .PP
  11 \fB\\$1\fR
  12 .PP
  13 ..
  14 .de Sp
  15 .if t .sp .5v
  16 .if n .sp
  17 ..
  18 .de Ip
  19 .br
  20 .ie \\n(.$>=3 .ne \\$3
  21 .el .ne 3
  22 .IP "\\$1" \\$2
  23 ..
  24 .de Vb
  25 .ft CW
  26 .nf
  27 .ne \\$1
  28 ..
  29 .de Ve
  30 .ft R
  31
  32 .fi
  33 ..
  34 '''
  35 '''
  36 '''     Set up \*(-- to give an unbreakable dash;
  37 '''     string Tr holds user defined translation string.
  38 '''     Bell System Logo is used as a dummy character.
  39 '''
  40 .tr \(*W-|\(bv\*(Tr
  41 .ie n \{\
  42 .ds -- \(*W-
  43 .ds PI pi
  44 .if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
  45 .if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch
  46 .ds L" ""
  47 .ds R" ""
  48 '''   \*(M", \*(S", \*(N" and \*(T" are the equivalent of
  49 '''   \*(L" and \*(R", except that they are used on ".xx" lines,
  50 '''   such as .IP and .SH, which do another additional levels of
  51 '''   double-quote interpretation
  52 .ds M" """
  53 .ds S" """
  54 .ds N" """""
  55 .ds T" """""
  56 .ds L' '
  57 .ds R' '
  58 .ds M' '
  59 .ds S' '
  60 .ds N' '
  61 .ds T' '
  62 'br\}
  63 .el\{\
  64 .ds -- \(em\|
  65 .tr \*(Tr
  66 .ds L" ``
  67 .ds R" ''
  68 .ds M" ``
  69 .ds S" ''
  70 .ds N" ``
  71 .ds T" ''
  72 .ds L' `
  73 .ds R' '
  74 .ds M' `
  75 .ds S' '
  76 .ds N' `
  77 .ds T' '
  78 .ds PI \(*p
  79 'br\}
  80 .\"     If the F register is turned on, we'll generate
  81 .\"     index entries out stderr for the following things:
  82 .\"             TH      Title
  83 .\"             SH      Header
  84 .\"             Sh      Subsection
  85 .\"             Ip      Item
  86 .\"             X<>     Xref  (embedded
  87 .\"     Of course, you have to process the output yourself
  88 .\"     in some meaninful fashion.
  89 .if \nF \{
  90 .de IX
  91 .tm Index:\\$1\t\\n%\t"\\$2"
  92 ..
  93 .nr % 0
  94 .rr F
  95 .\}
  96 .TH BN_generate_prime 3 "0.9.7d" "2/Sep/2004" "OpenSSL"
  97 .UC
  98 .if n .hy 0
  99 .if n .na
 100 .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
 101 .de CQ          \" put $1 in typewriter font
 102 .ft CW
 103 'if n "\c
 104 'if t \\&\\$1\c
 105 'if n \\&\\$1\c
 106 'if n \&"
 107 \\&\\$2 \\$3 \\$4 \\$5 \\$6 \\$7
 108 '.ft R
 109 ..
 110 .\" @(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2
 111 .       \" AM - accent mark definitions
 112 .bd B 3
 113 .       \" fudge factors for nroff and troff
 114 .if n \{\
 115 .       ds #H 0
 116 .       ds #V .8m
 117 .       ds #F .3m
 118 .       ds #[ \f1
 119 .       ds #] \fP
 120 .\}
 121 .if t \{\
 122 .       ds #H ((1u-(\\\\n(.fu%2u))*.13m)
 123 .       ds #V .6m
 124 .       ds #F 0
 125 .       ds #[ \&
 126 .       ds #] \&
 127 .\}
 128 .       \" simple accents for nroff and troff
 129 .if n \{\
 130 .       ds ' \&
 131 .       ds ` \&
 132 .       ds ^ \&
 133 .       ds , \&
 134 .       ds ~ ~
 135 .       ds ? ?
 136 .       ds ! !
 137 .       ds /
 138 .       ds q
 139 .\}
 140 .if t \{\
 141 .       ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
 142 .       ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
 143 .       ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
 144 .       ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
 145 .       ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
 146 .       ds ? \s-2c\h'-\w'c'u*7/10'\u\h'\*(#H'\zi\d\s+2\h'\w'c'u*8/10'
 147 .       ds ! \s-2\(or\s+2\h'-\w'\(or'u'\v'-.8m'.\v'.8m'
 148 .       ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
 149 .       ds q o\h'-\w'o'u*8/10'\s-4\v'.4m'\z\(*i\v'-.4m'\s+4\h'\w'o'u*8/10'
 150 .\}
 151 .       \" troff and (daisy-wheel) nroff accents
 152 .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
 153 .ds 8 \h'\*(#H'\(*b\h'-\*(#H'
 154 .ds v \\k:\h'-(\\n(.wu*9/10-\*(#H)'\v'-\*(#V'\*(#[\s-4v\s0\v'\*(#V'\h'|\\n:u'\*(#]
 155 .ds _ \\k:\h'-(\\n(.wu*9/10-\*(#H+(\*(#F*2/3))'\v'-.4m'\z\(hy\v'.4m'\h'|\\n:u'
 156 .ds . \\k:\h'-(\\n(.wu*8/10)'\v'\*(#V*4/10'\z.\v'-\*(#V*4/10'\h'|\\n:u'
 157 .ds 3 \*(#[\v'.2m'\s-2\&3\s0\v'-.2m'\*(#]
 158 .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
 159 .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
 160 .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
 161 .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
 162 .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
 163 .ds ae a\h'-(\w'a'u*4/10)'e
 164 .ds Ae A\h'-(\w'A'u*4/10)'E
 165 .ds oe o\h'-(\w'o'u*4/10)'e
 166 .ds Oe O\h'-(\w'O'u*4/10)'E
 167 .       \" corrections for vroff
 168 .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
 169 .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
 170 .       \" for low resolution devices (crt and lpr)
 171 .if \n(.H>23 .if \n(.V>19 \
 172 \{\
 173 .       ds : e
 174 .       ds 8 ss
 175 .       ds v \h'-1'\o'\(aa\(ga'
 176 .       ds _ \h'-1'^
 177 .       ds . \h'-1'.
 178 .       ds 3 3
 179 .       ds o a
 180 .       ds d- d\h'-1'\(ga
 181 .       ds D- D\h'-1'\(hy
 182 .       ds th \o'bp'
 183 .       ds Th \o'LP'
 184 .       ds ae ae
 185 .       ds Ae AE
 186 .       ds oe oe
 187 .       ds Oe OE
 188 .\}
 189 .rm #[ #] #H #V #F C
 190 .SH "NAME"
 191 BN_generate_prime, BN_is_prime, BN_is_prime_fasttest \- generate primes and test for primality
 192 .SH "SYNOPSIS"
 193 .PP
 194 .Vb 1
 195 \& #include <openssl/bn.h>
 196 .Ve
 197 .Vb 2
 198 \& BIGNUM *BN_generate_prime(BIGNUM *ret, int num, int safe, BIGNUM *add,
 199 \&     BIGNUM *rem, void (*callback)(int, int, void *), void *cb_arg);
 200 .Ve
 201 .Vb 2
 202 \& int BN_is_prime(const BIGNUM *a, int checks, void (*callback)(int, int,
 203 \&     void *), BN_CTX *ctx, void *cb_arg);
 204 .Ve
 205 .Vb 3
 206 \& int BN_is_prime_fasttest(const BIGNUM *a, int checks,
 207 \&     void (*callback)(int, int, void *), BN_CTX *ctx, void *cb_arg,
 208 \&     int do_trial_division);
 209 .Ve
 210 .SH "DESCRIPTION"
 211 \fIBN_generate_prime()\fR generates a pseudo-random prime number of \fBnum\fR
 212 bits.
 213 If \fBret\fR is not \fBNULL\fR, it will be used to store the number.
 214 .PP
 215 If \fBcallback\fR is not \fBNULL\fR, it is called as follows:
 216 .Ip "\(bu" 4
 217 \fBcallback(0, i, cb_arg)\fR is called after generating the i-th
 218 potential prime number.
 219 .Ip "\(bu" 4
 220 While the number is being tested for primality, \fBcallback(1, j,
 221 cb_arg)\fR is called as described below.
 222 .Ip "\(bu" 4
 223 When a prime has been found, \fBcallback(2, i, cb_arg)\fR is called.
 224 .PP
 225 The prime may have to fulfill additional requirements for use in
 226 Diffie-Hellman key exchange:
 227 .PP
 228 If \fBadd\fR is not \fB\s-1NULL\s0\fR, the prime will fulfill the condition p % \fBadd\fR
 229 == \fBrem\fR (p % \fBadd\fR == 1 if \fBrem\fR == \fB\s-1NULL\s0\fR) in order to suit a given
 230 generator.
 231 .PP
 232 If \fBsafe\fR is true, it will be a safe prime (i.e. a prime p so
 233 that (p-1)/2 is also prime).
 234 .PP
 235 The \s-1PRNG\s0 must be seeded prior to calling \fIBN_generate_prime()\fR.
 236 The prime number generation has a negligible error probability.
 237 .PP
 238 \fIBN_is_prime()\fR and \fIBN_is_prime_fasttest()\fR test if the number \fBa\fR is
 239 prime.  The following tests are performed until one of them shows that
 240 \fBa\fR is composite; if \fBa\fR passes all these tests, it is considered
 241 prime.
 242 .PP
 243 \fIBN_is_prime_fasttest()\fR, when called with \fBdo_trial_division == 1\fR,
 244 first attempts trial division by a number of small primes;
 245 if no divisors are found by this test and \fBcallback\fR is not \fB\s-1NULL\s0\fR,
 246 \fBcallback(1, \-1, cb_arg)\fR is called.
 247 If \fBdo_trial_division == 0\fR, this test is skipped.
 248 .PP
 249 Both \fIBN_is_prime()\fR and \fIBN_is_prime_fasttest()\fR perform a Miller-Rabin
 250 probabilistic primality test with \fBchecks\fR iterations. If
 251 \fBchecks == BN_prime_checks\fR, a number of iterations is used that
 252 yields a false positive rate of at most 2^\-80 for random input.
 253 .PP
 254 If \fBcallback\fR is not \fB\s-1NULL\s0\fR, \fBcallback(1, j, cb_arg)\fR is called
 255 after the j-th iteration (j = 0, 1, ...). \fBctx\fR is a
 256 pre-allocated \fB\s-1BN_CTX\s0\fR (to save the overhead of allocating and
 257 freeing the structure in a loop), or \fB\s-1NULL\s0\fR.
 258 .SH "RETURN VALUES"
 259 \fIBN_generate_prime()\fR returns the prime number on success, \fBNULL\fR otherwise.
 260 .PP
 261 \fIBN_is_prime()\fR returns 0 if the number is composite, 1 if it is
 262 prime with an error probability of less than 0.25^\fBchecks\fR, and
 263 \-1 on error.
 264 .PP
 265 The error codes can be obtained by ERR_get_error(3).
 266 .SH "SEE ALSO"
 267 bn(3), ERR_get_error(3), rand(3)
 268 .SH "HISTORY"
 269 The \fBcb_arg\fR arguments to \fIBN_generate_prime()\fR and to \fIBN_is_prime()\fR
 270 were added in SSLeay 0.9.0. The \fBret\fR argument to \fIBN_generate_prime()\fR
 271 was added in SSLeay 0.9.1.
 272 \fIBN_is_prime_fasttest()\fR was added in OpenSSL 0.9.5.
 273
 274 .rn }` ''
 275 .IX Title "BN_generate_prime 3"
 276 .IX Name "BN_generate_prime, BN_is_prime, BN_is_prime_fasttest - generate primes and test for primality"
 277
 278 .IX Header "NAME"
 279
 280 .IX Header "SYNOPSIS"
 281
 282 .IX Header "DESCRIPTION"
 283
 284 .IX Item "\(bu"
 285
 286 .IX Item "\(bu"
 287
 288 .IX Item "\(bu"
 289
 290 .IX Header "RETURN VALUES"
 291
 292 .IX Header "SEE ALSO"
 293
 294 .IX Header "HISTORY"
 295