1.\" $OpenBSD: BN_generate_prime.3,v 1.22 2023/04/30 20:17:59 tb 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: April 30 2023 $ 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_prime_checks_for_size is intentionally undocumented 84.\" because it is no longer used by LibreSSL. 85.Nd generate primes and test for primality 86.Sh SYNOPSIS 87.In openssl/bn.h 88.Ft int 89.Fo BN_is_prime_ex 90.Fa "const BIGNUM *a" 91.Fa "int nchecks" 92.Fa "BN_CTX *ctx" 93.Fa "BN_GENCB *cb" 94.Fc 95.Ft int 96.Fo BN_is_prime_fasttest_ex 97.Fa "const BIGNUM *a" 98.Fa "int nchecks" 99.Fa "BN_CTX *ctx" 100.Fa "int do_trial_division" 101.Fa "BN_GENCB *cb" 102.Fc 103.Ft int 104.Fo BN_generate_prime_ex 105.Fa "BIGNUM *ret" 106.Fa "int bits" 107.Fa "int safe" 108.Fa "const BIGNUM *modulus" 109.Fa "const BIGNUM *remainder" 110.Fa "BN_GENCB *cb" 111.Fc 112.Ft int 113.Fo BN_GENCB_call 114.Fa "BN_GENCB *cb" 115.Fa "int state_code" 116.Fa "int serial_number" 117.Fc 118.Ft BN_GENCB * 119.Fn BN_GENCB_new void 120.Ft void 121.Fo BN_GENCB_free 122.Fa "BN_GENCB *cb" 123.Fc 124.Ft void 125.Fo BN_GENCB_set 126.Fa "BN_GENCB *cb" 127.Fa "int (*cb_fp)(int, int, BN_GENCB *)" 128.Fa "void *cb_arg" 129.Fc 130.Ft void * 131.Fo BN_GENCB_get_arg 132.Fa "BN_GENCB *cb" 133.Fc 134.Pp 135Deprecated: 136.Pp 137.Ft void 138.Fo BN_GENCB_set_old 139.Fa "BN_GENCB *cb" 140.Fa "void (*cb_fp)(int, int, void *)" 141.Fa "void *cb_arg" 142.Fc 143.Sh DESCRIPTION 144.Fn BN_is_prime_ex 145and 146.Fn BN_is_prime_fasttest_ex 147test whether the number 148.Fa a 149is prime. 150In LibreSSL, both functions behave identically, 151use the Baillie-Pomerance-Selfridge-Wagstaff algorithm, 152and ignore the 153.Fa checks 154and 155.Fa do_trial_division 156arguments. 157.Pp 158It is unknown whether any composite number exists that the 159Baillie-PSW algorithm misclassifies as a prime. 160Some suspect that there may be infinitely many such numbers, 161but not a single one is currently known. 162It is known that no such number exists below 2\(ha64. 163.Pp 164If 165.Dv NULL 166is passed for the 167.Fa ctx 168argument, these function allocate a 169.Vt BN_CTX 170object internally when they need one and free it before returning. 171Alternatively, to save the overhead of allocating and freeing 172that object for each call, the caller can pre-allocate a 173.Vt BN_CTX 174object and pass it in the 175.Fa ctx 176argument. 177.Pp 178.Fn BN_generate_prime_ex 179generates a pseudo-random prime number of at least bit length 180.Fa bits 181and places it in 182.Fa ret . 183Primality of 184.Fa ret 185is tested internally using 186.Fn BN_is_prime_ex . 187Consequently, for 188.Fa bits 189larger than 64, it is theoretically possible 190that this function might place a composite number into 191.Fa ret ; 192the probability of such an event is unknown but very small. 193.Pp 194The prime may have to fulfill additional requirements for use in 195Diffie-Hellman key exchange: 196.Bl -bullet 197.It 198If 199.Fa modulus 200is not 201.Dv NULL , 202a prime is generated that fulfills the condition 203.Fa ret No % Fa modulus No = Fa remainder . 204If the 205.Fa remainder 206argument is 207.Dv NULL , 2081 is used as the desired remainder. 209.It 210If the 211.Fa safe 212argument is non-zero, a safe prime is generated, that is, 213.Po Fa ret No \- 1 Pc Ns /2 214is also prime. 215.El 216.Pp 217If 218.Fa cb 219is not 220.Dv NULL , 221it is used as follows: 222.Bl -bullet 223.It 224.Fn BN_GENCB_call cb 0 serial_number 225is called after generating a potential prime number. 226.It 227The 228.Fa state_code 229of 1 is reserved for callbacks during primality testing, 230but LibreSSL performs no such callbacks. 231.It 232When 233.Fa safe 234is non-zero and a safe prime has been found, 235.Fn BN_GENCB_call cb 2 serial_number 236is called. 237.It 238The callers of 239.Fn BN_generate_prime_ex 240may call 241.Fn BN_GENCB_call 242with other values as described in their respective manual pages; see 243.Sx SEE ALSO . 244.El 245.Pp 246In all cases, the 247.Fa serial_number 248is the number of candidates that have already been discarded 249for not being prime; that is, 250.Fa serial_number 251is 0 for the first candidate 252and then incremented whenever a new candidate is generated. 253.Pp 254.Fn BN_GENCB_call 255calls the callback function held in 256.Fa cb 257and passes the 258.Fa state_code 259and the 260.Fa serial_number 261as arguments. 262If 263.Fa cb 264is 265.Dv NULL 266or does not contain a callback function, no action occurs. 267.Pp 268.Fn BN_GENCB_new 269allocates a new 270.Vt BN_GENCB 271object. 272.Pp 273.Fn BN_GENCB_free 274frees 275.Fa cb . 276If 277.Fa cb 278is 279.Dv NULL , 280no action occurs. 281.Pp 282.Fn BN_GENCB_set 283initialises 284.Fa cb 285to use the callback function pointer 286.Fa cb_fp 287and the additional callback argument 288.Fa cb_arg . 289.Pp 290The deprecated function 291.Fn BN_GENCB_set_old 292initialises 293.Fa cb 294to use the old-style callback function pointer 295.Fa cb_fp 296and the additional callback argument 297.Fa cb_arg . 298.Sh RETURN VALUES 299.Fn BN_is_prime_ex 300and 301.Fn BN_is_prime_fasttest_ex 302return 0 if the number is composite, 1 if it is prime with a very small 303error probability, or \-1 on error. 304.Pp 305.Fn BN_generate_prime_ex 306returns 1 on success or 0 on error. 307.Pp 308.Fn BN_GENCB_call 309returns 1 on success, including when 310.Fa cb 311is 312.Dv NULL 313or does not contain a callback function, 314or 0 on error. 315.Pp 316.Fn BN_GENCB_new 317returns a pointer to the newly allocated 318.Vt BN_GENCB 319object or 320.Dv NULL 321if memory allocation fails. 322.Pp 323The callback functions pointed to by the 324.Fa cb_fp 325arguments are supposed to return 1 on success or 0 on error. 326.Pp 327.Fn BN_GENCB_get_arg 328returns the 329.Fa cb_arg 330pointer that was previously stored in 331.Fa cb 332using 333.Fn BN_GENCB_set 334or 335.Fn BN_GENCB_set_old . 336.Pp 337In some cases, error codes can be obtained by 338.Xr ERR_get_error 3 . 339.Sh SEE ALSO 340.Xr BN_new 3 , 341.Xr DH_generate_parameters 3 , 342.Xr DSA_generate_parameters 3 , 343.Xr RSA_generate_key 3 344.Sh HISTORY 345.Fn BN_generate_prime_ex , 346.Fn BN_is_prime_ex , 347.Fn BN_is_prime_fasttest_ex , 348.Fn BN_GENCB_call , 349.Fn BN_GENCB_set_old , 350and 351.Fn BN_GENCB_set 352first appeared in OpenSSL 0.9.8 and have been available since 353.Ox 4.5 . 354.Pp 355.Fn BN_GENCB_new , 356.Fn BN_GENCB_free , 357and 358.Fn BN_GENCB_get_arg 359first appeared in OpenSSL 1.1.0 and have been available since 360.Ox 6.3 . 361