Botan 2.19.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/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
16namespace Botan {
17
18namespace {
19
20class 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 {
26 for(size_t i = 0; i != m_sieve.size(); ++i)
27 m_sieve[i] = static_cast<uint16_t>(init_value % PRIMES[i]);
28 }
29
30 void step(word increment)
31 {
32 for(size_t i = 0; i != m_sieve.size(); ++i)
33 {
34 m_sieve[i] = (m_sieve[i] + increment) % PRIMES[i];
35 }
36 }
37
38 bool passes(bool check_2p1 = false) const
39 {
40 for(size_t i = 0; i != m_sieve.size(); ++i)
41 {
42 /*
43 In this case, p is a multiple of PRIMES[i]
44 */
45 if(m_sieve[i] == 0)
46 return false;
47
48 if(check_2p1)
49 {
50 /*
51 In this case, 2*p+1 will be a multiple of PRIMES[i]
52
53 So if potentially generating a safe prime, we want to
54 avoid this value because 2*p+1 will certainly not be prime.
55
56 See "Safe Prime Generation with a Combined Sieve" M. Wiener
57 https://eprint.iacr.org/2003/186.pdf
58 */
59 if(m_sieve[i] == (PRIMES[i] - 1) / 2)
60 return false;
61 }
62 }
63
64 return true;
65 }
66
67 private:
68 std::vector<uint16_t> m_sieve;
69 };
70
71}
72
73
74/*
75* Generate a random prime
76*/
78 size_t bits, const BigInt& coprime,
79 size_t equiv, size_t modulo,
80 size_t prob)
81 {
82 if(bits <= 1)
83 {
84 throw Invalid_Argument("random_prime: Can't make a prime of " +
85 std::to_string(bits) + " bits");
86 }
87 if(coprime.is_negative() || (!coprime.is_zero() && coprime.is_even()) || coprime.bits() >= bits)
88 {
89 throw Invalid_Argument("random_prime: invalid coprime");
90 }
91 if(modulo == 0)
92 {
93 throw Invalid_Argument("random_prime: Invalid modulo value");
94 }
95
96 equiv %= modulo;
97
98 if(equiv == 0)
99 throw Invalid_Argument("random_prime Invalid value for equiv/modulo");
100
101 // Handle small values:
102
103 if(bits <= 16)
104 {
105 if(equiv != 1 || modulo != 2 || coprime != 0)
106 throw Not_Implemented("random_prime equiv/modulo/coprime options not usable for small primes");
107
108 if(bits == 2)
109 {
110 return ((rng.next_byte() % 2) ? 2 : 3);
111 }
112 else if(bits == 3)
113 {
114 return ((rng.next_byte() % 2) ? 5 : 7);
115 }
116 else if(bits == 4)
117 {
118 return ((rng.next_byte() % 2) ? 11 : 13);
119 }
120 else
121 {
122 for(;;)
123 {
124 // This is slightly biased, but for small primes it does not seem to matter
125 uint8_t b[4];
126 rng.randomize(b, 4);
127 const size_t idx = load_le<uint32_t>(b, 0) % PRIME_TABLE_SIZE;
128 const uint16_t small_prime = PRIMES[idx];
129
130 if(high_bit(small_prime) == bits)
131 return small_prime;
132 }
133 }
134 }
135
136 const size_t MAX_ATTEMPTS = 32*1024;
137
138 const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);
139
140 while(true)
141 {
142 BigInt p(rng, bits);
143
144 // Force lowest and two top bits on
145 p.set_bit(bits - 1);
146 p.set_bit(bits - 2);
147 p.set_bit(0);
148
149 // Force p to be equal to equiv mod modulo
150 p += (modulo - (p % modulo)) + equiv;
151
152 Prime_Sieve sieve(p, bits);
153
154 for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt)
155 {
156 p += modulo;
157
158 sieve.step(modulo);
159
160 // p can be even if modulo is odd, continue on in that case
161 if(p.is_even() || sieve.passes(true) == false)
162 continue;
163
164 Modular_Reducer mod_p(p);
165
166 if(coprime > 1)
167 {
168 /*
169 First do a single M-R iteration to quickly elimate most non-primes,
170 before doing the coprimality check which is expensive
171 */
172 if(is_miller_rabin_probable_prime(p, mod_p, rng, 1) == false)
173 continue;
174
175 /*
176 * Check if p - 1 and coprime are relatively prime, using gcd.
177 * The gcd computation is const-time
178 */
179 if(gcd(p - 1, coprime) > 1)
180 continue;
181 }
182
183 if(p.bits() > bits)
184 break;
185
186 if(is_miller_rabin_probable_prime(p, mod_p, rng, mr_trials) == false)
187 continue;
188
189 if(prob > 32 && !is_lucas_probable_prime(p, mod_p))
190 continue;
191
192 return p;
193 }
194 }
195 }
196
198 RandomNumberGenerator& prime_test_rng,
199 size_t bits,
200 const BigInt& coprime,
201 size_t prob)
202 {
203 if(bits < 512)
204 throw Invalid_Argument("generate_rsa_prime bits too small");
205
206 /*
207 * The restriction on coprime <= 64 bits is arbitrary but generally speaking
208 * very large RSA public exponents are a bad idea both for performance and due
209 * to attacks on small d.
210 */
211 if(coprime <= 1 || coprime.is_even() || coprime.bits() > 64)
212 throw Invalid_Argument("generate_rsa_prime coprime must be small odd positive integer");
213
214 const size_t MAX_ATTEMPTS = 32*1024;
215
216 const size_t mr_trials = miller_rabin_test_iterations(bits, prob, true);
217
218 while(true)
219 {
220 BigInt p(keygen_rng, bits);
221
222 // Force high two bits so multiplication always results in expected n bit integer
223 p.set_bit(bits - 1);
224 p.set_bit(bits - 2);
225 p.set_bit(0);
226
227 const word step = 2;
228
229 Prime_Sieve sieve(p, bits);
230
231 for(size_t attempt = 0; attempt <= MAX_ATTEMPTS; ++attempt)
232 {
233 p += step;
234
235 sieve.step(step);
236
237 if(sieve.passes() == false)
238 continue;
239
240 Modular_Reducer mod_p(p);
241
242 /*
243 * Do a single primality test first before checking coprimality, since
244 * currently a single Miller-Rabin test is faster than computing gcd,
245 * and this eliminates almost all wasted gcd computations.
246 */
247 if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, 1) == false)
248 continue;
249
250 /*
251 * Check if p - 1 and coprime are relatively prime.
252 */
253 if(gcd(p - 1, coprime) > 1)
254 continue;
255
256 if(p.bits() > bits)
257 break;
258
259 if(is_miller_rabin_probable_prime(p, mod_p, prime_test_rng, mr_trials) == true)
260 return p;
261 }
262 }
263 }
264
265/*
266* Generate a random safe prime
267*/
269 {
270 if(bits <= 64)
271 throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
272 std::to_string(bits) + " bits");
273
274 const size_t error_bound = 128;
275
276 BigInt q, p;
277 for(;;)
278 {
279 /*
280 Generate q == 2 (mod 3), since otherwise [in the case of q == 1 (mod 3)],
281 2*q+1 == 3 (mod 3) and so certainly not prime.
282 */
283 q = random_prime(rng, bits - 1, 0, 2, 3, error_bound);
284 p = (q << 1) + 1;
285
286 if(is_prime(p, rng, error_bound, true))
287 {
288 return p;
289 }
290 }
291 }
292
293}
void set_bit(size_t n)
Definition: bigint.h:430
size_t bits() const
Definition: bigint.cpp:296
bool is_even() const
Definition: bigint.h:403
bool is_zero() const
Definition: bigint.h:421
bool is_negative() const
Definition: bigint.h:527
virtual void randomize(uint8_t output[], size_t length)=0
int(* final)(unsigned char *, CTX *)
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:213
Definition: alg_id.cpp:13
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo, size_t prob)
Definition: make_prm.cpp:77
uint32_t load_le< uint32_t >(const uint8_t in[], size_t off)
Definition: loadstor.h:198
const uint16_t PRIMES[]
Definition: primes.cpp:12
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:287
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:228
bool is_miller_rabin_probable_prime(const BigInt &n, const Modular_Reducer &mod_n, RandomNumberGenerator &rng, size_t test_iterations)
Definition: primality.cpp:143
BigInt generate_rsa_prime(RandomNumberGenerator &keygen_rng, RandomNumberGenerator &prime_test_rng, size_t bits, const BigInt &coprime, size_t prob)
Definition: make_prm.cpp:197
BigInt gcd(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:81
size_t miller_rabin_test_iterations(size_t n_bits, size_t prob, bool random)
Definition: primality.cpp:165
size_t high_bit(T n)
Definition: bit_ops.h:55
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:268
bool is_lucas_probable_prime(const BigInt &C, const Modular_Reducer &mod_C)
Definition: primality.cpp:17
Definition: bigint.h:1143