Botan  2.7.0
Crypto and TLS for C++11
dsa.cpp
Go to the documentation of this file.
1 /*
2 * DSA
3 * (C) 1999-2010,2014,2016 Jack Lloyd
4 * (C) 2016 RenĂ© Korthaus
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 */
8 
9 #include <botan/dsa.h>
10 #include <botan/keypair.h>
11 #include <botan/reducer.h>
12 #include <botan/rng.h>
13 #include <botan/internal/pk_ops_impl.h>
14 
15 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
16  #include <botan/emsa.h>
17  #include <botan/rfc6979.h>
18 #endif
19 
20 namespace Botan {
21 
22 /*
23 * DSA_PublicKey Constructor
24 */
26  {
27  m_group = grp;
28  m_y = y1;
29  }
30 
31 /*
32 * Create a DSA private key
33 */
35  const DL_Group& grp,
36  const BigInt& x_arg)
37  {
38  m_group = grp;
39 
40  if(x_arg == 0)
41  m_x = BigInt::random_integer(rng, 2, group_q());
42  else
43  m_x = x_arg;
44 
46  }
47 
49  const secure_vector<uint8_t>& key_bits) :
50  DL_Scheme_PrivateKey(alg_id, key_bits, DL_Group::ANSI_X9_57)
51  {
53  }
54 
55 /*
56 * Check Private DSA Parameters
57 */
58 bool DSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
59  {
60  if(!DL_Scheme_PrivateKey::check_key(rng, strong) || m_x >= group_q())
61  return false;
62 
63  if(!strong)
64  return true;
65 
66  return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-256)");
67  }
68 
69 namespace {
70 
71 /**
72 * Object that can create a DSA signature
73 */
74 class DSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
75  {
76  public:
77  DSA_Signature_Operation(const DSA_PrivateKey& dsa,
78  const std::string& emsa,
79  RandomNumberGenerator& rng) :
80  PK_Ops::Signature_with_EMSA(emsa),
81  m_group(dsa.get_group()),
82  m_x(dsa.get_x())
83  {
84 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
85  m_rfc6979_hash = hash_for_emsa(emsa);
86 #endif
87 
88  m_b = BigInt::random_integer(rng, 2, dsa.group_q());
89  m_b_inv = m_group.inverse_mod_q(m_b);
90  }
91 
92  size_t max_input_bits() const override { return m_group.get_q().bits(); }
93 
94  secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len,
95  RandomNumberGenerator& rng) override;
96  private:
97  const DL_Group m_group;
98  const BigInt& m_x;
99 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
100  std::string m_rfc6979_hash;
101 #endif
102 
103  BigInt m_b, m_b_inv;
104  };
105 
106 secure_vector<uint8_t>
107 DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
108  RandomNumberGenerator& rng)
109  {
110  const BigInt& q = m_group.get_q();
111 
112  BigInt m(msg, msg_len, m_group.q_bits());
113 
114  while(m >= q)
115  m -= q;
116 
117 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
118  BOTAN_UNUSED(rng);
119  const BigInt k = generate_rfc6979_nonce(m_x, q, m, m_rfc6979_hash);
120 #else
121  const BigInt k = BigInt::random_integer(rng, 1, q);
122 #endif
123 
124  const BigInt k_inv = m_group.inverse_mod_q(k);
125 
126  const BigInt r = m_group.mod_q(m_group.power_g_p(k, m_group.q_bits()));
127 
128  /*
129  * Blind the input message and compute x*r+m as (x*r*b + m*b)/b
130  */
131  m_b = m_group.square_mod_q(m_b);
132  m_b_inv = m_group.square_mod_q(m_b_inv);
133 
134  m = m_group.multiply_mod_q(m_b, m);
135  const BigInt xr = m_group.multiply_mod_q(m_b, m_x, r);
136 
137  const BigInt s = m_group.multiply_mod_q(m_b_inv, k_inv, m_group.mod_q(xr+m));
138 
139  // With overwhelming probability, a bug rather than actual zero r/s
140  if(r.is_zero() || s.is_zero())
141  throw Internal_Error("Computed zero r/s during DSA signature");
142 
143  return BigInt::encode_fixed_length_int_pair(r, s, q.bytes());
144  }
145 
146 /**
147 * Object that can verify a DSA signature
148 */
149 class DSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA
150  {
151  public:
152  DSA_Verification_Operation(const DSA_PublicKey& dsa,
153  const std::string& emsa) :
154  PK_Ops::Verification_with_EMSA(emsa),
155  m_group(dsa.get_group()),
156  m_y(dsa.get_y())
157  {
158  }
159 
160  size_t max_input_bits() const override { return m_group.get_q().bits(); }
161 
162  bool with_recovery() const override { return false; }
163 
164  bool verify(const uint8_t msg[], size_t msg_len,
165  const uint8_t sig[], size_t sig_len) override;
166  private:
167  const DL_Group m_group;
168  const BigInt& m_y;
169  };
170 
171 bool DSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
172  const uint8_t sig[], size_t sig_len)
173  {
174  const BigInt& q = m_group.get_q();
175  const size_t q_bytes = q.bytes();
176 
177  if(sig_len != 2*q_bytes || msg_len > q_bytes)
178  return false;
179 
180  BigInt r(sig, q_bytes);
181  BigInt s(sig + q_bytes, q_bytes);
182  BigInt i(msg, msg_len, q.bits());
183 
184  if(r <= 0 || r >= q || s <= 0 || s >= q)
185  return false;
186 
187  s = inverse_mod(s, q);
188 
189  const BigInt sr = m_group.multiply_mod_q(s, r);
190  const BigInt si = m_group.multiply_mod_q(s, i);
191 
192  s = m_group.multi_exponentiate(si, m_y, sr);
193 
194  return (m_group.mod_q(s) == r);
195  }
196 
197 }
198 
199 std::unique_ptr<PK_Ops::Verification>
200 DSA_PublicKey::create_verification_op(const std::string& params,
201  const std::string& provider) const
202  {
203  if(provider == "base" || provider.empty())
204  return std::unique_ptr<PK_Ops::Verification>(new DSA_Verification_Operation(*this, params));
205  throw Provider_Not_Found(algo_name(), provider);
206  }
207 
208 std::unique_ptr<PK_Ops::Signature>
210  const std::string& params,
211  const std::string& provider) const
212  {
213  if(provider == "base" || provider.empty())
214  return std::unique_ptr<PK_Ops::Signature>(new DSA_Signature_Operation(*this, params, rng));
215  throw Provider_Not_Found(algo_name(), provider);
216  }
217 
218 }
BigInt inverse_mod_q(const BigInt &x) const
Definition: dl_group.cpp:477
BigInt power_g_p(const BigInt &x) const
Definition: dl_group.cpp:513
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
Definition: dsa.cpp:209
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition: big_rand.cpp:45
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 algo_name() const override
Definition: dsa.h:21
BigInt square_mod_q(const BigInt &x) const
Definition: dl_group.cpp:502
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:288
DSA_PrivateKey(const AlgorithmIdentifier &alg_id, const secure_vector< uint8_t > &key_bits)
Definition: dsa.cpp:48
BigInt multiply_mod_q(const BigInt &x, const BigInt &y) const
Definition: dl_group.cpp:490
Definition: alg_id.cpp:13
size_t bytes() const
Definition: bigint.cpp:220
#define BOTAN_UNUSED(...)
Definition: assert.h:130
size_t q_bits() const
Definition: dl_group.cpp:445
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition: dl_algo.cpp:78
BigInt multi_exponentiate(const BigInt &x, const BigInt &y, const BigInt &z) const
Definition: dl_group.cpp:508
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition: dsa.cpp:58
std::unique_ptr< PK_Ops::Verification > create_verification_op(const std::string &params, const std::string &provider) const override
Definition: dsa.cpp:200
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
BigInt mod_q(const BigInt &x) const
Definition: dl_group.cpp:484
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 BigInt & group_q() const
Definition: dl_algo.h:55
const BigInt & get_q() const
Definition: dl_group.cpp:425