Botan  2.6.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/pow_mod.h>
12 #include <botan/reducer.h>
13 #include <botan/rng.h>
14 #include <botan/internal/pk_ops_impl.h>
15 
16 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
17  #include <botan/emsa.h>
18  #include <botan/rfc6979.h>
19 #endif
20 
21 namespace Botan {
22 
23 /*
24 * DSA_PublicKey Constructor
25 */
27  {
28  m_group = grp;
29  m_y = y1;
30  }
31 
32 /*
33 * Create a DSA private key
34 */
36  const DL_Group& grp,
37  const BigInt& x_arg)
38  {
39  m_group = grp;
40 
41  if(x_arg == 0)
42  m_x = BigInt::random_integer(rng, 2, group_q());
43  else
44  m_x = x_arg;
45 
47  }
48 
50  const secure_vector<uint8_t>& key_bits) :
51  DL_Scheme_PrivateKey(alg_id, key_bits, DL_Group::ANSI_X9_57)
52  {
54  }
55 
56 /*
57 * Check Private DSA Parameters
58 */
59 bool DSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
60  {
61  if(!DL_Scheme_PrivateKey::check_key(rng, strong) || m_x >= group_q())
62  return false;
63 
64  if(!strong)
65  return true;
66 
67  return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-256)");
68  }
69 
70 namespace {
71 
72 /**
73 * Object that can create a DSA signature
74 */
75 class DSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA
76  {
77  public:
78  DSA_Signature_Operation(const DSA_PrivateKey& dsa, const std::string& emsa) :
79  PK_Ops::Signature_with_EMSA(emsa),
80  m_group(dsa.get_group()),
81  m_x(dsa.get_x()),
82  m_mod_q(dsa.group_q())
83  {
84 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
85  m_rfc6979_hash = hash_for_emsa(emsa);
86 #endif
87  }
88 
89  size_t max_input_bits() const override { return m_group.get_q().bits(); }
90 
91  secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len,
92  RandomNumberGenerator& rng) override;
93  private:
94  const DL_Group m_group;
95  const BigInt& m_x;
96  Modular_Reducer m_mod_q;
97 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
98  std::string m_rfc6979_hash;
99 #endif
100  };
101 
102 secure_vector<uint8_t>
103 DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
104  RandomNumberGenerator& rng)
105  {
106  const BigInt& q = m_group.get_q();
107 
108  BigInt i(msg, msg_len, q.bits());
109 
110  while(i >= q)
111  i -= q;
112 
113 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
114  BOTAN_UNUSED(rng);
115  const BigInt k = generate_rfc6979_nonce(m_x, q, i, m_rfc6979_hash);
116 #else
117  const BigInt k = BigInt::random_integer(rng, 1, q);
118 #endif
119 
120  BigInt s = inverse_mod(k, q);
121  const BigInt r = m_mod_q.reduce(m_group.power_g_p(k));
122 
123  s = m_mod_q.multiply(s, mul_add(m_x, r, i));
124 
125  // With overwhelming probability, a bug rather than actual zero r/s
126  if(r.is_zero() || s.is_zero())
127  throw Internal_Error("Computed zero r/s during DSA signature");
128 
129  return BigInt::encode_fixed_length_int_pair(r, s, q.bytes());
130  }
131 
132 /**
133 * Object that can verify a DSA signature
134 */
135 class DSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA
136  {
137  public:
138  DSA_Verification_Operation(const DSA_PublicKey& dsa,
139  const std::string& emsa) :
140  PK_Ops::Verification_with_EMSA(emsa),
141  m_group(dsa.get_group()),
142  m_y(dsa.get_y()),
143  m_mod_q(dsa.group_q())
144  {}
145 
146  size_t max_input_bits() const override { return m_group.get_q().bits(); }
147 
148  bool with_recovery() const override { return false; }
149 
150  bool verify(const uint8_t msg[], size_t msg_len,
151  const uint8_t sig[], size_t sig_len) override;
152  private:
153  const DL_Group m_group;
154  const BigInt& m_y;
155 
156  Modular_Reducer m_mod_q;
157  };
158 
159 bool DSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
160  const uint8_t sig[], size_t sig_len)
161  {
162  const BigInt& q = m_group.get_q();
163  const size_t q_bytes = q.bytes();
164 
165  if(sig_len != 2*q_bytes || msg_len > q_bytes)
166  return false;
167 
168  BigInt r(sig, q_bytes);
169  BigInt s(sig + q_bytes, q_bytes);
170  BigInt i(msg, msg_len, q.bits());
171 
172  if(r <= 0 || r >= q || s <= 0 || s >= q)
173  return false;
174 
175  s = inverse_mod(s, q);
176 
177  const BigInt sr = m_mod_q.multiply(s, r);
178  const BigInt si = m_mod_q.multiply(s, i);
179 
180  s = m_group.multi_exponentiate(si, m_y, sr);
181 
182  return (m_mod_q.reduce(s) == r);
183  }
184 
185 }
186 
187 std::unique_ptr<PK_Ops::Verification>
188 DSA_PublicKey::create_verification_op(const std::string& params,
189  const std::string& provider) const
190  {
191  if(provider == "base" || provider.empty())
192  return std::unique_ptr<PK_Ops::Verification>(new DSA_Verification_Operation(*this, params));
193  throw Provider_Not_Found(algo_name(), provider);
194  }
195 
196 std::unique_ptr<PK_Ops::Signature>
198  const std::string& params,
199  const std::string& provider) const
200  {
201  if(provider == "base" || provider.empty())
202  return std::unique_ptr<PK_Ops::Signature>(new DSA_Signature_Operation(*this, params));
203  throw Provider_Not_Found(algo_name(), provider);
204  }
205 
206 }
BigInt mul_add(const BigInt &a, const BigInt &b, const BigInt &c)
Definition: mp_numth.cpp:30
Modular_Reducer m_mod_q
Definition: rsa.cpp:259
BigInt power_g_p(const BigInt &x) const
Definition: dl_group.cpp:447
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
Definition: dsa.cpp:197
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
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:279
DSA_PrivateKey(const AlgorithmIdentifier &alg_id, const secure_vector< uint8_t > &key_bits)
Definition: dsa.cpp:49
Definition: alg_id.cpp:13
size_t bytes() const
Definition: bigint.cpp:208
#define BOTAN_UNUSED(...)
Definition: assert.h:117
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:31
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition: dl_algo.cpp:76
BigInt multi_exponentiate(const BigInt &x, const BigInt &y, const BigInt &z) const
Definition: dl_group.cpp:442
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition: dsa.cpp:59
std::unique_ptr< PK_Ops::Verification > create_verification_op(const std::string &params, const std::string &provider) const override
Definition: dsa.cpp:188
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
const BigInt & group_q() const
Definition: dl_algo.h:55
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31
const BigInt & get_q() const
Definition: dl_group.cpp:396