Botan  2.7.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 
33  bool strong) const
34  {
35  if(!public_point().on_the_curve())
36  return false;
37 
38  if(!strong)
39  return true;
40 
41  return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-256)");
42  }
43 
44 namespace {
45 
46 /**
47 * ECDSA signature operation
48 */
49 class ECDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
50  {
51  public:
52 
53  ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa,
54  const std::string& emsa,
55  RandomNumberGenerator& rng) :
56  PK_Ops::Signature_with_EMSA(emsa),
57  m_group(ecdsa.domain()),
58  m_x(ecdsa.private_value())
59  {
60 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
61  m_rfc6979_hash = hash_for_emsa(emsa);
62 #endif
63 
64  m_b = m_group.random_scalar(rng);
65  m_b_inv = m_group.inverse_mod_order(m_b);
66  }
67 
68  size_t max_input_bits() const override { return m_group.get_order_bits(); }
69 
70  secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len,
71  RandomNumberGenerator& rng) override;
72 
73  private:
74  const EC_Group m_group;
75  const BigInt& m_x;
76 
77 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
78  std::string m_rfc6979_hash;
79 #endif
80 
81  std::vector<BigInt> m_ws;
82 
83  BigInt m_b, m_b_inv;
84  };
85 
86 secure_vector<uint8_t>
87 ECDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
88  RandomNumberGenerator& rng)
89  {
90  BigInt m(msg, msg_len, m_group.get_order_bits());
91 
92 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
93  const BigInt k = generate_rfc6979_nonce(m_x, m_group.get_order(), m, m_rfc6979_hash);
94 #else
95  const BigInt k = m_group.random_scalar(rng);
96 #endif
97 
98  const BigInt r = m_group.mod_order(
99  m_group.blinded_base_point_multiply_x(k, rng, m_ws));
100 
101  const BigInt k_inv = m_group.inverse_mod_order(k);
102 
103  /*
104  * Blind the input message and compute x*r+m as (x*r*b + m*b)/b
105  */
106  m_b = m_group.square_mod_order(m_b);
107  m_b_inv = m_group.square_mod_order(m_b_inv);
108 
109  m = m_group.multiply_mod_order(m_b, m);
110  const BigInt xr = m_group.multiply_mod_order(m_x, m_b, r);
111 
112  const BigInt s = m_group.multiply_mod_order(k_inv, xr + m, m_b_inv);
113 
114  // With overwhelming probability, a bug rather than actual zero r/s
115  if(r.is_zero() || s.is_zero())
116  throw Internal_Error("During ECDSA signature generated zero r/s");
117 
118  return BigInt::encode_fixed_length_int_pair(r, s, m_group.get_order_bytes());
119  }
120 
121 /**
122 * ECDSA verification operation
123 */
124 class ECDSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA
125  {
126  public:
127  ECDSA_Verification_Operation(const ECDSA_PublicKey& ecdsa,
128  const std::string& emsa) :
129  PK_Ops::Verification_with_EMSA(emsa),
130  m_group(ecdsa.domain()),
131  m_gy_mul(m_group.get_base_point(), ecdsa.public_point())
132  {
133  }
134 
135  size_t max_input_bits() const override { return m_group.get_order_bits(); }
136 
137  bool with_recovery() const override { return false; }
138 
139  bool verify(const uint8_t msg[], size_t msg_len,
140  const uint8_t sig[], size_t sig_len) override;
141  private:
142  const EC_Group m_group;
143  const PointGFp_Multi_Point_Precompute m_gy_mul;
144  };
145 
146 bool ECDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
147  const uint8_t sig[], size_t sig_len)
148  {
149  if(sig_len != m_group.get_order_bytes() * 2)
150  return false;
151 
152  const BigInt e(msg, msg_len, m_group.get_order_bits());
153 
154  const BigInt r(sig, sig_len / 2);
155  const BigInt s(sig + sig_len / 2, sig_len / 2);
156 
157  if(r <= 0 || r >= m_group.get_order() || s <= 0 || s >= m_group.get_order())
158  return false;
159 
160  const BigInt w = m_group.inverse_mod_order(s);
161 
162  const BigInt u1 = m_group.multiply_mod_order(m_group.mod_order(e), w);
163  const BigInt u2 = m_group.multiply_mod_order(r, w);
164  const PointGFp R = m_gy_mul.multi_exp(u1, u2);
165 
166  if(R.is_zero())
167  return false;
168 
169  const BigInt v = m_group.mod_order(R.get_affine_x());
170  return (v == r);
171  }
172 
173 }
174 
175 std::unique_ptr<PK_Ops::Verification>
176 ECDSA_PublicKey::create_verification_op(const std::string& params,
177  const std::string& provider) const
178  {
179 #if defined(BOTAN_HAS_BEARSSL)
180  if(provider == "bearssl" || provider.empty())
181  {
182  try
183  {
184  return make_bearssl_ecdsa_ver_op(*this, params);
185  }
186  catch(Lookup_Error& e)
187  {
188  if(provider == "bearssl")
189  throw;
190  }
191  }
192 #endif
193 
194 #if defined(BOTAN_HAS_OPENSSL)
195  if(provider == "openssl" || provider.empty())
196  {
197  try
198  {
199  return make_openssl_ecdsa_ver_op(*this, params);
200  }
201  catch(Lookup_Error& e)
202  {
203  if(provider == "openssl")
204  throw;
205  }
206  }
207 #endif
208 
209  if(provider == "base" || provider.empty())
210  return std::unique_ptr<PK_Ops::Verification>(new ECDSA_Verification_Operation(*this, params));
211 
212  throw Provider_Not_Found(algo_name(), provider);
213  }
214 
215 std::unique_ptr<PK_Ops::Signature>
217  const std::string& params,
218  const std::string& provider) const
219  {
220 #if defined(BOTAN_HAS_BEARSSL)
221  if(provider == "bearssl" || provider.empty())
222  {
223  try
224  {
225  return make_bearssl_ecdsa_sig_op(*this, params);
226  }
227  catch(Lookup_Error& e)
228  {
229  if(provider == "bearssl")
230  throw;
231  }
232  }
233 #endif
234 
235 #if defined(BOTAN_HAS_OPENSSL)
236  if(provider == "openssl" || provider.empty())
237  {
238  try
239  {
240  return make_openssl_ecdsa_sig_op(*this, params);
241  }
242  catch(Lookup_Error& e)
243  {
244  if(provider == "openssl")
245  throw;
246  }
247  }
248 #endif
249 
250  if(provider == "base" || provider.empty())
251  return std::unique_ptr<PK_Ops::Signature>(new ECDSA_Signature_Operation(*this, params, rng));
252 
253  throw Provider_Not_Found(algo_name(), provider);
254  }
255 
256 }
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition: ecdsa.cpp:32
PointGFp multi_exp(const BigInt &k1, const BigInt &k2) const
Definition: point_mul.cpp:341
const PointGFp & public_point() const
Definition: ecc_key.h:57
BigInt generate_rfc6979_nonce(const BigInt &x, const BigInt &q, const BigInt &h, const std::string &hash)
Definition: rfc6979.cpp:49
bool signature_consistency_check(RandomNumberGenerator &rng, const Private_Key &private_key, const Public_Key &public_key, const std::string &padding)
Definition: keypair.cpp:49
std::string hash_for_emsa(const std::string &algo_spec)
Definition: emsa.cpp:168
std::unique_ptr< PK_Ops::Verification > create_verification_op(const std::string &params, const std::string &provider) const override
Definition: ecdsa.cpp:176
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:216
std::string algo_name() const override
Definition: ecdsa.h:46
static secure_vector< uint8_t > encode_fixed_length_int_pair(const BigInt &n1, const BigInt &n2, size_t bytes)
Definition: big_code.cpp:103