diff options
| -rw-r--r-- | CHANGES | 7 | ||||
| -rw-r--r-- | crypto/bn/bn.h | 87 | ||||
| -rw-r--r-- | doc/crypto/BN_generate_prime.pod | 12 |
3 files changed, 87 insertions, 19 deletions
@@ -9,6 +9,13 @@ Changes between 1.0.2o and 1.0.2p [xx XXX xxxx] + *) 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. + [Kurt Roeckx, Annie Yousar] + *) Increase the number of Miller-Rabin rounds for DSA key generating to 64. [Kurt Roeckx] diff --git a/crypto/bn/bn.h b/crypto/bn/bn.h index 633d1b1f60..c056bba5f0 100644 --- a/crypto/bn/bn.h +++ b/crypto/bn/bn.h @@ -375,25 +375,76 @@ int BN_GENCB_call(BN_GENCB *cb, int a, int b); * 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) + * 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) >= 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) + +# 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) diff --git a/doc/crypto/BN_generate_prime.pod b/doc/crypto/BN_generate_prime.pod index bf1b5308ad..0079f17a57 100644 --- a/doc/crypto/BN_generate_prime.pod +++ b/doc/crypto/BN_generate_prime.pod @@ -90,7 +90,17 @@ If B<do_trial_division == 0>, this test is skipped. Both BN_is_prime_ex() and BN_is_prime_fasttest_ex() perform a Miller-Rabin probabilistic primality test with B<nchecks> iterations. If B<nchecks == BN_prime_checks>, a number of iterations is used that -yields a false positive rate of at most 2^-80 for random input. +yields a false positive rate of at most 2^-64 for random input. +The error rate depends on the size of the prime and goes down for bigger primes. +The rate is 2^-80 starting at 308 bits, 2^-112 at 852 bit, 2^-128 at 1080 bits, +2^-192 at 3747 bit and 2^-256 at 6394 bit. + +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, B<nchecks> should be set to +64. If B<cb> is not B<NULL>, B<BN_GENCB_call(cb, 1, j)> is called after the j-th iteration (j = 0, 1, ...). B<ctx> is a |