1.\" $OpenBSD: BN_generate_prime.3,v 1.20 2022/11/24 19:06:38 schwarze Exp $ 2.\" full merge up to: OpenSSL f987a4dd Jun 27 10:12:08 2019 +0200 3.\" 4.\" This file is a derived work. 5.\" The changes are covered by the following Copyright and license: 6.\" 7.\" Copyright (c) 2022 Ingo Schwarze <schwarze@openbsd.org> 8.\" 9.\" Permission to use, copy, modify, and distribute this software for any 10.\" purpose with or without fee is hereby granted, provided that the above 11.\" copyright notice and this permission notice appear in all copies. 12.\" 13.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 14.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 15.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 16.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 17.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 18.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 19.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 20.\" 21.\" The original file was written by Ulf Moeller <ulf@openssl.org> 22.\" Bodo Moeller <bodo@openssl.org>, and Matt Caswell <matt@openssl.org>. 23.\" Copyright (c) 2000, 2003, 2013, 2014, 2018 The OpenSSL Project. 24.\" All rights reserved. 25.\" 26.\" Redistribution and use in source and binary forms, with or without 27.\" modification, are permitted provided that the following conditions 28.\" are met: 29.\" 30.\" 1. Redistributions of source code must retain the above copyright 31.\" notice, this list of conditions and the following disclaimer. 32.\" 33.\" 2. Redistributions in binary form must reproduce the above copyright 34.\" notice, this list of conditions and the following disclaimer in 35.\" the documentation and/or other materials provided with the 36.\" distribution. 37.\" 38.\" 3. All advertising materials mentioning features or use of this 39.\" software must display the following acknowledgment: 40.\" "This product includes software developed by the OpenSSL Project 41.\" for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 42.\" 43.\" 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 44.\" endorse or promote products derived from this software without 45.\" prior written permission. For written permission, please contact 46.\" openssl-core@openssl.org. 47.\" 48.\" 5. Products derived from this software may not be called "OpenSSL" 49.\" nor may "OpenSSL" appear in their names without prior written 50.\" permission of the OpenSSL Project. 51.\" 52.\" 6. Redistributions of any form whatsoever must retain the following 53.\" acknowledgment: 54.\" "This product includes software developed by the OpenSSL Project 55.\" for use in the OpenSSL Toolkit (http://www.openssl.org/)" 56.\" 57.\" THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 58.\" EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 59.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 60.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 61.\" ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 62.\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 63.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 64.\" LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 65.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 66.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 67.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 68.\" OF THE POSSIBILITY OF SUCH DAMAGE. 69.\" 70.Dd $Mdocdate: November 24 2022 $ 71.Dt BN_GENERATE_PRIME 3 72.Os 73.Sh NAME 74.Nm BN_is_prime_ex , 75.Nm BN_is_prime_fasttest_ex , 76.Nm BN_generate_prime_ex , 77.Nm BN_GENCB_call , 78.Nm BN_GENCB_new , 79.Nm BN_GENCB_free , 80.Nm BN_GENCB_set , 81.Nm BN_GENCB_get_arg , 82.Nm BN_GENCB_set_old , 83.Nm BN_generate_prime , 84.Nm BN_is_prime , 85.Nm BN_is_prime_fasttest 86.\" Nm BN_prime_checks_for_size is intentionally undocumented 87.\" because it is no longer used by LibreSSL. 88.Nd generate primes and test for primality 89.Sh SYNOPSIS 90.In openssl/bn.h 91.Ft int 92.Fo BN_is_prime_ex 93.Fa "const BIGNUM *a" 94.Fa "int nchecks" 95.Fa "BN_CTX *ctx" 96.Fa "BN_GENCB *cb" 97.Fc 98.Ft int 99.Fo BN_is_prime_fasttest_ex 100.Fa "const BIGNUM *a" 101.Fa "int nchecks" 102.Fa "BN_CTX *ctx" 103.Fa "int do_trial_division" 104.Fa "BN_GENCB *cb" 105.Fc 106.Ft int 107.Fo BN_generate_prime_ex 108.Fa "BIGNUM *ret" 109.Fa "int bits" 110.Fa "int safe" 111.Fa "const BIGNUM *modulus" 112.Fa "const BIGNUM *remainder" 113.Fa "BN_GENCB *cb" 114.Fc 115.Ft int 116.Fo BN_GENCB_call 117.Fa "BN_GENCB *cb" 118.Fa "int state_code" 119.Fa "int serial_number" 120.Fc 121.Ft BN_GENCB * 122.Fn BN_GENCB_new void 123.Ft void 124.Fo BN_GENCB_free 125.Fa "BN_GENCB *cb" 126.Fc 127.Ft void 128.Fo BN_GENCB_set 129.Fa "BN_GENCB *cb" 130.Fa "int (*cb_fp)(int, int, BN_GENCB *)" 131.Fa "void *cb_arg" 132.Fc 133.Ft void * 134.Fo BN_GENCB_get_arg 135.Fa "BN_GENCB *cb" 136.Fc 137.Pp 138Deprecated: 139.Pp 140.Ft void 141.Fo BN_GENCB_set_old 142.Fa "BN_GENCB *cb" 143.Fa "void (*cb_fp)(int, int, void *)" 144.Fa "void *cb_arg" 145.Fc 146.Ft BIGNUM * 147.Fo BN_generate_prime 148.Fa "BIGNUM *ret" 149.Fa "int num" 150.Fa "int safe" 151.Fa "BIGNUM *modulus" 152.Fa "BIGNUM *remainder" 153.Fa "void (*cb_fp)(int, int, void *)" 154.Fa "void *cb_arg" 155.Fc 156.Ft int 157.Fo BN_is_prime 158.Fa "const BIGNUM *a" 159.Fa "int checks" 160.Fa "void (*cb_fp)(int, int, void *)" 161.Fa "BN_CTX *ctx" 162.Fa "void *cb_arg" 163.Fc 164.Ft int 165.Fo BN_is_prime_fasttest 166.Fa "const BIGNUM *a" 167.Fa "int checks" 168.Fa "void (*cb_fp)(int, int, void *)" 169.Fa "BN_CTX *ctx" 170.Fa "void *cb_arg" 171.Fa "int do_trial_division" 172.Fc 173.Sh DESCRIPTION 174.Fn BN_is_prime_ex 175and 176.Fn BN_is_prime_fasttest_ex 177test whether the number 178.Fa a 179is prime. 180In LibreSSL, both functions behave identically, 181use the Baillie-Pomerance-Selfridge-Wagstaff algorithm, 182and ignore the 183.Fa checks 184and 185.Fa do_trial_division 186arguments. 187.Pp 188It is unknown whether any composite number exists that the 189Baillie-PSW algorithm misclassifies as a prime. 190Some suspect that there may be infinitely many such numbers, 191but not a single one is currently known. 192It is known that no such number exists below 2\(ha64. 193.Pp 194If 195.Dv NULL 196is passed for the 197.Fa ctx 198argument, these function allocate a 199.Vt BN_CTX 200object internally when they need one and free it before returning. 201Alternatively, to save the overhead of allocating and freeing 202that object for each call, the caller can pre-allocate a 203.Vt BN_CTX 204object and pass it in the 205.Fa ctx 206argument. 207.Pp 208.Fn BN_generate_prime_ex 209generates a pseudo-random prime number of at least bit length 210.Fa bits 211and places it in 212.Fa ret . 213Primality of 214.Fa ret 215is tested internally using 216.Fn BN_is_prime_ex . 217Consequently, for 218.Fa bits 219larger than 64, it is theoretically possible 220that this function might place a composite number into 221.Fa ret ; 222the probability of such an event is unknown but very small. 223.Pp 224The prime may have to fulfill additional requirements for use in 225Diffie-Hellman key exchange: 226.Bl -bullet 227.It 228If 229.Fa modulus 230is not 231.Dv NULL , 232a prime is generated that fulfills the condition 233.Fa ret No % Fa modulus No = Fa remainder . 234If the 235.Fa remainder 236argument is 237.Dv NULL , 2381 is used as the desired remainder. 239.It 240If the 241.Fa safe 242argument is non-zero, a safe prime is generated, that is, 243.Po Fa ret No \- 1 Pc Ns /2 244is also prime. 245.El 246.Pp 247If 248.Fa cb 249is not 250.Dv NULL , 251it is used as follows: 252.Bl -bullet 253.It 254.Fn BN_GENCB_call cb 0 serial_number 255is called after generating a potential prime number. 256.It 257The 258.Fa state_code 259of 1 is reserved for callbacks during primality testing, 260but LibreSSL performs no such callbacks. 261.It 262When 263.Fa safe 264is non-zero and a safe prime has been found, 265.Fn BN_GENCB_call cb 2 serial_number 266is called. 267.It 268The callers of 269.Fn BN_generate_prime_ex 270may call 271.Fn BN_GENCB_call 272with other values as described in their respective manual pages; see 273.Sx SEE ALSO . 274.El 275.Pp 276In all cases, the 277.Fa serial_number 278is the number of candidates that have already been discarded 279for not being prime; that is, 280.Fa serial_number 281is 0 for the first candidate 282and then incremented whenever a new candidate is generated. 283.Pp 284.Fn BN_GENCB_call 285calls the callback function held in 286.Fa cb 287and passes the 288.Fa state_code 289and the 290.Fa serial_number 291as arguments. 292If 293.Fa cb 294is 295.Dv NULL 296or does not contain a callback function, no action occurs. 297.Pp 298.Fn BN_GENCB_new 299allocates a new 300.Vt BN_GENCB 301object. 302.Pp 303.Fn BN_GENCB_free 304frees 305.Fa cb . 306If 307.Fa cb 308is 309.Dv NULL , 310no action occurs. 311.Pp 312.Fn BN_GENCB_set 313initialises 314.Fa cb 315to use the callback function pointer 316.Fa cb_fp 317and the additional callback argument 318.Fa cb_arg . 319.Pp 320The deprecated function 321.Fn BN_GENCB_set_old 322initialises 323.Fa cb 324to use the old-style callback function pointer 325.Fa cb_fp 326and the additional callback argument 327.Fa cb_arg . 328.Pp 329.Fn BN_generate_prime 330is a deprecated wrapper around 331.Fn BN_GENCB_set_old 332and 333.Fn BN_generate_prime_ex . 334In contrast to 335.Fn BN_generate_prime_ex , 336if 337.Dv NULL 338is passed for the 339.Fa ret 340argument, a new 341.Vt BIGNUM 342object is allocated and returned. 343.Pp 344Similarly, 345.Fn BN_is_prime 346and 347.Fn BN_is_prime_fasttest 348are deprecated wrappers around 349.Fn BN_GENCB_set_old 350and 351.Fn BN_is_prime_ex . 352.Sh RETURN VALUES 353.Fn BN_is_prime_ex , 354.Fn BN_is_prime_fasttest_ex , 355.Fn BN_is_prime , 356and 357.Fn BN_is_prime_fasttest 358return 0 if the number is composite, 1 if it is prime with a very small 359error probability, or \-1 on error. 360.Pp 361.Fn BN_generate_prime_ex 362returns 1 on success or 0 on error. 363.Pp 364.Fn BN_GENCB_call 365returns 1 on success, including when 366.Fa cb 367is 368.Dv NULL 369or does not contain a callback function, 370or 0 on error. 371.Pp 372.Fn BN_GENCB_new 373returns a pointer to the newly allocated 374.Vt BN_GENCB 375object or 376.Dv NULL 377if memory allocation fails. 378.Pp 379The callback functions pointed to by the 380.Fa cb_fp 381arguments are supposed to return 1 on success or 0 on error. 382.Pp 383.Fn BN_GENCB_get_arg 384returns the 385.Fa cb_arg 386pointer that was previously stored in 387.Fa cb 388using 389.Fn BN_GENCB_set 390or 391.Fn BN_GENCB_set_old . 392.Pp 393.Fn BN_generate_prime 394returns the prime number on success or 395.Dv NULL 396on failure. 397.Pp 398In some cases, error codes can be obtained by 399.Xr ERR_get_error 3 . 400.Sh SEE ALSO 401.Xr BN_new 3 , 402.Xr DH_generate_parameters 3 , 403.Xr DSA_generate_parameters 3 , 404.Xr RSA_generate_key 3 405.Sh HISTORY 406.Fn BN_generate_prime 407and 408.Fn BN_is_prime 409first appeared in SSLeay 0.5.1 and had their 410.Fa cb_arg 411argument added in SSLeay 0.9.0. 412These two functions have been available since 413.Ox 2.4 . 414.Pp 415The 416.Fa ret 417argument to 418.Fn BN_generate_prime 419was added in SSLeay 0.9.1 and 420.Ox 2.6 . 421.Pp 422.Fn BN_is_prime_fasttest 423first appeared in OpenSSL 0.9.5 and has been available since 424.Ox 2.7 . 425.Pp 426.Fn BN_generate_prime_ex , 427.Fn BN_is_prime_ex , 428.Fn BN_is_prime_fasttest_ex , 429.Fn BN_GENCB_call , 430.Fn BN_GENCB_set_old , 431and 432.Fn BN_GENCB_set 433first appeared in OpenSSL 0.9.8 and have been available since 434.Ox 4.5 . 435.Pp 436.Fn BN_GENCB_new , 437.Fn BN_GENCB_free , 438and 439.Fn BN_GENCB_get_arg 440first appeared in OpenSSL 1.1.0 and have been available since 441.Ox 6.3 . 442