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