/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 | | 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 | |
|
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 | |
|
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_Format::ANSI_X9_57) |
52 | 168 | { |
53 | 168 | m_y = m_group.power_g_p(m_x, m_group.q_bits()); |
54 | 168 | } 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 | 168 | { | 53 | 168 | m_y = m_group.power_g_p(m_x, m_group.q_bits()); | 54 | 168 | } |
|
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 | | |
64 | 0 | if(!strong) |
65 | 0 | return true; |
66 | | |
67 | 0 | return KeyPair::signature_consistency_check(rng, *this, "EMSA1(SHA-256)"); |
68 | 0 | } |
69 | | |
70 | | std::unique_ptr<Public_Key> DSA_PrivateKey::public_key() const |
71 | 0 | { |
72 | 0 | return std::make_unique<DSA_PublicKey>(get_group(), get_y()); |
73 | 0 | } |
74 | | |
75 | | namespace { |
76 | | |
77 | | /** |
78 | | * Object that can create a DSA signature |
79 | | */ |
80 | | class DSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA |
81 | | { |
82 | | public: |
83 | | DSA_Signature_Operation(const DSA_PrivateKey& dsa, |
84 | | const std::string& emsa, |
85 | | RandomNumberGenerator& rng) : |
86 | | PK_Ops::Signature_with_EMSA(emsa), |
87 | | m_group(dsa.get_group()), |
88 | | m_x(dsa.get_x()) |
89 | 0 | { |
90 | 0 | m_b = BigInt::random_integer(rng, 2, dsa.group_q()); |
91 | 0 | m_b_inv = m_group.inverse_mod_q(m_b); |
92 | 0 | } |
93 | | |
94 | 0 | size_t signature_length() const override { return 2*m_group.q_bytes(); } |
95 | 0 | size_t max_input_bits() const override { return m_group.q_bits(); } |
96 | | |
97 | | secure_vector<uint8_t> raw_sign(const uint8_t msg[], size_t msg_len, |
98 | | RandomNumberGenerator& rng) override; |
99 | | private: |
100 | | const DL_Group m_group; |
101 | | const BigInt& m_x; |
102 | | BigInt m_b, m_b_inv; |
103 | | }; |
104 | | |
105 | | secure_vector<uint8_t> |
106 | | DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len, |
107 | | RandomNumberGenerator& rng) |
108 | 0 | { |
109 | 0 | const BigInt& q = m_group.get_q(); |
110 | |
|
111 | 0 | BigInt m = BigInt::from_bytes_with_max_bits(msg, msg_len, m_group.q_bits()); |
112 | |
|
113 | 0 | while(m >= q) |
114 | 0 | m -= q; |
115 | |
|
116 | 0 | #if defined(BOTAN_HAS_RFC6979_GENERATOR) |
117 | 0 | BOTAN_UNUSED(rng); |
118 | 0 | const BigInt k = generate_rfc6979_nonce(m_x, q, m, this->hash_for_signature()); |
119 | | #else |
120 | | const BigInt k = BigInt::random_integer(rng, 1, q); |
121 | | #endif |
122 | |
|
123 | 0 | const BigInt k_inv = m_group.inverse_mod_q(k); |
124 | | |
125 | | /* |
126 | | * It may not be strictly necessary for the reduction (g^k mod p) mod q to be |
127 | | * const time, since r is published as part of the signature, and deriving |
128 | | * anything useful about k from g^k mod p would seem to require computing a |
129 | | * discrete logarithm. |
130 | | * |
131 | | * However it only increases the cost of signatures by about 7-10%, and DSA is |
132 | | * only for legacy use anyway so we don't care about the performance so much. |
133 | | */ |
134 | 0 | const BigInt r = ct_modulo(m_group.power_g_p(k, m_group.q_bits()), m_group.get_q()); |
135 | | |
136 | | /* |
137 | | * Blind the input message and compute x*r+m as (x*r*b + m*b)/b |
138 | | */ |
139 | 0 | m_b = m_group.square_mod_q(m_b); |
140 | 0 | m_b_inv = m_group.square_mod_q(m_b_inv); |
141 | |
|
142 | 0 | m = m_group.multiply_mod_q(m_b, m); |
143 | 0 | const BigInt xr = m_group.multiply_mod_q(m_b, m_x, r); |
144 | |
|
145 | 0 | const BigInt s = m_group.multiply_mod_q(m_b_inv, k_inv, m_group.mod_q(xr+m)); |
146 | | |
147 | | // With overwhelming probability, a bug rather than actual zero r/s |
148 | 0 | if(r.is_zero() || s.is_zero()) |
149 | 0 | throw Internal_Error("Computed zero r/s during DSA signature"); |
150 | | |
151 | 0 | return BigInt::encode_fixed_length_int_pair(r, s, q.bytes()); |
152 | 0 | } |
153 | | |
154 | | /** |
155 | | * Object that can verify a DSA signature |
156 | | */ |
157 | | class DSA_Verification_Operation final : public PK_Ops::Verification_with_EMSA |
158 | | { |
159 | | public: |
160 | | DSA_Verification_Operation(const DSA_PublicKey& dsa, |
161 | | const std::string& emsa) : |
162 | | PK_Ops::Verification_with_EMSA(emsa), |
163 | | m_group(dsa.get_group()), |
164 | | m_y(dsa.get_y()) |
165 | 121 | { |
166 | 121 | } |
167 | | |
168 | 105 | size_t max_input_bits() const override { return m_group.q_bits(); } |
169 | | |
170 | 105 | bool with_recovery() const override { return false; } |
171 | | |
172 | | bool verify(const uint8_t msg[], size_t msg_len, |
173 | | const uint8_t sig[], size_t sig_len) override; |
174 | | private: |
175 | | const DL_Group m_group; |
176 | | const BigInt& m_y; |
177 | | }; |
178 | | |
179 | | bool DSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len, |
180 | | const uint8_t sig[], size_t sig_len) |
181 | 105 | { |
182 | 105 | const BigInt& q = m_group.get_q(); |
183 | 105 | const size_t q_bytes = q.bytes(); |
184 | | |
185 | 105 | if(sig_len != 2*q_bytes || msg_len > q_bytes) |
186 | 0 | return false; |
187 | | |
188 | 105 | BigInt r(sig, q_bytes); |
189 | 105 | BigInt s(sig + q_bytes, q_bytes); |
190 | 105 | BigInt i = BigInt::from_bytes_with_max_bits(msg, msg_len, m_group.q_bits()); |
191 | | |
192 | 105 | if(r <= 0 || r >= q || s <= 0 || s >= q) |
193 | 5 | return false; |
194 | | |
195 | 100 | s = inverse_mod(s, q); |
196 | | |
197 | 100 | const BigInt sr = m_group.multiply_mod_q(s, r); |
198 | 100 | const BigInt si = m_group.multiply_mod_q(s, i); |
199 | | |
200 | 100 | s = m_group.multi_exponentiate(si, m_y, sr); |
201 | | |
202 | | // s is too big for Barrett, and verification doesn't need to be const-time |
203 | 100 | return (s % m_group.get_q() == r); |
204 | 100 | } |
205 | | |
206 | | } |
207 | | |
208 | | std::unique_ptr<PK_Ops::Verification> |
209 | | DSA_PublicKey::create_verification_op(const std::string& params, |
210 | | const std::string& provider) const |
211 | 121 | { |
212 | 121 | if(provider == "base" || provider.empty()) |
213 | 121 | return std::make_unique<DSA_Verification_Operation>(*this, params); |
214 | 0 | throw Provider_Not_Found(algo_name(), provider); |
215 | 0 | } |
216 | | |
217 | | std::unique_ptr<PK_Ops::Signature> |
218 | | DSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng, |
219 | | const std::string& params, |
220 | | const std::string& provider) const |
221 | 0 | { |
222 | 0 | if(provider == "base" || provider.empty()) |
223 | 0 | return std::make_unique<DSA_Signature_Operation>(*this, params, rng); |
224 | 0 | throw Provider_Not_Found(algo_name(), provider); |
225 | 0 | } |
226 | | |
227 | | } |