diff options
| -rw-r--r-- | lib/libcrypto/man/BN_generate_prime.3 | 426 |
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 , |