summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/bn/bn.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/bn/bn.h')
-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 */