diff options
| -rw-r--r-- | lib/libcrypto/bn/bn.h | 91 | ||||
| -rw-r--r-- | lib/libcrypto/man/BN_generate_prime.3 | 28 |
2 files changed, 93 insertions, 26 deletions
diff --git a/lib/libcrypto/bn/bn.h b/lib/libcrypto/bn/bn.h index cd94e393459..cc1f467523e 100644 --- a/lib/libcrypto/bn/bn.h +++ b/lib/libcrypto/bn/bn.h @@ -1,4 +1,4 @@ -/* $OpenBSD: bn.h,v 1.38 2018/02/20 17:13:14 jsing Exp $ */ +/* $OpenBSD: bn.h,v 1.39 2019/08/25 19:23:59 schwarze Exp $ */ /* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) * All rights reserved. * @@ -308,24 +308,79 @@ int BN_GENCB_call(BN_GENCB *cb, int a, int b); #define BN_prime_checks 0 /* default: select number of iterations based on the size of the number */ -/* number of Miller-Rabin iterations for an error rate of less than 2^-80 - * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook - * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996]; - * original paper: Damgaard, Landrock, Pomerance: Average case error estimates - * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */ -#define BN_prime_checks_for_size(b) ((b) >= 1300 ? 2 : \ - (b) >= 850 ? 3 : \ - (b) >= 650 ? 4 : \ - (b) >= 550 ? 5 : \ - (b) >= 450 ? 6 : \ - (b) >= 400 ? 7 : \ - (b) >= 350 ? 8 : \ - (b) >= 300 ? 9 : \ - (b) >= 250 ? 12 : \ - (b) >= 200 ? 15 : \ - (b) >= 150 ? 18 : \ - /* b >= 100 */ 27) +/* + * BN_prime_checks_for_size() returns the number of Miller-Rabin + * iterations that will be done for checking that a random number + * is probably prime. The error rate for accepting a composite + * number as prime depends on the size of the prime |b|. The error + * rates used are for calculating an RSA key with 2 primes, and so + * the level is what you would expect for a key of double the size + * of the prime. + * + * This table is generated using the algorithm of FIPS PUB 186-4 + * Digital Signature Standard (DSS), section F.1, page 117. + * (https://dx.doi.org/10.6028/NIST.FIPS.186-4) + * + * The following magma script was used to generate the output: + * securitybits:=125; + * k:=1024; + * for t:=1 to 65 do + * for M:=3 to Floor(2*Sqrt(k-1)-1) do + * S:=0; + * // Sum over m + * for m:=3 to M do + * s:=0; + * // Sum over j + * for j:=2 to m do + * s+:=(RealField(32)!2)^-(j+(k-1)/j); + * end for; + * S+:=2^(m-(m-1)*t)*s; + * end for; + * A:=2^(k-2-M*t); + * B:=8*(Pi(RealField(32))^2-6)/3*2^(k-2)*S; + * pkt:=2.00743*Log(2)*k*2^-k*(A+B); + * seclevel:=Floor(-Log(2,pkt)); + * if seclevel ge securitybits then + * printf "k: %5o, security: %o bits (t: %o, M: %o)\n",k,seclevel,t,M; + * break; + * end if; + * end for; + * if seclevel ge securitybits then break; end if; + * end for; + * + * It can be run online at: + * http://magma.maths.usyd.edu.au/calc + * + * And will output: + * k: 1024, security: 129 bits (t: 6, M: 23) + * + * k is the number of bits of the prime, securitybits is the level + * we want to reach. + * + * prime length | RSA key size | # MR tests | security level + * -------------+--------------|------------+--------------- + * (b) >= 6394 | >= 12788 | 3 | 256 bit + * (b) >= 3747 | >= 7494 | 3 | 192 bit + * (b) >= 1345 | >= 2690 | 4 | 128 bit + * (b) >= 1080 | >= 2160 | 5 | 128 bit + * (b) >= 852 | >= 1704 | 5 | 112 bit + * (b) >= 476 | >= 952 | 5 | 80 bit + * (b) >= 400 | >= 800 | 6 | 80 bit + * (b) >= 347 | >= 694 | 7 | 80 bit + * (b) >= 308 | >= 616 | 8 | 80 bit + * (b) >= 55 | >= 110 | 27 | 64 bit + * (b) >= 6 | >= 12 | 34 | 64 bit + */ +#define BN_prime_checks_for_size(b) ((b) >= 3747 ? 3 : \ + (b) >= 1345 ? 4 : \ + (b) >= 476 ? 5 : \ + (b) >= 400 ? 6 : \ + (b) >= 347 ? 7 : \ + (b) >= 308 ? 8 : \ + (b) >= 55 ? 27 : \ + /* b >= 6 */ 34) + #define BN_num_bytes(a) ((BN_num_bits(a)+7)/8) /* Note that BN_abs_is_word didn't work reliably for w == 0 until 0.9.8 */ diff --git a/lib/libcrypto/man/BN_generate_prime.3 b/lib/libcrypto/man/BN_generate_prime.3 index 2369b6f24f1..7db27fd6274 100644 --- a/lib/libcrypto/man/BN_generate_prime.3 +++ b/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 |