Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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 */
77 BigInt random_prime(RandomNumberGenerator& rng,
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 const uint8_t b0 = rng.next_byte();
126 const uint8_t b1 = rng.next_byte();
127 const size_t idx = make_uint16(b0, b1) % 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 while(true)
139 {
140 BigInt p(rng, bits);
141
142 // Force lowest and two top bits on
143 p.set_bit(bits - 1);
144 p.set_bit(bits - 2);
145 p.set_bit(0);
146
147 // Force p to be equal to equiv mod modulo
148 p += (modulo - (p % modulo)) + equiv;
149
150 Prime_Sieve sieve(p, bits);
151
152 for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt)
153 {
154 p += modulo;
155
156 sieve.step(modulo);
157
158 // p can be even if modulo is odd, continue on in that case
159 if(p.is_even() || sieve.passes(true) == false)
160 continue;
161
162 Modular_Reducer mod_p(p);
163
164 /*
165 First do a single M-R iteration to quickly elimate most non-primes,
166 before doing the coprimality check which is expensive
167 */
168 if(is_miller_rabin_probable_prime(p, mod_p, rng, 1) == false)
169 continue;
170
171 if(coprime > 1)
172 {
173 /*
174 * Check if gcd(p - 1, coprime) != 1 by attempting to compute a
175 * modular inverse. We are assured coprime is odd (since if it was
176 * even, it would always have a common factor with p - 1), so
177 * take off the factors of 2 from (p-1) then compute the inverse
178 * of coprime modulo that integer.
179 */
180 BigInt p1 = p - 1;
181 p1 >>= low_zero_bits(p1);
182 if(ct_inverse_mod_odd_modulus(coprime, p1).is_zero())
183 {
184 BOTAN_DEBUG_ASSERT(gcd(p - 1, coprime) > 1);
185 continue;
186 }
187
188 BOTAN_DEBUG_ASSERT(gcd(p - 1, coprime) == 1);
189 }
190
191 if(p.bits() > bits)
192 break;
193
194 const size_t t = miller_rabin_test_iterations(bits, prob, true);
195
196 if(is_miller_rabin_probable_prime(p, mod_p, rng, t) == false)
197 continue;
198
199 if(prob > 32 && !is_lucas_probable_prime(p, mod_p))
200 continue;
201
202 return p;
203 }
204 }
205 }
206
207 BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng,
208 RandomNumberGenerator& prime_test_rng,
209 size_t bits,
210 const BigInt& coprime,
211 size_t prob)
212 {
213 if(bits < 512)
214 throw Invalid_Argument("generate_rsa_prime bits too small");
215
216 /*
217 * The restriction on coprime <= 64 bits is arbitrary but generally speaking
218 * very large RSA public exponents are a bad idea both for performance and due
219 * to attacks on small d.
220 */
221 if(coprime <= 1 || coprime.is_even() || coprime.bits() > 64)
222 throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer");
223
224 const size_t MAX_ATTEMPTS = 32*1024;
225
226 while(true)
227 {
228 BigInt p(keygen_rng, bits);
229
230 // Force lowest and two top bits on
231 p.set_bit(bits - 1);
232 p.set_bit(bits - 2);
233 p.set_bit(0);
234
235 Prime_Sieve sieve(p, bits);
236
237 const word step = 2;
238
239 for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt)
240 {
241 p += step;
242
243 sieve.step(step);
244
245 if(sieve.passes() == false)
246 continue;
247
248 Modular_Reducer mod_p(p);
249
250 /*
251 * Do a single primality test first before checking coprimality, since
252 * currently a single Miller-Rabin test is faster than computing modular
253 * inverse, and this eliminates almost all wasted modular inverses.
254 */
255 if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, 1) == false)
256 continue;
257
258 /*
259 * Check if p - 1 and coprime are relatively prime by computing the inverse.
260 *
261 * We avoid gcd here because that algorithm is not constant time.
262 * Modular inverse is (for odd modulus anyway).
263 *
264 * We earlier verified that coprime argument is odd. Thus the factors of 2
265 * in (p - 1) cannot possibly be factors in coprime, so remove them from p - 1.
266 * Using an odd modulus allows the const time algorithm to be used.
267 *
268 * This assumes coprime < p - 1 which is always true for RSA.
269 */
270 BigInt p1 = p - 1;
271 p1 >>= low_zero_bits(p1);
272 if(ct_inverse_mod_odd_modulus(coprime, p1).is_zero())
273 {
274 BOTAN_DEBUG_ASSERT(gcd(p - 1, coprime) > 1);
275 continue;
276 }
277
278 BOTAN_DEBUG_ASSERT(gcd(p - 1, coprime) == 1);
279
280 if(p.bits() > bits)
281 break;
282
283 const size_t t = miller_rabin_test_iterations(bits, prob, true);
284
285 if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, t) == true)
286 return p;
287 }
288 }
289 }
290
291 /*
292 * Generate a random safe prime
293 */
294 BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
295 {
296 if(bits <= 64)
297 throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
298 std::to_string(bits) + " bits");
299
300 BigInt q, p;
301 for(;;)
302 {
303 /*
304 Generate q == 2 (mod 3)
305
306 Otherwise [q == 1 (mod 3) case], 2*q+1 == 3 (mod 3) and not prime.
307
308 Initially allow a very high error prob (1/2**8) to allow for fast checks,
309 then if 2*q+1 turns out to be a prime go back and strongly check q.
310 */
311 q = random_prime(rng, bits - 1, 0, 2, 3, 8);
312 p = (q << 1) + 1;
313
314 if(is_prime(p, rng, 128, true))
315 {
316 // We did only a weak check before, go back and verify q before returning
317 if(is_prime(q, rng, 128, true))
318 return p;
319 }
320 }
321 }
322
323 }
Botan::PRIME_TABLE_SIZE
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:276
Botan::Invalid_Argument
Definition: exceptn.h:136
Botan::is_lucas_probable_prime
bool is_lucas_probable_prime(const BigInt &C, const Modular_Reducer &mod_C)
Definition: primality.cpp:17
Botan::BigInt::is_even
bool is_even() const
Definition: bigint.h:401
Botan::RandomNumberGenerator::next_byte
uint8_t next_byte()
Definition: rng.h:159
Botan::PRIMES
const uint16_t PRIMES[]
Definition: primes.cpp:12
Botan::low_zero_bits
size_t low_zero_bits(const BigInt &n)
Definition: numthry.cpp:40
Botan::BigInt
Definition: bigint.h:24
Botan::gcd
BigInt gcd(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:66
Botan::miller_rabin_test_iterations
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
Definition: primality.cpp:168
Botan::RandomNumberGenerator
Definition: rng.h:24
Botan::BigInt::set_bit
void set_bit(size_t n)
Definition: bigint.h:428
final
int(* final)(unsigned char *, CTX *)
Definition: commoncrypto_hash.cpp:28
std
Definition: bigint.h:1135
Botan::ct_inverse_mod_odd_modulus
BigInt ct_inverse_mod_odd_modulus(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:200
Botan::is_prime
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:528
Botan::Not_Implemented
Definition: exceptn.h:355
Botan::BigInt::is_negative
bool is_negative() const
Definition: bigint.h:525
Botan::ASN1::to_string
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
Botan::BigInt::bits
size_t bits() const
Definition: bigint.cpp:288
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
Botan::random_safe_prime
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:294
Botan::high_bit
size_t high_bit(T n)
Definition: bit_ops.h:55
Botan
Definition: alg_id.cpp:13
Botan::random_prime
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
Botan::is_miller_rabin_probable_prime
bool is_miller_rabin_probable_prime(const BigInt &n, const Modular_Reducer &mod_n, RandomNumberGenerator &rng, size_t test_iterations)
Definition: primality.cpp:146
Botan::BigInt::is_zero
bool is_zero() const
Definition: bigint.h:419
Botan::generate_rsa_prime
BigInt generate_rsa_prime(RandomNumberGenerator &keygen_rng, RandomNumberGenerator &prime_test_rng, size_t bits, const BigInt &coprime, size_t prob)
Definition: make_prm.cpp:207
m_sieve
std::vector< uint16_t > m_sieve
Definition: make_prm.cpp:68
Botan::make_uint16
constexpr uint16_t make_uint16(uint8_t i0, uint8_t i1)
Definition: loadstor.h:54
Botan::Modular_Reducer
Definition: reducer.h:18