Botan 3.14.1
Crypto and TLS for C&
primality.cpp
Go to the documentation of this file.
1/*
2* (C) 2016,2018,2026 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#include <botan/internal/primality.h>
8
9#include <botan/bigint.h>
10#include <botan/numthry.h>
11#include <botan/rng.h>
12#include <botan/internal/bit_ops.h>
13#include <botan/internal/ct_utils.h>
14#include <botan/internal/divide.h>
15#include <botan/internal/monty.h>
16#include <botan/internal/monty_exp.h>
17#include <botan/internal/mp_core.h>
18#include <botan/internal/target_info.h>
19#include <tuple>
20#include <utility>
21
22#if defined(BOTAN_HAS_THREAD_UTILS) && !defined(BOTAN_HAS_VALGRIND)
23 #include <botan/internal/thread_pool.h>
24#endif
25
26namespace Botan {
27
28namespace {
29
30/*
31* Jacobi symbol (a/n) for odd n and a < n, returned as masks for the symbol
32* being -1 or 0
33*
34* This is the binary algorithm run for a fixed number of iterations, so it is
35* constant time with respect to a. The value of n is public.
36*/
37std::pair<CT::Mask<word>, CT::Mask<word>> ct_jacobi_word(word a, word n) {
38 // Each iteration reduces the total bit length of a and n by at least one,
39 // ending with a == 0 and n == gcd(a, n)
40 const size_t iterations = 2 * high_bit(n);
41
42 word s = 0; // the sign, in bit 1
43
44 for(size_t i = 0; i != iterations; ++i) {
45 const auto a_odd = CT::Mask<word>::expand_bit(a, 0);
46 const auto swap = a_odd & CT::Mask<word>::is_lt(a, n);
47
48 // (a/n) = -(n/a) if a and n are both 3 (mod 4)
49 s ^= swap.if_set_return(a & n & 2);
50 swap.conditional_swap(a, n);
51
52 a -= a_odd.if_set_return(n);
53 a >>= 1;
54
55 // (2/n) = -1 if n is 3 or 5 (mod 8)
56 s ^= (n ^ (n >> 1)) & 2;
57 }
58
59 const auto gcd_is_one = CT::Mask<word>::is_equal(n, 1);
60 return {gcd_is_one & CT::Mask<word>::expand(s), ~gcd_is_one};
61}
62
63/*
64* Search count entries of the sequence 5, -7, 9, -11, 13, ..., starting at
65* index first, for the first D with Jacobi symbol (D/C) != 1
66*
67* This is constant time with respect to C. Returns masks indicating if such
68* a D was found and if (D/C) == 0, along with the index of D.
69*/
70std::tuple<CT::Mask<word>, CT::Mask<word>, word> selfridge_search(const BigInt& C, size_t first, size_t count) {
71 auto found = CT::Mask<word>::cleared();
72 auto symbol_zero = CT::Mask<word>::cleared();
73 word index = 0;
74
75 for(size_t i = first; i != first + count; ++i) {
76 const word d = 5 + 2 * i;
77
78 // Every D in the sequence is 1 (mod 4), which implies (D/C) == (C/|D|)
79 const word r = ct_mod_word(C, d);
80 CT::poison(r);
81 const auto [minus_one, zero] = ct_jacobi_word(r, d);
82
83 const auto first_hit = ~found & (minus_one | zero);
84 index = first_hit.select(static_cast<word>(i), index);
85 symbol_zero |= first_hit & zero;
86 found |= first_hit;
87 }
88
89 return {found, symbol_zero, index};
90}
91
92/*
93* Lucas probable prime test, following FIPS 186-4 C.3.3 with all values
94* kept in Montgomery form
95*/
96bool lucas_test(const BigInt& C, const Montgomery_Params& monty_C, bool vartime) {
97 BOTAN_ARG_CHECK(C.signum() >= 0, "Argument must be non-negative");
98
99 if(C == 2 || C == 3 || C == 5 || C == 7 || C == 11 || C == 13) {
100 return true;
101 }
102
103 if(C <= 1 || CT::driveby_unpoison(C.is_even())) {
104 return false;
105 }
106
107 /*
108 * Find the first D in the sequence 5, -7, 9, -11, 13, ... with (D/C) == -1
109 *
110 * Which D is chosen depends on C, so the constant time variant checks a
111 * block of 256 values at once, revealing only which block contained D. For
112 * a random prime C, the first block fails with probability about 2^-96.
113 */
114 const size_t block = vartime ? 8 : 256;
115
116 word D_index = 0;
117 for(size_t first = 0;; first += block) {
118 const auto [found, symbol_zero, index] = selfridge_search(C, first, block);
119
120 if(found.as_bool()) {
121 if(symbol_zero.as_bool()) {
122 return false;
123 }
124 D_index = index;
125 break;
126 }
127
128 // A perfect square has no D with (D/C) == -1
129 if(first == 0 && is_perfect_square(C).signum() != 0) {
130 return false;
131 }
132 }
133
134 if(vartime) {
135 CT::unpoison(D_index);
136 }
137
138 const word D = 5 + 2 * D_index;
139 const bool D_negative = (D_index % 2) == 1;
140
141 const BigInt K = C + 1;
142 const size_t K_bits = K.bits() - 1;
143
145
147 Montgomery_Int V = U;
148 Montgomery_Int Ut = U;
149 Montgomery_Int Vt = U;
150 Montgomery_Int U2 = U;
151 Montgomery_Int V2 = U;
152 Montgomery_Int T = U;
153
154 // z += D*t, overwriting t
155 const auto add_D_times = [&](Montgomery_Int& z, Montgomery_Int& t) {
156 t.mul_by_word(D);
157 if(vartime) {
158 if(D_negative) {
159 z -= t;
160 } else {
161 z += t;
162 }
163 } else {
164 t.ct_cond_negate(D_negative);
165 z += t;
166 }
167 };
168
169 for(size_t i = 0; i != K_bits; ++i) {
170 const bool k_bit = K.get_bit(K_bits - 1 - i);
171
172 // U_temp = U V
173 Ut = U;
174 Ut.mul_by(V, ws);
175
176 // V_temp = (V^2 + D U^2) / 2
177 T = U;
178 T.square_this_n_times(ws, 1);
179 Vt = V;
180 Vt.square_this_n_times(ws, 1);
181 add_D_times(Vt, T);
182 Vt.div2();
183
184 if(!vartime || k_bit) {
185 // U_i = (U_temp + V_temp) / 2
186 U2 = Ut;
187 U2 += Vt;
188 U2.div2();
189
190 // V_i = (V_temp + D U_temp) / 2
191 T = Ut;
192 V2 = Vt;
193 add_D_times(V2, T);
194 V2.div2();
195 }
196
197 if(vartime) {
198 if(k_bit) {
199 U = U2;
200 V = V2;
201 } else {
202 U = Ut;
203 V = Vt;
204 }
205 } else {
206 U = Ut;
207 V = Vt;
208 U.ct_cond_assign(k_bit, U2);
209 V.ct_cond_assign(k_bit, V2);
210 }
211 }
212
213 return U.is_zero();
214}
215
216/*
217* Window size for variable time exponentiation of an exponent of exp_bits
218*/
219size_t vartime_window_bits(size_t exp_bits) {
220 if(exp_bits <= 256) {
221 return 4;
222 } else if(exp_bits <= 1024) {
223 return 5;
224 } else if(exp_bits <= 2048) {
225 return 6;
226 } else {
227 return 7;
228 }
229}
230
231/**
232* Precomputed values shared by all Miller-Rabin tests of a single n
233*/
234class Miller_Rabin_Test final {
235 public:
236 Miller_Rabin_Test(const BigInt& n, const Montgomery_Params& monty_n, bool vartime) :
237 m_monty_n(monty_n), m_vartime(vartime) {
238 BOTAN_ARG_CHECK(n >= 3 && CT::driveby_unpoison(n.is_odd()), "Invalid integer for Miller-Rabin test");
239
240 const size_t N = m_monty_n.p_words();
241
242 const BigInt n_minus_1 = n - 1;
243 /*
244 * This unpoison is not ideal but realistically there is no way to
245 * hide the number of loop iterations (below). The main user of
246 * secret primes is RSA and we always generate RSA primes such that
247 * p == 3 (mod 4), which means s is always 1.
248 */
249 m_s = CT::driveby_unpoison(low_zero_bits(n_minus_1));
250 m_d = n_minus_1 >> m_s;
251 m_d_bits = m_d.bits();
252
253 // 1 and -1 in Montgomery form
254 m_one.assign(m_monty_n.R1()._as_span().first(N).begin(), m_monty_n.R1()._as_span().first(N).end());
255 m_minus_one.resize(N);
256 bigint_sub3(m_minus_one.data(), n._data(), N, m_one.data(), N);
257 }
258
259 /**
260 * Perform a single Miller-Rabin test with the specified base
261 */
262 bool passes(const BigInt& a) const {
263 Montgomery_Int y = [&]() {
264 if(m_vartime) {
265 const auto powm_a = monty_precompute(m_monty_n, a, vartime_window_bits(m_d_bits));
266 return monty_execute_vartime(*powm_a, m_d);
267 } else {
268 const auto powm_a = monty_precompute(m_monty_n, a, 4);
269 return monty_execute(*powm_a, m_d, m_d_bits);
270 }
271 }();
272
273 if(is_one(y) || is_minus_one(y)) {
274 return true;
275 }
276
277 secure_vector<word> ws(2 * m_monty_n.p_words());
278
279 for(size_t i = 1; i != m_s; ++i) {
280 y.square_this_n_times(ws, 1);
281
282 if(is_one(y)) { // found a non-trivial square root
283 return false;
284 }
285
286 /*
287 -1 is the trivial square root of unity, so ``a`` is not a
288 witness for this number - give up
289 */
290 if(is_minus_one(y)) {
291 return true;
292 }
293 }
294
295 return false;
296 }
297
298 private:
299 bool is_one(const Montgomery_Int& y) const {
300 return CT::is_equal(y.repr().data(), m_one.data(), m_one.size()).as_bool();
301 }
302
303 bool is_minus_one(const Montgomery_Int& y) const {
304 return CT::is_equal(y.repr().data(), m_minus_one.data(), m_minus_one.size()).as_bool();
305 }
306
307 Montgomery_Params m_monty_n;
308 bool m_vartime;
309 size_t m_s;
310 BigInt m_d;
311 size_t m_d_bits;
313 secure_vector<word> m_minus_one;
314};
315
316bool miller_rabin_test(const BigInt& n,
317 const Montgomery_Params& monty_n,
319 size_t test_iterations,
320 bool vartime) {
321 if(n < 3 || CT::driveby_unpoison(n.is_even())) {
322 return false;
323 }
324
325 const Miller_Rabin_Test mr(n, monty_n, vartime);
326
327 for(size_t i = 0; i != test_iterations; ++i) {
328 const BigInt a = BigInt::random_integer(rng, BigInt::from_word(2), n);
329
330 if(!mr.passes(a)) {
331 return false;
332 }
333 }
334
335 // Failed to find a counterexample
336 return true;
337}
338
339#if defined(BOTAN_HAS_THREAD_UTILS) && !defined(BOTAN_HAS_VALGRIND)
340
341/*
342* Miller-Rabin tests per thread pool job
343*
344* The cost of a test grows roughly quadratically with the size of n, so
345* smaller n get more tests per job to keep each job worth dispatching.
346*/
347size_t miller_rabin_tests_per_job(size_t n_bits) {
348 constexpr size_t ref_bits = 1024;
349 constexpr size_t ref_tests = 8;
350 if(n_bits > ref_bits) {
351 return ref_tests;
352 } else {
353 return std::max(ref_tests, (ref_tests * ref_bits * ref_bits) / (n_bits * n_bits));
354 }
355}
356
357#endif
358
359bool miller_rabin_lucas_test(
360 const BigInt& n, const Montgomery_Params& monty_n, RandomNumberGenerator& rng, size_t t, bool vartime) {
361 if(n < 3 || CT::driveby_unpoison(n.is_even())) {
362 return false;
363 }
364 if(t == 0) {
365 t = 1;
366 }
367
368 const Miller_Rabin_Test mr(n, monty_n, vartime);
369
370 const auto random_base = [&]() { return BigInt::random_integer(rng, BigInt::from_word(2), n); };
371
372 // A single test first, since that alone rejects almost all composites
373 if(!mr.passes(random_base())) {
374 return false;
375 }
376 t -= 1;
377
378#if defined(BOTAN_HAS_THREAD_UTILS) && !defined(BOTAN_HAS_VALGRIND)
379 auto& pool = Thread_Pool::global_instance();
380 const size_t tests_per_job = miller_rabin_tests_per_job(n.bits());
381
382 // The Lucas test costs about as much as three Miller-Rabin tests
383 if(pool.worker_count() > 0 && t > 0 && t + 3 >= tests_per_job) {
384 // The jobs cannot share the RNG, so draw all of the bases here
385 std::vector<BigInt> bases;
386 bases.reserve(t);
387 for(size_t i = 0; i != t; ++i) {
388 bases.push_back(random_base());
389 }
390
391 // Split the tests into jobs of (nearly) equal size
392 const size_t job_tests = ceil_division(t, ceil_division(t, tests_per_job));
393 const size_t jobs = ceil_division(t, job_tests);
394
395 const auto passes_tests = [&](size_t from, size_t to) {
396 for(size_t i = from; i != to; ++i) {
397 if(!mr.passes(bases[i])) {
398 return false;
399 }
400 }
401 return true;
402 };
403
404 std::vector<Joining_Future<bool>> futures;
405 futures.reserve(jobs);
406
407 futures.push_back(pool.run([&]() { return lucas_test(n, monty_n, vartime); }));
408
409 // The first job runs in this thread, the rest in the pool
410 for(size_t j = 1; j < jobs; ++j) {
411 const size_t from = j * job_tests;
412 const size_t to = std::min(t, from + job_tests);
413 futures.push_back(pool.run([&, from, to]() { return passes_tests(from, to); }));
414 }
415
416 bool passes = passes_tests(0, std::min(t, job_tests));
417
418 // Collect every result, so that an exception from any job propagates
419 for(auto& future : futures) {
420 passes = future.get() && passes;
421 }
422
423 return passes;
424 }
425#endif
426
427 for(size_t i = 0; i != t; ++i) {
428 if(!mr.passes(random_base())) {
429 return false;
430 }
431 }
432
433 return lucas_test(n, monty_n, vartime);
434}
435
436bool bailie_psw_test(const BigInt& n, const Montgomery_Params& monty_n, bool vartime) {
437 if(n == 2) {
438 return true;
439 } else if(n <= 1 || CT::driveby_unpoison(n.is_even())) {
440 return false;
441 }
442
443 const Miller_Rabin_Test mr(n, monty_n, vartime);
444 return mr.passes(BigInt::from_word(2)) && lucas_test(n, monty_n, vartime);
445}
446
447} // namespace
448
449bool is_lucas_probable_prime(const BigInt& n, const Montgomery_Params& monty_n) {
450 return lucas_test(n, monty_n, false);
451}
452
454 return lucas_test(n, monty_n, true);
455}
456
458 return bailie_psw_test(n, monty_n, false);
459}
460
462 return bailie_psw_test(n, monty_n, true);
463}
464
466 if(n == 2) {
467 return true;
468 } else if(n <= 1 || CT::driveby_unpoison(n.is_even())) {
469 return false;
470 }
471
472 return bailie_psw_test(n, Montgomery_Params(n), false);
473}
474
476 if(n == 2) {
477 return true;
478 } else if(n <= 1 || n.is_even()) {
479 return false;
480 }
481
482 return bailie_psw_test(n, Montgomery_Params(n), true);
483}
484
486 const Montgomery_Params& monty_n,
488 size_t test_iterations) {
489 return miller_rabin_test(n, monty_n, rng, test_iterations, false);
490}
491
493 const Montgomery_Params& monty_n,
495 size_t test_iterations) {
496 return miller_rabin_test(n, monty_n, rng, test_iterations, true);
497}
498
500 const Montgomery_Params& monty_n,
502 size_t test_iterations) {
503 return miller_rabin_lucas_test(n, monty_n, rng, test_iterations, false);
504}
505
507 const Montgomery_Params& monty_n,
509 size_t test_iterations) {
510 return miller_rabin_lucas_test(n, monty_n, rng, test_iterations, true);
511}
512
513size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random) {
514 // Cap prob at 512 bits as _way_ more than enough; a random fault causing
515 // false accept is much more likely to occur than an actual 2^-512 event is.
516
517 prob = std::min<size_t>(512, prob);
518
519 const size_t base = (prob + 2) / 2; // worst case 4^-t error rate
520
521 /*
522 * If the candidate prime was maliciously constructed, we can't rely
523 * on arguments based on p being random.
524 */
525 if(!random) {
526 return base;
527 }
528
529 /*
530 * For randomly chosen numbers we can use the estimates from
531 * http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf
532 *
533 * These values are derived from the inequality for p(k,t) given on
534 * the second page.
535 */
536 if(prob <= 128) {
537 if(n_bits >= 1536) {
538 return 4; // < 2^-133
539 }
540 if(n_bits >= 1024) {
541 return 6; // < 2^-133
542 }
543 if(n_bits >= 512) {
544 return 12; // < 2^-129
545 }
546 if(n_bits >= 256) {
547 return 29; // < 2^-128
548 }
549 }
550
551 /*
552 If the user desires a smaller error probability than we have
553 precomputed error estimates for, just fall back to using the worst
554 case error rate.
555 */
556 return base;
557}
558
559} // namespace Botan
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition big_rand.cpp:45
size_t bits() const
Definition bigint.cpp:308
bool is_even() const
Definition bigint.h:481
static BigInt from_word(word n)
Definition bigint.cpp:36
static constexpr Mask< T > expand_bit(T v, size_t bit)
Definition ct_utils.h:426
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447
static constexpr Mask< T > is_lt(T x, T y)
Definition ct_utils.h:455
static constexpr Mask< T > cleared()
Definition ct_utils.h:392
static Montgomery_Int one(const Montgomery_Params &params)
Definition monty.cpp:237
bool is_zero() const
Definition monty.cpp:501
static Thread_Pool & global_instance()
constexpr decltype(auto) driveby_unpoison(T &&v)
Definition ct_utils.h:243
constexpr CT::Mask< T > is_equal(const T x[], const T y[], size_t len)
Definition ct_utils.h:803
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56
word ct_mod_word(const BigInt &x, word y)
Definition divide.cpp:247
bool is_miller_rabin_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n, RandomNumberGenerator &rng, size_t test_iterations)
BOTAN_FORCE_INLINE constexpr T ceil_division(T a, T b)
Definition bit_ops.h:167
bool is_bailie_psw_probable_prime(const BigInt &n, const Montgomery_Params &monty_n)
size_t low_zero_bits(const BigInt &n)
Definition numthry.cpp:194
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:196
bool is_bailie_psw_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n)
std::shared_ptr< const Montgomery_Exponentiation_State > monty_precompute(const Montgomery_Int &g, size_t window_bits)
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
Definition bit_ops.h:73
Montgomery_Int monty_execute_vartime(const Montgomery_Exponentiation_State &precomputed_state, const BigInt &k)
bool is_lucas_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n)
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
BigInt is_perfect_square(const BigInt &C)
Definition numthry.cpp:352
bool is_miller_rabin_lucas_probable_prime(const BigInt &n, const Montgomery_Params &monty_n, RandomNumberGenerator &rng, size_t test_iterations)
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)
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)
bool is_miller_rabin_lucas_probable_prime_vartime(const BigInt &n, const Montgomery_Params &monty_n, RandomNumberGenerator &rng, size_t test_iterations)
Montgomery_Int monty_execute(const Montgomery_Exponentiation_State &precomputed_state, const BigInt &k, size_t max_k_bits)