Botan 3.3.0
Crypto and TLS for C&
dsa_gen.cpp
Go to the documentation of this file.
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
10#include <botan/hash.h>
11#include <botan/numthry.h>
12#include <botan/reducer.h>
13#include <botan/rng.h>
14#include <botan/internal/fmt.h>
15
16namespace Botan {
17
18namespace {
19
20/*
21* Check if this size is allowed by FIPS 186-3
22*/
23bool fips186_3_valid_size(size_t pbits, size_t qbits) {
24 if(qbits == 160) {
25 return (pbits == 1024);
26 }
27
28 if(qbits == 224) {
29 return (pbits == 2048);
30 }
31
32 if(qbits == 256) {
33 return (pbits == 2048 || pbits == 3072);
34 }
35
36 return false;
37}
38
39// qbits assumed to be a valid size for FIPS param gen
40std::string hash_function_for(size_t qbits) {
41 if(qbits == 160) {
42 return "SHA-1";
43 }
44
45 return "SHA-" + std::to_string(qbits);
46}
47
48} // namespace
49
50/*
51* Attempt DSA prime generation with given seed
52*/
54 BigInt& p,
55 BigInt& q,
56 size_t pbits,
57 size_t qbits,
58 const std::vector<uint8_t>& seed_c,
59 size_t offset) {
60 if(!fips186_3_valid_size(pbits, qbits)) {
61 throw Invalid_Argument(fmt("FIPS 186-3 does not allow DSA domain parameters of {}/{} bits long", pbits, qbits));
62 }
63
64 if(seed_c.size() * 8 < qbits) {
65 throw Invalid_Argument(
66 fmt("Generating a DSA parameter set with a {} bit long q requires a seed at least as many bits long", qbits));
67 }
68
69 const std::string hash_name = hash_function_for(qbits);
70 auto hash = HashFunction::create_or_throw(hash_name);
71
72 const size_t HASH_SIZE = hash->output_length();
73
74 class Seed final {
75 public:
76 explicit Seed(const std::vector<uint8_t>& s) : m_seed(s) {}
77
78 const std::vector<uint8_t>& value() const { return m_seed; }
79
80 Seed& operator++() {
81 for(size_t j = m_seed.size(); j > 0; --j) {
82 if(++m_seed[j - 1]) {
83 break;
84 }
85 }
86 return (*this);
87 }
88
89 private:
90 std::vector<uint8_t> m_seed;
91 };
92
93 Seed seed(seed_c);
94
95 q.binary_decode(hash->process(seed.value()));
96 q.set_bit(qbits - 1);
97 q.set_bit(0);
98
99 if(!is_prime(q, rng, 128, true)) {
100 return false;
101 }
102
103 const size_t n = (pbits - 1) / (HASH_SIZE * 8), b = (pbits - 1) % (HASH_SIZE * 8);
104
105 BigInt X;
106 std::vector<uint8_t> V(HASH_SIZE * (n + 1));
107
108 Modular_Reducer mod_2q(2 * q);
109
110 for(size_t j = 0; j != 4 * pbits; ++j) {
111 for(size_t k = 0; k <= n; ++k) {
112 ++seed;
113 hash->update(seed.value());
114 hash->final(&V[HASH_SIZE * (n - k)]);
115 }
116
117 if(j >= offset) {
118 X.binary_decode(&V[HASH_SIZE - 1 - b / 8], V.size() - (HASH_SIZE - 1 - b / 8));
119 X.set_bit(pbits - 1);
120
121 p = X - (mod_2q.reduce(X) - 1);
122
123 if(p.bits() == pbits && is_prime(p, rng, 128, true)) {
124 return true;
125 }
126 }
127 }
128 return false;
129}
130
131/*
132* Generate DSA Primes
133*/
134std::vector<uint8_t> generate_dsa_primes(RandomNumberGenerator& rng, BigInt& p, BigInt& q, size_t pbits, size_t qbits) {
135 while(true) {
136 std::vector<uint8_t> seed(qbits / 8);
137 rng.randomize(seed.data(), seed.size());
138
139 if(generate_dsa_primes(rng, p, q, pbits, qbits, seed)) {
140 return seed;
141 }
142 }
143}
144
145} // namespace Botan
void binary_decode(const uint8_t buf[], size_t length)
Definition bigint.cpp:403
void set_bit(size_t n)
Definition bigint.h:434
size_t bits() const
Definition bigint.cpp:290
static std::unique_ptr< HashFunction > create_or_throw(std::string_view algo_spec, std::string_view provider="")
Definition hash.cpp:298
BigInt reduce(const BigInt &x) const
Definition reducer.cpp:37
void randomize(std::span< uint8_t > output)
Definition rng.h:52
int(* final)(unsigned char *, CTX *)
FE_25519 X
Definition ge.cpp:25
std::string fmt(std::string_view format, const T &... args)
Definition fmt.h:53
constexpr auto operator++(Strong< T, Tags... > &a, int)
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition numthry.cpp:357
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)
Definition dsa_gen.cpp:53