diff options
Diffstat (limited to 'src/lib/math/numbertheory')
| -rw-r--r-- | src/lib/math/numbertheory/make_prm.cpp | 157 | ||||
| -rw-r--r-- | src/lib/math/numbertheory/numthry.cpp | 40 | ||||
| -rw-r--r-- | src/lib/math/numbertheory/numthry.h | 17 |
3 files changed, 173 insertions, 41 deletions
diff --git a/src/lib/math/numbertheory/make_prm.cpp b/src/lib/math/numbertheory/make_prm.cpp index bd0ae8e92..85089c9cb 100644 --- a/src/lib/math/numbertheory/make_prm.cpp +++ b/src/lib/math/numbertheory/make_prm.cpp @@ -12,6 +12,61 @@ namespace Botan { +namespace { + +class Prime_Sieve + { + public: + Prime_Sieve(const BigInt& init_value) : m_sieve(PRIME_TABLE_SIZE) + { + for(size_t i = 0; i != m_sieve.size(); ++i) + m_sieve[i] = static_cast<uint16_t>(init_value % PRIMES[i]); + } + + void step(word increment) + { + for(size_t i = 0; i != m_sieve.size(); ++i) + { + m_sieve[i] = (m_sieve[i] + increment) % PRIMES[i]; + } + } + + bool passes(bool check_2p1 = false) const + { + for(size_t i = 0; i != m_sieve.size(); ++i) + { + /* + In this case, p is a multiple of PRIMES[i] + */ + if(m_sieve[i] == 0) + return false; + + if(check_2p1) + { + /* + In this case, 2*p+1 will be a multiple of PRIMES[i] + + So if potentially generating a safe prime, we want to + avoid this value because 2*p+1 will certainly not be prime. + + See "Safe Prime Generation with a Combined Sieve" M. Wiener + https://eprint.iacr.org/2003/186.pdf + */ + if(m_sieve[i] == (PRIMES[i] - 1) / 2) + return false; + } + } + + return true; + } + + private: + std::vector<uint16_t> m_sieve; + }; + +} + + /* * Generate a random prime */ @@ -64,7 +119,6 @@ BigInt random_prime(RandomNumberGenerator& rng, } } - secure_vector<uint16_t> sieve(PRIME_TABLE_SIZE); const size_t MAX_ATTEMPTS = 32*1024; while(true) @@ -79,8 +133,7 @@ BigInt random_prime(RandomNumberGenerator& rng, // Force p to be equal to equiv mod modulo p += (modulo - (p % modulo)) + equiv; - for(size_t i = 0; i != sieve.size(); ++i) - sieve[i] = static_cast<uint16_t>(p % PRIMES[i]); + Prime_Sieve sieve(p); size_t counter = 0; while(true) @@ -94,46 +147,89 @@ BigInt random_prime(RandomNumberGenerator& rng, p += modulo; - if(p.bits() > bits) - break; + sieve.step(modulo); - // Now that p is updated, update the sieve - for(size_t i = 0; i != sieve.size(); ++i) - { - sieve[i] = (sieve[i] + modulo) % PRIMES[i]; - } + if(sieve.passes(true) == false) + continue; - bool passes_sieve = true; - for(size_t i = 0; passes_sieve && (i != sieve.size()); ++i) + if(coprime > 1) { /* - In this case, p is a multiple of PRIMES[i] + * Check if gcd(p - 1, coprime) != 1 by computing the inverse. The + * gcd algorithm is not constant time, but modular inverse is (for + * odd modulus anyway). This avoids a side channel attack against RSA + * key generation, though RSA keygen should be using generate_rsa_prime. */ - if(sieve[i] == 0) - passes_sieve = false; + if(inverse_mod(p - 1, coprime).is_zero()) + continue; + } - /* - In this case, 2*p+1 will be a multiple of PRIMES[i] + if(p.bits() > bits) + break; - So if generating a safe prime, we want to avoid this value - because 2*p+1 will not be useful. Since the check is cheap to - do and doesn't seem to affect the overall distribution of the - generated primes overmuch it's used in all cases. + if(is_prime(p, rng, prob, true)) + return p; + } + } + } - See "Safe Prime Generation with a Combined Sieve" M. Wiener - https://eprint.iacr.org/2003/186.pdf - */ - if(sieve[i] == (PRIMES[i] - 1) / 2) - passes_sieve = false; +BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng, + RandomNumberGenerator& prime_test_rng, + size_t bits, + const BigInt& coprime, + size_t prob) + { + if(bits < 512) + throw Invalid_Argument("generate_rsa_prime bits too small"); + + if(coprime <= 1 || coprime.is_even()) + throw Invalid_Argument("generate_rsa_prime coprime must be odd positive integer"); + + const size_t MAX_ATTEMPTS = 32*1024; + + while(true) + { + BigInt p(keygen_rng, bits); + + // Force lowest and two top bits on + p.set_bit(bits - 1); + p.set_bit(bits - 2); + p.set_bit(0); + + Prime_Sieve sieve(p); + + const word step = 2; + + size_t counter = 0; + while(true) + { + ++counter; + + if(counter > MAX_ATTEMPTS) + { + break; // don't try forever, choose a new starting point } - if(!passes_sieve) + p += step; + + sieve.step(step); + + if(sieve.passes() == false) continue; - if(coprime > 0 && gcd(p - 1, coprime) != 1) + /* + * Check if gcd(p - 1, coprime) != 1 by computing the inverse. The + * gcd algorithm is not constant time, but modular inverse is (for + * odd modulus anyway). This avoids a side channel attack against RSA + * key generation. + */ + if(inverse_mod(p - 1, coprime).is_zero()) continue; - if(is_prime(p, rng, prob, true)) + if(p.bits() > bits) + break; + + if(is_prime(p, prime_test_rng, prob, true)) return p; } } @@ -156,7 +252,7 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits) Otherwise [q == 1 (mod 3) case], 2*q+1 == 3 (mod 3) and not prime. */ - q = random_prime(rng, bits - 1, 1, 2, 3, 8); + q = random_prime(rng, bits - 1, 0, 2, 3, 8); p = (q << 1) + 1; if(is_prime(p, rng, 128, true)) @@ -165,7 +261,6 @@ BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits) if(is_prime(q, rng, 128, true)) return p; } - } } diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp index 76d7936bc..8cc930175 100644 --- a/src/lib/math/numbertheory/numthry.cpp +++ b/src/lib/math/numbertheory/numthry.cpp @@ -453,22 +453,44 @@ size_t mr_test_iterations(size_t n_bits, size_t prob, bool random) const size_t base = (prob + 2) / 2; // worst case 4^-t error rate /* + * If the candidate prime was maliciously constructed, we can't rely + * on arguments based on p being random. + */ + if(random == false) + return base; + + /* * For randomly chosen numbers we can use the estimates from * http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf * * These values are derived from the inequality for p(k,t) given on * the second page. */ - if(random && prob <= 80) + if(random) { - if(n_bits >= 1536) - return 2; // < 2^-89 - if(n_bits >= 1024) - return 4; // < 2^-89 - if(n_bits >= 512) - return 5; // < 2^-80 - if(n_bits >= 256) - return 11; // < 2^-80 + if(prob <= 80) + { + if(n_bits >= 1536) + return 2; // < 2^-89 + if(n_bits >= 1024) + return 3; // < 2^-89 + if(n_bits >= 512) + return 5; // < 2^-80 + if(n_bits >= 256) + return 11; // < 2^-80 + } + + if(prob <= 128) + { + if(n_bits >= 1536) + return 4; // < 2^-133 + if(n_bits >= 1024) + return 6; // < 2^-133 + if(n_bits >= 512) + return 12; // < 2^-129 + if(n_bits >= 256) + return 28; // < 2^-128 + } } return base; diff --git a/src/lib/math/numbertheory/numthry.h b/src/lib/math/numbertheory/numthry.h index 61da93bcd..7097979bd 100644 --- a/src/lib/math/numbertheory/numthry.h +++ b/src/lib/math/numbertheory/numthry.h @@ -189,7 +189,7 @@ inline bool verify_prime(const BigInt& n, RandomNumberGenerator& rng) /** -* Randomly generate a prime +* Randomly generate a prime suitable for discrete logarithm parameters * @param rng a random number generator * @param bits how large the resulting prime should be in bits * @param coprime a positive integer that (prime - 1) should be coprime to @@ -207,6 +207,21 @@ BigInt BOTAN_PUBLIC_API(2,0) random_prime(RandomNumberGenerator& rng, size_t prob = 128); /** +* Generate a prime suitable for RSA p/q +* @param keygen_rng a random number generator +* @param prime_test_rng a random number generator +* @param bits how large the resulting prime should be in bits (must be >= 512) +* @param coprime a positive integer that (prime - 1) should be coprime to +* @param prob use test so false positive is bounded by 1/2**prob +* @return random prime with the specified criteria +*/ +BigInt BOTAN_PUBLIC_API(2,7) generate_rsa_prime(RandomNumberGenerator& keygen_rng, + RandomNumberGenerator& prime_test_rng, + size_t bits, + const BigInt& coprime, + size_t prob = 128); + +/** * Return a 'safe' prime, of the form p=2*q+1 with q prime * @param rng a random number generator * @param bits is how long the resulting prime should be |