Botan  2.18.1
Crypto and TLS for C++11
make_prm.cpp
Go to the documentation of this file.
1 /*
2 * Prime Generation
3 * (C) 1999-2007,2018,2019 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/numthry.h>
9 #include <botan/rng.h>
10 #include <botan/internal/bit_ops.h>
11 #include <botan/loadstor.h>
12 #include <botan/reducer.h>
13 #include <botan/internal/primality.h>
14 #include <algorithm>
15 
16 namespace Botan {
17 
18 namespace {
19 
20 class Prime_Sieve final
21  {
22  public:
23  Prime_Sieve(const BigInt& init_value, size_t sieve_size) :
24  m_sieve(std::min(sieve_size, PRIME_TABLE_SIZE))
25  {
26  for(size_t i = 0; i != m_sieve.size(); ++i)
27  m_sieve[i] = static_cast<uint16_t>(init_value % PRIMES[i]);
28  }
29 
30  void step(word increment)
31  {
32  for(size_t i = 0; i != m_sieve.size(); ++i)
33  {
34  m_sieve[i] = (m_sieve[i] + increment) % PRIMES[i];
35  }
36  }
37 
38  bool passes(bool check_2p1 = false) const
39  {
40  for(size_t i = 0; i != m_sieve.size(); ++i)
41  {
42  /*
43  In this case, p is a multiple of PRIMES[i]
44  */
45  if(m_sieve[i] == 0)
46  return false;
47 
48  if(check_2p1)
49  {
50  /*
51  In this case, 2*p+1 will be a multiple of PRIMES[i]
52 
53  So if potentially generating a safe prime, we want to
54  avoid this value because 2*p+1 will certainly not be prime.
55 
56  See "Safe Prime Generation with a Combined Sieve" M. Wiener
57  https://eprint.iacr.org/2003/186.pdf
58  */
59  if(m_sieve[i] == (PRIMES[i] - 1) / 2)
60  return false;
61  }
62  }
63 
64  return true;
65  }
66 
67  private:
68  std::vector<uint16_t> m_sieve;
69  };
70 
71 }
72 
73 
74 /*
75 * Generate a random prime
76 */
78  size_t bits, const BigInt& coprime,
79  size_t equiv, size_t modulo,
80  size_t prob)
81  {
82  if(bits <= 1)
83  {
84  throw Invalid_Argument("random_prime: Can't make a prime of " +
85  std::to_string(bits) + " bits");
86  }
87  if(coprime.is_negative() || (!coprime.is_zero() && coprime.is_even()) || coprime.bits() >= bits)
88  {
89  throw Invalid_Argument("random_prime: invalid coprime");
90  }
91  if(modulo == 0)
92  {
93  throw Invalid_Argument("random_prime: Invalid modulo value");
94  }
95 
96  equiv %= modulo;
97 
98  if(equiv == 0)
99  throw Invalid_Argument("random_prime Invalid value for equiv/modulo");
100 
101  // Handle small values:
102 
103  if(bits <= 16)
104  {
105  if(equiv != 1 || modulo != 2 || coprime != 0)
106  throw Not_Implemented("random_prime equiv/modulo/coprime options not usable for small primes");
107 
108  if(bits == 2)
109  {
110  return ((rng.next_byte() % 2) ? 2 : 3);
111  }
112  else if(bits == 3)
113  {
114  return ((rng.next_byte() % 2) ? 5 : 7);
115  }
116  else if(bits == 4)
117  {
118  return ((rng.next_byte() % 2) ? 11 : 13);
119  }
120  else
121  {
122  for(;;)
123  {
124  // This is slightly biased, but for small primes it does not seem to matter
125  uint8_t b[4];
126  rng.randomize(b, 4);
127  const size_t idx = load_le<uint32_t>(b, 0) % PRIME_TABLE_SIZE;
128  const uint16_t small_prime = PRIMES[idx];
129 
130  if(high_bit(small_prime) == bits)
131  return small_prime;
132  }
133  }
134  }
135 
136  const size_t MAX_ATTEMPTS = 32*1024;
137 
138  const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);
139 
140  while(true)
141  {
142  BigInt p(rng, bits);
143 
144  // Force lowest and two top bits on
145  p.set_bit(bits - 1);
146  p.set_bit(bits - 2);
147  p.set_bit(0);
148 
149  // Force p to be equal to equiv mod modulo
150  p += (modulo - (p % modulo)) + equiv;
151 
152  Prime_Sieve sieve(p, bits);
153 
154  for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt)
155  {
156  p += modulo;
157 
158  sieve.step(modulo);
159 
160  // p can be even if modulo is odd, continue on in that case
161  if(p.is_even() || sieve.passes(true) == false)
162  continue;
163 
164  Modular_Reducer mod_p(p);
165 
166  if(coprime > 1)
167  {
168  /*
169  First do a single M-R iteration to quickly elimate most non-primes,
170  before doing the coprimality check which is expensive
171  */
172  if(is_miller_rabin_probable_prime(p, mod_p, rng, 1) == false)
173  continue;
174 
175  /*
176  * Check if p - 1 and coprime are relatively prime, using gcd.
177  * The gcd computation is const-time
178  */
179  if(gcd(p - 1, coprime) > 1)
180  continue;
181  }
182 
183  if(p.bits() > bits)
184  break;
185 
186  if(is_miller_rabin_probable_prime(p, mod_p, rng, mr_trials) == false)
187  continue;
188 
189  if(prob > 32 && !is_lucas_probable_prime(p, mod_p))
190  continue;
191 
192  return p;
193  }
194  }
195  }
196 
198  RandomNumberGenerator& prime_test_rng,
199  size_t bits,
200  const BigInt& coprime,
201  size_t prob)
202  {
203  if(bits < 512)
204  throw Invalid_Argument("generate_rsa_prime bits too small");
205 
206  /*
207  * The restriction on coprime <= 64 bits is arbitrary but generally speaking
208  * very large RSA public exponents are a bad idea both for performance and due
209  * to attacks on small d.
210  */
211  if(coprime <= 1 || coprime.is_even() || coprime.bits() > 64)
212  throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer");
213 
214  const size_t MAX_ATTEMPTS = 32*1024;
215 
216  const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);
217 
218  while(true)
219  {
220  BigInt p(keygen_rng, bits);
221 
222  // Force high two bits so multiplication always results in expected n bit integer
223  p.set_bit(bits - 1);
224  p.set_bit(bits - 2);
225  p.set_bit(0);
226 
227  const word step = 2;
228 
229  Prime_Sieve sieve(p, bits);
230 
231  for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt)
232  {
233  p += step;
234 
235  sieve.step(step);
236 
237  if(sieve.passes() == false)
238  continue;
239 
240  Modular_Reducer mod_p(p);
241 
242  /*
243  * Do a single primality test first before checking coprimality, since
244  * currently a single Miller-Rabin test is faster than computing gcd,
245  * and this eliminates almost all wasted gcd computations.
246  */
247  if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, 1) == false)
248  continue;
249 
250  /*
251  * Check if p - 1 and coprime are relatively prime.
252  */
253  if(gcd(p - 1, coprime) > 1)
254  continue;
255 
256  if(p.bits() > bits)
257  break;
258 
259  if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, mr_trials) == true)
260  return p;
261  }
262  }
263  }
264 
265 /*
266 * Generate a random safe prime
267 */
269  {
270  if(bits <= 64)
271  throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
272  std::to_string(bits) + " bits");
273 
274  const size_t error_bound = 128;
275 
276  BigInt q, p;
277  for(;;)
278  {
279  /*
280  Generate q == 2 (mod 3), since otherwise [in the case of q == 1 (mod 3)],
281  2*q+1 == 3 (mod 3) and so certainly not prime.
282  */
283  q = random_prime(rng, bits - 1, 0, 2, 3, error_bound);
284  p = (q << 1) + 1;
285 
286  if(is_prime(p, rng, error_bound, true))
287  {
288  return p;
289  }
290  }
291  }
292 
293 }
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:287
bool is_lucas_probable_prime(const BigInt &C, const Modular_Reducer &mod_C)
Definition: primality.cpp:17
bool is_negative() const
Definition: bigint.h:527
const uint16_t PRIMES[]
Definition: primes.cpp:12
BigInt gcd(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:81
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
Definition: primality.cpp:165
virtual void randomize(uint8_t output[], size_t length)=0
size_t bits() const
Definition: bigint.cpp:296
void set_bit(size_t n)
Definition: bigint.h:430
int(* final)(unsigned char *, CTX *)
bool is_zero() const
Definition: bigint.h:421
Definition: bigint.h:1143
uint32_t load_le< uint32_t >(const uint8_t in[], size_t off)
Definition: loadstor.h:198
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:228
bool is_even() const
Definition: bigint.h:403
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:268
size_t high_bit(T n)
Definition: bit_ops.h:55
Definition: alg_id.cpp:13
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo, size_t prob)
Definition: make_prm.cpp:77
bool is_miller_rabin_probable_prime(const BigInt &n, const Modular_Reducer &mod_n, RandomNumberGenerator &rng, size_t test_iterations)
Definition: primality.cpp:143
BigInt generate_rsa_prime(RandomNumberGenerator &keygen_rng, RandomNumberGenerator &prime_test_rng, size_t bits, const BigInt &coprime, size_t prob)
Definition: make_prm.cpp:197