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