Botan  2.4.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 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 <algorithm>
11 
12 namespace Botan {
13 
14 /*
15 * Generate a random prime
16 */
18  size_t bits, const BigInt& coprime,
19  size_t equiv, size_t modulo)
20  {
21  if(coprime <= 0)
22  {
23  throw Invalid_Argument("random_prime: coprime must be > 0");
24  }
25  if(modulo % 2 == 1 || modulo == 0)
26  {
27  throw Invalid_Argument("random_prime: Invalid modulo value");
28  }
29  if(equiv >= modulo || equiv % 2 == 0)
30  {
31  throw Invalid_Argument("random_prime: equiv must be < modulo, and odd");
32  }
33 
34  // Handle small values:
35  if(bits <= 1)
36  {
37  throw Invalid_Argument("random_prime: Can't make a prime of " +
38  std::to_string(bits) + " bits");
39  }
40  else if(bits == 2)
41  {
42  return ((rng.next_byte() % 2) ? 2 : 3);
43  }
44  else if(bits == 3)
45  {
46  return ((rng.next_byte() % 2) ? 5 : 7);
47  }
48  else if(bits == 4)
49  {
50  return ((rng.next_byte() % 2) ? 11 : 13);
51  }
52 
53  while(true)
54  {
55  BigInt p(rng, bits);
56 
57  // Force lowest and two top bits on
58  p.set_bit(bits - 1);
59  p.set_bit(bits - 2);
60  p.set_bit(0);
61 
62  if(p % modulo != equiv)
63  p += (modulo - p % modulo) + equiv;
64 
65  const size_t sieve_size = std::min(bits / 2, PRIME_TABLE_SIZE);
66  secure_vector<uint16_t> sieve(sieve_size);
67 
68  for(size_t j = 0; j != sieve.size(); ++j)
69  sieve[j] = static_cast<uint16_t>(p % PRIMES[j]);
70 
71  size_t counter = 0;
72  while(true)
73  {
74  ++counter;
75 
76  if(counter >= 4096)
77  {
78  break; // don't try forever, choose a new starting point
79  }
80 
81  p += modulo;
82 
83  if(p.bits() > bits)
84  break;
85 
86  bool passes_sieve = true;
87  for(size_t j = 0; j != sieve.size(); ++j)
88  {
89  sieve[j] = (sieve[j] + modulo) % PRIMES[j];
90  if(sieve[j] == 0)
91  {
92  passes_sieve = false;
93  break;
94  }
95  }
96 
97  if(!passes_sieve)
98  continue;
99 
100  if(gcd(p - 1, coprime) != 1)
101  continue;
102 
103  if(is_prime(p, rng, 128, true))
104  {
105  return p;
106  }
107  }
108  }
109  }
110 
111 /*
112 * Generate a random safe prime
113 */
115  {
116  if(bits <= 64)
117  throw Invalid_Argument("random_safe_prime: Can't make a prime of " +
118  std::to_string(bits) + " bits");
119 
120  BigInt p;
121  do
122  p = (random_prime(rng, bits - 1) << 1) + 1;
123  while(!is_prime(p, rng, 128, true));
124 
125  return p;
126  }
127 
128 }
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:240
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:183
void set_bit(size_t n)
Definition: bigint.cpp:156
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:455
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:108
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo)
Definition: make_prm.cpp:17
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:114
Definition: alg_id.cpp:13
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88