Major overhaul.

Remove many statements that are no longer true after tb@, in July,
massively improved the algorithms used by these functions
and also did some cleanup of the interface.  Instead, explain
many aspects that were missing.  Also use more descriptive argument
names, drop some redundancy, and improve ordering in various respects.

Feedback and enthusiastic OK from tb@.

1 files changed, 216 insertions, 210 deletions

diff --git a/lib/libcrypto/man/BN_generate_prime.3 b/lib/libcrypto/man/BN_generate_prime.3
index 764ea6f873b..df28d3775c3 100644
--- a/lib/libcrypto/man/BN_generate_prime.3
+++ b/lib/libcrypto/man/BN_generate_prime.3
@@ -1,7 +1,24 @@
-.\" $OpenBSD: BN_generate_prime.3,v 1.19 2020/06/24 18:15:00 jmc Exp $
+.\" $OpenBSD: BN_generate_prime.3,v 1.20 2022/11/24 19:06:38 schwarze Exp $
 .\" full merge up to: OpenSSL f987a4dd Jun 27 10:12:08 2019 +0200
 .\"
-.\" This file was written by Ulf Moeller <ulf@openssl.org>
+.\" This file is a derived work.
+.\" The changes are covered by the following Copyright and license:
+.\"
+.\" Copyright (c) 2022 Ingo Schwarze <schwarze@openbsd.org>
+.\"
+.\" Permission to use, copy, modify, and distribute this software for any
+.\" purpose with or without fee is hereby granted, provided that the above
+.\" copyright notice and this permission notice appear in all copies.
+.\"
+.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+.\"
+.\" The original file was written by Ulf Moeller <ulf@openssl.org>
 .\" Bodo Moeller <bodo@openssl.org>, and Matt Caswell <matt@openssl.org>.
 .\" Copyright (c) 2000, 2003, 2013, 2014, 2018 The OpenSSL Project.
 .\" All rights reserved.
@@ -50,54 +67,56 @@
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 .\" OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd $Mdocdate: June 24 2020 $
+.Dd $Mdocdate: November 24 2022 $
 .Dt BN_GENERATE_PRIME 3
 .Os
 .Sh NAME
-.Nm BN_generate_prime_ex ,
 .Nm BN_is_prime_ex ,
 .Nm BN_is_prime_fasttest_ex ,
+.Nm BN_generate_prime_ex ,
 .Nm BN_GENCB_call ,
 .Nm BN_GENCB_new ,
 .Nm BN_GENCB_free ,
-.Nm BN_GENCB_set_old ,
 .Nm BN_GENCB_set ,
 .Nm BN_GENCB_get_arg ,
+.Nm BN_GENCB_set_old ,
 .Nm BN_generate_prime ,
 .Nm BN_is_prime ,
 .Nm BN_is_prime_fasttest
+.\" Nm BN_prime_checks_for_size is intentionally undocumented
+.\" because it is no longer used by LibreSSL.
 .Nd generate primes and test for primality
 .Sh SYNOPSIS
 .In openssl/bn.h
 .Ft int
-.Fo BN_generate_prime_ex
-.Fa "BIGNUM *ret"
-.Fa "int bits"
-.Fa "int safe"
-.Fa "const BIGNUM *add"
-.Fa "const BIGNUM *rem"
-.Fa "BN_GENCB *cb"
-.Fc
-.Ft int
 .Fo BN_is_prime_ex
-.Fa "const BIGNUM *p"
+.Fa "const BIGNUM *a"
 .Fa "int nchecks"
 .Fa "BN_CTX *ctx"
 .Fa "BN_GENCB *cb"
 .Fc
 .Ft int
 .Fo BN_is_prime_fasttest_ex
-.Fa "const BIGNUM *p"
+.Fa "const BIGNUM *a"
 .Fa "int nchecks"
 .Fa "BN_CTX *ctx"
 .Fa "int do_trial_division"
 .Fa "BN_GENCB *cb"
 .Fc
 .Ft int
+.Fo BN_generate_prime_ex
+.Fa "BIGNUM *ret"
+.Fa "int bits"
+.Fa "int safe"
+.Fa "const BIGNUM *modulus"
+.Fa "const BIGNUM *remainder"
+.Fa "BN_GENCB *cb"
+.Fc
+.Ft int
 .Fo BN_GENCB_call
 .Fa "BN_GENCB *cb"
-.Fa "int a"
-.Fa "int b"
+.Fa "int state_code"
+.Fa "int serial_number"
 .Fc
 .Ft BN_GENCB *
 .Fn BN_GENCB_new void
@@ -106,15 +125,9 @@
 .Fa "BN_GENCB *cb"
 .Fc
 .Ft void
-.Fo BN_GENCB_set_old
-.Fa "BN_GENCB *gencb"
-.Fa "void (*callback)(int, int, void *)"
-.Fa "void *cb_arg"
-.Fc
-.Ft void
 .Fo BN_GENCB_set
-.Fa "BN_GENCB *gencb"
-.Fa "int (*callback)(int, int, BN_GENCB *)"
+.Fa "BN_GENCB *cb"
+.Fa "int (*cb_fp)(int, int, BN_GENCB *)"
 .Fa "void *cb_arg"
 .Fc
 .Ft void *
@@ -124,21 +137,27 @@
 .Pp
 Deprecated:
 .Pp
+.Ft void
+.Fo BN_GENCB_set_old
+.Fa "BN_GENCB *cb"
+.Fa "void (*cb_fp)(int, int, void *)"
+.Fa "void *cb_arg"
+.Fc
 .Ft BIGNUM *
 .Fo BN_generate_prime
 .Fa "BIGNUM *ret"
 .Fa "int num"
 .Fa "int safe"
-.Fa "BIGNUM *add"
-.Fa "BIGNUM *rem"
-.Fa "void (*callback)(int, int, void *)"
+.Fa "BIGNUM *modulus"
+.Fa "BIGNUM *remainder"
+.Fa "void (*cb_fp)(int, int, void *)"
 .Fa "void *cb_arg"
 .Fc
 .Ft int
 .Fo BN_is_prime
 .Fa "const BIGNUM *a"
 .Fa "int checks"
-.Fa "void (*callback)(int, int, void *)"
+.Fa "void (*cb_fp)(int, int, void *)"
 .Fa "BN_CTX *ctx"
 .Fa "void *cb_arg"
 .Fc
@@ -146,22 +165,84 @@ Deprecated:
 .Fo BN_is_prime_fasttest
 .Fa "const BIGNUM *a"
 .Fa "int checks"
-.Fa "void (*callback)(int, int, void *)"
+.Fa "void (*cb_fp)(int, int, void *)"
 .Fa "BN_CTX *ctx"
 .Fa "void *cb_arg"
 .Fa "int do_trial_division"
 .Fc
 .Sh DESCRIPTION
+.Fn BN_is_prime_ex
+and
+.Fn BN_is_prime_fasttest_ex
+test whether the number
+.Fa a
+is prime.
+In LibreSSL, both functions behave identically,
+use the Baillie-Pomerance-Selfridge-Wagstaff algorithm,
+and ignore the
+.Fa checks
+and
+.Fa do_trial_division
+arguments.
+.Pp
+It is unknown whether any composite number exists that the
+Baillie-PSW algorithm misclassifies as a prime.
+Some suspect that there may be infinitely many such numbers,
+but not a single one is currently known.
+It is known that no such number exists below 2\(ha64.
+.Pp
+If
+.Dv NULL
+is passed for the
+.Fa ctx
+argument, these function allocate a
+.Vt BN_CTX
+object internally when they need one and free it before returning.
+Alternatively, to save the overhead of allocating and freeing
+that object for each call, the caller can pre-allocate a
+.Vt BN_CTX
+object and pass it in the
+.Fa ctx
+argument.
+.Pp
 .Fn BN_generate_prime_ex
 generates a pseudo-random prime number of at least bit length
-.Fa bits .
-The returned number is probably prime, but there is a very small
-probability of returning a non-prime number.
-If
+.Fa bits
+and places it in
+.Fa ret .
+Primality of
 .Fa ret
+is tested internally using
+.Fn BN_is_prime_ex .
+Consequently, for
+.Fa bits
+larger than 64, it is theoretically possible
+that this function might place a composite number into
+.Fa ret ;
+the probability of such an event is unknown but very small.
+.Pp
+The prime may have to fulfill additional requirements for use in
+Diffie-Hellman key exchange:
+.Bl -bullet
+.It
+If
+.Fa modulus
 is not
 .Dv NULL ,
-it will be used to store the number.
+a prime is generated that fulfills the condition
+.Fa ret No % Fa modulus No = Fa remainder .
+If the
+.Fa remainder
+argument is
+.Dv NULL ,
+1 is used as the desired remainder.
+.It
+If the
+.Fa safe
+argument is non-zero, a safe prime is generated, that is,
+.Po Fa ret No \- 1 Pc Ns /2
+is also prime.
+.El
 .Pp
 If
 .Fa cb
@@ -170,15 +251,18 @@ is not
 it is used as follows:
 .Bl -bullet
 .It
-.Fn BN_GENCB_call cb 0 i
-is called after generating the i-th potential prime number.
+.Fn BN_GENCB_call cb 0 serial_number
+is called after generating a potential prime number.
 .It
-While the number is being tested for primality,
-.Fn BN_GENCB_call cb 1 j
-is called as described below.
+The
+.Fa state_code
+of 1 is reserved for callbacks during primality testing,
+but LibreSSL performs no such callbacks.
 .It
-When a prime has been found,
-.Fn BN_GENCB_call cb 2 i
+When
+.Fa safe
+is non-zero and a safe prime has been found,
+.Fn BN_GENCB_call cb 2 serial_number
 is called.
 .It
 The callers of
@@ -189,207 +273,129 @@ with other values as described in their respective manual pages; see
 .Sx SEE ALSO .
 .El
 .Pp
-The prime may have to fulfill additional requirements for use in
-Diffie-Hellman key exchange:
-.Pp
-If
-.Fa add
-is not
-.Dv NULL ,
-the prime will fulfill the condition p %
-.Fa add
-==
-.Fa rem
-(p %
-.Fa add
-== 1 if
-.Fa rem
-==
-.Dv NULL )
-in order to suit a given generator.
-.Pp
-If
-.Fa safe
-is true, it will be a safe prime (i.e. a prime p so that (p-1)/2
-is also prime).
-.Pp
-.Fn BN_is_prime_ex
-and
-.Fn BN_is_prime_fasttest_ex
-test if the number
-.Fa p
-is prime.
-The following tests are performed until one of them shows that
-.Fa p
-is composite; if
-.Fa p
-passes all these tests, it is considered prime.
+In all cases, the
+.Fa serial_number
+is the number of candidates that have already been discarded
+for not being prime; that is,
+.Fa serial_number
+is 0 for the first candidate
+and then incremented whenever a new candidate is generated.
 .Pp
-.Fn BN_is_prime_fasttest_ex ,
-when called with
-.Fa do_trial_division
-== 1, first attempts trial division by a number of small primes;
-if no divisors are found by this test and
+.Fn BN_GENCB_call
+calls the callback function held in
 .Fa cb
-is not
-.Dv NULL ,
-.Sy BN_GENCB_call(cb, 1, -1)
-is called.
-If
-.Fa do_trial_division
-== 0, this test is skipped.
-.Pp
-Both
-.Fn BN_is_prime_ex
-and
-.Fn BN_is_prime_fasttest_ex
-perform a Miller-Rabin probabilistic primality test with
-.Fa nchecks
-iterations.
+and passes the
+.Fa state_code
+and the
+.Fa serial_number
+as arguments.
 If
-.Fa nchecks
-==
-.Dv BN_prime_checks ,
-a number of iterations is used that yields a false positive rate
-of at most 2\(ha-64 for random input.
-The error rate depends on the size of the prime
-and goes down for bigger primes.
-The rate is 2\(ha-80 starting at 308 bits, 2\(ha-112 at 852 bits,
-2\(ha-128 at 1080 bits, 2\(ha-192 at 3747 bits
-and 2\(ha-256 at 6394 bits.
+.Fa cb
+is
+.Dv NULL
+or does not contain a callback function, no action occurs.
 .Pp
-When the source of the prime is not random or not trusted, the
-number of checks needs to be much higher to reach the same level
-of assurance: It should equal half of the targeted security level
-in bits (rounded up to the next integer if necessary).
-For instance, to reach the 128-bit security level,
-.Fa nchecks
-should be set to 64.
+.Fn BN_GENCB_new
+allocates a new
+.Vt BN_GENCB
+object.
 .Pp
+.Fn BN_GENCB_free
+frees
+.Fa cb .
 If
 .Fa cb
-is not
+is
 .Dv NULL ,
-.Fa BN_GENCB_call cb 1 j
-is called after the j-th iteration (j = 0, 1, ...).
-.Fa ctx
-is a pre-allocated
-.Vt BN_CTX
-(to save the overhead of allocating and freeing the structure in a
-loop), or
-.Dv NULL .
+no action occurs.
 .Pp
-.Fn BN_GENCB_call
-calls the callback function held in the
-.Vt BN_GENCB
-structure and passes the ints
-.Fa a
-and
-.Fa b
-as arguments.
-There are two types of
-.Vt BN_GENCB
-structures that are supported: "new" style and "old" style.
-New programs should prefer the "new" style, whilst the "old" style is
-provided for backwards compatibility purposes.
+.Fn BN_GENCB_set
+initialises
+.Fa cb
+to use the callback function pointer
+.Fa cb_fp
+and the additional callback argument
+.Fa cb_arg .
 .Pp
-A
-.Vt BN_GENCB
-structure should be created through a call to
-.Fn BN_GENCB_new
-and freed through a call to
-.Fn BN_GENCB_free .
+The deprecated function
+.Fn BN_GENCB_set_old
+initialises
+.Fa cb
+to use the old-style callback function pointer
+.Fa cb_fp
+and the additional callback argument
+.Fa cb_arg .
 .Pp
-For "new" style callbacks a
-.Vt BN_GENCB
-structure should be initialised with a call to
-.Fn BN_GENCB_set ,
-where
-.Fa gencb
-is a
-.Vt BN_GENCB * ,
-.Fa callback
-is of type
-.Vt int (*callback)(int, int, BN_GENCB *)
-and
-.Fa cb_arg
-is a
-.Vt void * .
-"Old" style callbacks are the same except they are initialised with a
-call to
+.Fn BN_generate_prime
+is a deprecated wrapper around
 .Fn BN_GENCB_set_old
 and
-.Fa callback
-is of type
-.Vt void (*callback)(int, int, void *) .
-.Pp
-A callback is invoked through a call to
-.Fn BN_GENCB_call .
-This will check the type of the callback and will invoke
-.Fn callback a b gencb
-for new style callbacks or
-.Fn callback a b cb_arg
-for old style.
-.Pp
-It is possible to obtain the argument associated with a
-.Vt BN_GENCB
-structure (set via a call to
-.Fn BN_GENCB_set
-or
-.Fn BN_GENCB_set_old )
-using
-.Fn BN_GENCB_get_arg .
+.Fn BN_generate_prime_ex .
+In contrast to
+.Fn BN_generate_prime_ex ,
+if
+.Dv NULL
+is passed for the
+.Fa ret
+argument, a new
+.Vt BIGNUM
+object is allocated and returned.
 .Pp
-.Fn BN_generate_prime
-(deprecated) works in the same way as
-.Fn BN_generate_prime_ex
-but expects an old style callback function directly in the
-.Fa callback
-parameter, and an argument to pass to it in the
-.Fa cb_arg .
-Similarly
+Similarly,
 .Fn BN_is_prime
 and
 .Fn BN_is_prime_fasttest
-are deprecated and can be compared to
-.Fn BN_is_prime_ex
+are deprecated wrappers around
+.Fn BN_GENCB_set_old
 and
-.Fn BN_is_prime_fasttest_ex
-respectively.
+.Fn BN_is_prime_ex .
 .Sh RETURN VALUES
-.Fn BN_generate_prime_ex
-returns 1 on success or 0 on error.
-.Pp
 .Fn BN_is_prime_ex ,
 .Fn BN_is_prime_fasttest_ex ,
 .Fn BN_is_prime ,
 and
 .Fn BN_is_prime_fasttest
-return 0 if the number is composite, 1 if it is prime with an error
-probability of less than
-.Pf 0.25^ Fa nchecks ,
-and -1 on error.
+return 0 if the number is composite, 1 if it is prime with a very small
+error probability, or \-1 on error.
 .Pp
-.Fn BN_generate_prime
-returns the prime number on success,
+.Fn BN_generate_prime_ex
+returns 1 on success or 0 on error.
+.Pp
+.Fn BN_GENCB_call
+returns 1 on success, including when
+.Fa cb
+is
 .Dv NULL
-otherwise.
+or does not contain a callback function,
+or 0 on error.
 .Pp
 .Fn BN_GENCB_new
-returns a pointer to a
+returns a pointer to the newly allocated
 .Vt BN_GENCB
-structure on success, or
+object or
 .Dv NULL
-otherwise.
+if memory allocation fails.
+.Pp
+The callback functions pointed to by the
+.Fa cb_fp
+arguments are supposed to return 1 on success or 0 on error.
 .Pp
 .Fn BN_GENCB_get_arg
-returns the argument previously associated with a
-.Vt BN_GENCB
-structure.
+returns the
+.Fa cb_arg
+pointer that was previously stored in
+.Fa cb
+using
+.Fn BN_GENCB_set
+or
+.Fn BN_GENCB_set_old .
 .Pp
-Callback functions should return 1 on success or 0 on error.
+.Fn BN_generate_prime
+returns the prime number on success or
+.Dv NULL
+on failure.
 .Pp
-The error codes can be obtained by
+In some cases, error codes can be obtained by
 .Xr ERR_get_error 3 .
 .Sh SEE ALSO
 .Xr BN_new 3 ,