Botan 2.1.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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/parsing.h>
10 #include <algorithm>
11
12 namespace Botan {
13
14 /*
15 * Generate a random prime
16 */
17 BigInt random_prime(RandomNumberGenerator& rng,
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 */
114 BigInt random_safe_prime(RandomNumberGenerator& rng, size_t bits)
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 }
Botan::PRIME_TABLE_SIZE
const size_t PRIME_TABLE_SIZE
Definition: numthry.h:240
Botan::Invalid_Argument
Definition: exceptn.h:34
Botan::RandomNumberGenerator::next_byte
uint8_t next_byte()
Definition: rng.h:144
Botan::PRIMES
const uint16_t BOTAN_DLL PRIMES[]
Definition: primes.cpp:12
Botan::BigInt
Definition: bigint.h:23
Botan::RandomNumberGenerator
Definition: rng.h:25
Botan::is_prime
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition: numthry.cpp:441
Botan::BigInt::set_bit
void set_bit(size_t n)
Definition: bigint.cpp:157
Botan::gcd
BigInt gcd(const BigInt &a, const BigInt &b)
Definition: numthry.cpp:46
Botan::ASN1::to_string
std::string to_string(const BER_Object &obj)
Definition: asn1_obj.cpp:47
Botan::BigInt::bits
size_t bits() const
Definition: bigint.cpp:184
Botan::secure_vector
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:121
Botan
Definition: alg_id.cpp:13
Botan::random_safe_prime
BigInt random_safe_prime(RandomNumberGenerator &rng, size_t bits)
Definition: make_prm.cpp:114
Botan::CT::min
T min(T a, T b)
Definition: ct_utils.h:180
Botan::random_prime
BigInt random_prime(RandomNumberGenerator &rng, size_t bits, const BigInt &coprime, size_t equiv, size_t modulo)
Definition: make_prm.cpp:17