22855031980

Committed 09 Mar 2026 01:10PM UTC coverage: 90.173% (-0.01%) from 90.184%

Build # 22855031980

Build Type

Pull #5425

github

Committed by

web-flow

Commit Message

Merge 058be2a86 into cdaa9c0ff

Pull Request Pull Request #5425: BigInt encoding cleanups

Coverage Stats

103789 of 115100 relevant lines covered (90.17%)

11503649.25 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.2

/src/lib/pubkey/dsa/dsa.cpp

/*
* DSA
* (C) 1999-2010,2014,2016,2023 Jack Lloyd
* (C) 2016 René Korthaus
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/dsa.h>

#include <botan/assert.h>
#include <botan/internal/buffer_stuffer.h>
#include <botan/internal/divide.h>
#include <botan/internal/dl_scheme.h>
#include <botan/internal/keypair.h>
#include <botan/internal/pk_ops_impl.h>

#if defined(BOTAN_HAS_RFC6979_GENERATOR)
   #include <botan/internal/rfc6979.h>
#endif

namespace Botan {

std::optional<size_t> DSA_PublicKey::_signature_element_size_for_DER_encoding() const {
   return m_public_key->group().q_bytes();
}

size_t DSA_PublicKey::estimated_strength() const {
   return m_public_key->estimated_strength();
}

size_t DSA_PublicKey::key_length() const {
   return m_public_key->p_bits();
}

const BigInt& DSA_PublicKey::get_int_field(std::string_view field) const {
   return m_public_key->get_int_field(algo_name(), field);
}

AlgorithmIdentifier DSA_PublicKey::algorithm_identifier() const {
   return AlgorithmIdentifier(object_identifier(), m_public_key->group().DER_encode(DL_Group_Format::ANSI_X9_57));
}

std::vector<uint8_t> DSA_PublicKey::raw_public_key_bits() const {
   return m_public_key->public_key_as_bytes();
}

std::vector<uint8_t> DSA_PublicKey::public_key_bits() const {
   return m_public_key->DER_encode();
}

bool DSA_PublicKey::check_key(RandomNumberGenerator& rng, bool strong) const {
   return m_public_key->check_key(rng, strong);
}

std::unique_ptr<Private_Key> DSA_PublicKey::generate_another(RandomNumberGenerator& rng) const {
   return std::make_unique<DSA_PrivateKey>(rng, m_public_key->group());
}

DSA_PublicKey::DSA_PublicKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
   m_public_key = std::make_shared<DL_PublicKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_57);

   BOTAN_ARG_CHECK(m_public_key->group().has_q(), "Q parameter must be set for DSA");
}

DSA_PublicKey::DSA_PublicKey(const DL_Group& group, const BigInt& y) {
   m_public_key = std::make_shared<DL_PublicKey>(group, y);

   BOTAN_ARG_CHECK(m_public_key->group().has_q(), "Q parameter must be set for DSA");
}

DSA_PrivateKey::DSA_PrivateKey(RandomNumberGenerator& rng, const DL_Group& group) {
   BOTAN_ARG_CHECK(group.has_q(), "Q parameter must be set for DSA");

   m_private_key = std::make_shared<DL_PrivateKey>(group, rng);
   m_public_key = m_private_key->public_key();
}

DSA_PrivateKey::DSA_PrivateKey(const DL_Group& group, const BigInt& x) {
   BOTAN_ARG_CHECK(group.has_q(), "Q parameter must be set for DSA");

   m_private_key = std::make_shared<DL_PrivateKey>(group, x);
   m_public_key = m_private_key->public_key();
}

DSA_PrivateKey::DSA_PrivateKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
   m_private_key = std::make_shared<DL_PrivateKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_57);
   m_public_key = m_private_key->public_key();

   BOTAN_ARG_CHECK(m_private_key->group().has_q(), "Q parameter must be set for DSA");
}

bool DSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const {
   if(!m_private_key->check_key(rng, strong)) {
      return false;
   }

   if(m_private_key->private_key() >= m_private_key->group().get_q()) {
      return false;
   }

   return KeyPair::signature_consistency_check(rng, *this, "SHA-256");
}

secure_vector<uint8_t> DSA_PrivateKey::private_key_bits() const {
   return m_private_key->DER_encode();
}

secure_vector<uint8_t> DSA_PrivateKey::raw_private_key_bits() const {
   return m_private_key->raw_private_key_bits();
}

const BigInt& DSA_PrivateKey::get_int_field(std::string_view field) const {
   return m_private_key->get_int_field(algo_name(), field);
}

std::unique_ptr<Public_Key> DSA_PrivateKey::public_key() const {
   // can't use make_unique here due to private constructor
   return std::unique_ptr<DSA_PublicKey>(new DSA_PublicKey(m_public_key));
}

namespace {

/**
* Object that can create a DSA signature
*/
class DSA_Signature_Operation final : public PK_Ops::Signature_with_Hash {
   public:
      DSA_Signature_Operation(const std::shared_ptr<const DL_PrivateKey>& key,
                              std::string_view hash_fn,
                              RandomNumberGenerator& rng) :
            PK_Ops::Signature_with_Hash(hash_fn), m_key(key) {
         m_b = BigInt::random_integer(rng, BigInt::from_s32(2), m_key->group().get_q());
         m_b_inv = m_key->group().inverse_mod_q(m_b);
      }

      size_t signature_length() const override { return 2 * m_key->group().q_bytes(); }

      std::vector<uint8_t> raw_sign(std::span<const uint8_t> msg, RandomNumberGenerator& rng) override;

      AlgorithmIdentifier algorithm_identifier() const override;

   private:
      std::shared_ptr<const DL_PrivateKey> m_key;
      BigInt m_b, m_b_inv;
};

AlgorithmIdentifier DSA_Signature_Operation::algorithm_identifier() const {
   const std::string full_name = "DSA/" + hash_function();
   const OID oid = OID::from_string(full_name);
   return AlgorithmIdentifier(oid, AlgorithmIdentifier::USE_EMPTY_PARAM);
}

std::vector<uint8_t> DSA_Signature_Operation::raw_sign(std::span<const uint8_t> msg, RandomNumberGenerator& rng) {
   const DL_Group& group = m_key->group();
   const BigInt& q = group.get_q();

   BigInt m = BigInt::from_bytes_with_max_bits(msg.data(), msg.size(), group.q_bits());

   if(m >= q) {
      m -= q;
   }

#if defined(BOTAN_HAS_RFC6979_GENERATOR)
   BOTAN_UNUSED(rng);
   const BigInt k = generate_rfc6979_nonce(m_key->private_key(), q, m, this->rfc6979_hash_function());
#else
   const BigInt k = BigInt::random_integer(rng, 1, q);
#endif

   const BigInt k_inv = group.multiply_mod_q(group.inverse_mod_q(group.mod_q(m_b * k)), m_b);

   /*
   * It may not be strictly necessary for the reduction (g^k mod p) mod q to be
   * const time, since r is published as part of the signature, and deriving
   * anything useful about k from g^k mod p would seem to require computing a
   * discrete logarithm.
   *
   * However it only increases the cost of signatures by about 7-10%, and DSA is
   * only for legacy use anyway so we don't care about the performance so much.
   */
   const BigInt r = ct_modulo(group.power_g_p(k, group.q_bits()), group.get_q());

   /*
   * Blind the input message and compute x*r+m as (x*r*b + m*b)/b
   */
   m_b = group.square_mod_q(m_b);
   m_b_inv = group.square_mod_q(m_b_inv);

   m = group.multiply_mod_q(m_b, m);
   const BigInt xr = group.multiply_mod_q(m_b, m_key->private_key(), r);

   const BigInt s = group.multiply_mod_q(m_b_inv, k_inv, group.mod_q(xr + m));

   // With overwhelming probability, a bug rather than actual zero r/s
   if(r.is_zero() || s.is_zero()) {
      throw Internal_Error("Computed zero r/s during DSA signature");
   }

   const size_t q_bytes = q.bytes();
   std::vector<uint8_t> sig(2 * q_bytes);
   BufferStuffer stuffer(sig);
   r.serialize_to(stuffer.next(q_bytes));
   s.serialize_to(stuffer.next(q_bytes));
   return sig;
}

/**
* Object that can verify a DSA signature
*/
class DSA_Verification_Operation final : public PK_Ops::Verification_with_Hash {
   public:
      DSA_Verification_Operation(const std::shared_ptr<const DL_PublicKey>& key, std::string_view hash_fn) :
            PK_Ops::Verification_with_Hash(hash_fn), m_key(key) {}

      DSA_Verification_Operation(const std::shared_ptr<const DL_PublicKey>& key, const AlgorithmIdentifier& alg_id) :
            PK_Ops::Verification_with_Hash(alg_id, "DSA"), m_key(key) {}

      bool verify(std::span<const uint8_t> input, std::span<const uint8_t> sig) override;

   private:
      std::shared_ptr<const DL_PublicKey> m_key;
};

bool DSA_Verification_Operation::verify(std::span<const uint8_t> input, std::span<const uint8_t> sig) {
   const auto group = m_key->group();

   const BigInt& q = group.get_q();
   const size_t q_bytes = q.bytes();

   if(sig.size() != 2 * q_bytes) {
      return false;
   }

   const BigInt r(sig.first(q_bytes));
   BigInt s(sig.last(q_bytes));

   if(r == 0 || r >= q || s == 0 || s >= q) {
      return false;
   }

   BigInt i = BigInt::from_bytes_with_max_bits(input.data(), input.size(), group.q_bits());
   if(i >= q) {
      i -= q;
   }

   s = group.inverse_mod_q(s);

   const BigInt sr = group.multiply_mod_q(s, r);
   const BigInt si = group.multiply_mod_q(s, i);

   s = group.multi_exponentiate(si, m_key->public_key(), sr);

   // s is too big for Barrett, and verification doesn't need to be const-time
   return (s % group.get_q() == r);
}

}  // namespace

std::unique_ptr<PK_Ops::Verification> DSA_PublicKey::create_verification_op(std::string_view params,
                                                                            std::string_view provider) const {
   if(provider == "base" || provider.empty()) {
      return std::make_unique<DSA_Verification_Operation>(this->m_public_key, params);
   }
   throw Provider_Not_Found(algo_name(), provider);
}

std::unique_ptr<PK_Ops::Verification> DSA_PublicKey::create_x509_verification_op(
   const AlgorithmIdentifier& signature_algorithm, std::string_view provider) const {
   if(provider == "base" || provider.empty()) {
      return std::make_unique<DSA_Verification_Operation>(this->m_public_key, signature_algorithm);
   }

   throw Provider_Not_Found(algo_name(), provider);
}

std::unique_ptr<PK_Ops::Signature> DSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
                                                                       std::string_view params,
                                                                       std::string_view provider) const {
   if(provider == "base" || provider.empty()) {
      return std::make_unique<DSA_Signature_Operation>(this->m_private_key, params, rng);
   }
   throw Provider_Not_Found(algo_name(), provider);
}

}  // namespace Botan

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

randombit / botan / 22855031980

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous