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