Botan  2.9.0
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 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 <algorithm>
12 
13 namespace Botan {
14 
15 namespace {
16 
17 class Prime_Sieve final
18  {
19  public:
20  Prime_Sieve(const BigInt& init_value, size_t sieve_size) :
21  m_sieve(std::min(sieve_size, PRIME_TABLE_SIZE))
22  {
23  for(size_t i = 0; i != m_sieve.size(); ++i)
24  m_sieve[i] = static_cast<uint16_t>(init_value % PRIMES[i]);
25  }
26 
27  void step(word increment)
28  {
29  for(size_t i = 0; i != m_sieve.size(); ++i)
30  {
31  m_sieve[i] = (m_sieve[i] + increment) % PRIMES[i];
32  }
33  }
34 
35  bool passes(bool check_2p1 = false) const
36  {
37  for(size_t i = 0; i != m_sieve.size(); ++i)
38  {
39  /*
40  In this case, p is a multiple of PRIMES[i]
41  */
42  if(m_sieve[i] == 0)
43  return false;
44 
45  if(check_2p1)
46  {
47  /*
48  In this case, 2*p+1 will be a multiple of PRIMES[i]
49 
50  So if potentially generating a safe prime, we want to
51  avoid this value because 2*p+1 will certainly not be prime.
52 
53  See "Safe Prime Generation with a Combined Sieve" M. Wiener
54  https://eprint.iacr.org/2003/186.pdf
55  */
56  if(m_sieve[i] == (PRIMES[i] - 1) / 2)
57  return false;
58  }
59  }
60 
61  return true;
62  }
63 
64  private:
65  std::vector<uint16_t> m_sieve;
66  };
67 
68 }
69 
70 
71 /*
72 * Generate a random prime
73 */
75  size_t bits, const BigInt& coprime,
76  size_t equiv, size_t modulo,
77  size_t prob)
78  {
79  if(coprime.is_negative())
80  {
81  throw Invalid_Argument("random_prime: coprime must be >= 0");
82  }
83  if(modulo == 0)
84  {
85  throw Invalid_Argument("random_prime: Invalid modulo value");
86  }
87 
88  equiv %= modulo;
89 
90  if(equiv == 0)
91  throw Invalid_Argument("random_prime Invalid value for equiv/modulo");
92 
93  // Handle small values:
94  if(bits <= 1)
95  {
96  throw Invalid_Argument("random_prime: Can't make a prime of " +
97  std::to_string(bits) + " bits");
98  }
99  else if(bits == 2)
100  {
101  return ((rng.next_byte() % 2) ? 2 : 3);
102  }
103  else if(bits == 3)
104  {
105  return ((rng.next_byte() % 2) ? 5 : 7);
106  }
107  else if(bits == 4)
108  {
109  return ((rng.next_byte() % 2) ? 11 : 13);
110  }
111  else if(bits <= 16)
112  {
113  for(;;)
114  {
115  size_t idx = make_uint16(rng.next_byte(), rng.next_byte()) % PRIME_TABLE_SIZE;
116  uint16_t small_prime = PRIMES[idx];
117 
118  if(high_bit(small_prime) == bits)
119  return small_prime;
120  }
121  }
122 
123  const size_t MAX_ATTEMPTS = 32*1024;
124 
125  while(true)
126  {
127  BigInt p(rng, bits);
128 
129  // Force lowest and two top bits on
130  p.set_bit(bits - 1);
131  p.set_bit(bits - 2);
132  p.set_bit(0);
133 
134  // Force p to be equal to equiv mod modulo
135  p += (modulo - (p % modulo)) + equiv;
136 
137  Prime_Sieve sieve(p, bits);
138 
139  size_t counter = 0;
140  while(true)
141  {
142  ++counter;
143 
144  if(counter > MAX_ATTEMPTS)
145  {
146  break; // don't try forever, choose a new starting point
147  }
148 
149  p += modulo;
150 
151  sieve.step(modulo);
152 
153  if(sieve.passes(true) == false)
154  continue;
155 
156  if(coprime > 1)
157  {
158  /*
159  * Check if gcd(p - 1, coprime) != 1 by computing the inverse. The
160  * gcd algorithm is not constant time, but modular inverse is (for
161  * odd modulus anyway). This avoids a side channel attack against RSA
162  * key generation, though RSA keygen should be using generate_rsa_prime.
163  */
164  if(inverse_mod(p - 1, coprime).is_zero())
165  continue;
166  }
167 
168  if(p.bits() > bits)
169  break;
170 
171  if(is_prime(p, rng, prob, true))
172  return p;
173  }
174  }
175  }
176 
178  RandomNumberGenerator& prime_test_rng,
179  size_t bits,
180  const BigInt& coprime,
181  size_t prob)
182  {
183  if(bits < 512)
184  throw Invalid_Argument("generate_rsa_prime bits too small");
185 
186  /*
187  * The restriction on coprime <= 64 bits is arbitrary but generally speaking
188  * very large RSA public exponents are a bad idea both for performance and due
189  * to attacks on small d.
190  */
191  if(coprime <= 1 || coprime.is_even() || coprime.bits() > 64)
192  throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer");
193 
194  const size_t MAX_ATTEMPTS = 32*1024;
195 
196  while(true)
197  {
198  BigInt p(keygen_rng, bits);
199 
200  // Force lowest and two top bits on
201  p.set_bit(bits - 1);
202  p.set_bit(bits - 2);
203  p.set_bit(0);
204 
205  Prime_Sieve sieve(p, bits);
206 
207  const word step = 2;
208 
209  size_t counter = 0;
210  while(true)
211  {
212  ++counter;
213 
214  if(counter > MAX_ATTEMPTS)
215  {
216  break; // don't try forever, choose a new starting point
217  }
218 
219  p += step;
220 
221  sieve.step(step);
222 
223  if(sieve.passes() == false)
224  continue;
225 
226  /*
227  * Check if p - 1 and coprime are relatively prime by computing the inverse.
228  *
229  * We avoid gcd here because that algorithm is not constant time.
230  * Modular inverse is (for odd modulus anyway).
231  *
232  * We earlier verified that coprime argument is odd. Thus the factors of 2
233  * in (p - 1) cannot possibly be factors in coprime, so remove them from p - 1.
234  * Using an odd modulus allows the const time algorithm to be used.
235  *
236  * This assumes coprime < p - 1 which is always true for RSA.
237  */
238  BigInt p1 = p - 1;
239  p1 >>= low_zero_bits(p1);
240  if(inverse_mod(coprime, p1).is_zero())
241  {
242  BOTAN_DEBUG_ASSERT(gcd(p1, coprime) > 1);
243  continue;
244  }
245 
246  BOTAN_DEBUG_ASSERT(gcd(p1, coprime) == 1);
247 
248  if(p.bits() > bits)
249  break;
250 
251  if(is_prime(p, prime_test_rng, prob, true))
252  return p;
253  }
254  }
255  }
256 
257 /*
258 * Generate a random safe prime
259 */
261  {
262  if(bits <= 64)
263  throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
264  std::to_string(bits) + " bits");
265 
266  BigInt q, p;
267  for(;;)
268  {
269  /*
270  Generate q == 2 (mod 3)
271 
272  Otherwise [q == 1 (mod 3) case], 2*q+1 == 3 (mod 3) and not prime.
273 
274  Initially allow a very high error prob (1/2**8) to allow for fast checks,
275  then if 2*q+1 turns out to be a prime go back and strongly check q.
276  */
277  q = random_prime(rng, bits - 1, 0, 2, 3, 8);
278  p = (q << 1) + 1;
279 
280  if(is_prime(p, rng, 128, true))
281  {
282  // We did only a weak check before, go back and verify q before returning
283  if(is_prime(q, rng, 128, true))
284  return p;
285  }
286  }
287  }
288 
289 }
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:276
bool is_negative() const
Definition: bigint.h:530
const uint16_t PRIMES[]
Definition: primes.cpp:12
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:26
BigInt gcd(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:52
size_t bits() const
Definition: bigint.cpp:281
void set_bit(size_t n)
Definition: bigint.h:429
int(* final)(unsigned char *, CTX *)
bool is_zero() const
Definition: bigint.h:420
Definition: bigint.h:1125
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:488
bool is_even() const
Definition: bigint.h:402
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:210
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:260
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:290
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:74
BigInt generate_rsa_prime(RandomNumberGenerator &keygen_rng, RandomNumberGenerator &prime_test_rng, size_t bits, const BigInt &coprime, size_t prob)
Definition: make_prm.cpp:177
constexpr uint16_t make_uint16(uint8_t i0, uint8_t i1)
Definition: loadstor.h:52