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