Botan  2.10.0
Crypto and TLS for C++11
ecdsa.cpp
Go to the documentation of this file.
1 /*
2 * ECDSA implemenation
3 * (C) 2007 Manuel Hartl, FlexSecure GmbH
4 * 2007 Falko Strenzke, FlexSecure GmbH
5 * 2008-2010,2015,2016,2018 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 #include <botan/internal/pk_ops_impl.h>
13 #include <botan/internal/point_mul.h>
14 #include <botan/keypair.h>
15 #include <botan/reducer.h>
16 #include <botan/emsa.h>
17 
18 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
19  #include <botan/rfc6979.h>
20 #endif
21 
22 #if defined(BOTAN_HAS_BEARSSL)
23  #include <botan/internal/bearssl.h>
24 #endif
25 
26 #if defined(BOTAN_HAS_OPENSSL)
27  #include <botan/internal/openssl.h>
28 #endif
29 
30 namespace Botan {
31 
32 namespace {
33 
34 PointGFp recover_ecdsa_public_key(const EC_Group& group,
35  const std::vector<uint8_t>& msg,
36  const BigInt& r,
37  const BigInt& s,
38  uint8_t v)
39  {
40  if(group.get_cofactor() != 1)
41  throw Invalid_Argument("ECDSA public key recovery only supported for prime order groups");
42 
43  if(v > 4)
44  throw Invalid_Argument("Unexpected v param for ECDSA public key recovery");
45 
46  const uint8_t y_odd = v % 2;
47  const uint8_t add_order = v >> 1;
48 
49  const BigInt& group_order = group.get_order();
50  const size_t p_bytes = group.get_p_bytes();
51 
52  try
53  {
54  const BigInt e(msg.data(), msg.size(), group.get_order_bits());
55  const BigInt r_inv = group.inverse_mod_order(r);
56 
57  BigInt x = r + add_order*group_order;
58 
59  std::vector<uint8_t> X(p_bytes + 1);
60 
61  X[0] = 0x02 | y_odd;
62  BigInt::encode_1363(&X[1], p_bytes, x);
63 
64  const PointGFp R = group.OS2ECP(X);
65 
66  if((R*group_order).is_zero() == false)
67  throw Decoding_Error("Unable to recover ECDSA public key");
68 
69  // Compute r_inv * (s*R - eG)
70  PointGFp_Multi_Point_Precompute RG_mul(R, group.get_base_point());
71  const BigInt ne = group.mod_order(group_order - e);
72  return r_inv * RG_mul.multi_exp(s, ne);
73  }
74  catch(...)
75  {
76  // continue on and throw
77  }
78 
79  throw Decoding_Error("Failed to recover ECDSA public key from signature/msg pair");
80  }
81 
82 }
83 
85  const std::vector<uint8_t>& msg,
86  const BigInt& r,
87  const BigInt& s,
88  uint8_t v) :
89  EC_PublicKey(group, recover_ecdsa_public_key(group, msg, r, s, v)) {}
90 
91 
92 uint8_t ECDSA_PublicKey::recovery_param(const std::vector<uint8_t>& msg,
93  const BigInt& r,
94  const BigInt& s) const
95  {
96  for(uint8_t v = 0; v != 4; ++v)
97  {
98  try
99  {
100  PointGFp R = recover_ecdsa_public_key(this->domain(), msg, r, s, v);
101 
102  if(R == this->public_point())
103  {
104  return v;
105  }
106  }
107  catch(Decoding_Error&)
108  {
109  // try the next v
110  }
111  }
112 
113  throw Internal_Error("Could not determine ECDSA recovery parameter");
114  }
115 
117  bool strong) const
118  {
119  if(!public_point().on_the_curve())
120  return false;
121 
122  if(!strong)
123  return true;
124 
125  return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-256)");
126  }
127 
128 namespace {
129 
130 /**
131 * ECDSA signature operation
132 */
133 class ECDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
134  {
135  public:
136 
137  ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa,
138  const std::string& emsa,
139  RandomNumberGenerator& rng) :
141  m_group(ecdsa.domain()),
142  m_x(ecdsa.private_value())
143  {
144 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
145  m_rfc6979.reset(new RFC6979_Nonce_Generator(hash_for_emsa(emsa), m_group.get_order(), m_x));
146 #endif
147 
148  m_b = m_group.random_scalar(rng);
149  m_b_inv = m_group.inverse_mod_order(m_b);
150  }
151 
152  size_t signature_length() const override { return 2*m_group.get_order_bytes(); }
153 
154  size_t max_input_bits() const override { return m_group.get_order_bits(); }
155 
156  secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len,
157  RandomNumberGenerator& rng) override;
158 
159  private:
160  const EC_Group m_group;
161  const BigInt& m_x;
162 
163 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
164  std::unique_ptr<RFC6979_Nonce_Generator> m_rfc6979;
165 #endif
166 
167  std::vector<BigInt> m_ws;
168 
169  BigInt m_b, m_b_inv;
170  };
171 
173 ECDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
175  {
176  BigInt m(msg, msg_len, m_group.get_order_bits());
177 
178 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
179  const BigInt k = m_rfc6979->nonce_for(m);
180 #else
181  const BigInt k = m_group.random_scalar(rng);
182 #endif
183 
184  const BigInt r = m_group.mod_order(
185  m_group.blinded_base_point_multiply_x(k, rng, m_ws));
186 
187  const BigInt k_inv = m_group.inverse_mod_order(k);
188 
189  /*
190  * Blind the input message and compute x*r+m as (x*r*b + m*b)/b
191  */
192  m_b = m_group.square_mod_order(m_b);
193  m_b_inv = m_group.square_mod_order(m_b_inv);
194 
195  m = m_group.multiply_mod_order(m_b, m_group.mod_order(m));
196  const BigInt xr_m = m_group.mod_order(m_group.multiply_mod_order(m_x, m_b, r) + m);
197 
198  const BigInt s = m_group.multiply_mod_order(k_inv, xr_m, m_b_inv);
199 
200  // With overwhelming probability, a bug rather than actual zero r/s
201  if(r.is_zero() || s.is_zero())
202  throw Internal_Error("During ECDSA signature generated zero r/s");
203 
204  return BigInt::encode_fixed_length_int_pair(r, s, m_group.get_order_bytes());
205  }
206 
207 /**
208 * ECDSA verification operation
209 */
210 class ECDSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA
211  {
212  public:
213  ECDSA_Verification_Operation(const ECDSA_PublicKey& ecdsa,
214  const std::string& emsa) :
216  m_group(ecdsa.domain()),
217  m_gy_mul(m_group.get_base_point(), ecdsa.public_point())
218  {
219  }
220 
221  size_t max_input_bits() const override { return m_group.get_order_bits(); }
222 
223  bool with_recovery() const override { return false; }
224 
225  bool verify(const uint8_t msg[], size_t msg_len,
226  const uint8_t sig[], size_t sig_len) override;
227  private:
228  const EC_Group m_group;
229  const PointGFp_Multi_Point_Precompute m_gy_mul;
230  };
231 
232 bool ECDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
233  const uint8_t sig[], size_t sig_len)
234  {
235  if(sig_len != m_group.get_order_bytes() * 2)
236  return false;
237 
238  const BigInt e(msg, msg_len, m_group.get_order_bits());
239 
240  const BigInt r(sig, sig_len / 2);
241  const BigInt s(sig + sig_len / 2, sig_len / 2);
242 
243  if(r <= 0 || r >= m_group.get_order() || s <= 0 || s >= m_group.get_order())
244  return false;
245 
246  const BigInt w = m_group.inverse_mod_order(s);
247 
248  const BigInt u1 = m_group.multiply_mod_order(m_group.mod_order(e), w);
249  const BigInt u2 = m_group.multiply_mod_order(r, w);
250  const PointGFp R = m_gy_mul.multi_exp(u1, u2);
251 
252  if(R.is_zero())
253  return false;
254 
255  const BigInt v = m_group.mod_order(R.get_affine_x());
256  return (v == r);
257  }
258 
259 }
260 
261 std::unique_ptr<PK_Ops::Verification>
262 ECDSA_PublicKey::create_verification_op(const std::string& params,
263  const std::string& provider) const
264  {
265 #if defined(BOTAN_HAS_BEARSSL)
266  if(provider == "bearssl" || provider.empty())
267  {
268  try
269  {
270  return make_bearssl_ecdsa_ver_op(*this, params);
271  }
272  catch(Lookup_Error& e)
273  {
274  if(provider == "bearssl")
275  throw;
276  }
277  }
278 #endif
279 
280 #if defined(BOTAN_HAS_OPENSSL)
281  if(provider == "openssl" || provider.empty())
282  {
283  try
284  {
285  return make_openssl_ecdsa_ver_op(*this, params);
286  }
287  catch(Lookup_Error& e)
288  {
289  if(provider == "openssl")
290  throw;
291  }
292  }
293 #endif
294 
295  if(provider == "base" || provider.empty())
296  return std::unique_ptr<PK_Ops::Verification>(new ECDSA_Verification_Operation(*this, params));
297 
298  throw Provider_Not_Found(algo_name(), provider);
299  }
300 
301 std::unique_ptr<PK_Ops::Signature>
303  const std::string& params,
304  const std::string& provider) const
305  {
306 #if defined(BOTAN_HAS_BEARSSL)
307  if(provider == "bearssl" || provider.empty())
308  {
309  try
310  {
311  return make_bearssl_ecdsa_sig_op(*this, params);
312  }
313  catch(Lookup_Error& e)
314  {
315  if(provider == "bearssl")
316  throw;
317  }
318  }
319 #endif
320 
321 #if defined(BOTAN_HAS_OPENSSL)
322  if(provider == "openssl" || provider.empty())
323  {
324  try
325  {
326  return make_openssl_ecdsa_sig_op(*this, params);
327  }
328  catch(Lookup_Error& e)
329  {
330  if(provider == "openssl")
331  throw;
332  }
333  }
334 #endif
335 
336  if(provider == "base" || provider.empty())
337  return std::unique_ptr<PK_Ops::Signature>(new ECDSA_Signature_Operation(*this, params, rng));
338 
339  throw Provider_Not_Found(algo_name(), provider);
340  }
341 
342 }
fe X
Definition: ge.cpp:27
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition: ecdsa.cpp:116
const BigInt & private_value() const
Definition: ecc_key.cpp:99
const PointGFp & public_point() const
Definition: ecc_key.h:57
bool is_zero() const
Definition: bigint.h:420
BigInt get_affine_x() const
Definition: point_gfp.cpp:499
bool signature_consistency_check(RandomNumberGenerator &rng, const Private_Key &private_key, const Public_Key &public_key, const std::string &padding)
Definition: keypair.cpp:49
const EC_Group & domain() const
Definition: ecc_key.h:72
std::string hash_for_emsa(const std::string &algo_spec)
Definition: emsa.cpp:189
std::unique_ptr< PK_Ops::Verification > create_verification_op(const std::string &params, const std::string &provider) const override
Definition: ecdsa.cpp:262
Definition: alg_id.cpp:13
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
Definition: ecdsa.cpp:302
bool is_zero() const
Definition: point_gfp.h:183
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
Definition: big_code.cpp:111
std::string algo_name() const override
Definition: ecdsa.h:61
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
static secure_vector< uint8_t > encode_fixed_length_int_pair(const BigInt &n1, const BigInt &n2, size_t bytes)
Definition: big_code.cpp:133
uint8_t recovery_param(const std::vector< uint8_t > &msg, const BigInt &r, const BigInt &s) const
Definition: ecdsa.cpp:92