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
|
/*
* DSA Parameter Generation
* (C) 1999-2007 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
#include <botan/numthry.h>
#include <botan/hash.h>
#include <botan/reducer.h>
#include <botan/rng.h>
namespace Botan {
namespace {
/*
* Check if this size is allowed by FIPS 186-3
*/
bool fips186_3_valid_size(size_t pbits, size_t qbits)
{
if(qbits == 160)
return (pbits == 1024);
if(qbits == 224)
return (pbits == 2048);
if(qbits == 256)
return (pbits == 2048 || pbits == 3072);
return false;
}
}
/*
* Attempt DSA prime generation with given seed
*/
bool generate_dsa_primes(RandomNumberGenerator& rng,
BigInt& p, BigInt& q,
size_t pbits, size_t qbits,
const std::vector<uint8_t>& seed_c,
size_t offset)
{
if(!fips186_3_valid_size(pbits, qbits))
throw Invalid_Argument(
"FIPS 186-3 does not allow DSA domain parameters of " +
std::to_string(pbits) + "/" + std::to_string(qbits) + " bits long");
if(seed_c.size() * 8 < qbits)
throw Invalid_Argument(
"Generating a DSA parameter set with a " + std::to_string(qbits) +
" bit long q requires a seed at least as many bits long");
const std::string hash_name = "SHA-" + std::to_string(qbits);
std::unique_ptr<HashFunction> hash(HashFunction::create_or_throw(hash_name));
const size_t HASH_SIZE = hash->output_length();
class Seed final
{
public:
explicit Seed(const std::vector<uint8_t>& s) : m_seed(s) {}
const std::vector<uint8_t>& value() const { return m_seed; }
Seed& operator++()
{
for(size_t j = m_seed.size(); j > 0; --j)
if(++m_seed[j-1])
break;
return (*this);
}
private:
std::vector<uint8_t> m_seed;
};
Seed seed(seed_c);
q.binary_decode(hash->process(seed.value()));
q.set_bit(qbits-1);
q.set_bit(0);
if(!is_prime(q, rng, 128, true))
return false;
const size_t n = (pbits-1) / (HASH_SIZE * 8),
b = (pbits-1) % (HASH_SIZE * 8);
BigInt X;
std::vector<uint8_t> V(HASH_SIZE * (n+1));
Modular_Reducer mod_2q(2*q);
for(size_t j = 0; j != 4*pbits; ++j)
{
for(size_t k = 0; k <= n; ++k)
{
++seed;
hash->update(seed.value());
hash->final(&V[HASH_SIZE * (n-k)]);
}
if(j >= offset)
{
X.binary_decode(&V[HASH_SIZE - 1 - b/8],
V.size() - (HASH_SIZE - 1 - b/8));
X.set_bit(pbits-1);
p = X - (mod_2q.reduce(X) - 1);
if(p.bits() == pbits && is_prime(p, rng, 128, true))
return true;
}
}
return false;
}
/*
* Generate DSA Primes
*/
std::vector<uint8_t> generate_dsa_primes(RandomNumberGenerator& rng,
BigInt& p, BigInt& q,
size_t pbits, size_t qbits)
{
while(true)
{
std::vector<uint8_t> seed(qbits / 8);
rng.randomize(seed.data(), seed.size());
if(generate_dsa_primes(rng, p, q, pbits, qbits, seed))
return seed;
}
}
}
|
