/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/internal/keypair.h> |
11 | | #include <botan/reducer.h> |
12 | | #include <botan/rng.h> |
13 | | #include <botan/internal/divide.h> |
14 | | #include <botan/internal/pk_ops_impl.h> |
15 | | |
16 | | #if defined(BOTAN_HAS_RFC6979_GENERATOR) |
17 | | #include <botan/internal/emsa.h> |
18 | | #include <botan/internal/rfc6979.h> |
19 | | #endif |
20 | | |
21 | | namespace Botan { |
22 | | |
23 | | /* |
24 | | * DSA_PublicKey Constructor |
25 | | */ |
26 | | |
27 | | DSA_PublicKey::DSA_PublicKey(const AlgorithmIdentifier& alg_id, |
28 | | const std::vector<uint8_t>& key_bits) : |
29 | | DL_Scheme_PublicKey(alg_id, key_bits, DL_Group_Format::ANSI_X9_57) |
30 | 173 | { |
31 | 173 | BOTAN_ARG_CHECK(group_q().bytes() > 0, "Q parameter must be set for DSA"); |
32 | 173 | } Unexecuted instantiation: Botan::DSA_PublicKey::DSA_PublicKey(Botan::AlgorithmIdentifier const&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) Botan::DSA_PublicKey::DSA_PublicKey(Botan::AlgorithmIdentifier const&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) Line | Count | Source | 30 | 173 | { | 31 | 173 | BOTAN_ARG_CHECK(group_q().bytes() > 0, "Q parameter must be set for DSA"); | 32 | 173 | } |
|
33 | | |
34 | | |
35 | | DSA_PublicKey::DSA_PublicKey(const DL_Group& grp, const BigInt& y1) |
36 | 0 | { |
37 | 0 | m_group = grp; |
38 | 0 | m_y = y1; |
39 | |
|
40 | 0 | BOTAN_ARG_CHECK(grp.q_bytes() > 0, "Q parameter must be set for DSA"); |
41 | 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&) |
42 | | |
43 | | /* |
44 | | * Create a DSA private key |
45 | | */ |
46 | | DSA_PrivateKey::DSA_PrivateKey(RandomNumberGenerator& rng, |
47 | | const DL_Group& grp, |
48 | | const BigInt& x_arg) |
49 | 0 | { |
50 | 0 | m_group = grp; |
51 | 0 | BOTAN_ARG_CHECK(x_arg.is_positive(), "x must be positive"); |
52 | |
|
53 | 0 | if(x_arg == 0) |
54 | 0 | m_x = BigInt::random_integer(rng, 2, group_q()); |
55 | 0 | else |
56 | 0 | { |
57 | 0 | BOTAN_ARG_CHECK(m_x < m_group.get_q(), "x must not be larger than q"); |
58 | 0 | m_x = x_arg; |
59 | 0 | } |
60 | |
|
61 | 0 | m_y = m_group.power_g_p(m_x, m_group.q_bits()); |
62 | 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&) |
63 | | |
64 | | DSA_PrivateKey::DSA_PrivateKey(const AlgorithmIdentifier& alg_id, |
65 | | const secure_vector<uint8_t>& key_bits) : |
66 | | DL_Scheme_PrivateKey(alg_id, key_bits, DL_Group_Format::ANSI_X9_57) |
67 | 308 | { |
68 | 308 | BOTAN_ARG_CHECK(m_x > 0, "x must be greater than zero"); |
69 | 308 | BOTAN_ARG_CHECK(m_x < m_group.get_q(), "x must not be larger than q"); |
70 | 308 | m_y = m_group.power_g_p(m_x, m_group.q_bits()); |
71 | 308 | } 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 | 67 | 308 | { | 68 | 308 | BOTAN_ARG_CHECK(m_x > 0, "x must be greater than zero"); | 69 | 308 | BOTAN_ARG_CHECK(m_x < m_group.get_q(), "x must not be larger than q"); | 70 | 308 | m_y = m_group.power_g_p(m_x, m_group.q_bits()); | 71 | 308 | } |
|
72 | | |
73 | | /* |
74 | | * Check Private DSA Parameters |
75 | | */ |
76 | | bool DSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const |
77 | 0 | { |
78 | 0 | if(!DL_Scheme_PrivateKey::check_key(rng, strong) || m_x >= group_q()) |
79 | 0 | return false; |
80 | | |
81 | 0 | if(!strong) |
82 | 0 | return true; |
83 | | |
84 | 0 | return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-256)"); |
85 | 0 | } |
86 | | |
87 | | std::unique_ptr<Public_Key> DSA_PrivateKey::public_key() const |
88 | 0 | { |
89 | 0 | return std::make_unique<DSA_PublicKey>(get_group(), get_y()); |
90 | 0 | } |
91 | | |
92 | | namespace { |
93 | | |
94 | | /** |
95 | | * Object that can create a DSA signature |
96 | | */ |
97 | | class DSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA |
98 | | { |
99 | | public: |
100 | | DSA_Signature_Operation(const DSA_PrivateKey& dsa, |
101 | | const std::string& emsa, |
102 | | RandomNumberGenerator& rng) : |
103 | | PK_Ops::Signature_with_EMSA(emsa), |
104 | | m_group(dsa.get_group()), |
105 | | m_x(dsa.get_x()) |
106 | 0 | { |
107 | 0 | m_b = BigInt::random_integer(rng, 2, dsa.group_q()); |
108 | 0 | m_b_inv = m_group.inverse_mod_q(m_b); |
109 | 0 | } |
110 | | |
111 | 0 | size_t signature_length() const override { return 2*m_group.q_bytes(); } |
112 | 0 | size_t max_input_bits() const override { return m_group.q_bits(); } |
113 | | |
114 | | secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len, |
115 | | RandomNumberGenerator& rng) override; |
116 | | private: |
117 | | const DL_Group m_group; |
118 | | const BigInt& m_x; |
119 | | BigInt m_b, m_b_inv; |
120 | | }; |
121 | | |
122 | | secure_vector<uint8_t> |
123 | | DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len, |
124 | | RandomNumberGenerator& rng) |
125 | 0 | { |
126 | 0 | const BigInt& q = m_group.get_q(); |
127 | |
|
128 | 0 | BigInt m = BigInt::from_bytes_with_max_bits(msg, msg_len, m_group.q_bits()); |
129 | |
|
130 | 0 | while(m >= q) |
131 | 0 | m -= q; |
132 | |
|
133 | 0 | #if defined(BOTAN_HAS_RFC6979_GENERATOR) |
134 | 0 | BOTAN_UNUSED(rng); |
135 | 0 | const BigInt k = generate_rfc6979_nonce(m_x, q, m, this->hash_for_signature()); |
136 | | #else |
137 | | const BigInt k = BigInt::random_integer(rng, 1, q); |
138 | | #endif |
139 | |
|
140 | 0 | const BigInt k_inv = m_group.inverse_mod_q(k); |
141 | | |
142 | | /* |
143 | | * It may not be strictly necessary for the reduction (g^k mod p) mod q to be |
144 | | * const time, since r is published as part of the signature, and deriving |
145 | | * anything useful about k from g^k mod p would seem to require computing a |
146 | | * discrete logarithm. |
147 | | * |
148 | | * However it only increases the cost of signatures by about 7-10%, and DSA is |
149 | | * only for legacy use anyway so we don't care about the performance so much. |
150 | | */ |
151 | 0 | const BigInt r = ct_modulo(m_group.power_g_p(k, m_group.q_bits()), m_group.get_q()); |
152 | | |
153 | | /* |
154 | | * Blind the input message and compute x*r+m as (x*r*b + m*b)/b |
155 | | */ |
156 | 0 | m_b = m_group.square_mod_q(m_b); |
157 | 0 | m_b_inv = m_group.square_mod_q(m_b_inv); |
158 | |
|
159 | 0 | m = m_group.multiply_mod_q(m_b, m); |
160 | 0 | const BigInt xr = m_group.multiply_mod_q(m_b, m_x, r); |
161 | |
|
162 | 0 | const BigInt s = m_group.multiply_mod_q(m_b_inv, k_inv, m_group.mod_q(xr+m)); |
163 | | |
164 | | // With overwhelming probability, a bug rather than actual zero r/s |
165 | 0 | if(r.is_zero() || s.is_zero()) |
166 | 0 | throw Internal_Error("Computed zero r/s during DSA signature"); |
167 | | |
168 | 0 | return BigInt::encode_fixed_length_int_pair(r, s, q.bytes()); |
169 | 0 | } |
170 | | |
171 | | /** |
172 | | * Object that can verify a DSA signature |
173 | | */ |
174 | | class DSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA |
175 | | { |
176 | | public: |
177 | | DSA_Verification_Operation(const DSA_PublicKey& dsa, |
178 | | const std::string& emsa) : |
179 | | PK_Ops::Verification_with_EMSA(emsa), |
180 | | m_group(dsa.get_group()), |
181 | | m_y(dsa.get_y()) |
182 | 163 | { |
183 | 163 | } |
184 | | |
185 | 144 | size_t max_input_bits() const override { return m_group.q_bits(); } |
186 | | |
187 | 144 | bool with_recovery() const override { return false; } |
188 | | |
189 | | bool verify(const uint8_t msg[], size_t msg_len, |
190 | | const uint8_t sig[], size_t sig_len) override; |
191 | | private: |
192 | | const DL_Group m_group; |
193 | | const BigInt& m_y; |
194 | | }; |
195 | | |
196 | | bool DSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len, |
197 | | const uint8_t sig[], size_t sig_len) |
198 | 144 | { |
199 | 144 | const BigInt& q = m_group.get_q(); |
200 | 144 | const size_t q_bytes = q.bytes(); |
201 | | |
202 | 144 | if(sig_len != 2*q_bytes || msg_len > q_bytes) |
203 | 0 | return false; |
204 | | |
205 | 144 | BigInt r(sig, q_bytes); |
206 | 144 | BigInt s(sig + q_bytes, q_bytes); |
207 | 144 | BigInt i = BigInt::from_bytes_with_max_bits(msg, msg_len, m_group.q_bits()); |
208 | | |
209 | 144 | if(r <= 0 || r >= q || s <= 0 || s >= q) |
210 | 6 | return false; |
211 | | |
212 | 138 | s = inverse_mod(s, q); |
213 | | |
214 | 138 | const BigInt sr = m_group.multiply_mod_q(s, r); |
215 | 138 | const BigInt si = m_group.multiply_mod_q(s, i); |
216 | | |
217 | 138 | s = m_group.multi_exponentiate(si, m_y, sr); |
218 | | |
219 | | // s is too big for Barrett, and verification doesn't need to be const-time |
220 | 138 | return (s % m_group.get_q() == r); |
221 | 144 | } |
222 | | |
223 | | } |
224 | | |
225 | | std::unique_ptr<PK_Ops::Verification> |
226 | | DSA_PublicKey::create_verification_op(const std::string& params, |
227 | | const std::string& provider) const |
228 | 163 | { |
229 | 163 | if(provider == "base" || provider.empty()) |
230 | 163 | return std::make_unique<DSA_Verification_Operation>(*this, params); |
231 | 0 | throw Provider_Not_Found(algo_name(), provider); |
232 | 163 | } |
233 | | |
234 | | std::unique_ptr<PK_Ops::Signature> |
235 | | DSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng, |
236 | | const std::string& params, |
237 | | const std::string& provider) const |
238 | 0 | { |
239 | 0 | if(provider == "base" || provider.empty()) |
240 | 0 | return std::make_unique<DSA_Signature_Operation>(*this, params, rng); |
241 | 0 | throw Provider_Not_Found(algo_name(), provider); |
242 | 0 | } |
243 | | |
244 | | } |