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