summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn
diff options
context:
space:
mode:
authorschwarze <>2019-08-25 19:24:00 +0000
committerschwarze <>2019-08-25 19:24:00 +0000
commit778a6d338bf2610d12d814b4a503d2638cfc8d1d (patch)
treeb5109bcc1c452d104f90693aee6a22d0e945d314 /src/lib/libcrypto/bn
parent533a7ff91759c413fd387c34db7eef7bfcad50eb (diff)
downloadopenbsd-778a6d338bf2610d12d814b4a503d2638cfc8d1d.tar.gz
openbsd-778a6d338bf2610d12d814b4a503d2638cfc8d1d.tar.bz2
openbsd-778a6d338bf2610d12d814b4a503d2638cfc8d1d.zip
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@.
Diffstat (limited to 'src/lib/libcrypto/bn')
-rw-r--r--src/lib/libcrypto/bn/bn.h91
1 files changed, 73 insertions, 18 deletions
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 @@
1/* $OpenBSD: bn.h,v 1.38 2018/02/20 17:13:14 jsing Exp $ */ 1/* $OpenBSD: bn.h,v 1.39 2019/08/25 19:23:59 schwarze Exp $ */
2/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com) 2/* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com)
3 * All rights reserved. 3 * All rights reserved.
4 * 4 *
@@ -308,24 +308,79 @@ int BN_GENCB_call(BN_GENCB *cb, int a, int b);
308#define BN_prime_checks 0 /* default: select number of iterations 308#define BN_prime_checks 0 /* default: select number of iterations
309 based on the size of the number */ 309 based on the size of the number */
310 310
311/* number of Miller-Rabin iterations for an error rate of less than 2^-80 311/*
312 * for random 'b'-bit input, b >= 100 (taken from table 4.4 in the Handbook 312 * BN_prime_checks_for_size() returns the number of Miller-Rabin
313 * of Applied Cryptography [Menezes, van Oorschot, Vanstone; CRC Press 1996]; 313 * iterations that will be done for checking that a random number
314 * original paper: Damgaard, Landrock, Pomerance: Average case error estimates 314 * is probably prime. The error rate for accepting a composite
315 * for the strong probable prime test. -- Math. Comp. 61 (1993) 177-194) */ 315 * number as prime depends on the size of the prime |b|. The error
316#define BN_prime_checks_for_size(b) ((b) >= 1300 ? 2 : \ 316 * rates used are for calculating an RSA key with 2 primes, and so
317 (b) >= 850 ? 3 : \ 317 * the level is what you would expect for a key of double the size
318 (b) >= 650 ? 4 : \ 318 * of the prime.
319 (b) >= 550 ? 5 : \ 319 *
320 (b) >= 450 ? 6 : \ 320 * This table is generated using the algorithm of FIPS PUB 186-4
321 (b) >= 400 ? 7 : \ 321 * Digital Signature Standard (DSS), section F.1, page 117.
322 (b) >= 350 ? 8 : \ 322 * (https://dx.doi.org/10.6028/NIST.FIPS.186-4)
323 (b) >= 300 ? 9 : \ 323 *
324 (b) >= 250 ? 12 : \ 324 * The following magma script was used to generate the output:
325 (b) >= 200 ? 15 : \ 325 * securitybits:=125;
326 (b) >= 150 ? 18 : \ 326 * k:=1024;
327 /* b >= 100 */ 27) 327 * for t:=1 to 65 do
328 * for M:=3 to Floor(2*Sqrt(k-1)-1) do
329 * S:=0;
330 * // Sum over m
331 * for m:=3 to M do
332 * s:=0;
333 * // Sum over j
334 * for j:=2 to m do
335 * s+:=(RealField(32)!2)^-(j+(k-1)/j);
336 * end for;
337 * S+:=2^(m-(m-1)*t)*s;
338 * end for;
339 * A:=2^(k-2-M*t);
340 * B:=8*(Pi(RealField(32))^2-6)/3*2^(k-2)*S;
341 * pkt:=2.00743*Log(2)*k*2^-k*(A+B);
342 * seclevel:=Floor(-Log(2,pkt));
343 * if seclevel ge securitybits then
344 * printf "k: %5o, security: %o bits (t: %o, M: %o)\n",k,seclevel,t,M;
345 * break;
346 * end if;
347 * end for;
348 * if seclevel ge securitybits then break; end if;
349 * end for;
350 *
351 * It can be run online at:
352 * http://magma.maths.usyd.edu.au/calc
353 *
354 * And will output:
355 * k: 1024, security: 129 bits (t: 6, M: 23)
356 *
357 * k is the number of bits of the prime, securitybits is the level
358 * we want to reach.
359 *
360 * prime length | RSA key size | # MR tests | security level
361 * -------------+--------------|------------+---------------
362 * (b) >= 6394 | >= 12788 | 3 | 256 bit
363 * (b) >= 3747 | >= 7494 | 3 | 192 bit
364 * (b) >= 1345 | >= 2690 | 4 | 128 bit
365 * (b) >= 1080 | >= 2160 | 5 | 128 bit
366 * (b) >= 852 | >= 1704 | 5 | 112 bit
367 * (b) >= 476 | >= 952 | 5 | 80 bit
368 * (b) >= 400 | >= 800 | 6 | 80 bit
369 * (b) >= 347 | >= 694 | 7 | 80 bit
370 * (b) >= 308 | >= 616 | 8 | 80 bit
371 * (b) >= 55 | >= 110 | 27 | 64 bit
372 * (b) >= 6 | >= 12 | 34 | 64 bit
373 */
328 374
375#define BN_prime_checks_for_size(b) ((b) >= 3747 ? 3 : \
376 (b) >= 1345 ? 4 : \
377 (b) >= 476 ? 5 : \
378 (b) >= 400 ? 6 : \
379 (b) >= 347 ? 7 : \
380 (b) >= 308 ? 8 : \
381 (b) >= 55 ? 27 : \
382 /* b >= 6 */ 34)
383
329#define BN_num_bytes(a) ((BN_num_bits(a)+7)/8) 384#define BN_num_bytes(a) ((BN_num_bits(a)+7)/8)
330 385
331/* Note that BN_abs_is_word didn't work reliably for w == 0 until 0.9.8 */ 386/* Note that BN_abs_is_word didn't work reliably for w == 0 until 0.9.8 */