/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/numthry.h> |
9 | | #include <botan/rng.h> |
10 | | #include <botan/internal/bit_ops.h> |
11 | | #include <botan/loadstor.h> |
12 | | #include <botan/reducer.h> |
13 | | #include <botan/internal/primality.h> |
14 | | #include <algorithm> |
15 | | |
16 | | namespace Botan { |
17 | | |
18 | | namespace { |
19 | | |
20 | | class Prime_Sieve final |
21 | | { |
22 | | public: |
23 | | Prime_Sieve(const BigInt& init_value, size_t sieve_size) : |
24 | | m_sieve(std::min(sieve_size, PRIME_TABLE_SIZE)) |
25 | 1 | { |
26 | 257 | for(size_t i = 0; i != m_sieve.size(); ++i) |
27 | 256 | m_sieve[i] = static_cast<uint16_t>(init_value % PRIMES[i]); |
28 | 1 | } |
29 | | |
30 | | void step(word increment) |
31 | 999 | { |
32 | 256k | for(size_t i = 0; i != m_sieve.size(); ++i) |
33 | 255k | { |
34 | 255k | m_sieve[i] = (m_sieve[i] + increment) % PRIMES[i]; |
35 | 255k | } |
36 | 999 | } |
37 | | |
38 | | bool passes(bool check_2p1 = false) const |
39 | 999 | { |
40 | 7.25k | for(size_t i = 0; i != m_sieve.size(); ++i) |
41 | 7.23k | { |
42 | 7.23k | /* |
43 | 7.23k | In this case, p is a multiple of PRIMES[i] |
44 | 7.23k | */ |
45 | 7.23k | if(m_sieve[i] == 0) |
46 | 495 | return false; |
47 | 6.74k | |
48 | 6.74k | if(check_2p1) |
49 | 6.74k | { |
50 | 6.74k | /* |
51 | 6.74k | In this case, 2*p+1 will be a multiple of PRIMES[i] |
52 | 6.74k | |
53 | 6.74k | So if potentially generating a safe prime, we want to |
54 | 6.74k | avoid this value because 2*p+1 will certainly not be prime. |
55 | 6.74k | |
56 | 6.74k | See "Safe Prime Generation with a Combined Sieve" M. Wiener |
57 | 6.74k | https://eprint.iacr.org/2003/186.pdf |
58 | 6.74k | */ |
59 | 6.74k | if(m_sieve[i] == (PRIMES[i] - 1) / 2) |
60 | 489 | return false; |
61 | 6.74k | } |
62 | 6.74k | } |
63 | 999 | |
64 | 999 | return true; |
65 | 999 | } |
66 | | |
67 | | private: |
68 | | std::vector<uint16_t> m_sieve; |
69 | | }; |
70 | | |
71 | | } |
72 | | |
73 | | |
74 | | /* |
75 | | * Generate a random prime |
76 | | */ |
77 | | BigInt random_prime(RandomNumberGenerator& rng, |
78 | | size_t bits, const BigInt& coprime, |
79 | | size_t equiv, size_t modulo, |
80 | | size_t prob) |
81 | 1 | { |
82 | 1 | if(bits <= 1) |
83 | 0 | { |
84 | 0 | throw Invalid_Argument("random_prime: Can't make a prime of " + |
85 | 0 | std::to_string(bits) + " bits"); |
86 | 0 | } |
87 | 1 | if(coprime.is_negative() || (!coprime.is_zero() && coprime.is_even()) || coprime.bits() >= bits) |
88 | 0 | { |
89 | 0 | throw Invalid_Argument("random_prime: invalid coprime"); |
90 | 0 | } |
91 | 1 | if(modulo == 0) |
92 | 0 | { |
93 | 0 | throw Invalid_Argument("random_prime: Invalid modulo value"); |
94 | 0 | } |
95 | 1 | |
96 | 1 | equiv %= modulo; |
97 | 1 | |
98 | 1 | if(equiv == 0) |
99 | 0 | throw Invalid_Argument("random_prime Invalid value for equiv/modulo"); |
100 | 1 | |
101 | 1 | // Handle small values: |
102 | 1 | |
103 | 1 | if(bits <= 16) |
104 | 0 | { |
105 | 0 | if(equiv != 1 || modulo != 2 || coprime != 0) |
106 | 0 | throw Not_Implemented("random_prime equiv/modulo/coprime options not usable for small primes"); |
107 | 0 | |
108 | 0 | if(bits == 2) |
109 | 0 | { |
110 | 0 | return ((rng.next_byte() % 2) ? 2 : 3); |
111 | 0 | } |
112 | 0 | else if(bits == 3) |
113 | 0 | { |
114 | 0 | return ((rng.next_byte() % 2) ? 5 : 7); |
115 | 0 | } |
116 | 0 | else if(bits == 4) |
117 | 0 | { |
118 | 0 | return ((rng.next_byte() % 2) ? 11 : 13); |
119 | 0 | } |
120 | 0 | else |
121 | 0 | { |
122 | 0 | for(;;) |
123 | 0 | { |
124 | 0 | // This is slightly biased, but for small primes it does not seem to matter |
125 | 0 | const uint8_t b0 = rng.next_byte(); |
126 | 0 | const uint8_t b1 = rng.next_byte(); |
127 | 0 | const size_t idx = make_uint16(b0, b1) % PRIME_TABLE_SIZE; |
128 | 0 | const uint16_t small_prime = PRIMES[idx]; |
129 | 0 |
|
130 | 0 | if(high_bit(small_prime) == bits) |
131 | 0 | return small_prime; |
132 | 0 | } |
133 | 0 | } |
134 | 0 | } |
135 | 1 | |
136 | 1 | const size_t MAX_ATTEMPTS = 32*1024; |
137 | 1 | |
138 | 1 | while(true) |
139 | 1 | { |
140 | 1 | BigInt p(rng, bits); |
141 | 1 | |
142 | 1 | // Force lowest and two top bits on |
143 | 1 | p.set_bit(bits - 1); |
144 | 1 | p.set_bit(bits - 2); |
145 | 1 | p.set_bit(0); |
146 | 1 | |
147 | 1 | // Force p to be equal to equiv mod modulo |
148 | 1 | p += (modulo - (p % modulo)) + equiv; |
149 | 1 | |
150 | 1 | Prime_Sieve sieve(p, bits); |
151 | 1 | |
152 | 999 | for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) |
153 | 999 | { |
154 | 999 | p += modulo; |
155 | 999 | |
156 | 999 | sieve.step(modulo); |
157 | 999 | |
158 | 999 | // p can be even if modulo is odd, continue on in that case |
159 | 999 | if(p.is_even() || sieve.passes(true) == false) |
160 | 984 | continue; |
161 | 15 | |
162 | 15 | Modular_Reducer mod_p(p); |
163 | 15 | |
164 | 15 | /* |
165 | 15 | First do a single M-R iteration to quickly elimate most non-primes, |
166 | 15 | before doing the coprimality check which is expensive |
167 | 15 | */ |
168 | 15 | if(is_miller_rabin_probable_prime(p, mod_p, rng, 1) == false) |
169 | 14 | continue; |
170 | 1 | |
171 | 1 | if(coprime > 1) |
172 | 0 | { |
173 | 0 | /* |
174 | 0 | * Check if gcd(p - 1, coprime) != 1 by attempting to compute a |
175 | 0 | * modular inverse. We are assured coprime is odd (since if it was |
176 | 0 | * even, it would always have a common factor with p - 1), so |
177 | 0 | * take off the factors of 2 from (p-1) then compute the inverse |
178 | 0 | * of coprime modulo that integer. |
179 | 0 | */ |
180 | 0 | BigInt p1 = p - 1; |
181 | 0 | p1 >>= low_zero_bits(p1); |
182 | 0 | if(ct_inverse_mod_odd_modulus(coprime, p1).is_zero()) |
183 | 0 | { |
184 | 0 | BOTAN_DEBUG_ASSERT(gcd(p - 1, coprime) > 1); |
185 | 0 | continue; |
186 | 0 | } |
187 | 0 |
|
188 | 0 | BOTAN_DEBUG_ASSERT(gcd(p - 1, coprime) == 1); |
189 | 0 | } |
190 | 1 | |
191 | 1 | if(p.bits() > bits) |
192 | 0 | break; |
193 | 1 | |
194 | 1 | const size_t t = miller_rabin_test_iterations(bits, prob, true); |
195 | 1 | |
196 | 1 | if(is_miller_rabin_probable_prime(p, mod_p, rng, t) == false) |
197 | 0 | continue; |
198 | 1 | |
199 | 1 | if(prob > 32 && !is_lucas_probable_prime(p, mod_p)) |
200 | 0 | continue; |
201 | 1 | |
202 | 1 | return p; |
203 | 1 | } |
204 | 1 | } |
205 | 1 | } |
206 | | |
207 | | BigInt generate_rsa_prime(RandomNumberGenerator& keygen_rng, |
208 | | RandomNumberGenerator& prime_test_rng, |
209 | | size_t bits, |
210 | | const BigInt& coprime, |
211 | | size_t prob) |
212 | 0 | { |
213 | 0 | if(bits < 512) |
214 | 0 | throw Invalid_Argument("generate_rsa_prime bits too small"); |
215 | 0 | |
216 | 0 | /* |
217 | 0 | * The restriction on coprime <= 64 bits is arbitrary but generally speaking |
218 | 0 | * very large RSA public exponents are a bad idea both for performance and due |
219 | 0 | * to attacks on small d. |
220 | 0 | */ |
221 | 0 | if(coprime <= 1 || coprime.is_even() || coprime.bits() > 64) |
222 | 0 | throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer"); |
223 | 0 | |
224 | 0 | const size_t MAX_ATTEMPTS = 32*1024; |
225 | 0 |
|
226 | 0 | while(true) |
227 | 0 | { |
228 | 0 | BigInt p(keygen_rng, bits); |
229 | 0 |
|
230 | 0 | // Force lowest and two top bits on |
231 | 0 | p.set_bit(bits - 1); |
232 | 0 | p.set_bit(bits - 2); |
233 | 0 | p.set_bit(0); |
234 | 0 |
|
235 | 0 | Prime_Sieve sieve(p, bits); |
236 | 0 |
|
237 | 0 | const word step = 2; |
238 | 0 |
|
239 | 0 | for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt) |
240 | 0 | { |
241 | 0 | p += step; |
242 | 0 |
|
243 | 0 | sieve.step(step); |
244 | 0 |
|
245 | 0 | if(sieve.passes() == false) |
246 | 0 | continue; |
247 | 0 | |
248 | 0 | Modular_Reducer mod_p(p); |
249 | 0 |
|
250 | 0 | /* |
251 | 0 | * Do a single primality test first before checking coprimality, since |
252 | 0 | * currently a single Miller-Rabin test is faster than computing modular |
253 | 0 | * inverse, and this eliminates almost all wasted modular inverses. |
254 | 0 | */ |
255 | 0 | if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, 1) == false) |
256 | 0 | continue; |
257 | 0 | |
258 | 0 | /* |
259 | 0 | * Check if p - 1 and coprime are relatively prime by computing the inverse. |
260 | 0 | * |
261 | 0 | * We avoid gcd here because that algorithm is not constant time. |
262 | 0 | * Modular inverse is (for odd modulus anyway). |
263 | 0 | * |
264 | 0 | * We earlier verified that coprime argument is odd. Thus the factors of 2 |
265 | 0 | * in (p - 1) cannot possibly be factors in coprime, so remove them from p - 1. |
266 | 0 | * Using an odd modulus allows the const time algorithm to be used. |
267 | 0 | * |
268 | 0 | * This assumes coprime < p - 1 which is always true for RSA. |
269 | 0 | */ |
270 | 0 | BigInt p1 = p - 1; |
271 | 0 | p1 >>= low_zero_bits(p1); |
272 | 0 | if(ct_inverse_mod_odd_modulus(coprime, p1).is_zero()) |
273 | 0 | { |
274 | 0 | BOTAN_DEBUG_ASSERT(gcd(p - 1, coprime) > 1); |
275 | 0 | continue; |
276 | 0 | } |
277 | 0 |
|
278 | 0 | BOTAN_DEBUG_ASSERT(gcd(p - 1, coprime) == 1); |
279 | 0 |
|
280 | 0 | if(p.bits() > bits) |
281 | 0 | break; |
282 | 0 | |
283 | 0 | const size_t t = miller_rabin_test_iterations(bits, prob, true); |
284 | 0 |
|
285 | 0 | if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, t) == true) |
286 | 0 | return p; |
287 | 0 | } |
288 | 0 | } |
289 | 0 | } |
290 | | |
291 | | /* |
292 | | * Generate a random safe prime |
293 | | */ |
294 | | BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits) |
295 | 0 | { |
296 | 0 | if(bits <= 64) |
297 | 0 | throw Invalid_Argument("random_safe_prime: Can't make a prime of " + |
298 | 0 | std::to_string(bits) + " bits"); |
299 | 0 | |
300 | 0 | BigInt q, p; |
301 | 0 | for(;;) |
302 | 0 | { |
303 | 0 | /* |
304 | 0 | Generate q == 2 (mod 3) |
305 | 0 |
|
306 | 0 | Otherwise [q == 1 (mod 3) case], 2*q+1 == 3 (mod 3) and not prime. |
307 | 0 |
|
308 | 0 | Initially allow a very high error prob (1/2**8) to allow for fast checks, |
309 | 0 | then if 2*q+1 turns out to be a prime go back and strongly check q. |
310 | 0 | */ |
311 | 0 | q = random_prime(rng, bits - 1, 0, 2, 3, 8); |
312 | 0 | p = (q << 1) + 1; |
313 | 0 |
|
314 | 0 | if(is_prime(p, rng, 128, true)) |
315 | 0 | { |
316 | 0 | // We did only a weak check before, go back and verify q before returning |
317 | 0 | if(is_prime(q, rng, 128, true)) |
318 | 0 | return p; |
319 | 0 | } |
320 | 0 | } |
321 | 0 | } |
322 | | |
323 | | } |