From 778a6d338bf2610d12d814b4a503d2638cfc8d1d Mon Sep 17 00:00:00 2001 From: schwarze <> Date: Sun, 25 Aug 2019 19:24:00 +0000 Subject: 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 and Annie Yousar via OpenSSL commit feac7a1c Jul 25 18:55:16 2018 +0200, still under a free license. OK tb@. --- src/lib/libcrypto/man/BN_generate_prime.3 | 28 ++++++++++++++++++++-------- 1 file changed, 20 insertions(+), 8 deletions(-) (limited to 'src/lib/libcrypto/man/BN_generate_prime.3') 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 .\" Bodo Moeller , and Matt Caswell . @@ -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 -- cgit v1.2.3-55-g6feb