/src/botan/src/lib/math/numbertheory/dsa_gen.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * DSA Parameter 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/internal/primality.h> |
9 | | #include <botan/numthry.h> |
10 | | #include <botan/hash.h> |
11 | | #include <botan/reducer.h> |
12 | | #include <botan/rng.h> |
13 | | |
14 | | namespace Botan { |
15 | | |
16 | | namespace { |
17 | | |
18 | | /* |
19 | | * Check if this size is allowed by FIPS 186-3 |
20 | | */ |
21 | | bool fips186_3_valid_size(size_t pbits, size_t qbits) |
22 | 0 | { |
23 | 0 | if(qbits == 160) |
24 | 0 | return (pbits == 1024); |
25 | | |
26 | 0 | if(qbits == 224) |
27 | 0 | return (pbits == 2048); |
28 | | |
29 | 0 | if(qbits == 256) |
30 | 0 | return (pbits == 2048 || pbits == 3072); |
31 | | |
32 | 0 | return false; |
33 | 0 | } |
34 | | |
35 | | } |
36 | | |
37 | | /* |
38 | | * Attempt DSA prime generation with given seed |
39 | | */ |
40 | | bool generate_dsa_primes(RandomNumberGenerator& rng, |
41 | | BigInt& p, BigInt& q, |
42 | | size_t pbits, size_t qbits, |
43 | | const std::vector<uint8_t>& seed_c, |
44 | | size_t offset) |
45 | 0 | { |
46 | 0 | if(!fips186_3_valid_size(pbits, qbits)) |
47 | 0 | throw Invalid_Argument( |
48 | 0 | "FIPS 186-3 does not allow DSA domain parameters of " + |
49 | 0 | std::to_string(pbits) + "/" + std::to_string(qbits) + " bits long"); |
50 | | |
51 | 0 | if(seed_c.size() * 8 < qbits) |
52 | 0 | throw Invalid_Argument( |
53 | 0 | "Generating a DSA parameter set with a " + std::to_string(qbits) + |
54 | 0 | " bit long q requires a seed at least as many bits long"); |
55 | | |
56 | 0 | const std::string hash_name = "SHA-" + std::to_string(qbits); |
57 | 0 | std::unique_ptr<HashFunction> hash(HashFunction::create_or_throw(hash_name)); |
58 | |
|
59 | 0 | const size_t HASH_SIZE = hash->output_length(); |
60 | |
|
61 | 0 | class Seed final |
62 | 0 | { |
63 | 0 | public: |
64 | 0 | explicit Seed(const std::vector<uint8_t>& s) : m_seed(s) {} |
65 | |
|
66 | 0 | const std::vector<uint8_t>& value() const { return m_seed; } |
67 | |
|
68 | 0 | Seed& operator++() |
69 | 0 | { |
70 | 0 | for(size_t j = m_seed.size(); j > 0; --j) |
71 | 0 | if(++m_seed[j-1]) |
72 | 0 | break; |
73 | 0 | return (*this); |
74 | 0 | } |
75 | 0 | private: |
76 | 0 | std::vector<uint8_t> m_seed; |
77 | 0 | }; |
78 | |
|
79 | 0 | Seed seed(seed_c); |
80 | |
|
81 | 0 | q.binary_decode(hash->process(seed.value())); |
82 | 0 | q.set_bit(qbits-1); |
83 | 0 | q.set_bit(0); |
84 | |
|
85 | 0 | if(!is_prime(q, rng, 128, true)) |
86 | 0 | return false; |
87 | | |
88 | 0 | const size_t n = (pbits-1) / (HASH_SIZE * 8), |
89 | 0 | b = (pbits-1) % (HASH_SIZE * 8); |
90 | |
|
91 | 0 | BigInt X; |
92 | 0 | std::vector<uint8_t> V(HASH_SIZE * (n+1)); |
93 | |
|
94 | 0 | Modular_Reducer mod_2q(2*q); |
95 | |
|
96 | 0 | for(size_t j = 0; j != 4*pbits; ++j) |
97 | 0 | { |
98 | 0 | for(size_t k = 0; k <= n; ++k) |
99 | 0 | { |
100 | 0 | ++seed; |
101 | 0 | hash->update(seed.value()); |
102 | 0 | hash->final(&V[HASH_SIZE * (n-k)]); |
103 | 0 | } |
104 | |
|
105 | 0 | if(j >= offset) |
106 | 0 | { |
107 | 0 | X.binary_decode(&V[HASH_SIZE - 1 - b/8], |
108 | 0 | V.size() - (HASH_SIZE - 1 - b/8)); |
109 | 0 | X.set_bit(pbits-1); |
110 | |
|
111 | 0 | p = X - (mod_2q.reduce(X) - 1); |
112 | |
|
113 | 0 | if(p.bits() == pbits && is_prime(p, rng, 128, true)) |
114 | 0 | return true; |
115 | 0 | } |
116 | 0 | } |
117 | 0 | return false; |
118 | 0 | } |
119 | | |
120 | | /* |
121 | | * Generate DSA Primes |
122 | | */ |
123 | | std::vector<uint8_t> generate_dsa_primes(RandomNumberGenerator& rng, |
124 | | BigInt& p, BigInt& q, |
125 | | size_t pbits, size_t qbits) |
126 | 0 | { |
127 | 0 | while(true) |
128 | 0 | { |
129 | 0 | std::vector<uint8_t> seed(qbits / 8); |
130 | 0 | rng.randomize(seed.data(), seed.size()); |
131 | |
|
132 | 0 | if(generate_dsa_primes(rng, p, q, pbits, qbits, seed)) |
133 | 0 | return seed; |
134 | 0 | } |
135 | 0 | } |
136 | | |
137 | | } |