1.\" $OpenBSD: BN_generate_prime.3,v 1.6 2017/01/07 05:06:22 schwarze Exp $ 2.\" OpenSSL 2afb29b4 Aug 14 16:47:13 2014 -0400 3.\" 4.\" This file was written by Ulf Moeller <ulf@openssl.org> 5.\" Bodo Moeller <bodo@openssl.org>, and Matt Caswell <matt@openssl.org>. 6.\" Copyright (c) 2000, 2003, 2013, 2014 The OpenSSL Project. 7.\" All rights reserved. 8.\" 9.\" Redistribution and use in source and binary forms, with or without 10.\" modification, are permitted provided that the following conditions 11.\" are met: 12.\" 13.\" 1. Redistributions of source code must retain the above copyright 14.\" notice, this list of conditions and the following disclaimer. 15.\" 16.\" 2. Redistributions in binary form must reproduce the above copyright 17.\" notice, this list of conditions and the following disclaimer in 18.\" the documentation and/or other materials provided with the 19.\" distribution. 20.\" 21.\" 3. All advertising materials mentioning features or use of this 22.\" software must display the following acknowledgment: 23.\" "This product includes software developed by the OpenSSL Project 24.\" for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 25.\" 26.\" 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 27.\" endorse or promote products derived from this software without 28.\" prior written permission. For written permission, please contact 29.\" openssl-core@openssl.org. 30.\" 31.\" 5. Products derived from this software may not be called "OpenSSL" 32.\" nor may "OpenSSL" appear in their names without prior written 33.\" permission of the OpenSSL Project. 34.\" 35.\" 6. Redistributions of any form whatsoever must retain the following 36.\" acknowledgment: 37.\" "This product includes software developed by the OpenSSL Project 38.\" for use in the OpenSSL Toolkit (http://www.openssl.org/)" 39.\" 40.\" THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 41.\" EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 43.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 44.\" ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 45.\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 46.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 47.\" LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 49.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 50.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 51.\" OF THE POSSIBILITY OF SUCH DAMAGE. 52.\" 53.Dd $Mdocdate: January 7 2017 $ 54.Dt BN_GENERATE_PRIME 3 55.Os 56.Sh NAME 57.Nm BN_generate_prime_ex , 58.Nm BN_is_prime_ex , 59.Nm BN_is_prime_fasttest_ex , 60.Nm BN_GENCB_call , 61.Nm BN_GENCB_set_old , 62.Nm BN_GENCB_set , 63.Nm BN_generate_prime , 64.Nm BN_is_prime , 65.Nm BN_is_prime_fasttest 66.Nd generate primes and test for primality 67.Sh SYNOPSIS 68.In openssl/bn.h 69.Ft int 70.Fo BN_generate_prime_ex 71.Fa "BIGNUM *ret" 72.Fa "int bits" 73.Fa "int safe" 74.Fa "const BIGNUM *add" 75.Fa "const BIGNUM *rem" 76.Fa "BN_GENCB *cb" 77.Fc 78.Ft int 79.Fo BN_is_prime_ex 80.Fa "const BIGNUM *p" 81.Fa "int nchecks" 82.Fa "BN_CTX *ctx" 83.Fa "BN_GENCB *cb" 84.Fc 85.Ft int 86.Fo BN_is_prime_fasttest_ex 87.Fa "const BIGNUM *p" 88.Fa "int nchecks" 89.Fa "BN_CTX *ctx" 90.Fa "int do_trial_division" 91.Fa "BN_GENCB *cb" 92.Fc 93.Ft int 94.Fo BN_GENCB_call 95.Fa "BN_GENCB *cb" 96.Fa "int a" 97.Fa "int b" 98.Fc 99.Ft void 100.Fo BN_GENCB_set_old 101.Fa "BN_GENCB *gencb" 102.Fa "void (*callback)(int, int, void *)" 103.Fa "void *cb_arg" 104.Fc 105.Ft void 106.Fo BN_GENCB_set 107.Fa "BN_GENCB *gencb" 108.Fa "int (*callback)(int, int, BN_GENCB *)" 109.Fa "void *cb_arg" 110.Fc 111.Pp 112Deprecated: 113.Pp 114.Ft BIGNUM * 115.Fo BN_generate_prime 116.Fa "BIGNUM *ret" 117.Fa "int num" 118.Fa "int safe" 119.Fa "BIGNUM *add" 120.Fa "BIGNUM *rem" 121.Fa "void (*callback)(int, int, void *)" 122.Fa "void *cb_arg" 123.Fc 124.Ft int 125.Fo BN_is_prime 126.Fa "const BIGNUM *a" 127.Fa "int checks" 128.Fa "void (*callback)(int, int, void *)" 129.Fa "BN_CTX *ctx" 130.Fa "void *cb_arg" 131.Fc 132.Ft int 133.Fo BN_is_prime_fasttest 134.Fa "const BIGNUM *a" 135.Fa "int checks" 136.Fa "void (*callback)(int, int, void *)" 137.Fa "BN_CTX *ctx" 138.Fa "void *cb_arg" 139.Fa "int do_trial_division" 140.Fc 141.Sh DESCRIPTION 142.Fn BN_generate_prime_ex 143generates a pseudo-random prime number of at least bit length 144.Fa bits . 145If 146.Fa ret 147is not 148.Dv NULL , 149it will be used to store the number. 150.Pp 151If 152.Fa cb 153is not 154.Dv NULL , 155it is used as follows: 156.Bl -bullet 157.It 158.Fn BN_GENCB_call cb 0 i 159is called after generating the i-th potential prime number. 160.It 161While the number is being tested for primality, 162.Fn BN_GENCB_call cb 1 j 163is called as described below. 164.It 165When a prime has been found, 166.Fn BN_GENCB_call cb 2 i 167is called. 168.El 169.Pp 170The prime may have to fulfill additional requirements for use in 171Diffie-Hellman key exchange: 172.Pp 173If 174.Fa add 175is not 176.Dv NULL , 177the prime will fulfill the condition p % 178.Fa add 179== 180.Fa rem 181(p % 182.Fa add 183== 1 if 184.Fa rem 185== 186.Dv NULL ) 187in order to suit a given generator. 188.Pp 189If 190.Fa safe 191is true, it will be a safe prime (i.e. a prime p so that (p-1)/2 192is also prime). 193.Pp 194The prime number generation has a negligible error probability. 195.Pp 196.Fn BN_is_prime_ex 197and 198.Fn BN_is_prime_fasttest_ex 199test if the number 200.Fa p 201is prime. 202The following tests are performed until one of them shows that 203.Fa p 204is composite; if 205.Fa p 206passes all these tests, it is considered prime. 207.Pp 208.Fn BN_is_prime_fasttest_ex , 209when called with 210.Fa do_trial_division 211== 1, first attempts trial division by a number of small primes; 212if no divisors are found by this test and 213.Fa cb 214is not 215.Dv NULL , 216.Sy BN_GENCB_call(cb, 1, -1) 217is called. 218If 219.Fa do_trial_division 220== 0, this test is skipped. 221.Pp 222Both 223.Fn BN_is_prime_ex 224and 225.Fn BN_is_prime_fasttest_ex 226perform a Miller-Rabin probabilistic primality test with 227.Fa nchecks 228iterations. 229If 230.Fa nchecks 231== 232.Dv BN_prime_checks , 233a number of iterations is used that yields a false positive rate of at 234most 2^-80 for random input. 235.Pp 236If 237.Fa cb 238is not 239.Dv NULL , 240.Fa BN_GENCB_call cb 1 j 241is called after the j-th iteration (j = 0, 1, ...). 242.Fa ctx 243is a pre-allocated 244.Vt BN_CTX 245(to save the overhead of allocating and freeing the structure in a 246loop), or 247.Dv NULL . 248.Pp 249.Fn BN_GENCB_call 250calls the callback function held in the 251.Vt BN_GENCB 252structure and passes the ints 253.Fa a 254and 255.Fa b 256as arguments. 257There are two types of 258.Vt BN_GENCB 259structures that are supported: "new" style and "old" style. 260New programs should prefer the "new" style, whilst the "old" style is 261provided for backwards compatibility purposes. 262.Pp 263For "new" style callbacks a 264.Vt BN_GENCB 265structure should be initialised with a call to the macro 266.Fn BN_GENCB_set , 267where 268.Fa gencb 269is a 270.Vt BN_GENCB * , 271.Fa callback 272is of type 273.Vt int (*callback)(int, int, BN_GENCB *) 274and 275.Fa cb_arg 276is a 277.Vt void * . 278"Old" style callbacks are the same except they are initialised with a 279call to the macro 280.Fn BN_GENCB_set_old 281and 282.Fa callback 283is of type 284.Vt void (*callback)(int, int, void *) . 285.Pp 286A callback is invoked through a call to 287.Fn BN_GENCB_call . 288This will check the type of the callback and will invoke 289.Fn callback a b gencb 290for new style callbacks or 291.Fn callback a b cb_arg 292for old style. 293.Pp 294.Fn BN_generate_prime 295(deprecated) works in the same way as 296.Fn BN_generate_prime_ex 297but expects an old style callback function directly in the 298.Fa callback 299parameter, and an argument to pass to it in the 300.Fa cb_arg . 301Similarly 302.Fn BN_is_prime 303and 304.Fn BN_is_prime_fasttest 305are deprecated and can be compared to 306.Fn BN_is_prime_ex 307and 308.Fn BN_is_prime_fasttest_ex 309respectively. 310.Sh RETURN VALUES 311.Fn BN_generate_prime_ex 312returns 1 on success or 0 on error. 313.Pp 314.Fn BN_is_prime_ex , 315.Fn BN_is_prime_fasttest_ex , 316.Fn BN_is_prime , 317and 318.Fn BN_is_prime_fasttest 319return 0 if the number is composite, 1 if it is prime with an error 320probability of less than 321.Pf 0.25^ Fa nchecks , 322and -1 on error. 323.Pp 324.Fn BN_generate_prime 325returns the prime number on success, 326.Dv NULL 327otherwise. 328.Pp 329Callback functions should return 1 on success or 0 on error. 330.Pp 331The error codes can be obtained by 332.Xr ERR_get_error 3 . 333.Sh SEE ALSO 334.Xr BN_new 3 , 335.Xr ERR_get_error 3 , 336.Xr RAND_bytes 3 337.Sh HISTORY 338The 339.Fa cb_arg 340arguments to 341.Fn BN_generate_prime 342and to 343.Fn BN_is_prime 344were added in SSLeay 0.9.0. 345The 346.Fa ret 347argument to 348.Fn BN_generate_prime 349was added in SSLeay 0.9.1. 350.Fn BN_is_prime_fasttest 351was added in OpenSSL 0.9.5. 352