Botan 3.14.1
Crypto and TLS for C&
ecdsa.cpp
Go to the documentation of this file.
1/*
2* ECDSA implementation
3* (C) 2007 Manuel Hartl, FlexSecure GmbH
4* 2007 Falko Strenzke, FlexSecure GmbH
5* 2008-2010,2015,2016,2018,2024 Jack Lloyd
6* 2016 René Korthaus
7*
8* Botan is released under the Simplified BSD License (see license.txt)
9*/
10
11#include <botan/ecdsa.h>
12
13#include <botan/ec_group.h>
14#include <botan/pk_options_readers.h>
15#include <botan/internal/ct_utils.h>
16#include <botan/internal/keypair.h>
17#include <botan/internal/pk_ops_impl.h>
18#include <botan/internal/pk_options_impl.h>
19
20#if defined(BOTAN_HAS_RFC6979_GENERATOR)
21 #include <botan/internal/rfc6979.h>
22#endif
23
24namespace Botan {
25
26namespace {
27
28EC_AffinePoint recover_ecdsa_public_key(
29 const EC_Group& group, const std::vector<uint8_t>& msg, const BigInt& r, const BigInt& s, uint8_t v) {
30 if(group.has_cofactor()) {
31 throw Invalid_Argument("ECDSA public key recovery only supported for prime order groups");
32 }
33
34 if(v >= 4) {
35 throw Invalid_Argument("Unexpected v param for ECDSA public key recovery");
36 }
37
38 const BigInt& group_order = group.get_order();
39
40 if(r <= 0 || r >= group_order || s <= 0 || s >= group_order) {
41 throw Invalid_Argument("Out of range r/s cannot recover ECDSA public key");
42 }
43
44 const uint8_t y_odd = v % 2;
45 const bool add_order = (v >> 1) == 0x01;
46 const size_t p_bytes = group.get_p_bytes();
47
48 BigInt x = r;
49
50 if(add_order) {
51 x += group_order;
52 }
53
54 if(x.bytes() <= p_bytes) {
55 std::vector<uint8_t> X(p_bytes + 1);
56
57 X[0] = 0x02 | y_odd;
58 x.serialize_to(std::span{X}.subspan(1));
59
60 if(auto R = EC_AffinePoint::deserialize_compressed(group, X)) {
61 // Compute r_inv * (-eG + s*R)
62 const auto ne = EC_Scalar::from_bytes_with_trunc(group, msg).negate();
63 const auto ss = EC_Scalar::from_bigint(group, s);
64
65 const auto r_inv = EC_Scalar::from_bigint(group, r).invert_vartime();
66
67 const EC_Group::Mul2Table GR_mul(R.value());
68 if(auto egsr = GR_mul.mul2_vartime(ne * r_inv, ss * r_inv)) {
69 return egsr.value();
70 }
71 }
72 }
73
74 throw Decoding_Error("Failed to recover ECDSA public key from signature/msg pair");
75}
76
77} // namespace
78
80 const EC_Group& group, const std::vector<uint8_t>& msg, const BigInt& r, const BigInt& s, uint8_t v) :
81 EC_PublicKey(group, recover_ecdsa_public_key(group, msg, r, s, v)) {}
82
84 return domain().get_order_bytes();
85}
86
87std::unique_ptr<Private_Key> ECDSA_PublicKey::generate_another(RandomNumberGenerator& rng) const {
88 return std::make_unique<ECDSA_PrivateKey>(rng, domain());
89}
90
91uint8_t ECDSA_PublicKey::recovery_param(const std::vector<uint8_t>& msg, const BigInt& r, const BigInt& s) const {
92 const auto this_key = this->public_ec_point().serialize_compressed();
93
94 for(uint8_t v = 0; v != 4; ++v) {
95 try {
96 const auto R = recover_ecdsa_public_key(this->domain(), msg, r, s, v);
97
98 if(R.serialize_compressed() == this_key) {
99 return v;
100 }
101 } catch(Decoding_Error&) {
102 // try the next v
103 }
104 }
105
106 throw Internal_Error("Could not determine ECDSA recovery parameter");
107}
108
109std::unique_ptr<Public_Key> ECDSA_PrivateKey::public_key() const {
110 return std::make_unique<ECDSA_PublicKey>(domain(), public_ec_point());
111}
112
114 if(!EC_PrivateKey::check_key(rng, strong)) {
115 return false;
116 }
117
118 if(!strong) {
119 return true;
120 }
121
122 return KeyPair::signature_consistency_check(rng, *this, "SHA-256");
123}
124
125namespace {
126
127/**
128* ECDSA signature operation
129*/
130class ECDSA_Signature_Operation final : public PK_Ops::Signature_with_Hash {
131 public:
132 ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa,
133 const PK_Signature_Options_Reader& options,
135 PK_Ops::Signature_with_Hash(options),
136 m_group(ecdsa.domain()),
137 m_x(ecdsa._private_key()),
138 m_b(EC_Scalar::random(m_group, rng)) {
139#if defined(BOTAN_HAS_RFC6979_GENERATOR)
140 if(options.using_deterministic_signature()) {
141 m_rfc6979 = std::make_unique<RFC6979_Nonce_Generator>(
142 this->rfc6979_hash_function(), m_group.get_order_bits(), ecdsa._private_key());
143 }
144#else
145 if(options.using_deterministic_signature()) {
146 throw Not_Implemented("Deterministic ECDSA signatures require RFC 6979 support");
147 }
148#endif
149 }
150
151 size_t signature_length() const override { return 2 * m_group.get_order_bytes(); }
152
153 std::vector<uint8_t> raw_sign(std::span<const uint8_t> msg, RandomNumberGenerator& rng) override;
154
155 AlgorithmIdentifier algorithm_identifier() const override;
156
157 private:
158 const EC_Group m_group;
159 const EC_Scalar m_x;
160
161#if defined(BOTAN_HAS_RFC6979_GENERATOR)
162 std::unique_ptr<RFC6979_Nonce_Generator> m_rfc6979;
163#endif
164
165 EC_Scalar m_b;
166};
167
168AlgorithmIdentifier ECDSA_Signature_Operation::algorithm_identifier() const {
169 const std::string full_name = "ECDSA/" + hash_function();
170 const OID oid = OID::from_string(full_name);
171 return AlgorithmIdentifier(oid, AlgorithmIdentifier::USE_EMPTY_PARAM);
172}
173
174std::vector<uint8_t> ECDSA_Signature_Operation::raw_sign(std::span<const uint8_t> msg, RandomNumberGenerator& rng) {
175 const auto m = EC_Scalar::from_bytes_with_trunc(m_group, msg);
176
177 const auto scope = CT::scoped_poison(m_x, m_b);
178
179#if defined(BOTAN_HAS_RFC6979_GENERATOR)
180 const auto k = m_rfc6979 ? m_rfc6979->nonce_for(m_group, m) : EC_Scalar::random(m_group, rng);
181#else
182 const auto k = EC_Scalar::random(m_group, rng);
183#endif
184 CT::poison(k);
185
186 /*
187 * Blind the inputs
188 *
189 * Here we are computing (x*r+m)/k
190 *
191 * Instead have a random b and compute (k*b)^-1
192 *
193 * Then compute (x*r+m) as (x*r*b + m*b)
194 *
195 * Finally (x*r*b + m*b)/(k*b) = (x*r+m)/k
196 *
197 * This effectively blinds both the inversion as well as the various scalar
198 * multiplications. All of these operations should be constant-time anyway but
199 * blinding is very cheap and may help if either the compiler introduces
200 * variable-time behavior, or for the case of EM/power side channel attacks [1].
201 *
202 * [1] But note that such attacks are currently outside of Botan's threat model.
203 *
204 * NOTE: if you change anything here also update ECDSA_Timing_Test
205 * in cli/timing_tests.cpp to use the same formulas
206 */
207 const auto r = EC_Scalar::gk_x_mod_order(k, rng);
208
209 const auto k_inv = (m_b * k).invert();
210
211 const auto xr_m = ((m_x * m_b) * r) + (m * m_b);
212
213 const auto s = (k_inv * xr_m);
214
215 // Generate the next blinding value via modular squaring
216 m_b.square_self();
217
218 CT::unpoison_all(r, s);
219
220 // With overwhelming probability, a bug rather than actual zero r/s
221 if(r.is_zero() || s.is_zero()) {
222 throw Internal_Error("During ECDSA signature generated zero r/s");
223 }
224
225 return EC_Scalar::serialize_pair(r, s);
226}
227
228/**
229* ECDSA verification operation
230*/
231class ECDSA_Verification_Operation final : public PK_Ops::Verification_with_Hash {
232 public:
233 ECDSA_Verification_Operation(const ECDSA_PublicKey& ecdsa, const PK_Signature_Options_Reader& options) :
234 PK_Ops::Verification_with_Hash(options), m_group(ecdsa.domain()), m_gy_mul(ecdsa.public_ec_point()) {}
235
236 ECDSA_Verification_Operation(const ECDSA_PublicKey& ecdsa, const AlgorithmIdentifier& alg_id) :
237 /*
238 * RFC 5758 Section 3.2 is clear that for ECDSA signatures the parameters field is empty
239 *
240 * When the [ecdsa-with-SHA*] algorithm identifier appears in the algorithm
241 * field as an AlgorithmIdentifier, the encoding MUST omit the parameters
242 * field. That is, the AlgorithmIdentifier SHALL be a SEQUENCE of one
243 * component, the OID [ecdsa-with-SHA*].
244 *
245 * However ECDSA is old enough and widely implemented enough that many non-conformant
246 * implementations which emit X509 signatures using an explicit NULL parameter do exist,
247 * so accept it here.
248 */
249 PK_Ops::Verification_with_Hash(alg_id, "ECDSA", true),
250 m_group(ecdsa.domain()),
251 m_gy_mul(ecdsa.public_ec_point()) {}
252
253 bool verify(std::span<const uint8_t> msg, std::span<const uint8_t> sig) override;
254
255 private:
256 const EC_Group m_group;
257 const EC_Group::Mul2Table m_gy_mul;
258};
259
260bool ECDSA_Verification_Operation::verify(std::span<const uint8_t> msg, std::span<const uint8_t> sig) {
261 if(auto rs = EC_Scalar::deserialize_pair(m_group, sig)) {
262 const auto& [r, s] = rs.value();
263
264 if(r.is_nonzero() && s.is_nonzero()) {
265 const auto m = EC_Scalar::from_bytes_with_trunc(m_group, msg);
266
267 const auto w = s.invert_vartime();
268
269 // Check if r == x_coord(g*w*m + y*w*r) % n
270 return m_gy_mul.mul2_vartime_x_mod_order_eq(r, w, m, r);
271 }
272 }
273
274 return false;
275}
276
277} // namespace
278
279std::unique_ptr<PK_Ops::Verification> ECDSA_PublicKey::_create_verification_op(
280 const PK_Signature_Options_Reader& options) const {
282
283 return std::make_unique<ECDSA_Verification_Operation>(*this, options);
284}
285
286std::unique_ptr<PK_Ops::Verification> ECDSA_PublicKey::create_x509_verification_op(
287 const AlgorithmIdentifier& signature_algorithm, std::string_view provider) const {
288 if(provider == "base" || provider.empty()) {
289 return std::make_unique<ECDSA_Verification_Operation>(*this, signature_algorithm);
290 }
291
292 throw Provider_Not_Found(algo_name(), provider);
293}
294
295std::unique_ptr<PK_Ops::Signature> ECDSA_PrivateKey::_create_signature_op(
296 RandomNumberGenerator& rng, const PK_Signature_Options_Reader& options) const {
298
299 return std::make_unique<ECDSA_Signature_Operation>(*this, options, rng);
300}
301
302} // namespace Botan
std::unique_ptr< Public_Key > public_key() const override
Definition ecdsa.cpp:109
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition ecdsa.cpp:113
std::unique_ptr< PK_Ops::Signature > _create_signature_op(RandomNumberGenerator &rng, const PK_Signature_Options_Reader &options) const override
Definition ecdsa.cpp:295
std::string algo_name() const override
Definition ecdsa.h:62
std::unique_ptr< PK_Ops::Verification > create_x509_verification_op(const AlgorithmIdentifier &signature_algorithm, std::string_view provider) const override
Definition ecdsa.cpp:286
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const override
Definition ecdsa.cpp:87
std::unique_ptr< PK_Ops::Verification > _create_verification_op(const PK_Signature_Options_Reader &options) const override
Definition ecdsa.cpp:279
uint8_t recovery_param(const std::vector< uint8_t > &msg, const BigInt &r, const BigInt &s) const
Definition ecdsa.cpp:91
std::optional< size_t > _signature_element_size_for_DER_encoding() const override
Definition ecdsa.cpp:83
static std::optional< EC_AffinePoint > deserialize_compressed(const EC_Group &group, std::span< const uint8_t > bytes)
T serialize_compressed() const
Definition ec_apoint.h:248
bool mul2_vartime_x_mod_order_eq(const EC_Scalar &v, const EC_Scalar &x, const EC_Scalar &y) const
Definition ec_group.cpp:987
size_t get_order_bytes() const
Definition ec_group.cpp:733
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition ecc_key.cpp:237
const EC_Group & domain() const
Definition ecc_key.cpp:76
const EC_AffinePoint & public_ec_point() const
Definition ecc_key.cpp:88
EC_PublicKey(const EC_PublicKey &other)=default
static EC_Scalar from_bigint(const EC_Group &group, const BigInt &bn)
Definition ec_scalar.cpp:84
EC_Scalar invert_vartime() const
EC_Scalar negate() const
static EC_Scalar from_bytes_with_trunc(const EC_Group &group, std::span< const uint8_t > bytes)
Definition ec_scalar.cpp:64
bool signature_consistency_check(RandomNumberGenerator &rng, const Private_Key &private_key, const Public_Key &public_key, std::string_view padding)
Definition keypair.cpp:49
void require_software_provider(const OptionsT &options, std::string_view algo_name)