Botan 3.14.1
Crypto and TLS for C&
dsa.cpp
Go to the documentation of this file.
1/*
2* DSA
3* (C) 1999-2010,2014,2016,2023 Jack Lloyd
4* (C) 2016 René Korthaus
5*
6* Botan is released under the Simplified BSD License (see license.txt)
7*/
8
9#include <botan/dsa.h>
10
11#include <botan/exceptn.h>
12#include <botan/pk_options_readers.h>
13#include <botan/internal/buffer_stuffer.h>
14#include <botan/internal/ct_utils.h>
15#include <botan/internal/divide.h>
16#include <botan/internal/dl_scheme.h>
17#include <botan/internal/keypair.h>
18#include <botan/internal/pk_ops_impl.h>
19#include <botan/internal/pk_options_impl.h>
20
21#if defined(BOTAN_HAS_RFC6979_GENERATOR)
22 #include <botan/internal/rfc6979.h>
23#endif
24
25namespace Botan {
26
27namespace {
28
29void check_dsa_group(const DL_Group& group) {
30 if(!group.has_q()) {
31 throw Decoding_Error("Q parameter must be set for DSA");
32 }
33
34 const size_t q_bits = group.q_bits();
35 const size_t p_bits = group.p_bits();
36
37 // TODO(Botan4) restrict to exactly the parameter sizes from FIPS 186-4
38 // (1024,160), (2048,224), (2048,256), or (3072,256)
39
40 if(q_bits < 160 || q_bits > 256) {
41 throw Decoding_Error("Invalid DSA q parameter size");
42 }
43 if(p_bits < 512 || p_bits > 3072) {
44 throw Decoding_Error("Invalid DSA p parameter size");
45 }
46}
47
48} // namespace
49
51 return m_public_key->group().q_bytes();
52}
53
55 return m_public_key->estimated_strength();
56}
57
59 return m_public_key->p_bits();
60}
61
62const BigInt& DSA_PublicKey::get_int_field(std::string_view field) const {
63 return m_public_key->get_int_field(algo_name(), field);
64}
65
69
70std::vector<uint8_t> DSA_PublicKey::raw_public_key_bits() const {
71 return m_public_key->public_key_as_bytes();
72}
73
74std::vector<uint8_t> DSA_PublicKey::public_key_bits() const {
75 return m_public_key->DER_encode();
76}
77
78bool DSA_PublicKey::check_key(RandomNumberGenerator& rng, bool strong) const {
79 return m_public_key->check_key(rng, strong);
80}
81
82std::unique_ptr<Private_Key> DSA_PublicKey::generate_another(RandomNumberGenerator& rng) const {
83 return std::make_unique<DSA_PrivateKey>(rng, m_public_key->group());
84}
85
86DSA_PublicKey::DSA_PublicKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
87 m_public_key = std::make_shared<DL_PublicKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_57);
88
89 check_dsa_group(m_public_key->group());
90}
91
93 m_public_key = std::make_shared<DL_PublicKey>(group, y);
94
95 check_dsa_group(m_public_key->group());
96}
97
99 check_dsa_group(group);
100
101 m_private_key = std::make_shared<DL_PrivateKey>(group, rng);
102 m_public_key = m_private_key->public_key();
103}
104
106 check_dsa_group(group);
107
108 m_private_key = std::make_shared<DL_PrivateKey>(group, x);
109 m_public_key = m_private_key->public_key();
110}
111
112DSA_PrivateKey::DSA_PrivateKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
113 m_private_key = std::make_shared<DL_PrivateKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_57);
114 m_public_key = m_private_key->public_key();
115
116 check_dsa_group(m_private_key->group());
117}
118
120 if(!m_private_key->check_key(rng, strong)) {
121 return false;
122 }
123
124 if(!strong) {
125 return true;
126 }
127
128 return KeyPair::signature_consistency_check(rng, *this, "SHA-256");
129}
130
132 return m_private_key->DER_encode();
133}
134
136 return m_private_key->raw_private_key_bits();
137}
138
139const BigInt& DSA_PrivateKey::get_int_field(std::string_view field) const {
140 return m_private_key->get_int_field(algo_name(), field);
141}
142
143std::unique_ptr<Public_Key> DSA_PrivateKey::public_key() const {
144 // can't use make_unique here due to private constructor
145 return std::unique_ptr<DSA_PublicKey>(new DSA_PublicKey(m_public_key));
146}
147
148namespace {
149
150/**
151* Object that can create a DSA signature
152*/
153class DSA_Signature_Operation final : public PK_Ops::Signature_with_Hash {
154 public:
155 DSA_Signature_Operation(const std::shared_ptr<const DL_PrivateKey>& key,
156 const PK_Signature_Options_Reader& options,
158 PK_Ops::Signature_with_Hash(options), m_key(key), m_deterministic(options.using_deterministic_signature()) {
159#if !defined(BOTAN_HAS_RFC6979_GENERATOR)
160 if(m_deterministic) {
161 throw Not_Implemented("Deterministic DSA signatures require RFC 6979 support");
162 }
163#endif
164 m_b = BigInt::random_integer(rng, BigInt::from_s32(2), m_key->group().get_q());
165 CT::poison(m_b);
166 m_b_inv = m_key->group().inverse_mod_q(m_b);
167 CT::unpoison_all(m_b, m_b_inv);
168 }
169
170 size_t signature_length() const override { return 2 * m_key->group().q_bytes(); }
171
172 std::vector<uint8_t> raw_sign(std::span<const uint8_t> msg, RandomNumberGenerator& rng) override;
173
174 AlgorithmIdentifier algorithm_identifier() const override;
175
176 private:
177 std::shared_ptr<const DL_PrivateKey> m_key;
178 bool m_deterministic;
179 BigInt m_b, m_b_inv;
180};
181
182AlgorithmIdentifier DSA_Signature_Operation::algorithm_identifier() const {
183 const std::string full_name = "DSA/" + hash_function();
184 const OID oid = OID::from_string(full_name);
185 return AlgorithmIdentifier(oid, AlgorithmIdentifier::USE_EMPTY_PARAM);
186}
187
188std::vector<uint8_t> DSA_Signature_Operation::raw_sign(std::span<const uint8_t> msg, RandomNumberGenerator& rng) {
189 const DL_Group& group = m_key->group();
190 const BigInt& q = group.get_q();
191
192 BigInt m = BigInt::from_bytes_with_max_bits(msg.data(), msg.size(), group.q_bits());
193
194 if(m >= q) {
195 m -= q;
196 }
197
198 const auto scope = CT::scoped_poison(m_key->private_key(), m_b, m_b_inv);
199
200#if defined(BOTAN_HAS_RFC6979_GENERATOR)
201 const BigInt k = m_deterministic ? generate_rfc6979_nonce(m_key->private_key(), q, m, this->rfc6979_hash_function())
202 : BigInt::random_integer(rng, 1, q);
203#else
204 const BigInt k = BigInt::random_integer(rng, 1, q);
205#endif
206 CT::poison(k);
207
208 const BigInt k_inv = group.multiply_mod_q(group.inverse_mod_q(group.mod_q(m_b * k)), m_b);
209
210 /*
211 * It may not be strictly necessary for the reduction (g^k mod p) mod q to be
212 * const time, since r is published as part of the signature, and deriving
213 * anything useful about k from g^k mod p would seem to require computing a
214 * discrete logarithm.
215 *
216 * However it only increases the cost of signatures by about 7-10%, and DSA is
217 * only for legacy use anyway so we don't care about the performance so much.
218 */
219 const BigInt r = ct_modulo(group.power_g_p(k, group.q_bits()), group.get_q());
220
221 /*
222 * Blind the input message and compute x*r+m as (x*r*b + m*b)/b
223 */
224 m_b = group.square_mod_q(m_b);
225 m_b_inv = group.square_mod_q(m_b_inv);
226
227 m = group.multiply_mod_q(m_b, m);
228 const BigInt xr = group.multiply_mod_q(m_b, m_key->private_key(), r);
229
230 const BigInt s = group.multiply_mod_q(m_b_inv, k_inv, group.mod_q(xr + m));
231
232 CT::unpoison_all(r, s);
233
234 // With overwhelming probability, a bug rather than actual zero r/s
235 if(r.is_zero() || s.is_zero()) {
236 throw Internal_Error("Computed zero r/s during DSA signature");
237 }
238
239 const size_t q_bytes = q.bytes();
240 std::vector<uint8_t> sig(2 * q_bytes);
241 BufferStuffer stuffer(sig);
242 r.serialize_to(stuffer.next(q_bytes));
243 s.serialize_to(stuffer.next(q_bytes));
244 return sig;
245}
246
247/**
248* Object that can verify a DSA signature
249*/
250class DSA_Verification_Operation final : public PK_Ops::Verification_with_Hash {
251 public:
252 DSA_Verification_Operation(const std::shared_ptr<const DL_PublicKey>& key,
253 const PK_Signature_Options_Reader& options) :
254 PK_Ops::Verification_with_Hash(options), m_key(key) {}
255
256 DSA_Verification_Operation(const std::shared_ptr<const DL_PublicKey>& key, const AlgorithmIdentifier& alg_id) :
257 PK_Ops::Verification_with_Hash(alg_id, "DSA"), m_key(key) {}
258
259 bool verify(std::span<const uint8_t> input, std::span<const uint8_t> sig) override;
260
261 private:
262 std::shared_ptr<const DL_PublicKey> m_key;
263};
264
265bool DSA_Verification_Operation::verify(std::span<const uint8_t> input, std::span<const uint8_t> sig) {
266 const auto group = m_key->group();
267
268 const BigInt& q = group.get_q();
269 const size_t q_bytes = q.bytes();
270
271 if(sig.size() != 2 * q_bytes) {
272 return false;
273 }
274
275 const BigInt r(sig.first(q_bytes));
276 BigInt s(sig.last(q_bytes));
277
278 if(r == 0 || r >= q || s == 0 || s >= q) {
279 return false;
280 }
281
282 BigInt i = BigInt::from_bytes_with_max_bits(input.data(), input.size(), group.q_bits());
283 if(i >= q) {
284 i -= q;
285 }
286
287 s = group.inverse_mod_q(s);
288
289 // Since we already checked for s == 0 above this shouldn't happen
290 if(s.is_zero()) {
291 return false;
292 }
293
294 const BigInt sr = group.multiply_mod_q(s, r);
295 const BigInt si = group.multiply_mod_q(s, i);
296
297 s = group.multi_exponentiate(si, m_key->public_key(), sr);
298
299 // s is too big for Barrett, and verification doesn't need to be const-time
300 return (s % group.get_q() == r);
301}
302
303} // namespace
304
305std::unique_ptr<PK_Ops::Verification> DSA_PublicKey::_create_verification_op(
306 const PK_Signature_Options_Reader& options) const {
308
309 return std::make_unique<DSA_Verification_Operation>(this->m_public_key, options);
310}
311
312std::unique_ptr<PK_Ops::Verification> DSA_PublicKey::create_x509_verification_op(
313 const AlgorithmIdentifier& signature_algorithm, std::string_view provider) const {
314 if(provider == "base" || provider.empty()) {
315 return std::make_unique<DSA_Verification_Operation>(this->m_public_key, signature_algorithm);
316 }
317
318 throw Provider_Not_Found(algo_name(), provider);
319}
320
321std::unique_ptr<PK_Ops::Signature> DSA_PrivateKey::_create_signature_op(
322 RandomNumberGenerator& rng, const PK_Signature_Options_Reader& options) const {
324
325 return std::make_unique<DSA_Signature_Operation>(this->m_private_key, options, rng);
326}
327
328} // namespace Botan
virtual OID object_identifier() const
Definition pk_keys.cpp:24
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition big_rand.cpp:45
static BigInt from_s32(int32_t n)
Definition bigint.cpp:43
std::unique_ptr< PK_Ops::Signature > _create_signature_op(RandomNumberGenerator &rng, const PK_Signature_Options_Reader &options) const override
Definition dsa.cpp:321
secure_vector< uint8_t > private_key_bits() const override
Definition dsa.cpp:131
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition dsa.cpp:119
secure_vector< uint8_t > raw_private_key_bits() const override
Definition dsa.cpp:135
std::unique_ptr< Public_Key > public_key() const override
Definition dsa.cpp:143
const BigInt & get_int_field(std::string_view field) const override
Definition dsa.cpp:139
std::optional< size_t > _signature_element_size_for_DER_encoding() const override
Definition dsa.cpp:50
std::vector< uint8_t > raw_public_key_bits() const override
Definition dsa.cpp:70
std::unique_ptr< PK_Ops::Verification > _create_verification_op(const PK_Signature_Options_Reader &options) const override
Definition dsa.cpp:305
DSA_PublicKey(const AlgorithmIdentifier &alg_id, std::span< const uint8_t > key_bits)
Definition dsa.cpp:86
size_t estimated_strength() const override
Definition dsa.cpp:54
std::unique_ptr< PK_Ops::Verification > create_x509_verification_op(const AlgorithmIdentifier &signature_algorithm, std::string_view provider) const override
Definition dsa.cpp:312
friend class DSA_PrivateKey
Definition dsa.h:69
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition dsa.cpp:78
std::vector< uint8_t > public_key_bits() const override
Definition dsa.cpp:74
AlgorithmIdentifier algorithm_identifier() const override
Definition dsa.cpp:66
const BigInt & get_int_field(std::string_view field) const override
Definition dsa.cpp:62
std::string algo_name() const override
Definition dsa.h:44
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const final
Definition dsa.cpp:82
size_t key_length() const override
Definition dsa.cpp:58
constexpr void unpoison_all(const Ts &... ts)
Definition ct_utils.h:207
constexpr void poison(const T *p, size_t n)
Definition ct_utils.h:56
bool signature_consistency_check(RandomNumberGenerator &rng, const Private_Key &private_key, const Public_Key &public_key, std::string_view padding)
Definition keypair.cpp:49
BigInt generate_rfc6979_nonce(const BigInt &x, const BigInt &q, const BigInt &h, std::string_view hash)
Definition rfc6979.h:56
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:262
void require_software_provider(const OptionsT &options, std::string_view algo_name)
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128