diff options
Diffstat (limited to 'src/lib/libcrypto/bn/bn.h')
-rw-r--r-- | src/lib/libcrypto/bn/bn.h | 91 |
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 */ |