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
173
174
175
176
177
|
/*************************************************
* Prime Generation Source File *
* (C) 1999-2006 The Botan Project *
*************************************************/
#include <botan/numthry.h>
#include <botan/libstate.h>
#include <botan/lookup.h>
#include <botan/bit_ops.h>
#include <botan/parsing.h>
#include <botan/rng.h>
#include <algorithm>
#include <memory>
namespace Botan {
namespace {
/*************************************************
* Increment the seed by one *
*************************************************/
void increment(SecureVector<byte>& seed)
{
for(u32bit j = seed.size(); j > 0; --j)
if(++seed[j-1])
break;
}
}
/*************************************************
* Attempt DSA prime generation with given seed *
*************************************************/
bool generate_dsa_primes(BigInt& p, BigInt& q, const byte const_seed[],
u32bit seed_len, u32bit pbits, u32bit counter_start)
{
if(seed_len < 20)
throw Invalid_Argument("DSA prime generation needs a seed "
"at least 160 bits long");
if((pbits % 64 != 0) || (pbits > 1024) || (pbits < 512))
throw Invalid_Argument("DSA prime generation algorithm does not support "
"prime size " + to_string(pbits));
std::auto_ptr<HashFunction> sha1(get_hash("SHA-1"));
SecureVector<byte> seed(const_seed, seed_len);
SecureVector<byte> qhash = sha1->process(seed);
increment(seed);
SecureVector<byte> qhash2 = sha1->process(seed);
xor_buf(qhash, qhash2, qhash.size());
qhash[0] |= 0x80;
qhash[19] |= 0x01;
q.binary_decode(qhash, qhash.size());
if(!is_prime(q))
return false;
global_state().pulse(PRIME_FOUND);
u32bit n = (pbits-1) / 160, b = (pbits-1) % 160;
SecureVector<byte> W(20 * (n+1));
BigInt X;
for(u32bit j = 0; j != counter_start; ++j)
for(u32bit k = 0; k != n + 1; ++k)
increment(seed);
for(u32bit j = 0; j != 4096 - counter_start; ++j)
{
global_state().pulse(PRIME_SEARCHING);
for(u32bit k = 0; k != n + 1; ++k)
{
increment(seed);
sha1->update(seed);
sha1->final(W + 20 * (n-k));
}
X.binary_decode(W + (20 - 1 - b/8), W.size() - (20 - 1 - b/8));
X.set_bit(pbits-1);
p = X - (X % (2*q) - 1);
if(p.bits() == pbits && is_prime(p))
{
global_state().pulse(PRIME_FOUND);
return true;
}
}
return false;
}
/*************************************************
* Generate DSA Primes *
*************************************************/
SecureVector<byte> generate_dsa_primes(BigInt& p, BigInt& q, u32bit pbits)
{
SecureVector<byte> seed(20);
while(true)
{
Global_RNG::randomize(seed, seed.size());
global_state().pulse(PRIME_SEARCHING);
if(generate_dsa_primes(p, q, seed, seed.size(), pbits))
return seed;
}
}
/*************************************************
* Generate a random prime *
*************************************************/
BigInt random_prime(u32bit bits, const BigInt& coprime,
u32bit equiv, u32bit modulo)
{
if(bits < 48)
throw Invalid_Argument("random_prime: Can't make a prime of " +
to_string(bits) + " bits");
if(coprime <= 0)
throw Invalid_Argument("random_prime: coprime must be > 0");
if(modulo % 2 == 1 || modulo == 0)
throw Invalid_Argument("random_prime: Invalid modulo value");
if(equiv >= modulo || equiv % 2 == 0)
throw Invalid_Argument("random_prime: equiv must be < modulo, and odd");
while(true)
{
global_state().pulse(PRIME_SEARCHING);
BigInt p = random_integer(bits);
p.set_bit(bits - 2);
p.set_bit(0);
if(p % modulo != equiv)
p += (modulo - p % modulo) + equiv;
const u32bit sieve_size = std::min(bits / 2, PRIME_TABLE_SIZE);
SecureVector<u32bit> sieve(sieve_size);
for(u32bit j = 0; j != sieve.size(); ++j)
{
sieve[j] = p % PRIMES[j];
global_state().pulse(PRIME_SIEVING);
}
u32bit counter = 0;
while(true)
{
if(counter == 4096 || p.bits() > bits)
break;
global_state().pulse(PRIME_SEARCHING);
bool passes_sieve = true;
++counter;
p += modulo;
for(u32bit j = 0; j != sieve.size(); ++j)
{
sieve[j] = (sieve[j] + modulo) % PRIMES[j];
global_state().pulse(PRIME_SIEVING);
if(sieve[j] == 0)
passes_sieve = false;
}
if(!passes_sieve || gcd(p - 1, coprime) != 1)
continue;
global_state().pulse(PRIME_PASSED_SIEVE);
if(passes_mr_tests(p))
{
global_state().pulse(PRIME_FOUND);
return p;
}
}
}
}
}
|
