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
|
/*************************************************
* DSA Parameter Generation Source File *
* (C) 1999-2007 The Botan Project *
*************************************************/
#include <botan/dl_group.h>
#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;
}
/*************************************************
* Check if this size is allowed by FIPS 186-3 *
*************************************************/
bool fips186_3_valid_size(u32bit pbits, u32bit qbits)
{
if(pbits == 1024 && qbits == 160)
return true;
if(pbits == 2048 && qbits == 256)
return true;
if(pbits == 3072 && qbits == 256)
return true;
return false;
}
}
/*************************************************
* Attempt DSA prime generation with given seed *
*************************************************/
bool DL_Group::generate_dsa_primes(BigInt& p, BigInt& q,
u32bit pbits, u32bit qbits,
const MemoryRegion<byte>& seed_c)
{
if(!fips186_3_valid_size(pbits, qbits))
throw Invalid_Argument(
"FIPS 186-3 does not allow DSA domain parameters of " +
to_string(pbits) + "/" + to_string(qbits) + " bits long");
if(seed_c.size() * 8 < qbits)
throw Invalid_Argument(
"Generating a DSA parameter set with a " + to_string(qbits) +
"long q requires a seed at least as many bits long");
std::auto_ptr<HashFunction> hash(get_hash("SHA-" + to_string(qbits)));
const u32bit HASH_SIZE = hash->OUTPUT_LENGTH;
SecureVector<byte> seed = seed_c;
q.binary_decode(hash->process(seed));
q.set_bit(qbits-1);
q.set_bit(0);
if(!is_prime(q))
return false;
global_state().pulse(PRIME_FOUND);
const u32bit n = (pbits-1) / (HASH_SIZE * 8), b = (pbits-1) % (HASH_SIZE * 8);
BigInt X;
SecureVector<byte> V(HASH_SIZE * (n+1));
for(u32bit j = 0; j != 4096; ++j)
{
global_state().pulse(PRIME_SEARCHING);
for(u32bit k = 0; k <= n; ++k)
{
increment(seed);
hash->update(seed);
hash->final(V + HASH_SIZE * (n-k));
}
X.binary_decode(V + (HASH_SIZE - 1 - b/8), V.size() - (HASH_SIZE - 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> DL_Group::generate_dsa_primes(BigInt& p, BigInt& q,
u32bit pbits, u32bit qbits)
{
SecureVector<byte> seed(qbits/8);
while(true)
{
Global_RNG::randomize(seed, seed.size());
global_state().pulse(PRIME_SEARCHING);
if(generate_dsa_primes(p, q, pbits, qbits, seed))
return seed;
}
}
}
|
