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