1.\" $OpenBSD: BN_generate_prime.3,v 1.25 2023/12/29 19:12:46 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: December 29 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 should not be used outside of libcrypto. 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 151and use the Baillie-Pomerance-Selfridge-Wagstaff algorithm 152combined with 153.Fa checks 154Miller-Rabin rounds. 155The 156.Fa do_trial_division 157argument is ignored. 158.Pp 159It is unknown whether any composite number exists that the 160Baillie-PSW algorithm misclassifies as a prime. 161Some suspect that there may be infinitely many such numbers, 162but not a single one is currently known. 163It is known that no such number exists below 2\(ha64. 164.Pp 165In order to reduce the likelihood of a composite number 166passing the primality tests 167.Fn BN_is_prime_fasttest_ex 168and 169.Fn BN_is_prime_ex , 170a number of rounds of the probabilistic Miller-Rabin test is performed. 171If 172.Fa checks 173is positive, it is used as the number of rounds; 174if it is zero or the special value 175.Dv BN_prime_checks , 176a suitable number of rounds is calculated from the bit length of 177.Fa a . 178.Pp 179If 180.Dv NULL 181is passed for the 182.Fa ctx 183argument, these function allocate a 184.Vt BN_CTX 185object internally when they need one and free it before returning. 186Alternatively, to save the overhead of allocating and freeing 187that object for each call, the caller can pre-allocate a 188.Vt BN_CTX 189object and pass it in the 190.Fa ctx 191argument. 192.Pp 193.Fn BN_generate_prime_ex 194generates a pseudo-random prime number of at least bit length 195.Fa bits 196and places it in 197.Fa ret . 198Primality of 199.Fa ret 200is tested internally using 201.Fn BN_is_prime_ex . 202Consequently, for 203.Fa bits 204larger than 64, it is theoretically possible 205that this function might place a composite number into 206.Fa ret ; 207the probability of such an event is unknown but very small. 208.Pp 209The prime may have to fulfill additional requirements for use in 210Diffie-Hellman key exchange: 211.Bl -bullet 212.It 213If 214.Fa modulus 215is not 216.Dv NULL , 217a prime is generated that fulfills the condition 218.Fa ret No % Fa modulus No = Fa remainder . 219If the 220.Fa remainder 221argument is 222.Dv NULL , 2231 is used as the desired remainder. 224.It 225If the 226.Fa safe 227argument is non-zero, a safe prime is generated, that is, 228.Po Fa ret No \- 1 Pc Ns /2 229is also prime. 230.El 231.Pp 232If 233.Fa cb 234is not 235.Dv NULL , 236it is used as follows: 237.Bl -bullet 238.It 239.Fn BN_GENCB_call cb 0 serial_number 240is called after generating a potential prime number. 241.It 242The 243.Fa state_code 244of 1 is reserved for callbacks during primality testing, 245but LibreSSL performs no such callbacks. 246.It 247When 248.Fa safe 249is non-zero and a safe prime has been found, 250.Fn BN_GENCB_call cb 2 serial_number 251is called. 252.It 253The callers of 254.Fn BN_generate_prime_ex 255may call 256.Fn BN_GENCB_call 257with other values as described in their respective manual pages; see 258.Sx SEE ALSO . 259.El 260.Pp 261In all cases, the 262.Fa serial_number 263is the number of candidates that have already been discarded 264for not being prime; that is, 265.Fa serial_number 266is 0 for the first candidate 267and then incremented whenever a new candidate is generated. 268.Pp 269.Fn BN_GENCB_call 270calls the callback function held in 271.Fa cb 272and passes the 273.Fa state_code 274and the 275.Fa serial_number 276as arguments. 277If 278.Fa cb 279is 280.Dv NULL 281or does not contain a callback function, no action occurs. 282.Pp 283.Fn BN_GENCB_new 284allocates a new 285.Vt BN_GENCB 286object. 287.Pp 288.Fn BN_GENCB_free 289frees 290.Fa cb . 291If 292.Fa cb 293is 294.Dv NULL , 295no action occurs. 296.Pp 297.Fn BN_GENCB_set 298initialises 299.Fa cb 300to use the callback function pointer 301.Fa cb_fp 302and the additional callback argument 303.Fa cb_arg . 304.Pp 305The deprecated function 306.Fn BN_GENCB_set_old 307initialises 308.Fa cb 309to use the old-style callback function pointer 310.Fa cb_fp 311and the additional callback argument 312.Fa cb_arg . 313.Sh RETURN VALUES 314.Fn BN_is_prime_ex 315and 316.Fn BN_is_prime_fasttest_ex 317return 0 if the number is composite, 1 if it is prime with a very small 318error probability, or \-1 on error. 319.Pp 320.Fn BN_generate_prime_ex 321returns 1 on success or 0 on error. 322.Pp 323.Fn BN_GENCB_call 324returns 1 on success, including when 325.Fa cb 326is 327.Dv NULL 328or does not contain a callback function, 329or 0 on error. 330.Pp 331.Fn BN_GENCB_new 332returns a pointer to the newly allocated 333.Vt BN_GENCB 334object or 335.Dv NULL 336if memory allocation fails. 337.Pp 338The callback functions pointed to by the 339.Fa cb_fp 340arguments are supposed to return 1 on success or 0 on error. 341.Pp 342.Fn BN_GENCB_get_arg 343returns the 344.Fa cb_arg 345pointer that was previously stored in 346.Fa cb 347using 348.Fn BN_GENCB_set 349or 350.Fn BN_GENCB_set_old . 351.Pp 352In some cases, error codes can be obtained by 353.Xr ERR_get_error 3 . 354.Sh SEE ALSO 355.Xr BN_new 3 , 356.Xr DH_generate_parameters 3 , 357.Xr DSA_generate_parameters_ex 3 , 358.Xr RSA_generate_key 3 359.Sh HISTORY 360.Fn BN_generate_prime_ex , 361.Fn BN_is_prime_ex , 362.Fn BN_is_prime_fasttest_ex , 363.Fn BN_GENCB_call , 364.Fn BN_GENCB_set_old , 365and 366.Fn BN_GENCB_set 367first appeared in OpenSSL 0.9.8 and have been available since 368.Ox 4.5 . 369.Pp 370.Fn BN_GENCB_new , 371.Fn BN_GENCB_free , 372and 373.Fn BN_GENCB_get_arg 374first appeared in OpenSSL 1.1.0 and have been available since 375.Ox 6.3 . 376