Botan 3.7.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/internal/divide.h>
12#include <botan/internal/dl_scheme.h>
13#include <botan/internal/keypair.h>
14#include <botan/internal/pk_ops_impl.h>
15
16#if defined(BOTAN_HAS_RFC6979_GENERATOR)
17 #include <botan/internal/rfc6979.h>
18#endif
19
20namespace Botan {
21
23 return m_public_key->group().q_bytes();
24}
25
27 return m_public_key->estimated_strength();
28}
29
31 return m_public_key->p_bits();
32}
33
34const BigInt& DSA_PublicKey::get_int_field(std::string_view field) const {
35 return m_public_key->get_int_field(algo_name(), field);
36}
37
41
42std::vector<uint8_t> DSA_PublicKey::raw_public_key_bits() const {
43 return m_public_key->public_key_as_bytes();
44}
45
46std::vector<uint8_t> DSA_PublicKey::public_key_bits() const {
47 return m_public_key->DER_encode();
48}
49
50bool DSA_PublicKey::check_key(RandomNumberGenerator& rng, bool strong) const {
51 return m_public_key->check_key(rng, strong);
52}
53
54std::unique_ptr<Private_Key> DSA_PublicKey::generate_another(RandomNumberGenerator& rng) const {
55 return std::make_unique<DSA_PrivateKey>(rng, m_public_key->group());
56}
57
58DSA_PublicKey::DSA_PublicKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
59 m_public_key = std::make_shared<DL_PublicKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_57);
60
61 BOTAN_ARG_CHECK(m_public_key->group().has_q(), "Q parameter must be set for DSA");
62}
63
64DSA_PublicKey::DSA_PublicKey(const DL_Group& group, const BigInt& y) {
65 m_public_key = std::make_shared<DL_PublicKey>(group, y);
66
67 BOTAN_ARG_CHECK(m_public_key->group().has_q(), "Q parameter must be set for DSA");
68}
69
71 BOTAN_ARG_CHECK(group.has_q(), "Q parameter must be set for DSA");
72
73 m_private_key = std::make_shared<DL_PrivateKey>(group, rng);
74 m_public_key = m_private_key->public_key();
75}
76
78 BOTAN_ARG_CHECK(group.has_q(), "Q parameter must be set for DSA");
79
80 m_private_key = std::make_shared<DL_PrivateKey>(group, x);
81 m_public_key = m_private_key->public_key();
82}
83
84DSA_PrivateKey::DSA_PrivateKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
85 m_private_key = std::make_shared<DL_PrivateKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_57);
86 m_public_key = m_private_key->public_key();
87
88 BOTAN_ARG_CHECK(m_private_key->group().has_q(), "Q parameter must be set for DSA");
89}
90
91bool DSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const {
92 if(!m_private_key->check_key(rng, strong)) {
93 return false;
94 }
95
96 if(m_private_key->private_key() >= m_private_key->group().get_q()) {
97 return false;
98 }
99
100 return KeyPair::signature_consistency_check(rng, *this, "SHA-256");
101}
102
104 return m_private_key->DER_encode();
105}
106
108 return m_private_key->raw_private_key_bits();
109}
110
111const BigInt& DSA_PrivateKey::get_int_field(std::string_view field) const {
112 return m_private_key->get_int_field(algo_name(), field);
113}
114
115std::unique_ptr<Public_Key> DSA_PrivateKey::public_key() const {
116 // can't use make_unique here due to private constructor
117 return std::unique_ptr<DSA_PublicKey>(new DSA_PublicKey(m_public_key));
118}
119
120namespace {
121
122/**
123* Object that can create a DSA signature
124*/
125class DSA_Signature_Operation final : public PK_Ops::Signature_with_Hash {
126 public:
127 DSA_Signature_Operation(const std::shared_ptr<const DL_PrivateKey>& key,
128 std::string_view emsa,
130 PK_Ops::Signature_with_Hash(emsa), m_key(key) {
131 m_b = BigInt::random_integer(rng, 2, m_key->group().get_q());
132 m_b_inv = m_key->group().inverse_mod_q(m_b);
133 }
134
135 size_t signature_length() const override { return 2 * m_key->group().q_bytes(); }
136
137 std::vector<uint8_t> raw_sign(std::span<const uint8_t> msg, RandomNumberGenerator& rng) override;
138
139 AlgorithmIdentifier algorithm_identifier() const override;
140
141 private:
142 std::shared_ptr<const DL_PrivateKey> m_key;
143 BigInt m_b, m_b_inv;
144};
145
146AlgorithmIdentifier DSA_Signature_Operation::algorithm_identifier() const {
147 const std::string full_name = "DSA/" + hash_function();
148 const OID oid = OID::from_string(full_name);
149 return AlgorithmIdentifier(oid, AlgorithmIdentifier::USE_EMPTY_PARAM);
150}
151
152std::vector<uint8_t> DSA_Signature_Operation::raw_sign(std::span<const uint8_t> msg, RandomNumberGenerator& rng) {
153 const DL_Group& group = m_key->group();
154 const BigInt& q = group.get_q();
155
156 BigInt m = BigInt::from_bytes_with_max_bits(msg.data(), msg.size(), group.q_bits());
157
158 if(m >= q) {
159 m -= q;
160 }
161
162#if defined(BOTAN_HAS_RFC6979_GENERATOR)
163 BOTAN_UNUSED(rng);
164 const BigInt k = generate_rfc6979_nonce(m_key->private_key(), q, m, this->rfc6979_hash_function());
165#else
166 const BigInt k = BigInt::random_integer(rng, 1, q);
167#endif
168
169 const BigInt k_inv = group.inverse_mod_q(group.mod_q(m_b * k)) * m_b;
170
171 /*
172 * It may not be strictly necessary for the reduction (g^k mod p) mod q to be
173 * const time, since r is published as part of the signature, and deriving
174 * anything useful about k from g^k mod p would seem to require computing a
175 * discrete logarithm.
176 *
177 * However it only increases the cost of signatures by about 7-10%, and DSA is
178 * only for legacy use anyway so we don't care about the performance so much.
179 */
180 const BigInt r = ct_modulo(group.power_g_p(k, group.q_bits()), group.get_q());
181
182 /*
183 * Blind the input message and compute x*r+m as (x*r*b + m*b)/b
184 */
185 m_b = group.square_mod_q(m_b);
186 m_b_inv = group.square_mod_q(m_b_inv);
187
188 m = group.multiply_mod_q(m_b, m);
189 const BigInt xr = group.multiply_mod_q(m_b, m_key->private_key(), r);
190
191 const BigInt s = group.multiply_mod_q(m_b_inv, k_inv, group.mod_q(xr + m));
192
193 // With overwhelming probability, a bug rather than actual zero r/s
194 if(r.is_zero() || s.is_zero()) {
195 throw Internal_Error("Computed zero r/s during DSA signature");
196 }
197
198 return unlock(BigInt::encode_fixed_length_int_pair(r, s, q.bytes()));
199}
200
201/**
202* Object that can verify a DSA signature
203*/
204class DSA_Verification_Operation final : public PK_Ops::Verification_with_Hash {
205 public:
206 DSA_Verification_Operation(const std::shared_ptr<const DL_PublicKey>& key, std::string_view emsa) :
207 PK_Ops::Verification_with_Hash(emsa), m_key(key) {}
208
209 DSA_Verification_Operation(const std::shared_ptr<const DL_PublicKey>& key, const AlgorithmIdentifier& alg_id) :
210 PK_Ops::Verification_with_Hash(alg_id, "DSA"), m_key(key) {}
211
212 bool verify(std::span<const uint8_t> input, std::span<const uint8_t> sig) override;
213
214 private:
215 std::shared_ptr<const DL_PublicKey> m_key;
216};
217
218bool DSA_Verification_Operation::verify(std::span<const uint8_t> input, std::span<const uint8_t> sig) {
219 const auto group = m_key->group();
220
221 const BigInt& q = group.get_q();
222 const size_t q_bytes = q.bytes();
223
224 if(sig.size() != 2 * q_bytes) {
225 return false;
226 }
227
228 BigInt r(sig.first(q_bytes));
229 BigInt s(sig.last(q_bytes));
230
231 if(r == 0 || r >= q || s == 0 || s >= q) {
232 return false;
233 }
234
235 BigInt i = BigInt::from_bytes_with_max_bits(input.data(), input.size(), group.q_bits());
236 if(i >= q) {
237 i -= q;
238 }
239
240 s = group.inverse_mod_q(s);
241
242 const BigInt sr = group.multiply_mod_q(s, r);
243 const BigInt si = group.multiply_mod_q(s, i);
244
245 s = group.multi_exponentiate(si, m_key->public_key(), sr);
246
247 // s is too big for Barrett, and verification doesn't need to be const-time
248 return (s % group.get_q() == r);
249}
250
251} // namespace
252
253std::unique_ptr<PK_Ops::Verification> DSA_PublicKey::create_verification_op(std::string_view params,
254 std::string_view provider) const {
255 if(provider == "base" || provider.empty()) {
256 return std::make_unique<DSA_Verification_Operation>(this->m_public_key, params);
257 }
258 throw Provider_Not_Found(algo_name(), provider);
259}
260
261std::unique_ptr<PK_Ops::Verification> DSA_PublicKey::create_x509_verification_op(
262 const AlgorithmIdentifier& signature_algorithm, std::string_view provider) const {
263 if(provider == "base" || provider.empty()) {
264 return std::make_unique<DSA_Verification_Operation>(this->m_public_key, signature_algorithm);
265 }
266
267 throw Provider_Not_Found(algo_name(), provider);
268}
269
270std::unique_ptr<PK_Ops::Signature> DSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
271 std::string_view params,
272 std::string_view provider) const {
273 if(provider == "base" || provider.empty()) {
274 return std::make_unique<DSA_Signature_Operation>(this->m_private_key, params, rng);
275 }
276 throw Provider_Not_Found(algo_name(), provider);
277}
278
279} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:118
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
virtual OID object_identifier() const
Definition pk_keys.cpp:22
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition big_rand.cpp:43
bool has_q() const
Definition dl_group.cpp:487
secure_vector< uint8_t > private_key_bits() const override
Definition dsa.cpp:103
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition dsa.cpp:91
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
Definition dsa.cpp:270
secure_vector< uint8_t > raw_private_key_bits() const override
Definition dsa.cpp:107
std::unique_ptr< Public_Key > public_key() const override
Definition dsa.cpp:115
const BigInt & get_int_field(std::string_view field) const override
Definition dsa.cpp:111
std::optional< size_t > _signature_element_size_for_DER_encoding() const override
Definition dsa.cpp:22
std::vector< uint8_t > raw_public_key_bits() const override
Definition dsa.cpp:42
size_t estimated_strength() const override
Definition dsa.cpp:26
std::unique_ptr< PK_Ops::Verification > create_x509_verification_op(const AlgorithmIdentifier &signature_algorithm, std::string_view provider) const override
Definition dsa.cpp:261
friend class DSA_PrivateKey
Definition dsa.h:69
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition dsa.cpp:50
std::vector< uint8_t > public_key_bits() const override
Definition dsa.cpp:46
AlgorithmIdentifier algorithm_identifier() const override
Definition dsa.cpp:38
const BigInt & get_int_field(std::string_view field) const override
Definition dsa.cpp:34
std::string algo_name() const override
Definition dsa.h:44
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const final
Definition dsa.cpp:54
size_t key_length() const override
Definition dsa.cpp:30
std::unique_ptr< PK_Ops::Verification > create_verification_op(std::string_view params, std::string_view provider) const override
Definition dsa.cpp:253
int(* final)(unsigned char *, CTX *)
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:52
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:181
std::vector< T > unlock(const secure_vector< T > &in)
Definition secmem.h:75
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61