Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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/divide.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 */
26 DSA_PublicKey::DSA_PublicKey(const DL_Group& grp, const BigInt& y1)
27 {
28 m_group = grp;
29 m_y = y1;
30 }
31
32 /*
33 * Create a DSA private key
34 */
35 DSA_PrivateKey::DSA_PrivateKey(RandomNumberGenerator& rng,
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
46 m_y = m_group.power_g_p(m_x, m_group.q_bits());
47 }
48
49 DSA_PrivateKey::DSA_PrivateKey(const AlgorithmIdentifier& alg_id,
50 const secure_vector<uint8_t>& key_bits) :
51 DL_Scheme_PrivateKey(alg_id, key_bits, DL_Group::ANSI_X9_57)
52 {
53 m_y = m_group.power_g_p(m_x, m_group.q_bits());
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,
79 const std::string& emsa,
80 RandomNumberGenerator& rng) :
81 PK_Ops::Signature_with_EMSA(emsa),
82 m_group(dsa.get_group()),
83 m_x(dsa.get_x())
84 {
85 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
86 m_rfc6979_hash = hash_for_emsa(emsa);
87 #endif
88
89 m_b = BigInt::random_integer(rng, 2, dsa.group_q());
90 m_b_inv = m_group.inverse_mod_q(m_b);
91 }
92
93 size_t signature_length() const override { return 2*m_group.q_bytes(); }
94 size_t max_input_bits() const override { return m_group.q_bits(); }
95
96 secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len,
97 RandomNumberGenerator& rng) override;
98 private:
99 const DL_Group m_group;
100 const BigInt& m_x;
101 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
102 std::string m_rfc6979_hash;
103 #endif
104
105 BigInt m_b, m_b_inv;
106 };
107
108 secure_vector<uint8_t>
109 DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
110 RandomNumberGenerator& rng)
111 {
112 const BigInt& q = m_group.get_q();
113
114 BigInt m(msg, msg_len, m_group.q_bits());
115
116 while(m >= q)
117 m -= q;
118
119 #if defined(BOTAN_HAS_RFC6979_GENERATOR)
120 BOTAN_UNUSED(rng);
121 const BigInt k = generate_rfc6979_nonce(m_x, q, m, m_rfc6979_hash);
122 #else
123 const BigInt k = BigInt::random_integer(rng, 1, q);
124 #endif
125
126 const BigInt k_inv = m_group.inverse_mod_q(k);
127
128 /*
129 * It may not be strictly necessary for the reduction (g^k mod p) mod q to be
130 * const time, since r is published as part of the signature, and deriving
131 * anything useful about k from g^k mod p would seem to require computing a
132 * discrete logarithm.
133 *
134 * However it only increases the cost of signatures by about 7-10%, and DSA is
135 * only for legacy use anyway so we don't care about the performance so much.
136 */
137 const BigInt r = ct_modulo(m_group.power_g_p(k, m_group.q_bits()), m_group.get_q());
138
139 /*
140 * Blind the input message and compute x*r+m as (x*r*b + m*b)/b
141 */
142 m_b = m_group.square_mod_q(m_b);
143 m_b_inv = m_group.square_mod_q(m_b_inv);
144
145 m = m_group.multiply_mod_q(m_b, m);
146 const BigInt xr = m_group.multiply_mod_q(m_b, m_x, r);
147
148 const BigInt s = m_group.multiply_mod_q(m_b_inv, k_inv, m_group.mod_q(xr+m));
149
150 // With overwhelming probability, a bug rather than actual zero r/s
151 if(r.is_zero() || s.is_zero())
152 throw Internal_Error("Computed zero r/s during DSA signature");
153
154 return BigInt::encode_fixed_length_int_pair(r, s, q.bytes());
155 }
156
157 /**
158 * Object that can verify a DSA signature
159 */
160 class DSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA
161 {
162 public:
163 DSA_Verification_Operation(const DSA_PublicKey& dsa,
164 const std::string& emsa) :
165 PK_Ops::Verification_with_EMSA(emsa),
166 m_group(dsa.get_group()),
167 m_y(dsa.get_y())
168 {
169 }
170
171 size_t max_input_bits() const override { return m_group.q_bits(); }
172
173 bool with_recovery() const override { return false; }
174
175 bool verify(const uint8_t msg[], size_t msg_len,
176 const uint8_t sig[], size_t sig_len) override;
177 private:
178 const DL_Group m_group;
179 const BigInt& m_y;
180 };
181
182 bool DSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
183 const uint8_t sig[], size_t sig_len)
184 {
185 const BigInt& q = m_group.get_q();
186 const size_t q_bytes = q.bytes();
187
188 if(sig_len != 2*q_bytes || msg_len > q_bytes)
189 return false;
190
191 BigInt r(sig, q_bytes);
192 BigInt s(sig + q_bytes, q_bytes);
193 BigInt i(msg, msg_len, q.bits());
194
195 if(r <= 0 || r >= q || s <= 0 || s >= q)
196 return false;
197
198 s = inverse_mod(s, q);
199
200 const BigInt sr = m_group.multiply_mod_q(s, r);
201 const BigInt si = m_group.multiply_mod_q(s, i);
202
203 s = m_group.multi_exponentiate(si, m_y, sr);
204
205 // s is too big for Barrett, and verification doesn't need to be const-time
206 return (s % m_group.get_q() == r);
207 }
208
209 }
210
211 std::unique_ptr<PK_Ops::Verification>
212 DSA_PublicKey::create_verification_op(const std::string& params,
213 const std::string& provider) const
214 {
215 if(provider == "base" || provider.empty())
216 return std::unique_ptr<PK_Ops::Verification>(new DSA_Verification_Operation(*this, params));
217 throw Provider_Not_Found(algo_name(), provider);
218 }
219
220 std::unique_ptr<PK_Ops::Signature>
221 DSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
222 const std::string& params,
223 const std::string& provider) const
224 {
225 if(provider == "base" || provider.empty())
226 return std::unique_ptr<PK_Ops::Signature>(new DSA_Signature_Operation(*this, params, rng));
227 throw Provider_Not_Found(algo_name(), provider);
228 }
229
230 }
Botan::DL_Scheme_PrivateKey
Definition: dl_algo.h:103
m_b_inv
BigInt m_b_inv
Definition: dsa.cpp:105
Botan::DL_Group::q_bits
size_t q_bits() const
Definition: dl_group.cpp:446
Botan::DL_Scheme_PrivateKey::m_x
BigInt m_x
Definition: dl_algo.h:135
Botan::BigInt
Definition: bigint.h:24
Botan::DL_Group::square_mod_q
BigInt square_mod_q(const BigInt &x) const
Definition: dl_group.cpp:509
m_x
const BigInt & m_x
Definition: dsa.cpp:100
Botan::RandomNumberGenerator
Definition: rng.h:24
final
int(* final)(unsigned char *, CTX *)
Definition: commoncrypto_hash.cpp:28
Botan::DL_Scheme_PublicKey::group_q
const BigInt & group_q() const
Definition: dl_algo.h:55
Botan::DSA_PrivateKey::create_signature_op
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &rng, const std::string &params, const std::string &provider) const override
Definition: dsa.cpp:221
Botan::DL_Group::get_q
const BigInt & get_q() const
Definition: dl_group.cpp:426
Botan::ct_modulo
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition: divide.cpp:118
m_b
BigInt m_b
Definition: dsa.cpp:105
m_y
const BigInt & m_y
Definition: dsa.cpp:179
Botan::BigInt::random_integer
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
Definition: big_rand.cpp:45
Botan::generate_rfc6979_nonce
BigInt generate_rfc6979_nonce(const BigInt &x, const BigInt &q, const BigInt &h, const std::string &hash)
Definition: rfc6979.cpp:49
Botan::DL_Group::inverse_mod_q
BigInt inverse_mod_q(const BigInt &x) const
Definition: dl_group.cpp:484
Botan::KeyPair::signature_consistency_check
bool signature_consistency_check(RandomNumberGenerator &rng, const Private_Key &private_key, const Public_Key &public_key, const std::string &padding)
Definition: keypair.cpp:49
Botan::DL_Group
Definition: dl_group.h:23
Botan::secure_vector
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:65
Botan::DSA_PublicKey::algo_name
std::string algo_name() const override
Definition: dsa.h:21
Botan::DL_Scheme_PublicKey::m_group
DL_Group m_group
Definition: dl_algo.h:97
Botan::DSA_PrivateKey
Definition: dsa.h:55
Botan::DL_Scheme_PublicKey::m_y
BigInt m_y
Definition: dl_algo.h:92
Botan::hash_for_emsa
std::string hash_for_emsa(const std::string &algo_spec)
Definition: emsa.cpp:189
Botan::inverse_mod
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:325
Botan::DSA_PrivateKey::DSA_PrivateKey
DSA_PrivateKey(const AlgorithmIdentifier &alg_id, const secure_vector< uint8_t > &key_bits)
Definition: dsa.cpp:49
m_group
const DL_Group m_group
Definition: dsa.cpp:99
Botan::PK_Ops::Signature_with_EMSA
Definition: pk_ops_impl.h:127
Botan
Definition: alg_id.cpp:13
Botan::DL_Group::multi_exponentiate
BigInt multi_exponentiate(const BigInt &x, const BigInt &y, const BigInt &z) const
Definition: dl_group.cpp:515
BOTAN_UNUSED
#define BOTAN_UNUSED(...)
Definition: assert.h:142
Botan::DL_Group::multiply_mod_q
BigInt multiply_mod_q(const BigInt &x, const BigInt &y) const
Definition: dl_group.cpp:497
Botan::DL_Group::power_g_p
BigInt power_g_p(const BigInt &x) const
Definition: dl_group.cpp:520
Botan::DL_Group::mod_q
BigInt mod_q(const BigInt &x) const
Definition: dl_group.cpp:491
Botan::DL_Scheme_PrivateKey::check_key
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition: dl_algo.cpp:78
Botan::DSA_PublicKey::DSA_PublicKey
DSA_PublicKey()=default
Botan::AlgorithmIdentifier
Definition: alg_id.h:21
Botan::DSA_PrivateKey::check_key
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition: dsa.cpp:59
Botan::DSA_PublicKey::create_verification_op
std::unique_ptr< PK_Ops::Verification > create_verification_op(const std::string &params, const std::string &provider) const override
Definition: dsa.cpp:212
Botan::OCSP::Response_Status_Code::Internal_Error
Botan::Provider_Not_Found
Definition: exceptn.h:278
Botan::BigInt::encode_fixed_length_int_pair
static secure_vector< uint8_t > encode_fixed_length_int_pair(const BigInt &n1, const BigInt &n2, size_t bytes)
Definition: big_code.cpp:133
Botan::BigInt::bytes
size_t bytes() const
Definition: bigint.cpp:273