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 <kurt@roeckx.be> and Annie Yousar via OpenSSL commit
 feac7a1c Jul 25 18:55:16 2018 +0200, still under a free license. OK tb@.

---
 src/lib/libcrypto/bn/bn.h | 91 +++++++++++++++++++++++++++++++++++++----------
 1 file changed, 73 insertions(+), 18 deletions(-)

(limited to 'src/lib/libcrypto/bn')

diff --git a/src/lib/libcrypto/bn/bn.h b/src/lib/libcrypto/bn/bn.h
index cd94e39345..cc1f467523 100644
--- a/src/lib/libcrypto/bn/bn.h
+++ b/src/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 */
-- 
cgit v1.2.3-55-g6feb