1.\" $OpenBSD: BN_generate_prime.3,v 1.14 2018/03/27 17:35:50 schwarze Exp $ 2.\" full merge up to: OpenSSL b3696a55 Sep 2 09:35:50 2017 -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: March 27 2018 $ 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_new , 62.Nm BN_GENCB_free , 63.Nm BN_GENCB_set_old , 64.Nm BN_GENCB_set , 65.Nm BN_GENCB_get_arg , 66.Nm BN_generate_prime , 67.Nm BN_is_prime , 68.Nm BN_is_prime_fasttest 69.Nd generate primes and test for primality 70.Sh SYNOPSIS 71.In openssl/bn.h 72.Ft int 73.Fo BN_generate_prime_ex 74.Fa "BIGNUM *ret" 75.Fa "int bits" 76.Fa "int safe" 77.Fa "const BIGNUM *add" 78.Fa "const BIGNUM *rem" 79.Fa "BN_GENCB *cb" 80.Fc 81.Ft int 82.Fo BN_is_prime_ex 83.Fa "const BIGNUM *p" 84.Fa "int nchecks" 85.Fa "BN_CTX *ctx" 86.Fa "BN_GENCB *cb" 87.Fc 88.Ft int 89.Fo BN_is_prime_fasttest_ex 90.Fa "const BIGNUM *p" 91.Fa "int nchecks" 92.Fa "BN_CTX *ctx" 93.Fa "int do_trial_division" 94.Fa "BN_GENCB *cb" 95.Fc 96.Ft int 97.Fo BN_GENCB_call 98.Fa "BN_GENCB *cb" 99.Fa "int a" 100.Fa "int b" 101.Fc 102.Ft BN_GENCB * 103.Fn BN_GENCB_new void 104.Ft void 105.Fo BN_GENCB_free 106.Fa "BN_GENCB *cb" 107.Fc 108.Ft void 109.Fo BN_GENCB_set_old 110.Fa "BN_GENCB *gencb" 111.Fa "void (*callback)(int, int, void *)" 112.Fa "void *cb_arg" 113.Fc 114.Ft void 115.Fo BN_GENCB_set 116.Fa "BN_GENCB *gencb" 117.Fa "int (*callback)(int, int, BN_GENCB *)" 118.Fa "void *cb_arg" 119.Fc 120.Ft void * 121.Fo BN_GENCB_get_arg 122.Fa "BN_GENCB *cb" 123.Fc 124.Pp 125Deprecated: 126.Pp 127.Ft BIGNUM * 128.Fo BN_generate_prime 129.Fa "BIGNUM *ret" 130.Fa "int num" 131.Fa "int safe" 132.Fa "BIGNUM *add" 133.Fa "BIGNUM *rem" 134.Fa "void (*callback)(int, int, void *)" 135.Fa "void *cb_arg" 136.Fc 137.Ft int 138.Fo BN_is_prime 139.Fa "const BIGNUM *a" 140.Fa "int checks" 141.Fa "void (*callback)(int, int, void *)" 142.Fa "BN_CTX *ctx" 143.Fa "void *cb_arg" 144.Fc 145.Ft int 146.Fo BN_is_prime_fasttest 147.Fa "const BIGNUM *a" 148.Fa "int checks" 149.Fa "void (*callback)(int, int, void *)" 150.Fa "BN_CTX *ctx" 151.Fa "void *cb_arg" 152.Fa "int do_trial_division" 153.Fc 154.Sh DESCRIPTION 155.Fn BN_generate_prime_ex 156generates a pseudo-random prime number of at least bit length 157.Fa bits . 158If 159.Fa ret 160is not 161.Dv NULL , 162it will be used to store the number. 163.Pp 164If 165.Fa cb 166is not 167.Dv NULL , 168it is used as follows: 169.Bl -bullet 170.It 171.Fn BN_GENCB_call cb 0 i 172is called after generating the i-th potential prime number. 173.It 174While the number is being tested for primality, 175.Fn BN_GENCB_call cb 1 j 176is called as described below. 177.It 178When a prime has been found, 179.Fn BN_GENCB_call cb 2 i 180is called. 181.El 182.Pp 183The prime may have to fulfill additional requirements for use in 184Diffie-Hellman key exchange: 185.Pp 186If 187.Fa add 188is not 189.Dv NULL , 190the prime will fulfill the condition p % 191.Fa add 192== 193.Fa rem 194(p % 195.Fa add 196== 1 if 197.Fa rem 198== 199.Dv NULL ) 200in order to suit a given generator. 201.Pp 202If 203.Fa safe 204is true, it will be a safe prime (i.e. a prime p so that (p-1)/2 205is also prime). 206.Pp 207The prime number generation has a negligible error probability. 208.Pp 209.Fn BN_is_prime_ex 210and 211.Fn BN_is_prime_fasttest_ex 212test if the number 213.Fa p 214is prime. 215The following tests are performed until one of them shows that 216.Fa p 217is composite; if 218.Fa p 219passes all these tests, it is considered prime. 220.Pp 221.Fn BN_is_prime_fasttest_ex , 222when called with 223.Fa do_trial_division 224== 1, first attempts trial division by a number of small primes; 225if no divisors are found by this test and 226.Fa cb 227is not 228.Dv NULL , 229.Sy BN_GENCB_call(cb, 1, -1) 230is called. 231If 232.Fa do_trial_division 233== 0, this test is skipped. 234.Pp 235Both 236.Fn BN_is_prime_ex 237and 238.Fn BN_is_prime_fasttest_ex 239perform a Miller-Rabin probabilistic primality test with 240.Fa nchecks 241iterations. 242If 243.Fa nchecks 244== 245.Dv BN_prime_checks , 246a number of iterations is used that yields a false positive rate of at 247most 2^-80 for random input. 248.Pp 249If 250.Fa cb 251is not 252.Dv NULL , 253.Fa BN_GENCB_call cb 1 j 254is called after the j-th iteration (j = 0, 1, ...). 255.Fa ctx 256is a pre-allocated 257.Vt BN_CTX 258(to save the overhead of allocating and freeing the structure in a 259loop), or 260.Dv NULL . 261.Pp 262.Fn BN_GENCB_call 263calls the callback function held in the 264.Vt BN_GENCB 265structure and passes the ints 266.Fa a 267and 268.Fa b 269as arguments. 270There are two types of 271.Vt BN_GENCB 272structures that are supported: "new" style and "old" style. 273New programs should prefer the "new" style, whilst the "old" style is 274provided for backwards compatibility purposes. 275.Pp 276A 277.Vt BN_GENCB 278structure should be created through a call to 279.Fn BN_GENCB_new 280and freed through a call to 281.Fn BN_GENCB_free . 282.Pp 283For "new" style callbacks a 284.Vt BN_GENCB 285structure should be initialised with a call to 286.Fn BN_GENCB_set , 287where 288.Fa gencb 289is a 290.Vt BN_GENCB * , 291.Fa callback 292is of type 293.Vt int (*callback)(int, int, BN_GENCB *) 294and 295.Fa cb_arg 296is a 297.Vt void * . 298"Old" style callbacks are the same except they are initialised with a 299call to 300.Fn BN_GENCB_set_old 301and 302.Fa callback 303is of type 304.Vt void (*callback)(int, int, void *) . 305.Pp 306A callback is invoked through a call to 307.Fn BN_GENCB_call . 308This will check the type of the callback and will invoke 309.Fn callback a b gencb 310for new style callbacks or 311.Fn callback a b cb_arg 312for old style. 313.Pp 314It is possible to obtain the argument associated with a 315.Vt BN_GENCB 316structure (set via a call to 317.Fn BN_GENCB_set 318or 319.Fn BN_GENCB_set_old ) 320using 321.Fn BN_GENCB_get_arg . 322.Pp 323.Fn BN_generate_prime 324(deprecated) works in the same way as 325.Fn BN_generate_prime_ex 326but expects an old style callback function directly in the 327.Fa callback 328parameter, and an argument to pass to it in the 329.Fa cb_arg . 330Similarly 331.Fn BN_is_prime 332and 333.Fn BN_is_prime_fasttest 334are deprecated and can be compared to 335.Fn BN_is_prime_ex 336and 337.Fn BN_is_prime_fasttest_ex 338respectively. 339.Sh RETURN VALUES 340.Fn BN_generate_prime_ex 341returns 1 on success or 0 on error. 342.Pp 343.Fn BN_is_prime_ex , 344.Fn BN_is_prime_fasttest_ex , 345.Fn BN_is_prime , 346and 347.Fn BN_is_prime_fasttest 348return 0 if the number is composite, 1 if it is prime with an error 349probability of less than 350.Pf 0.25^ Fa nchecks , 351and -1 on error. 352.Pp 353.Fn BN_generate_prime 354returns the prime number on success, 355.Dv NULL 356otherwise. 357.Pp 358.Fn BN_GENCB_new 359returns a pointer to a 360.Vt BN_GENCB 361structure on success, or 362.Dv NULL 363otherwise. 364.Pp 365.Fn BN_GENCB_get_arg 366returns the argument previously associated with a 367.Vt BN_GENCB 368structure. 369.Pp 370Callback functions should return 1 on success or 0 on error. 371.Pp 372The error codes can be obtained by 373.Xr ERR_get_error 3 . 374.Sh SEE ALSO 375.Xr BN_new 3 , 376.Xr ERR_get_error 3 , 377.Xr RAND_bytes 3 378.Sh HISTORY 379.Fn BN_generate_prime 380and 381.Fn BN_is_prime 382first appeared in SSLeay 0.5.1 and had their 383.Fa cb_arg 384argument added in SSLeay 0.9.0. 385These two functions have been available since 386.Ox 2.4 . 387.Pp 388The 389.Fa ret 390argument to 391.Fn BN_generate_prime 392was added in SSLeay 0.9.1 and 393.Ox 2.6 . 394.Pp 395.Fn BN_is_prime_fasttest 396first appeared in OpenSSL 0.9.5 and has been available since 397.Ox 2.7 . 398.Pp 399.Fn BN_generate_prime_ex , 400.Fn BN_is_prime_ex , 401.Fn BN_is_prime_fasttest_ex , 402.Fn BN_GENCB_call , 403.Fn BN_GENCB_set_old , 404and 405.Fn BN_GENCB_set 406first appeared in OpenSSL 0.9.8 and have been available since 407.Ox 4.5 . 408.Pp 409.Fn BN_GENCB_new , 410.Fn BN_GENCB_free , 411and 412.Fn BN_GENCB_get_arg 413first appeared in OpenSSL 1.1.0 and have been available since 414.Ox 6.3 . 415