Botan 3.7.1
Crypto and TLS for C&
primality.cpp
Go to the documentation of this file.
1/*
2* (C) 2016,2018 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/reducer.h>
12#include <botan/rng.h>
13#include <botan/internal/monty.h>
14#include <botan/internal/monty_exp.h>
15#include <algorithm>
16
17namespace Botan {
18
19bool is_lucas_probable_prime(const BigInt& C, const Modular_Reducer& mod_C) {
20 if(C == 2 || C == 3 || C == 5 || C == 7 || C == 11 || C == 13) {
21 return true;
22 }
23
24 if(C <= 1 || C.is_even()) {
25 return false;
26 }
27
29
30 for(;;) {
31 int32_t j = jacobi(D, C);
32 if(j == 0) {
33 return false;
34 }
35
36 if(j == -1) {
37 break;
38 }
39
40 // Check 5, -7, 9, -11, 13, -15, 17, ...
41 if(D.is_negative()) {
42 D.flip_sign();
43 D += 2;
44 } else {
45 D += 2;
46 D.flip_sign();
47 }
48
49 if(D == 17 && is_perfect_square(C).is_nonzero()) {
50 return false;
51 }
52 }
53
54 const BigInt K = C + 1;
55 const size_t K_bits = K.bits() - 1;
56
57 BigInt U = BigInt::one();
58 BigInt V = BigInt::one();
59
60 BigInt Ut, Vt, U2, V2;
61
62 for(size_t i = 0; i != K_bits; ++i) {
63 const bool k_bit = K.get_bit(K_bits - 1 - i);
64
65 Ut = mod_C.multiply(U, V);
66
67 Vt = mod_C.reduce(mod_C.square(V) + mod_C.multiply(D, mod_C.square(U)));
68 Vt.ct_cond_add(Vt.is_odd(), C);
69 Vt >>= 1;
70 Vt = mod_C.reduce(Vt);
71
72 U = Ut;
73 V = Vt;
74
75 U2 = mod_C.reduce(Ut + Vt);
76 U2.ct_cond_add(U2.is_odd(), C);
77 U2 >>= 1;
78
79 V2 = mod_C.reduce(Vt + Ut * D);
80 V2.ct_cond_add(V2.is_odd(), C);
81 V2 >>= 1;
82
83 U.ct_cond_assign(k_bit, U2);
84 V.ct_cond_assign(k_bit, V2);
85 }
86
87 return (U == 0);
88}
89
91 if(n == 2) {
92 return true;
93 } else if(n <= 1 || n.is_even()) {
94 return false;
95 }
96
97 auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n);
98 const auto base = BigInt::from_word(2);
99 return passes_miller_rabin_test(n, mod_n, monty_n, base) && is_lucas_probable_prime(n, mod_n);
100}
101
103 const Modular_Reducer& mod_n,
104 const std::shared_ptr<Montgomery_Params>& monty_n,
105 const BigInt& a) {
106 if(n < 3 || n.is_even()) {
107 return false;
108 }
109
110 BOTAN_ASSERT_NOMSG(n > 1);
111
112 const BigInt n_minus_1 = n - 1;
113 const size_t s = low_zero_bits(n_minus_1);
114 const BigInt nm1_s = n_minus_1 >> s;
115 const size_t n_bits = n.bits();
116
117 const size_t powm_window = 4;
118
119 auto powm_a_n = monty_precompute(monty_n, a, powm_window);
120
121 BigInt y = monty_execute(*powm_a_n, nm1_s, n_bits).value();
122
123 if(y == 1 || y == n_minus_1) {
124 return true;
125 }
126
127 for(size_t i = 1; i != s; ++i) {
128 y = mod_n.square(y);
129
130 if(y == 1) { // found a non-trivial square root
131 return false;
132 }
133
134 /*
135 -1 is the trivial square root of unity, so ``a`` is not a
136 witness for this number - give up
137 */
138 if(y == n_minus_1) {
139 return true;
140 }
141 }
142
143 return false;
144}
145
147 const Modular_Reducer& mod_n,
149 size_t test_iterations) {
150 if(n < 3 || n.is_even()) {
151 return false;
152 }
153
154 auto monty_n = std::make_shared<Montgomery_Params>(n, mod_n);
155
156 for(size_t i = 0; i != test_iterations; ++i) {
157 const BigInt a = BigInt::random_integer(rng, BigInt::from_word(2), n);
158
159 if(!passes_miller_rabin_test(n, mod_n, monty_n, a)) {
160 return false;
161 }
162 }
163
164 // Failed to find a counterexample
165 return true;
166}
167
168size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random) {
169 const size_t base = (prob + 2) / 2; // worst case 4^-t error rate
170
171 /*
172 * If the candidate prime was maliciously constructed, we can't rely
173 * on arguments based on p being random.
174 */
175 if(random == false) {
176 return base;
177 }
178
179 /*
180 * For randomly chosen numbers we can use the estimates from
181 * http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf
182 *
183 * These values are derived from the inequality for p(k,t) given on
184 * the second page.
185 */
186 if(prob <= 128) {
187 if(n_bits >= 1536) {
188 return 4; // < 2^-133
189 }
190 if(n_bits >= 1024) {
191 return 6; // < 2^-133
192 }
193 if(n_bits >= 512) {
194 return 12; // < 2^-129
195 }
196 if(n_bits >= 256) {
197 return 29; // < 2^-128
198 }
199 }
200
201 /*
202 If the user desires a smaller error probability than we have
203 precomputed error estimates for, just fall back to using the worst
204 case error rate.
205 */
206 return base;
207}
208
209} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
void ct_cond_add(bool predicate, const BigInt &value)
Definition bigint.cpp:437
bool is_odd() const
Definition bigint.h:446
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition big_rand.cpp:43
void ct_cond_assign(bool predicate, const BigInt &other)
Definition bigint.cpp:500
void flip_sign()
Definition bigint.h:587
static BigInt one()
Definition bigint.h:55
size_t bits() const
Definition bigint.cpp:295
bool is_even() const
Definition bigint.h:440
static BigInt from_word(word n)
Definition bigint.cpp:42
bool is_negative() const
Definition bigint.h:560
BigInt square(const BigInt &x) const
Definition reducer.cpp:61
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition reducer.h:32
BigInt reduce(const BigInt &x) const
Definition reducer.cpp:54
BigInt value() const
Definition monty.cpp:335
size_t low_zero_bits(const BigInt &n)
Definition numthry.cpp:167
bool passes_miller_rabin_test(const BigInt &n, const Modular_Reducer &mod_n, const std::shared_ptr< Montgomery_Params > &monty_n, const BigInt &a)
bool is_miller_rabin_probable_prime(const BigInt &n, const Modular_Reducer &mod_n, RandomNumberGenerator &rng, size_t test_iterations)
bool is_bailie_psw_probable_prime(const BigInt &n, const Modular_Reducer &mod_n)
Definition primality.cpp:90
Montgomery_Int monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
BigInt is_perfect_square(const BigInt &C)
Definition numthry.cpp:321
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(const Montgomery_Int &g, size_t window_bits, bool const_time)
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
int32_t jacobi(const BigInt &a, const BigInt &n)
Definition numthry.cpp:116
bool is_lucas_probable_prime(const BigInt &C, const Modular_Reducer &mod_C)
Definition primality.cpp:19