8#include <botan/numthry.h>
10#include <botan/internal/bit_ops.h>
11#include <botan/loadstor.h>
12#include <botan/reducer.h>
13#include <botan/internal/primality.h>
20class Prime_Sieve
final
23 Prime_Sieve(
const BigInt& init_value,
size_t sieve_size) :
26 for(
size_t i = 0; i != m_sieve.size(); ++i)
27 m_sieve[i] =
static_cast<uint16_t
>(init_value %
PRIMES[i]);
30 void step(word increment)
32 for(
size_t i = 0; i != m_sieve.size(); ++i)
34 m_sieve[i] = (m_sieve[i] + increment) %
PRIMES[i];
38 bool passes(
bool check_2p1 =
false)
const
40 for(
size_t i = 0; i != m_sieve.size(); ++i)
59 if(m_sieve[i] == (
PRIMES[i] - 1) / 2)
68 std::vector<uint16_t> m_sieve;
78 size_t bits,
const BigInt& coprime,
79 size_t equiv,
size_t modulo,
105 if(equiv != 1 || modulo != 2 || coprime != 0)
106 throw Not_Implemented(
"random_prime equiv/modulo/coprime options not usable for small primes");
118 return ((rng.
next_byte() % 2) ? 11 : 13);
128 const uint16_t small_prime =
PRIMES[idx];
136 const size_t MAX_ATTEMPTS = 32*1024;
150 p += (modulo - (p % modulo)) + equiv;
152 Prime_Sieve sieve(p, bits);
154 for(
size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt)
161 if(p.
is_even() || sieve.passes(
true) ==
false)
179 if(
gcd(p - 1, coprime) > 1)
211 if(coprime <= 1 || coprime.
is_even() || coprime.
bits() > 64)
212 throw Invalid_Argument(
"generate_rsa_prime coprime must be small odd positive integer");
214 const size_t MAX_ATTEMPTS = 32*1024;
220 BigInt p(keygen_rng, bits);
229 Prime_Sieve sieve(p, bits);
231 for(
size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt)
237 if(sieve.passes() ==
false)
253 if(
gcd(p - 1, coprime) > 1)
274 const size_t error_bound = 128;
286 if(
is_prime(p, rng, error_bound,
true))
virtual void randomize(uint8_t output[], size_t length)=0
int(* final)(unsigned char *, CTX *)
std::string to_string(const BER_Object &obj)
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo, size_t prob)
uint32_t load_le< uint32_t >(const uint8_t in[], size_t off)
const size_t PRIME_TABLE_SIZE
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
bool is_miller_rabin_probable_prime(const BigInt &n, const Modular_Reducer &mod_n, RandomNumberGenerator &rng, size_t test_iterations)
BigInt generate_rsa_prime(RandomNumberGenerator &keygen_rng, RandomNumberGenerator &prime_test_rng, size_t bits, const BigInt &coprime, size_t prob)
BigInt gcd(const BigInt &a, const BigInt &b)
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
bool is_lucas_probable_prime(const BigInt &C, const Modular_Reducer &mod_C)