/src/botan/src/lib/pubkey/dsa/dsa.cpp
Line | Count | Source (jump to first uncovered line) |
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 | 0 | { |
28 | 0 | m_group = grp; |
29 | 0 | m_y = y1; |
30 | 0 | } Unexecuted instantiation: Botan::DSA_PublicKey::DSA_PublicKey(Botan::DL_Group const&, Botan::BigInt const&) Unexecuted instantiation: Botan::DSA_PublicKey::DSA_PublicKey(Botan::DL_Group const&, Botan::BigInt const&) |
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 | 0 | { |
39 | 0 | m_group = grp; |
40 | 0 |
|
41 | 0 | if(x_arg == 0) |
42 | 0 | m_x = BigInt::random_integer(rng, 2, group_q()); |
43 | 0 | else |
44 | 0 | m_x = x_arg; |
45 | 0 |
|
46 | 0 | m_y = m_group.power_g_p(m_x, m_group.q_bits()); |
47 | 0 | } Unexecuted instantiation: Botan::DSA_PrivateKey::DSA_PrivateKey(Botan::RandomNumberGenerator&, Botan::DL_Group const&, Botan::BigInt const&) Unexecuted instantiation: Botan::DSA_PrivateKey::DSA_PrivateKey(Botan::RandomNumberGenerator&, Botan::DL_Group const&, Botan::BigInt const&) |
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 | 158 | { |
53 | 158 | m_y = m_group.power_g_p(m_x, m_group.q_bits()); |
54 | 158 | } Unexecuted instantiation: Botan::DSA_PrivateKey::DSA_PrivateKey(Botan::AlgorithmIdentifier const&, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&) Botan::DSA_PrivateKey::DSA_PrivateKey(Botan::AlgorithmIdentifier const&, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&) Line | Count | Source | 52 | 158 | { | 53 | 158 | m_y = m_group.power_g_p(m_x, m_group.q_bits()); | 54 | 158 | } |
|
55 | | |
56 | | /* |
57 | | * Check Private DSA Parameters |
58 | | */ |
59 | | bool DSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const |
60 | 0 | { |
61 | 0 | if(!DL_Scheme_PrivateKey::check_key(rng, strong) || m_x >= group_q()) |
62 | 0 | return false; |
63 | 0 | |
64 | 0 | if(!strong) |
65 | 0 | return true; |
66 | 0 | |
67 | 0 | return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-256)"); |
68 | 0 | } |
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 | 0 | { |
85 | 0 | #if defined(BOTAN_HAS_RFC6979_GENERATOR) |
86 | 0 | m_rfc6979_hash = hash_for_emsa(emsa); |
87 | 0 | #endif |
88 | 0 |
|
89 | 0 | m_b = BigInt::random_integer(rng, 2, dsa.group_q()); |
90 | 0 | m_b_inv = m_group.inverse_mod_q(m_b); |
91 | 0 | } |
92 | | |
93 | 0 | size_t signature_length() const override { return 2*m_group.q_bytes(); } |
94 | 0 | 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 | 0 | { |
112 | 0 | const BigInt& q = m_group.get_q(); |
113 | 0 |
|
114 | 0 | BigInt m(msg, msg_len, m_group.q_bits()); |
115 | 0 |
|
116 | 0 | while(m >= q) |
117 | 0 | m -= q; |
118 | 0 |
|
119 | 0 | #if defined(BOTAN_HAS_RFC6979_GENERATOR) |
120 | 0 | BOTAN_UNUSED(rng); |
121 | 0 | 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 | 0 | const BigInt k_inv = m_group.inverse_mod_q(k); |
127 | 0 |
|
128 | 0 | /* |
129 | 0 | * It may not be strictly necessary for the reduction (g^k mod p) mod q to be |
130 | 0 | * const time, since r is published as part of the signature, and deriving |
131 | 0 | * anything useful about k from g^k mod p would seem to require computing a |
132 | 0 | * discrete logarithm. |
133 | 0 | * |
134 | 0 | * However it only increases the cost of signatures by about 7-10%, and DSA is |
135 | 0 | * only for legacy use anyway so we don't care about the performance so much. |
136 | 0 | */ |
137 | 0 | const BigInt r = ct_modulo(m_group.power_g_p(k, m_group.q_bits()), m_group.get_q()); |
138 | 0 |
|
139 | 0 | /* |
140 | 0 | * Blind the input message and compute x*r+m as (x*r*b + m*b)/b |
141 | 0 | */ |
142 | 0 | m_b = m_group.square_mod_q(m_b); |
143 | 0 | m_b_inv = m_group.square_mod_q(m_b_inv); |
144 | 0 |
|
145 | 0 | m = m_group.multiply_mod_q(m_b, m); |
146 | 0 | const BigInt xr = m_group.multiply_mod_q(m_b, m_x, r); |
147 | 0 |
|
148 | 0 | const BigInt s = m_group.multiply_mod_q(m_b_inv, k_inv, m_group.mod_q(xr+m)); |
149 | 0 |
|
150 | 0 | // With overwhelming probability, a bug rather than actual zero r/s |
151 | 0 | if(r.is_zero() || s.is_zero()) |
152 | 0 | throw Internal_Error("Computed zero r/s during DSA signature"); |
153 | 0 | |
154 | 0 | return BigInt::encode_fixed_length_int_pair(r, s, q.bytes()); |
155 | 0 | } |
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 | 107 | { |
169 | 107 | } |
170 | | |
171 | 101 | size_t max_input_bits() const override { return m_group.q_bits(); } |
172 | | |
173 | 101 | 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 | 101 | { |
185 | 101 | const BigInt& q = m_group.get_q(); |
186 | 101 | const size_t q_bytes = q.bytes(); |
187 | 101 | |
188 | 101 | if(sig_len != 2*q_bytes || msg_len > q_bytes) |
189 | 0 | return false; |
190 | 101 | |
191 | 101 | BigInt r(sig, q_bytes); |
192 | 101 | BigInt s(sig + q_bytes, q_bytes); |
193 | 101 | BigInt i(msg, msg_len, q.bits()); |
194 | 101 | |
195 | 101 | if(r <= 0 || r >= q || s <= 0 || s >= q) |
196 | 3 | return false; |
197 | 98 | |
198 | 98 | s = inverse_mod(s, q); |
199 | 98 | |
200 | 98 | const BigInt sr = m_group.multiply_mod_q(s, r); |
201 | 98 | const BigInt si = m_group.multiply_mod_q(s, i); |
202 | 98 | |
203 | 98 | s = m_group.multi_exponentiate(si, m_y, sr); |
204 | 98 | |
205 | 98 | // s is too big for Barrett, and verification doesn't need to be const-time |
206 | 98 | return (s % m_group.get_q() == r); |
207 | 98 | } |
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 | 107 | { |
215 | 107 | if(provider == "base" || provider.empty()) |
216 | 107 | return std::unique_ptr<PK_Ops::Verification>(new DSA_Verification_Operation(*this, params)); |
217 | 0 | throw Provider_Not_Found(algo_name(), provider); |
218 | 0 | } |
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 | 0 | { |
225 | 0 | if(provider == "base" || provider.empty()) |
226 | 0 | return std::unique_ptr<PK_Ops::Signature>(new DSA_Signature_Operation(*this, params, rng)); |
227 | 0 | throw Provider_Not_Found(algo_name(), provider); |
228 | 0 | } |
229 | | |
230 | | } |