/* Copyright (C) 1995-1998 Eric Young ([email protected]) * All rights reserved. * * This package is an SSL implementation written * by Eric Young ([email protected]). * The implementation was written so as to conform with Netscapes SSL. * * This library is free for commercial and non-commercial use as long as * the following conditions are aheared to. The following conditions * apply to all code found in this distribution, be it the RC4, RSA, * lhash, DES, etc., code; not just the SSL code. The SSL documentation * included with this distribution is covered by the same copyright terms * except that the holder is Tim Hudson ([email protected]). * * Copyright remains Eric Young's, and as such any Copyright notices in * the code are not to be removed. * If this package is used in a product, Eric Young should be given attribution * as the author of the parts of the library used. * This can be in the form of a textual message at program startup or * in documentation (online or textual) provided with the package. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software * must display the following acknowledgement: * "This product includes cryptographic software written by * Eric Young ([email protected])" * The word 'cryptographic' can be left out if the rouines from the library * being used are not cryptographic related :-). * 4. If you include any Windows specific code (or a derivative thereof) from * the apps directory (application code) you must include an acknowledgement: * "This product includes software written by Tim Hudson ([email protected])" * * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * The licence and distribution terms for any publically available version or * derivative of this code cannot be changed. i.e. this code cannot simply be * copied and put under another distribution licence * [including the GNU Public Licence.] */ /* ==================================================================== * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in * the documentation and/or other materials provided with the * distribution. * * 3. All advertising materials mentioning features or use of this * software must display the following acknowledgment: * "This product includes software developed by the OpenSSL Project * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" * * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to * endorse or promote products derived from this software without * prior written permission. For written permission, please contact * [email protected]. * * 5. Products derived from this software may not be called "OpenSSL" * nor may "OpenSSL" appear in their names without prior written * permission of the OpenSSL Project. * * 6. Redistributions of any form whatsoever must retain the following * acknowledgment: * "This product includes software developed by the OpenSSL Project * for use in the OpenSSL Toolkit (http://www.openssl.org/)" * * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED * OF THE POSSIBILITY OF SUCH DAMAGE. * ==================================================================== * * This product includes cryptographic software written by Eric Young * ([email protected]). This product includes software written by Tim * Hudson ([email protected]). */ #include <openssl/bn.h> #include <openssl/err.h> #include <openssl/mem.h> #include "internal.h" #include "../../internal.h" // kPrimes contains the first 1024 primes. static const uint16_t kPrimes[] = …; // BN_prime_checks_for_size returns the number of Miller-Rabin iterations // necessary for generating a 'bits'-bit candidate prime. // // // This table is generated using the algorithm of FIPS PUB 186-4 // Digital Signature Standard (DSS), section F.1, page 117. // (https://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 static int BN_prime_checks_for_size(int bits) { … } // num_trial_division_primes returns the number of primes to try with trial // division before using more expensive checks. For larger numbers, the value // of excluding a candidate with trial division is larger. static size_t num_trial_division_primes(const BIGNUM *n) { … } // BN_PRIME_CHECKS_BLINDED is the iteration count for blinding the constant-time // primality test. See |BN_primality_test| for details. This number is selected // so that, for a candidate N-bit RSA prime, picking |BN_PRIME_CHECKS_BLINDED| // random N-bit numbers will have at least |BN_prime_checks_for_size(N)| values // in range with high probability. // // The following Python script computes the blinding factor needed for the // corresponding iteration count. /* import math # We choose candidate RSA primes between sqrt(2)/2 * 2^N and 2^N and select # witnesses by generating random N-bit numbers. Thus the probability of # selecting one in range is at least sqrt(2)/2. p = math.sqrt(2) / 2 # Target around 2^-8 probability of the blinding being insufficient given that # key generation is a one-time, noisy operation. epsilon = 2**-8 def choose(a, b): r = 1 for i in xrange(b): r *= a - i r /= (i + 1) return r def failure_rate(min_uniform, iterations): """ Returns the probability that, for |iterations| candidate witnesses, fewer than |min_uniform| of them will be uniform. """ prob = 0.0 for i in xrange(min_uniform): prob += (choose(iterations, i) * p**i * (1-p)**(iterations - i)) return prob for min_uniform in (3, 4, 5, 6, 8, 13, 19, 28): # Find the smallest number of iterations under the target failure rate. iterations = min_uniform while True: prob = failure_rate(min_uniform, iterations) if prob < epsilon: print min_uniform, iterations, prob break iterations += 1 Output: 3 9 0.00368894873911 4 11 0.00363319494662 5 13 0.00336215573898 6 15 0.00300145783158 8 19 0.00225214119331 13 27 0.00385610026955 19 38 0.0021410539126 28 52 0.00325405801769 16 iterations suffices for 400-bit primes and larger (6 uniform samples needed), which is already well below the minimum acceptable key size for RSA. */ #define BN_PRIME_CHECKS_BLINDED … static int probable_prime(BIGNUM *rnd, int bits); static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); static int probable_prime_dh_safe(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx); BN_GENCB *BN_GENCB_new(void) { … } void BN_GENCB_free(BN_GENCB *callback) { … } void BN_GENCB_set(BN_GENCB *callback, int (*f)(int event, int n, struct bn_gencb_st *), void *arg) { … } int BN_GENCB_call(BN_GENCB *callback, int event, int n) { … } void *BN_GENCB_get_arg(const BN_GENCB *callback) { … } int BN_generate_prime_ex(BIGNUM *ret, int bits, int safe, const BIGNUM *add, const BIGNUM *rem, BN_GENCB *cb) { … } static int bn_trial_division(uint16_t *out, const BIGNUM *bn) { … } int bn_odd_number_is_obviously_composite(const BIGNUM *bn) { … } int bn_miller_rabin_init(BN_MILLER_RABIN *miller_rabin, const BN_MONT_CTX *mont, BN_CTX *ctx) { … } int bn_miller_rabin_iteration(const BN_MILLER_RABIN *miller_rabin, int *out_is_possibly_prime, const BIGNUM *b, const BN_MONT_CTX *mont, BN_CTX *ctx) { … } int BN_primality_test(int *out_is_probably_prime, const BIGNUM *w, int checks, BN_CTX *ctx, int do_trial_division, BN_GENCB *cb) { … } int BN_is_prime_ex(const BIGNUM *candidate, int checks, BN_CTX *ctx, BN_GENCB *cb) { … } int BN_is_prime_fasttest_ex(const BIGNUM *a, int checks, BN_CTX *ctx, int do_trial_division, BN_GENCB *cb) { … } int BN_enhanced_miller_rabin_primality_test( enum bn_primality_result_t *out_result, const BIGNUM *w, int checks, BN_CTX *ctx, BN_GENCB *cb) { … } static int probable_prime(BIGNUM *rnd, int bits) { … } static int probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx) { … } static int probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, const BIGNUM *rem, BN_CTX *ctx) { … }
Codebase Browser
chromium