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