Revision control
Copy as Markdown
Other Tools
/*
* Prime Generation
* (C) 1999-2007,2018,2019 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
#include <botan/numthry.h>
#include <botan/rng.h>
#include <botan/internal/bit_ops.h>
#include <botan/loadstor.h>
#include <botan/reducer.h>
#include <botan/internal/primality.h>
#include <algorithm>
namespace Botan {
namespace {
class Prime_Sieve final
{
public:
Prime_Sieve(const BigInt& init_value, size_t sieve_size) :
m_sieve(std::min(sieve_size, 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
*/
if(m_sieve[i] == (PRIMES[i] - 1) / 2)
return false;
}
}
return true;
}
private:
std::vector<uint16_t> m_sieve;
};
}
/*
* Generate a random prime
*/
BigInt random_prime(RandomNumberGenerator& rng,
size_t bits, const BigInt& coprime,
size_t equiv, size_t modulo,
size_t prob)
{
if(bits <= 1)
{
throw Invalid_Argument("random_prime: Can't make a prime of " +
std::to_string(bits) + " bits");
}
if(coprime.is_negative() || (!coprime.is_zero() && coprime.is_even()) || coprime.bits() >= bits)
{
throw Invalid_Argument("random_prime: invalid coprime");
}
if(modulo == 0)
{
throw Invalid_Argument("random_prime: Invalid modulo value");
}
equiv %= modulo;
if(equiv == 0)
throw Invalid_Argument("random_prime Invalid value for equiv/modulo");
// Handle small values:
if(bits <= 16)
{
if(equiv != 1 || modulo != 2 || coprime != 0)
throw Not_Implemented("random_prime equiv/modulo/coprime options not usable for small primes");
if(bits == 2)
{
return ((rng.next_byte() % 2) ? 2 : 3);
}
else if(bits == 3)
{
return ((rng.next_byte() % 2) ? 5 : 7);
}
else if(bits == 4)
{
return ((rng.next_byte() % 2) ? 11 : 13);
}
else
{
for(;;)
{
// This is slightly biased, but for small primes it does not seem to matter
uint8_t b[4];
rng.randomize(b, 4);
const size_t idx = load_le<uint32_t>(b, 0) % PRIME_TABLE_SIZE;
const uint16_t small_prime = PRIMES[idx];
if(high_bit(small_prime) == bits)
return small_prime;
}
}
}
const size_t MAX_ATTEMPTS = 32*1024;
const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);
while(true)
{
BigInt p(rng, bits);
// Force lowest and two top bits on
p.set_bit(bits - 1);
p.set_bit(bits - 2);
p.set_bit(0);
// Force p to be equal to equiv mod modulo
p += (modulo - (p % modulo)) + equiv;
Prime_Sieve sieve(p, bits);
for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt)
{
p += modulo;
sieve.step(modulo);
// p can be even if modulo is odd, continue on in that case
if(p.is_even() || sieve.passes(true) == false)
continue;
Modular_Reducer mod_p(p);
if(coprime > 1)
{
/*
First do a single M-R iteration to quickly elimate most non-primes,
before doing the coprimality check which is expensive
*/
if(is_miller_rabin_probable_prime(p, mod_p, rng, 1) == false)
continue;
/*
* Check if p - 1 and coprime are relatively prime, using gcd.
* The gcd computation is const-time
*/
if(gcd(p - 1, coprime) > 1)
continue;
}
if(p.bits() > bits)
break;
if(is_miller_rabin_probable_prime(p, mod_p, rng, mr_trials) == false)
continue;
if(prob > 32 && !is_lucas_probable_prime(p, mod_p))
continue;
return p;
}
}
}
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");
/*
* The restriction on coprime <= 64 bits is arbitrary but generally speaking
* very large RSA public exponents are a bad idea both for performance and due
* to attacks on small d.
*/
if(coprime <= 1 || coprime.is_even() || coprime.bits() > 64)
throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer");
const size_t MAX_ATTEMPTS = 32*1024;
const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);
while(true)
{
BigInt p(keygen_rng, bits);
// Force high two bits so multiplication always results in expected n bit integer
p.set_bit(bits - 1);
p.set_bit(bits - 2);
p.set_bit(0);
const word step = 2;
Prime_Sieve sieve(p, bits);
for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt)
{
p += step;
sieve.step(step);
if(sieve.passes() == false)
continue;
Modular_Reducer mod_p(p);
/*
* Do a single primality test first before checking coprimality, since
* currently a single Miller-Rabin test is faster than computing gcd,
* and this eliminates almost all wasted gcd computations.
*/
if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, 1) == false)
continue;
/*
* Check if p - 1 and coprime are relatively prime.
*/
if(gcd(p - 1, coprime) > 1)
continue;
if(p.bits() > bits)
break;
if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, mr_trials) == true)
return p;
}
}
}
/*
* Generate a random safe prime
*/
BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
{
if(bits <= 64)
throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
std::to_string(bits) + " bits");
const size_t error_bound = 128;
BigInt q, p;
for(;;)
{
/*
Generate q == 2 (mod 3), since otherwise [in the case of q == 1 (mod 3)],
2*q+1 == 3 (mod 3) and so certainly not prime.
*/
q = random_prime(rng, bits - 1, 0, 2, 3, error_bound);
p = (q << 1) + 1;
if(is_prime(p, rng, error_bound, true))
{
return p;
}
}
}
}