Botan  2.4.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 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/keypair.h>
14 #include <botan/reducer.h>
15 #include <botan/emsa.h>
16 
17 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
18  #include <botan/rfc6979.h>
19 #endif
20 
21 #if defined(BOTAN_HAS_BEARSSL)
22  #include <botan/internal/bearssl.h>
23 #endif
24 
25 #if defined(BOTAN_HAS_OPENSSL)
26  #include <botan/internal/openssl.h>
27 #endif
28 
29 namespace Botan {
30 
32  bool strong) const
33  {
34  if(!public_point().on_the_curve())
35  return false;
36 
37  if(!strong)
38  return true;
39 
40  return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-256)");
41  }
42 
43 namespace {
44 
45 /**
46 * ECDSA signature operation
47 */
48 class ECDSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
49  {
50  public:
51 
52  ECDSA_Signature_Operation(const ECDSA_PrivateKey& ecdsa,
53  const std::string& emsa) :
55  m_order(ecdsa.domain().get_order()),
56  m_base_point(ecdsa.domain().get_base_point(), m_order),
57  m_x(ecdsa.private_value()),
58  m_mod_order(m_order)
59  {
60 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
61  m_rfc6979_hash = hash_for_emsa(emsa);
62 #endif
63  }
64 
65  size_t max_input_bits() const override { return m_order.bits(); }
66 
67  secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len,
68  RandomNumberGenerator& rng) override;
69 
70  private:
71  const BigInt& m_order;
72  Blinded_Point_Multiply m_base_point;
73  const BigInt& m_x;
74  Modular_Reducer m_mod_order;
75 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
76  std::string m_rfc6979_hash;
77 #endif
78  };
79 
81 ECDSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
83  {
84  const BigInt m(msg, msg_len);
85 
86 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
87  const BigInt k = generate_rfc6979_nonce(m_x, m_order, m, m_rfc6979_hash);
88 #else
89  const BigInt k = BigInt::random_integer(rng, 1, m_order);
90 #endif
91 
92  const PointGFp k_times_P = m_base_point.blinded_multiply(k, rng);
93  const BigInt r = m_mod_order.reduce(k_times_P.get_affine_x());
94  const BigInt s = m_mod_order.multiply(inverse_mod(k, m_order), mul_add(m_x, r, m));
95 
96  // With overwhelming probability, a bug rather than actual zero r/s
97  BOTAN_ASSERT(s != 0, "invalid s");
98  BOTAN_ASSERT(r != 0, "invalid r");
99 
100  return BigInt::encode_fixed_length_int_pair(r, s, m_order.bytes());
101  }
102 
103 /**
104 * ECDSA verification operation
105 */
106 class ECDSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA
107  {
108  public:
109  ECDSA_Verification_Operation(const ECDSA_PublicKey& ecdsa,
110  const std::string& emsa) :
112  m_base_point(ecdsa.domain().get_base_point()),
113  m_public_point(ecdsa.public_point()),
114  m_order(ecdsa.domain().get_order()),
115  m_mod_order(m_order)
116  {
117  //m_public_point.precompute_multiples();
118  }
119 
120  size_t max_input_bits() const override { return m_order.bits(); }
121 
122  bool with_recovery() const override { return false; }
123 
124  bool verify(const uint8_t msg[], size_t msg_len,
125  const uint8_t sig[], size_t sig_len) override;
126  private:
127  const PointGFp& m_base_point;
128  const PointGFp& m_public_point;
129  const BigInt& m_order;
130  // FIXME: should be offered by curve
131  Modular_Reducer m_mod_order;
132  };
133 
134 bool ECDSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
135  const uint8_t sig[], size_t sig_len)
136  {
137  if(sig_len != m_order.bytes()*2)
138  return false;
139 
140  BigInt e(msg, msg_len);
141 
142  BigInt r(sig, sig_len / 2);
143  BigInt s(sig + sig_len / 2, sig_len / 2);
144 
145  if(r <= 0 || r >= m_order || s <= 0 || s >= m_order)
146  return false;
147 
148  BigInt w = inverse_mod(s, m_order);
149 
150  const BigInt u1 = m_mod_order.reduce(e * w);
151  const BigInt u2 = m_mod_order.reduce(r * w);
152  const PointGFp R = multi_exponentiate(m_base_point, u1, m_public_point, u2);
153 
154  if(R.is_zero())
155  return false;
156 
157  const BigInt v = m_mod_order.reduce(R.get_affine_x());
158  return (v == r);
159  }
160 
161 }
162 
163 std::unique_ptr<PK_Ops::Verification>
164 ECDSA_PublicKey::create_verification_op(const std::string& params,
165  const std::string& provider) const
166  {
167 #if defined(BOTAN_HAS_BEARSSL)
168  if(provider == "bearssl" || provider.empty())
169  {
170  try
171  {
172  return make_bearssl_ecdsa_ver_op(*this, params);
173  }
174  catch(Lookup_Error& e)
175  {
176  if(provider == "bearssl")
177  throw;
178  }
179  }
180 #endif
181 
182 #if defined(BOTAN_HAS_OPENSSL)
183  if(provider == "openssl" || provider.empty())
184  {
185  try
186  {
187  return make_openssl_ecdsa_ver_op(*this, params);
188  }
189  catch(Lookup_Error& e)
190  {
191  if(provider == "openssl")
192  throw;
193  }
194  }
195 #endif
196 
197  if(provider == "base" || provider.empty())
198  return std::unique_ptr<PK_Ops::Verification>(new ECDSA_Verification_Operation(*this, params));
199 
200  throw Provider_Not_Found(algo_name(), provider);
201  }
202 
203 std::unique_ptr<PK_Ops::Signature>
205  const std::string& params,
206  const std::string& provider) const
207  {
208 #if defined(BOTAN_HAS_BEARSSL)
209  if(provider == "bearssl" || provider.empty())
210  {
211  try
212  {
213  return make_bearssl_ecdsa_sig_op(*this, params);
214  }
215  catch(Lookup_Error& e)
216  {
217  if(provider == "bearssl")
218  throw;
219  }
220  }
221 #endif
222 
223 #if defined(BOTAN_HAS_OPENSSL)
224  if(provider == "openssl" || provider.empty())
225  {
226  try
227  {
228  return make_openssl_ecdsa_sig_op(*this, params);
229  }
230  catch(Lookup_Error& e)
231  {
232  if(provider == "openssl")
233  throw;
234  }
235  }
236 #endif
237 
238  if(provider == "base" || provider.empty())
239  return std::unique_ptr<PK_Ops::Signature>(new ECDSA_Signature_Operation(*this, params));
240 
241  throw Provider_Not_Found(algo_name(), provider);
242  }
243 
244 }
BigInt mul_add(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:35
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition: ecdsa.cpp:31
const BigInt & private_value() const
Definition: ecc_key.cpp:112
const PointGFp & get_base_point() const
Definition: ec_group.h:96
const PointGFp & public_point() const
Definition: ecc_key.h:57
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition: big_rand.cpp:45
BigInt get_affine_x() const
Definition: point_gfp.cpp:389
#define BOTAN_ASSERT(expr, assertion_made)
Definition: assert.h:29
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
const EC_Group & domain() const
Definition: ecc_key.h:72
std::string hash_for_emsa(const std::string &algo_spec)
Definition: emsa.cpp:168
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:277
std::unique_ptr< PK_Ops::Verification > create_verification_op(const std::string &params, const std::string &provider) const override
Definition: ecdsa.cpp:164
Definition: alg_id.cpp:13
const BigInt & get_order() const
Definition: ec_group.h:102
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
Definition: ecdsa.cpp:204
bool is_zero() const
Definition: point_gfp.h:179
std::string algo_name() const override
Definition: ecdsa.h:46
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
static secure_vector< uint8_t > encode_fixed_length_int_pair(const BigInt &n1, const BigInt &n2, size_t bytes)
Definition: big_code.cpp:103
PointGFp multi_exponentiate(const PointGFp &p1, const BigInt &z1, const PointGFp &p2, const BigInt &z2)
Definition: point_gfp.cpp:247