Coverage Report

Created: 2021-05-04 09:02

/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
}