Botan  2.6.0
Crypto and TLS for C++11
make_prm.cpp
Go to the documentation of this file.
1 /*
2 * Prime Generation
3 * (C) 1999-2007,2018 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 <algorithm>
12 
13 namespace Botan {
14 
15 /*
16 * Generate a random prime
17 */
19  size_t bits, const BigInt& coprime,
20  size_t equiv, size_t modulo,
21  size_t prob)
22  {
23  if(coprime.is_negative())
24  {
25  throw Invalid_Argument("random_prime: coprime must be >= 0");
26  }
27  if(modulo == 0)
28  {
29  throw Invalid_Argument("random_prime: Invalid modulo value");
30  }
31 
32  equiv %= modulo;
33 
34  if(equiv == 0)
35  throw Invalid_Argument("random_prime Invalid value for equiv/modulo");
36 
37  // Handle small values:
38  if(bits <= 1)
39  {
40  throw Invalid_Argument("random_prime: Can't make a prime of " +
41  std::to_string(bits) + " bits");
42  }
43  else if(bits == 2)
44  {
45  return ((rng.next_byte() % 2) ? 2 : 3);
46  }
47  else if(bits == 3)
48  {
49  return ((rng.next_byte() % 2) ? 5 : 7);
50  }
51  else if(bits == 4)
52  {
53  return ((rng.next_byte() % 2) ? 11 : 13);
54  }
55  else if(bits <= 16)
56  {
57  for(;;)
58  {
59  size_t idx = make_uint16(rng.next_byte(), rng.next_byte()) % PRIME_TABLE_SIZE;
60  uint16_t small_prime = PRIMES[idx];
61 
62  if(high_bit(small_prime) == bits)
63  return small_prime;
64  }
65  }
66 
68  const size_t MAX_ATTEMPTS = 32*1024;
69 
70  while(true)
71  {
72  BigInt p(rng, bits);
73 
74  // Force lowest and two top bits on
75  p.set_bit(bits - 1);
76  p.set_bit(bits - 2);
77  p.set_bit(0);
78 
79  // Force p to be equal to equiv mod modulo
80  p += (modulo - (p % modulo)) + equiv;
81 
82  for(size_t i = 0; i != sieve.size(); ++i)
83  sieve[i] = static_cast<uint16_t>(p % PRIMES[i]);
84 
85  size_t counter = 0;
86  while(true)
87  {
88  ++counter;
89 
90  if(counter > MAX_ATTEMPTS)
91  {
92  break; // don't try forever, choose a new starting point
93  }
94 
95  p += modulo;
96 
97  if(p.bits() > bits)
98  break;
99 
100  // Now that p is updated, update the sieve
101  for(size_t i = 0; i != sieve.size(); ++i)
102  {
103  sieve[i] = (sieve[i] + modulo) % PRIMES[i];
104  }
105 
106  bool passes_sieve = true;
107  for(size_t i = 0; passes_sieve && (i != sieve.size()); ++i)
108  {
109  /*
110  In this case, p is a multiple of PRIMES[i]
111  */
112  if(sieve[i] == 0)
113  passes_sieve = false;
114 
115  /*
116  In this case, 2*p+1 will be a multiple of PRIMES[i]
117 
118  So if generating a safe prime, we want to avoid this value
119  because 2*p+1 will not be useful. Since the check is cheap to
120  do and doesn't seem to affect the overall distribution of the
121  generated primes overmuch it's used in all cases.
122 
123  See "Safe Prime Generation with a Combined Sieve" M. Wiener
124  https://eprint.iacr.org/2003/186.pdf
125  */
126  if(sieve[i] == (PRIMES[i] - 1) / 2)
127  passes_sieve = false;
128  }
129 
130  if(!passes_sieve)
131  continue;
132 
133  if(coprime > 0 && gcd(p - 1, coprime) != 1)
134  continue;
135 
136  if(is_prime(p, rng, prob, true))
137  return p;
138  }
139  }
140  }
141 
142 /*
143 * Generate a random safe prime
144 */
146  {
147  if(bits <= 64)
148  throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
149  std::to_string(bits) + " bits");
150 
151  BigInt q, p;
152  for(;;)
153  {
154  /*
155  Generate q == 2 (mod 3)
156 
157  Otherwise [q == 1 (mod 3) case], 2*q+1 == 3 (mod 3) and not prime.
158  */
159  q = random_prime(rng, bits - 1, 1, 2, 3, 8);
160  p = (q << 1) + 1;
161 
162  if(is_prime(p, rng, 128, true))
163  {
164  // We did only a weak check before, go back and verify q before returning
165  if(is_prime(q, rng, 128, true))
166  return p;
167  }
168 
169  }
170  }
171 
172 }
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:254
bool is_negative() const
Definition: bigint.h:413
const uint16_t PRIMES[]
Definition: primes.cpp:12
BigInt gcd(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:47
size_t bits() const
Definition: bigint.cpp:216
void set_bit(size_t n)
Definition: bigint.cpp:189
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:482
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:145
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:145
size_t high_bit(T n)
Definition: bit_ops.h:37
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:18
uint16_t make_uint16(uint8_t i0, uint8_t i1)
Definition: loadstor.h:52
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88