Botan 3.14.1
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/exceptn.h>
11#include <botan/numthry.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 <botan/internal/monty.h>
17#include <numeric>
18
19namespace Botan {
20
21namespace {
22
23class Prime_Sieve final {
24 public:
25 Prime_Sieve(const BigInt& init_value, size_t sieve_size, word step, bool check_2p1) :
26 m_sieve(mod_small_primes(init_value, std::min(sieve_size, PRIME_TABLE_SIZE))),
27 m_step(step),
28 m_check_2p1(check_2p1) {}
29
30 size_t sieve_size() const { return m_sieve.size(); }
31
32 bool check_2p1() const { return m_check_2p1; }
33
34 bool next() {
35 auto passes = CT::Mask<word>::set();
36 for(size_t i = 0; i != m_sieve.size(); ++i) {
37 m_sieve[i] = sieve_step_incr(m_sieve[i], m_step, PRIMES[i]);
38
39 // If m_sieve[i] == 0 then val % p == 0 -> not prime
40 passes &= CT::Mask<word>::expand(m_sieve[i]);
41
42 if(this->check_2p1()) {
43 /*
44 If v % p == (p-1)/2 then 2*v+1 == 0 (mod p)
45
46 So if potentially generating a safe prime, we want to
47 avoid this value because 2*v+1 will certainly not be prime.
48
49 See "Safe Prime Generation with a Combined Sieve" M. Wiener
50 https://eprint.iacr.org/2003/186.pdf
51 */
52 passes &= ~CT::Mask<word>::is_equal(m_sieve[i], (PRIMES[i] - 1) / 2);
53 }
54 }
55
56 return passes.as_bool();
57 }
58
59 // Add r to the sieved value, in constant time with respect to r
60 void add(uint64_t r) {
61 const auto r_mod = mod_small_primes(r, m_sieve.size());
62 for(size_t i = 0; i != m_sieve.size(); ++i) {
63 const word next = m_sieve[i] + r_mod[i];
64 m_sieve[i] = next - CT::Mask<word>::is_gte(next, PRIMES[i]).if_set_return(PRIMES[i]);
65 }
66 }
67
68 private:
69 // Return (v + step) % mod
70 //
71 // This assumes v is already < mod, which is an invariant of the sieve
72 static constexpr word sieve_step_incr(word v, word step, word mod) {
73 BOTAN_DEBUG_ASSERT(v < mod);
74 // The sieve step and primes are public so this modulo is ok
75 const word stepmod = (step >= mod) ? (step % mod) : step;
76
77 // This sum is at most 2*(mod-1)
78 const word next = (v + stepmod);
79 return next - CT::Mask<word>::is_gte(next, mod).if_set_return(mod);
80 }
81
82 std::vector<word> m_sieve;
83 const word m_step;
84 const bool m_check_2p1;
85};
86
87#if defined(BOTAN_ENABLE_DEBUG_ASSERTS)
88
89bool no_small_multiples(const BigInt& v, const Prime_Sieve& sieve) {
90 const size_t sieve_size = sieve.sieve_size();
91 const bool check_2p1 = sieve.check_2p1();
92
93 if(v.is_even())
94 return false;
95
96 const BigInt v_x2_p1 = 2 * v + 1;
97
98 for(size_t i = 0; i != sieve_size; ++i) {
99 if((v % PRIMES[i]) == 0)
100 return false;
101
102 if(check_2p1) {
103 if(v_x2_p1 % PRIMES[i] == 0)
104 return false;
105 }
106 }
107
108 return true;
109}
110
111#endif
112
113BigInt random_prime_with_sieve(RandomNumberGenerator& rng,
114 size_t bits,
115 const BigInt& coprime,
116 size_t equiv,
117 size_t modulo,
118 size_t prob,
119 bool sieve_check_2p1) {
120 const size_t MAX_ATTEMPTS = 32 * 1024;
121
122 const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);
123
124 // Variable time gcd here is fine since these are generation parameters, not secrets
125 if(std::gcd(equiv, modulo) != 1) {
126 throw Invalid_Argument("random_prime equiv and modulo must be relatively prime");
127 }
128
129 while(true) {
130 BigInt p(rng, bits);
131
132 // Force lowest and two top bits on
133 p.set_bit(bits - 1);
134 p.set_bit(bits - 2);
135 p.set_bit(0);
136
137 // Force p to be equal to equiv mod modulo
138 p += (modulo - (p % modulo)) + equiv;
139
140 Prime_Sieve sieve(p, bits, modulo, sieve_check_2p1);
141
142 for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) {
143 p += modulo;
144
145 if(!sieve.next()) {
146 continue;
147 }
148
149 // here p can be even if modulo is odd, continue on in that case
150 if(p.is_even()) {
151 continue;
152 }
153
154 BOTAN_DEBUG_ASSERT(no_small_multiples(p, sieve));
155
156 const Montgomery_Params monty_p(p);
157
158 if(coprime > 1) {
159 /*
160 First do a single M-R iteration to quickly eliminate most non-primes,
161 before doing the coprimality check which is expensive
162 */
163 if(!is_miller_rabin_probable_prime(p, monty_p, rng, 1)) {
164 continue;
165 }
166
167 /*
168 * Check if p - 1 and coprime are relatively prime, using gcd.
169 * The gcd computation is const-time
170 */
171 if(gcd(p - 1, coprime) > 1) {
172 continue;
173 }
174 }
175
176 if(p.bits() > bits) {
177 break;
178 }
179
180 if(!is_miller_rabin_probable_prime(p, monty_p, rng, mr_trials)) {
181 continue;
182 }
183
184 if(prob > 32 && !is_lucas_probable_prime(p, monty_p)) {
185 continue;
186 }
187
188 return p;
189 }
190 }
191}
192
193} // namespace
194
195/*
196* Generate a random prime
197*/
199 RandomNumberGenerator& rng, size_t bits, const BigInt& coprime, size_t equiv, size_t modulo, size_t prob) {
200 if(bits <= 1) {
201 throw Invalid_Argument("random_prime: Can't make a prime of " + std::to_string(bits) + " bits");
202 }
203 if(coprime.signum() < 0 || (coprime.signum() != 0 && coprime.is_even()) || coprime.bits() >= bits) {
204 throw Invalid_Argument("random_prime: invalid coprime");
205 }
206 // TODO(Botan4) reduce this to ~1000
207 if(modulo == 0 || modulo >= 100000) {
208 throw Invalid_Argument("random_prime: Invalid modulo value");
209 }
210
211 // TODO(Botan4) reject equiv > modulo instead of reducing here
212 equiv %= modulo;
213
214 if(equiv == 0) {
215 throw Invalid_Argument("random_prime Invalid value for equiv/modulo");
216 }
217
218 // Handle small values:
219
220 if(bits <= 16) {
221 if(equiv != 1 || modulo != 2 || coprime != 0) {
222 throw Not_Implemented("random_prime equiv/modulo/coprime options not usable for small primes");
223 }
224
225 if(bits == 2) {
226 return BigInt::from_word(((rng.next_byte() % 2) == 0 ? 2 : 3));
227 } else if(bits == 3) {
228 return BigInt::from_word(((rng.next_byte() % 2) == 0 ? 5 : 7));
229 } else if(bits == 4) {
230 return BigInt::from_word(((rng.next_byte() % 2) == 0 ? 11 : 13));
231 } else {
232 for(;;) {
233 // This is slightly biased, but for small primes it does not seem to matter
234 uint8_t b[4] = {0};
235 rng.randomize(b, 4);
236 const size_t idx = load_le<uint32_t>(b, 0) % PRIME_TABLE_SIZE;
237 const uint16_t small_prime = PRIMES[idx];
238
239 if(high_bit(small_prime) == bits) {
240 return BigInt::from_word(small_prime);
241 }
242 }
243 }
244 }
245
246 // The check_2p1 sieve filter is only appropriate when generating q for a
247 // safe prime; for arbitrary equiv/modulo it can pre-reject every candidate
248 // (eg equiv=1, modulo=3 makes the residue mod 3 always equal (3-1)/2).
249 return random_prime_with_sieve(rng, bits, coprime, equiv, modulo, prob, false);
250}
251
253 RandomNumberGenerator& prime_test_rng,
254 size_t bits,
255 const BigInt& coprime,
256 size_t prob) {
257 if(bits < 512) {
258 throw Invalid_Argument("generate_rsa_prime bits too small");
259 }
260
261 /*
262 * The restriction on coprime <= 64 bits is arbitrary but generally speaking
263 * very large RSA public exponents are a bad idea both for performance and due
264 * to attacks on small d.
265 */
266 if(coprime <= 1 || coprime.is_even() || coprime.bits() > 64) {
267 throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer");
268 }
269
270 const size_t MAX_ATTEMPTS = 32 * 1024;
271
272 const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);
273
274 while(true) {
275 BigInt p(keygen_rng, bits);
276
277 const auto scope = CT::scoped_poison(p);
278
279 /*
280 Force high two bits so multiplication always results in expected n bit integer
281
282 Force the two low bits, and step by 4, so the generated prime is always == 3 (mod 4).
283 This way when we perform the inversion modulo phi(n) it is always of the form 2*o
284 with o odd, which allows a fastpath and avoids leaking any information about the
285 structure of the prime.
286 */
287 p.set_bit(bits - 1);
288 p.set_bit(bits - 2);
289 p.set_bit(1);
290 p.set_bit(0);
291
292 const word step = 4;
293
294 Prime_Sieve sieve(p, bits, step, false);
295
296 /*
297 * Which candidates pass the sieve and are then rejected is visible to a side
298 * channel, and their offsets from the final prime would reveal its residues
299 * modulo the sieve primes. After each rejection, skip ahead by a secret random
300 * multiple of the step so that these offsets are unknown.
301 */
302 const auto skip_ahead = [&]() {
303 // Always 64 bits so that the output does not depend on the word size
304 uint64_t r = load_le<uint64_t>(keygen_rng.random_array<8>());
305 CT::poison(r);
306 r *= step;
307 p += BigInt::from_u64(r);
308 sieve.add(r);
309 };
310
311 for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) {
312 p += step;
313
314 if(!sieve.next()) {
315 continue;
316 }
317
318 BOTAN_DEBUG_ASSERT(no_small_multiples(p, sieve));
319
320 const Montgomery_Params monty_p(p);
321
322 /*
323 * Do a single primality test first before checking coprimality, since
324 * currently a single Miller-Rabin test is faster than computing gcd,
325 * and this eliminates almost all wasted gcd computations.
326 */
327 if(!is_miller_rabin_probable_prime(p, monty_p, prime_test_rng, 1)) {
328 skip_ahead();
329 continue;
330 }
331
332 /*
333 * Check if p - 1 and coprime are relatively prime.
334 */
335 if(gcd(p - 1, coprime) > 1) {
336 skip_ahead();
337 continue;
338 }
339
340 if(p.bits() > bits) {
341 break;
342 }
343
344 if(is_miller_rabin_probable_prime(p, monty_p, prime_test_rng, mr_trials)) {
345 return p;
346 }
347
348 skip_ahead();
349 }
350 }
351}
352
353/*
354* Generate a random safe prime
355*/
357 if(bits <= 64) {
358 throw Invalid_Argument("random_safe_prime: Can't make a prime of " + std::to_string(bits) + " bits");
359 }
360
361 const size_t error_bound = 128;
362
363 BigInt q;
364 BigInt p;
365 for(;;) {
366 /*
367 Generate q == 2 (mod 3), since otherwise [in the case of q == 1 (mod 3)],
368 2*q+1 == 3 (mod 3) and so certainly not prime.
369 */
370 q = random_prime_with_sieve(rng, bits - 1, BigInt::zero(), 2, 3, error_bound, true);
371 p = (q << 1) + 1;
372
373 if(is_prime(p, rng, error_bound, true)) {
374 return p;
375 }
376 }
377}
378
379} // namespace Botan
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
static BigInt zero()
Definition bigint.h:50
int signum() const
Definition bigint.h:493
void set_bit(size_t n)
Definition bigint.h:516
size_t bits() const
Definition bigint.cpp:308
bool is_even() const
Definition bigint.h:481
static BigInt from_u64(uint64_t n)
Definition bigint.cpp:31
static BigInt from_word(word n)
Definition bigint.cpp:36
static constexpr Mask< T > is_gte(T x, T y)
Definition ct_utils.h:473
static constexpr Mask< T > set()
Definition ct_utils.h:387
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
void randomize(std::span< uint8_t > output)
Definition rng.h:86
std::array< uint8_t, bytes > random_array()
Definition rng.h:290
constexpr auto scoped_poison(const Ts &... xs)
Definition ct_utils.h:222
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo, size_t prob)
Definition make_prm.cpp:198
const size_t PRIME_TABLE_SIZE
Definition numthry.h:177
std::vector< word > BOTAN_TEST_API mod_small_primes(const BigInt &n, size_t num_primes)
Definition primes.cpp:493
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition numthry.cpp:449
BigInt generate_rsa_prime(RandomNumberGenerator &keygen_rng, RandomNumberGenerator &prime_test_rng, size_t bits, const BigInt &coprime, size_t prob)
Definition make_prm.cpp:252
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
Definition bit_ops.h:73
BigInt gcd(const BigInt &a, const BigInt &b)
Definition numthry.cpp:220
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
const uint16_t PRIMES[]
Definition primes.cpp:17
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
bool is_miller_rabin_probable_prime(const BigInt &n, const Montgomery_Params &monty_n, RandomNumberGenerator &rng, size_t test_iterations)
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition make_prm.cpp:356
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131
bool is_lucas_probable_prime(const BigInt &n, const Montgomery_Params &monty_n)