Change generating and checking of primes so that the error rate of

not being prime depends on the intended use based on the size of
the input.  For larger primes this will result in more rounds of
Miller-Rabin.  The maximal error rate for primes with more than
1080 bits is lowered to 2^-128.
Patch from Kurt Roeckx <kurt@roeckx.be> and Annie Yousar
via OpenSSL commit feac7a1c Jul 25 18:55:16 2018 +0200,
still under a free license.
OK tb@.

1 files changed, 20 insertions, 8 deletions

diff --git a/src/lib/libcrypto/man/BN_generate_prime.3 b/src/lib/libcrypto/man/BN_generate_prime.3
index 2369b6f24f..7db27fd627 100644
--- a/src/lib/libcrypto/man/BN_generate_prime.3
+++ b/src/lib/libcrypto/man/BN_generate_prime.3
@@ -1,6 +1,5 @@
-.\" $OpenBSD: BN_generate_prime.3,v 1.17 2019/06/10 14:58:48 schwarze Exp $
-.\" full merge up to: OpenSSL b3696a55 Sep 2 09:35:50 2017 -0400
-.\" selective merge up to: OpenSSL df75c2bf Dec 9 01:02:36 2018 +0100
+.\" $OpenBSD: BN_generate_prime.3,v 1.18 2019/08/25 19:24:00 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>
 .\" Bodo Moeller <bodo@openssl.org>, and Matt Caswell <matt@openssl.org>.
@@ -51,7 +50,7 @@
 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 .\" OF THE POSSIBILITY OF SUCH DAMAGE.
 .\"
-.Dd $Mdocdate: June 10 2019 $
+.Dd $Mdocdate: August 25 2019 $
 .Dt BN_GENERATE_PRIME 3
 .Os
 .Sh NAME
@@ -156,6 +155,8 @@ Deprecated:
 .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 ret
 is not
@@ -212,8 +213,6 @@ If
 is true, it will be a safe prime (i.e. a prime p so that (p-1)/2
 is also prime).
 .Pp
-The prime number generation has a negligible error probability.
-.Pp
 .Fn BN_is_prime_ex
 and
 .Fn BN_is_prime_fasttest_ex
@@ -251,8 +250,21 @@ If
 .Fa nchecks
 ==
 .Dv BN_prime_checks ,
-a number of iterations is used that yields a false positive rate of at
-most 2^-80 for random input.
+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.
+.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.
 .Pp
 If
 .Fa cb