/src/botan/src/lib/pubkey/rsa/rsa.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * RSA |
3 | | * (C) 1999-2010,2015,2016,2018,2019 Jack Lloyd |
4 | | * |
5 | | * Botan is released under the Simplified BSD License (see license.txt) |
6 | | */ |
7 | | |
8 | | #include <botan/rsa.h> |
9 | | #include <botan/internal/pk_ops_impl.h> |
10 | | #include <botan/internal/keypair.h> |
11 | | #include <botan/internal/blinding.h> |
12 | | #include <botan/reducer.h> |
13 | | #include <botan/internal/workfactor.h> |
14 | | #include <botan/der_enc.h> |
15 | | #include <botan/ber_dec.h> |
16 | | #include <botan/internal/monty.h> |
17 | | #include <botan/internal/divide.h> |
18 | | #include <botan/internal/monty_exp.h> |
19 | | |
20 | | #if defined(BOTAN_HAS_THREAD_UTILS) |
21 | | #include <botan/internal/thread_pool.h> |
22 | | #endif |
23 | | |
24 | | namespace Botan { |
25 | | |
26 | | class RSA_Public_Data final |
27 | | { |
28 | | public: |
29 | | RSA_Public_Data(BigInt&& n, BigInt&& e) : |
30 | | m_n(n), |
31 | | m_e(e), |
32 | | m_monty_n(std::make_shared<Montgomery_Params>(m_n)), |
33 | | m_public_modulus_bits(m_n.bits()), |
34 | | m_public_modulus_bytes(m_n.bytes()) |
35 | 6.57k | {} |
36 | | |
37 | | BigInt public_op(const BigInt& m) const |
38 | 5.97k | { |
39 | 5.97k | const size_t powm_window = 1; |
40 | 5.97k | auto powm_m_n = monty_precompute(m_monty_n, m, powm_window, false); |
41 | 5.97k | return monty_execute_vartime(*powm_m_n, m_e); |
42 | 5.97k | } |
43 | | |
44 | 6.23k | const BigInt& get_n() const { return m_n; } |
45 | 0 | const BigInt& get_e() const { return m_e; } |
46 | 5.97k | size_t public_modulus_bits() const { return m_public_modulus_bits; } |
47 | 0 | size_t public_modulus_bytes() const { return m_public_modulus_bytes; } |
48 | | |
49 | | private: |
50 | | BigInt m_n; |
51 | | BigInt m_e; |
52 | | std::shared_ptr<const Montgomery_Params> m_monty_n; |
53 | | size_t m_public_modulus_bits; |
54 | | size_t m_public_modulus_bytes; |
55 | | }; |
56 | | |
57 | | class RSA_Private_Data final |
58 | | { |
59 | | public: |
60 | | RSA_Private_Data(BigInt&& d, BigInt&& p, BigInt&& q, |
61 | | BigInt&& d1, BigInt&& d2, BigInt&& c) : |
62 | | m_d(d), |
63 | | m_p(p), |
64 | | m_q(q), |
65 | | m_d1(d1), |
66 | | m_d2(d2), |
67 | | m_c(c), |
68 | | m_mod_p(m_p), |
69 | | m_mod_q(m_q), |
70 | | m_monty_p(std::make_shared<Montgomery_Params>(m_p, m_mod_p)), |
71 | | m_monty_q(std::make_shared<Montgomery_Params>(m_q, m_mod_q)), |
72 | | m_p_bits(m_p.bits()), |
73 | | m_q_bits(m_q.bits()) |
74 | 219 | {} |
75 | | |
76 | 0 | const BigInt& get_d() const { return m_d; } |
77 | 0 | const BigInt& get_p() const { return m_p; } |
78 | 0 | const BigInt& get_q() const { return m_q; } |
79 | 0 | const BigInt& get_d1() const { return m_d1; } |
80 | 0 | const BigInt& get_d2() const { return m_d2; } |
81 | 0 | const BigInt& get_c() const { return m_c; } |
82 | | |
83 | | //private: |
84 | | BigInt m_d; |
85 | | BigInt m_p; |
86 | | BigInt m_q; |
87 | | BigInt m_d1; |
88 | | BigInt m_d2; |
89 | | BigInt m_c; |
90 | | |
91 | | Modular_Reducer m_mod_p; |
92 | | Modular_Reducer m_mod_q; |
93 | | std::shared_ptr<const Montgomery_Params> m_monty_p; |
94 | | std::shared_ptr<const Montgomery_Params> m_monty_q; |
95 | | size_t m_p_bits; |
96 | | size_t m_q_bits; |
97 | | }; |
98 | | |
99 | | std::shared_ptr<const RSA_Public_Data> RSA_PublicKey::public_data() const |
100 | 6.23k | { |
101 | 6.23k | return m_public; |
102 | 6.23k | } |
103 | | |
104 | 0 | const BigInt& RSA_PublicKey::get_n() const { return m_public->get_n(); } |
105 | 0 | const BigInt& RSA_PublicKey::get_e() const { return m_public->get_e(); } |
106 | | |
107 | | void RSA_PublicKey::init(BigInt&& n, BigInt&& e) |
108 | 6.65k | { |
109 | 6.65k | if(n.is_negative() || n.is_even() || e.is_negative() || e.is_even()) |
110 | 85 | throw Decoding_Error("Invalid RSA public key parameters"); |
111 | 6.57k | m_public = std::make_shared<RSA_Public_Data>(std::move(n), std::move(e)); |
112 | 6.57k | } |
113 | | |
114 | | RSA_PublicKey::RSA_PublicKey(const AlgorithmIdentifier& /*unused*/, |
115 | | const std::vector<uint8_t>& key_bits) |
116 | 6.58k | { |
117 | 6.58k | BigInt n, e; |
118 | 6.58k | BER_Decoder(key_bits) |
119 | 6.58k | .start_sequence() |
120 | 6.58k | .decode(n) |
121 | 6.58k | .decode(e) |
122 | 6.58k | .end_cons(); |
123 | | |
124 | 6.58k | init(std::move(n), std::move(e)); |
125 | 6.58k | } Unexecuted instantiation: Botan::RSA_PublicKey::RSA_PublicKey(Botan::AlgorithmIdentifier const&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) Botan::RSA_PublicKey::RSA_PublicKey(Botan::AlgorithmIdentifier const&, std::__1::vector<unsigned char, std::__1::allocator<unsigned char> > const&) Line | Count | Source | 116 | 6.58k | { | 117 | 6.58k | BigInt n, e; | 118 | 6.58k | BER_Decoder(key_bits) | 119 | 6.58k | .start_sequence() | 120 | 6.58k | .decode(n) | 121 | 6.58k | .decode(e) | 122 | 6.58k | .end_cons(); | 123 | | | 124 | 6.58k | init(std::move(n), std::move(e)); | 125 | 6.58k | } |
|
126 | | |
127 | | RSA_PublicKey::RSA_PublicKey(const BigInt& modulus, const BigInt& exponent) |
128 | 0 | { |
129 | 0 | BigInt n = modulus; |
130 | 0 | BigInt e = exponent; |
131 | 0 | init(std::move(n), std::move(e)); |
132 | 0 | } Unexecuted instantiation: Botan::RSA_PublicKey::RSA_PublicKey(Botan::BigInt const&, Botan::BigInt const&) Unexecuted instantiation: Botan::RSA_PublicKey::RSA_PublicKey(Botan::BigInt const&, Botan::BigInt const&) |
133 | | |
134 | | size_t RSA_PublicKey::key_length() const |
135 | 0 | { |
136 | 0 | return m_public->public_modulus_bits(); |
137 | 0 | } |
138 | | |
139 | | size_t RSA_PublicKey::estimated_strength() const |
140 | 0 | { |
141 | 0 | return if_work_factor(key_length()); |
142 | 0 | } |
143 | | |
144 | | AlgorithmIdentifier RSA_PublicKey::algorithm_identifier() const |
145 | 0 | { |
146 | 0 | return AlgorithmIdentifier(get_oid(), AlgorithmIdentifier::USE_NULL_PARAM); |
147 | 0 | } |
148 | | |
149 | | std::vector<uint8_t> RSA_PublicKey::public_key_bits() const |
150 | 0 | { |
151 | 0 | std::vector<uint8_t> output; |
152 | 0 | DER_Encoder der(output); |
153 | 0 | der.start_sequence() |
154 | 0 | .encode(get_n()) |
155 | 0 | .encode(get_e()) |
156 | 0 | .end_cons(); |
157 | |
|
158 | 0 | return output; |
159 | 0 | } |
160 | | |
161 | | /* |
162 | | * Check RSA Public Parameters |
163 | | */ |
164 | | bool RSA_PublicKey::check_key(RandomNumberGenerator& /*rng*/, bool /*strong*/) const |
165 | 0 | { |
166 | 0 | if(get_n() < 35 || get_n().is_even() || get_e() < 3 || get_e().is_even()) |
167 | 0 | return false; |
168 | 0 | return true; |
169 | 0 | } |
170 | | |
171 | | std::shared_ptr<const RSA_Private_Data> RSA_PrivateKey::private_data() const |
172 | 0 | { |
173 | 0 | return m_private; |
174 | 0 | } |
175 | | |
176 | | secure_vector<uint8_t> RSA_PrivateKey::private_key_bits() const |
177 | 0 | { |
178 | 0 | return DER_Encoder() |
179 | 0 | .start_sequence() |
180 | 0 | .encode(static_cast<size_t>(0)) |
181 | 0 | .encode(get_n()) |
182 | 0 | .encode(get_e()) |
183 | 0 | .encode(get_d()) |
184 | 0 | .encode(get_p()) |
185 | 0 | .encode(get_q()) |
186 | 0 | .encode(get_d1()) |
187 | 0 | .encode(get_d2()) |
188 | 0 | .encode(get_c()) |
189 | 0 | .end_cons() |
190 | 0 | .get_contents(); |
191 | 0 | } |
192 | | |
193 | 0 | const BigInt& RSA_PrivateKey::get_p() const { return m_private->get_p(); } |
194 | 0 | const BigInt& RSA_PrivateKey::get_q() const { return m_private->get_q(); } |
195 | 0 | const BigInt& RSA_PrivateKey::get_d() const { return m_private->get_d(); } |
196 | 0 | const BigInt& RSA_PrivateKey::get_c() const { return m_private->get_c(); } |
197 | 0 | const BigInt& RSA_PrivateKey::get_d1() const { return m_private->get_d1(); } |
198 | 0 | const BigInt& RSA_PrivateKey::get_d2() const { return m_private->get_d2(); } |
199 | | |
200 | | void RSA_PrivateKey::init(BigInt&& d, BigInt&& p, BigInt&& q, |
201 | | BigInt&& d1, BigInt&& d2, BigInt&& c) |
202 | 219 | { |
203 | 219 | m_private = std::make_shared<RSA_Private_Data>( |
204 | 219 | std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c)); |
205 | 219 | } |
206 | | |
207 | | RSA_PrivateKey::RSA_PrivateKey(const AlgorithmIdentifier& /*unused*/, |
208 | | const secure_vector<uint8_t>& key_bits) |
209 | 261 | { |
210 | 261 | BigInt n, e, d, p, q, d1, d2, c; |
211 | | |
212 | 261 | BER_Decoder(key_bits) |
213 | 261 | .start_sequence() |
214 | 261 | .decode_and_check<size_t>(0, "Unknown PKCS #1 key format version") |
215 | 261 | .decode(n) |
216 | 261 | .decode(e) |
217 | 261 | .decode(d) |
218 | 261 | .decode(p) |
219 | 261 | .decode(q) |
220 | 261 | .decode(d1) |
221 | 261 | .decode(d2) |
222 | 261 | .decode(c) |
223 | 261 | .end_cons(); |
224 | | |
225 | 261 | RSA_PublicKey::init(std::move(n), std::move(e)); |
226 | | |
227 | 261 | RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), |
228 | 261 | std::move(d1), std::move(d2), std::move(c)); |
229 | 261 | } Unexecuted instantiation: Botan::RSA_PrivateKey::RSA_PrivateKey(Botan::AlgorithmIdentifier const&, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&) Botan::RSA_PrivateKey::RSA_PrivateKey(Botan::AlgorithmIdentifier const&, std::__1::vector<unsigned char, Botan::secure_allocator<unsigned char> > const&) Line | Count | Source | 209 | 261 | { | 210 | 261 | BigInt n, e, d, p, q, d1, d2, c; | 211 | | | 212 | 261 | BER_Decoder(key_bits) | 213 | 261 | .start_sequence() | 214 | 261 | .decode_and_check<size_t>(0, "Unknown PKCS #1 key format version") | 215 | 261 | .decode(n) | 216 | 261 | .decode(e) | 217 | 261 | .decode(d) | 218 | 261 | .decode(p) | 219 | 261 | .decode(q) | 220 | 261 | .decode(d1) | 221 | 261 | .decode(d2) | 222 | 261 | .decode(c) | 223 | 261 | .end_cons(); | 224 | | | 225 | 261 | RSA_PublicKey::init(std::move(n), std::move(e)); | 226 | | | 227 | 261 | RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), | 228 | 261 | std::move(d1), std::move(d2), std::move(c)); | 229 | 261 | } |
|
230 | | |
231 | | RSA_PrivateKey::RSA_PrivateKey(const BigInt& prime1, |
232 | | const BigInt& prime2, |
233 | | const BigInt& exp, |
234 | | const BigInt& d_exp, |
235 | | const BigInt& mod) |
236 | 0 | { |
237 | 0 | BigInt p = prime1; |
238 | 0 | BigInt q = prime2; |
239 | 0 | BigInt n = mod; |
240 | 0 | if(n.is_zero()) |
241 | 0 | n = p * q; |
242 | |
|
243 | 0 | BigInt e = exp; |
244 | |
|
245 | 0 | BigInt d = d_exp; |
246 | |
|
247 | 0 | const BigInt p_minus_1 = p - 1; |
248 | 0 | const BigInt q_minus_1 = q - 1; |
249 | |
|
250 | 0 | if(d.is_zero()) |
251 | 0 | { |
252 | 0 | const BigInt phi_n = lcm(p_minus_1, q_minus_1); |
253 | 0 | d = inverse_mod(e, phi_n); |
254 | 0 | } |
255 | |
|
256 | 0 | BigInt d1 = ct_modulo(d, p_minus_1); |
257 | 0 | BigInt d2 = ct_modulo(d, q_minus_1); |
258 | 0 | BigInt c = inverse_mod(q, p); |
259 | |
|
260 | 0 | RSA_PublicKey::init(std::move(n), std::move(e)); |
261 | |
|
262 | 0 | RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), |
263 | 0 | std::move(d1), std::move(d2), std::move(c)); |
264 | 0 | } Unexecuted instantiation: Botan::RSA_PrivateKey::RSA_PrivateKey(Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&) Unexecuted instantiation: Botan::RSA_PrivateKey::RSA_PrivateKey(Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&, Botan::BigInt const&) |
265 | | |
266 | | /* |
267 | | * Create a RSA private key |
268 | | */ |
269 | | RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng, |
270 | | size_t bits, size_t exp) |
271 | 0 | { |
272 | 0 | if(bits < 1024) |
273 | 0 | throw Invalid_Argument(algo_name() + ": Can't make a key that is only " + |
274 | 0 | std::to_string(bits) + " bits long"); |
275 | 0 | if(exp < 3 || exp % 2 == 0) |
276 | 0 | throw Invalid_Argument(algo_name() + ": Invalid encryption exponent"); |
277 | | |
278 | 0 | BigInt n, e, d, p, q, d1, d2, c; |
279 | |
|
280 | 0 | e = exp; |
281 | |
|
282 | 0 | const size_t p_bits = (bits + 1) / 2; |
283 | 0 | const size_t q_bits = bits - p_bits; |
284 | |
|
285 | 0 | for(size_t attempt = 0; ; ++attempt) |
286 | 0 | { |
287 | 0 | if(attempt > 10) |
288 | 0 | throw Internal_Error("RNG failure during RSA key generation"); |
289 | | |
290 | | // TODO could generate primes in thread pool |
291 | 0 | p = generate_rsa_prime(rng, rng, p_bits, e); |
292 | 0 | q = generate_rsa_prime(rng, rng, q_bits, e); |
293 | |
|
294 | 0 | const BigInt diff = p - q; |
295 | 0 | if(diff.bits() < (bits/2) - 100) |
296 | 0 | continue; |
297 | | |
298 | 0 | n = p * q; |
299 | |
|
300 | 0 | if(n.bits() != bits) |
301 | 0 | continue; |
302 | | |
303 | 0 | break; |
304 | 0 | } |
305 | | |
306 | 0 | const BigInt p_minus_1 = p - 1; |
307 | 0 | const BigInt q_minus_1 = q - 1; |
308 | |
|
309 | 0 | const BigInt phi_n = lcm(p_minus_1, q_minus_1); |
310 | | // This is guaranteed because p,q == 3 mod 4 |
311 | 0 | BOTAN_DEBUG_ASSERT(low_zero_bits(phi_n) == 1); |
312 | 0 | d = inverse_mod(e, phi_n); |
313 | 0 | d1 = ct_modulo(d, p_minus_1); |
314 | 0 | d2 = ct_modulo(d, q_minus_1); |
315 | 0 | c = inverse_mod(q, p); |
316 | |
|
317 | 0 | RSA_PublicKey::init(std::move(n), std::move(e)); |
318 | |
|
319 | 0 | RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), |
320 | 0 | std::move(d1), std::move(d2), std::move(c)); |
321 | 0 | } Unexecuted instantiation: Botan::RSA_PrivateKey::RSA_PrivateKey(Botan::RandomNumberGenerator&, unsigned long, unsigned long) Unexecuted instantiation: Botan::RSA_PrivateKey::RSA_PrivateKey(Botan::RandomNumberGenerator&, unsigned long, unsigned long) |
322 | | |
323 | | std::unique_ptr<Public_Key> RSA_PrivateKey::public_key() const |
324 | 0 | { |
325 | 0 | return std::make_unique<RSA_PublicKey>(get_n(), get_e()); |
326 | 0 | } |
327 | | |
328 | | /* |
329 | | * Check Private RSA Parameters |
330 | | */ |
331 | | bool RSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const |
332 | 0 | { |
333 | 0 | if(get_n() < 35 || get_n().is_even() || get_e() < 3 || get_e().is_even()) |
334 | 0 | return false; |
335 | | |
336 | 0 | if(get_d() < 2 || get_p() < 3 || get_q() < 3) |
337 | 0 | return false; |
338 | | |
339 | 0 | if(get_p() * get_q() != get_n()) |
340 | 0 | return false; |
341 | | |
342 | 0 | if(get_p() == get_q()) |
343 | 0 | return false; |
344 | | |
345 | 0 | if(get_d1() != ct_modulo(get_d(), get_p() - 1)) |
346 | 0 | return false; |
347 | 0 | if(get_d2() != ct_modulo(get_d(), get_q() - 1)) |
348 | 0 | return false; |
349 | 0 | if(get_c() != inverse_mod(get_q(), get_p())) |
350 | 0 | return false; |
351 | | |
352 | 0 | const size_t prob = (strong) ? 128 : 12; |
353 | |
|
354 | 0 | if(!is_prime(get_p(), rng, prob)) |
355 | 0 | return false; |
356 | 0 | if(!is_prime(get_q(), rng, prob)) |
357 | 0 | return false; |
358 | | |
359 | 0 | if(strong) |
360 | 0 | { |
361 | 0 | if(ct_modulo(get_e() * get_d(), lcm(get_p() - 1, get_q() - 1)) != 1) |
362 | 0 | return false; |
363 | | |
364 | 0 | return KeyPair::signature_consistency_check(rng, *this, "EMSA4(SHA-256)"); |
365 | 0 | } |
366 | | |
367 | 0 | return true; |
368 | 0 | } |
369 | | |
370 | | namespace { |
371 | | |
372 | | /** |
373 | | * RSA private (decrypt/sign) operation |
374 | | */ |
375 | | class RSA_Private_Operation |
376 | | { |
377 | | protected: |
378 | 0 | size_t public_modulus_bits() const { return m_public->public_modulus_bits(); } |
379 | 0 | size_t public_modulus_bytes() const { return m_public->public_modulus_bytes(); } |
380 | | |
381 | | explicit RSA_Private_Operation(const RSA_PrivateKey& rsa, RandomNumberGenerator& rng) : |
382 | | m_public(rsa.public_data()), |
383 | | m_private(rsa.private_data()), |
384 | | m_blinder(m_public->get_n(), rng, |
385 | 0 | [this](const BigInt& k) { return m_public->public_op(k); }, |
386 | 0 | [this](const BigInt& k) { return inverse_mod(k, m_public->get_n()); }), |
387 | | m_blinding_bits(64), |
388 | | m_max_d1_bits(m_private->m_p_bits + m_blinding_bits), |
389 | | m_max_d2_bits(m_private->m_q_bits + m_blinding_bits) |
390 | 0 | { |
391 | 0 | } |
392 | | |
393 | | secure_vector<uint8_t> raw_op(const uint8_t input[], size_t input_len) |
394 | 0 | { |
395 | 0 | const BigInt input_bn(input, input_len); |
396 | 0 | if(input_bn >= m_public->get_n()) |
397 | 0 | throw Invalid_Argument("RSA private op - input is too large"); |
398 | | |
399 | | // TODO: This should be a function on blinder |
400 | | // BigInt Blinder::run_blinded_function(std::function<BigInt, BigInt> fn, const BigInt& input); |
401 | | |
402 | 0 | const BigInt recovered = m_blinder.unblind(rsa_private_op(m_blinder.blind(input_bn))); |
403 | 0 | BOTAN_ASSERT(input_bn == m_public->public_op(recovered), "RSA consistency check"); |
404 | 0 | return BigInt::encode_1363(recovered, m_public->public_modulus_bytes()); |
405 | 0 | } |
406 | | |
407 | | private: |
408 | | |
409 | | BigInt rsa_private_op(const BigInt& m) const |
410 | 0 | { |
411 | | /* |
412 | | TODO |
413 | | Consider using Montgomery reduction instead of Barrett, using |
414 | | the "Smooth RSA-CRT" method. https://eprint.iacr.org/2007/039.pdf |
415 | | */ |
416 | |
|
417 | 0 | static constexpr size_t powm_window = 4; |
418 | | |
419 | | // Compute this in main thread to avoid racing on the rng |
420 | 0 | const BigInt d1_mask(m_blinder.rng(), m_blinding_bits); |
421 | |
|
422 | 0 | #if defined(BOTAN_HAS_THREAD_UTILS) && !defined(BOTAN_HAS_VALGRIND) |
423 | 0 | #define BOTAN_RSA_USE_ASYNC |
424 | 0 | #endif |
425 | |
|
426 | 0 | #if defined(BOTAN_RSA_USE_ASYNC) |
427 | | /* |
428 | | * Precompute m.sig_words in the main thread before calling async. Otherwise |
429 | | * the two threads race (during Modular_Reducer::reduce) and while the output |
430 | | * is correct in both threads, helgrind warns. |
431 | | */ |
432 | 0 | m.sig_words(); |
433 | |
|
434 | 0 | auto future_j1 = Thread_Pool::global_instance().run([this, &m, &d1_mask]() { |
435 | 0 | #endif |
436 | 0 | const BigInt masked_d1 = m_private->get_d1() + (d1_mask * (m_private->get_p() - 1)); |
437 | 0 | auto powm_d1_p = monty_precompute(m_private->m_monty_p, m_private->m_mod_p.reduce(m), powm_window); |
438 | 0 | BigInt j1 = monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits); |
439 | |
|
440 | 0 | #if defined(BOTAN_RSA_USE_ASYNC) |
441 | 0 | return j1; |
442 | 0 | }); |
443 | 0 | #endif |
444 | |
|
445 | 0 | const BigInt d2_mask(m_blinder.rng(), m_blinding_bits); |
446 | 0 | const BigInt masked_d2 = m_private->get_d2() + (d2_mask * (m_private->get_q() - 1)); |
447 | 0 | auto powm_d2_q = monty_precompute(m_private->m_monty_q, m_private->m_mod_q.reduce(m), powm_window); |
448 | 0 | const BigInt j2 = monty_execute(*powm_d2_q, masked_d2, m_max_d2_bits); |
449 | |
|
450 | 0 | #if defined(BOTAN_RSA_USE_ASYNC) |
451 | 0 | BigInt j1 = future_j1.get(); |
452 | 0 | #endif |
453 | | |
454 | | /* |
455 | | * To recover the final value from the CRT representation (j1,j2) |
456 | | * we use Garner's algorithm: |
457 | | * c = q^-1 mod p (this is precomputed) |
458 | | * h = c*(j1-j2) mod p |
459 | | * m = j2 + h*q |
460 | | * |
461 | | * We must avoid leaking if j1 >= j2 or not, as doing so allows deriving |
462 | | * information about the secret prime. Do this by first adding p to j1, |
463 | | * which should ensure the subtraction of j2 does not underflow. But |
464 | | * this may still underflow if p and q are imbalanced in size. |
465 | | */ |
466 | |
|
467 | 0 | j1 = m_private->m_mod_p.multiply(m_private->m_mod_p.reduce((m_private->get_p() + j1) - j2), m_private->get_c()); |
468 | 0 | return j1*m_private->get_q() + j2; |
469 | 0 | } |
470 | | |
471 | | std::shared_ptr<const RSA_Public_Data> m_public; |
472 | | std::shared_ptr<const RSA_Private_Data> m_private; |
473 | | |
474 | | // XXX could the blinder starting pair be shared? |
475 | | Blinder m_blinder; |
476 | | const size_t m_blinding_bits; |
477 | | const size_t m_max_d1_bits; |
478 | | const size_t m_max_d2_bits; |
479 | | }; |
480 | | |
481 | | class RSA_Signature_Operation final : public PK_Ops::Signature_with_EMSA, |
482 | | private RSA_Private_Operation |
483 | | { |
484 | | public: |
485 | 0 | size_t max_input_bits() const override { return public_modulus_bits() - 1; } |
486 | | |
487 | 0 | size_t signature_length() const override { return public_modulus_bytes(); } |
488 | | |
489 | | RSA_Signature_Operation(const RSA_PrivateKey& rsa, const std::string& emsa, RandomNumberGenerator& rng) : |
490 | | PK_Ops::Signature_with_EMSA(emsa, true), |
491 | | RSA_Private_Operation(rsa, rng) |
492 | 0 | { |
493 | 0 | } |
494 | | |
495 | | secure_vector<uint8_t> raw_sign(const uint8_t input[], size_t input_len, |
496 | | RandomNumberGenerator& /*rng*/) override |
497 | 0 | { |
498 | 0 | return raw_op(input, input_len); |
499 | 0 | } |
500 | | }; |
501 | | |
502 | | class RSA_Decryption_Operation final : public PK_Ops::Decryption_with_EME, |
503 | | private RSA_Private_Operation |
504 | | { |
505 | | public: |
506 | | |
507 | | RSA_Decryption_Operation(const RSA_PrivateKey& rsa, const std::string& eme, RandomNumberGenerator& rng) : |
508 | | PK_Ops::Decryption_with_EME(eme), |
509 | | RSA_Private_Operation(rsa, rng) |
510 | 0 | { |
511 | 0 | } |
512 | | |
513 | 0 | size_t plaintext_length(size_t /*ctext_len*/) const override { return public_modulus_bytes(); } |
514 | | |
515 | | secure_vector<uint8_t> raw_decrypt(const uint8_t input[], size_t input_len) override |
516 | 0 | { |
517 | 0 | return raw_op(input, input_len); |
518 | 0 | } |
519 | | }; |
520 | | |
521 | | class RSA_KEM_Decryption_Operation final : public PK_Ops::KEM_Decryption_with_KDF, |
522 | | private RSA_Private_Operation |
523 | | { |
524 | | public: |
525 | | |
526 | | RSA_KEM_Decryption_Operation(const RSA_PrivateKey& key, |
527 | | const std::string& kdf, |
528 | | RandomNumberGenerator& rng) : |
529 | | PK_Ops::KEM_Decryption_with_KDF(kdf), |
530 | | RSA_Private_Operation(key, rng) |
531 | 0 | {} |
532 | | |
533 | | secure_vector<uint8_t> |
534 | | raw_kem_decrypt(const uint8_t encap_key[], size_t len) override |
535 | 0 | { |
536 | 0 | return raw_op(encap_key, len); |
537 | 0 | } |
538 | | }; |
539 | | |
540 | | /** |
541 | | * RSA public (encrypt/verify) operation |
542 | | */ |
543 | | class RSA_Public_Operation |
544 | | { |
545 | | public: |
546 | | explicit RSA_Public_Operation(const RSA_PublicKey& rsa) : |
547 | | m_public(rsa.public_data()) |
548 | 6.23k | {} |
549 | | |
550 | | size_t get_max_input_bits() const |
551 | 5.97k | { |
552 | 5.97k | const size_t n_bits = m_public->public_modulus_bits(); |
553 | | |
554 | | /* |
555 | | Make Coverity happy that n_bits - 1 won't underflow |
556 | | |
557 | | 5 bit minimum: smallest possible RSA key is 3*5 |
558 | | */ |
559 | 5.97k | BOTAN_ASSERT_NOMSG(n_bits >= 5); |
560 | 5.97k | return n_bits - 1; |
561 | 5.97k | } |
562 | | |
563 | | protected: |
564 | | BigInt public_op(const BigInt& m) const |
565 | 6.23k | { |
566 | 6.23k | if(m >= m_public->get_n()) |
567 | 261 | throw Invalid_Argument("RSA public op - input is too large"); |
568 | | |
569 | 5.97k | return m_public->public_op(m); |
570 | 6.23k | } |
571 | | |
572 | 0 | size_t public_modulus_bytes() const { return m_public->public_modulus_bytes(); } |
573 | | |
574 | 0 | const BigInt& get_n() const { return m_public->get_n(); } |
575 | | |
576 | | std::shared_ptr<const RSA_Public_Data> m_public; |
577 | | }; |
578 | | |
579 | | class RSA_Encryption_Operation final : public PK_Ops::Encryption_with_EME, |
580 | | private RSA_Public_Operation |
581 | | { |
582 | | public: |
583 | | |
584 | | RSA_Encryption_Operation(const RSA_PublicKey& rsa, const std::string& eme) : |
585 | | PK_Ops::Encryption_with_EME(eme), |
586 | | RSA_Public_Operation(rsa) |
587 | 0 | { |
588 | 0 | } |
589 | | |
590 | 0 | size_t ciphertext_length(size_t /*ptext_len*/) const override { return public_modulus_bytes(); } |
591 | | |
592 | 0 | size_t max_raw_input_bits() const override { return get_max_input_bits(); } |
593 | | |
594 | | secure_vector<uint8_t> raw_encrypt(const uint8_t input[], size_t input_len, |
595 | | RandomNumberGenerator& /*rng*/) override |
596 | 0 | { |
597 | 0 | BigInt input_bn(input, input_len); |
598 | 0 | return BigInt::encode_1363(public_op(input_bn), public_modulus_bytes()); |
599 | 0 | } |
600 | | }; |
601 | | |
602 | | class RSA_Verify_Operation final : public PK_Ops::Verification_with_EMSA, |
603 | | private RSA_Public_Operation |
604 | | { |
605 | | public: |
606 | | |
607 | 5.97k | size_t max_input_bits() const override { return get_max_input_bits(); } |
608 | | |
609 | | RSA_Verify_Operation(const RSA_PublicKey& rsa, const std::string& emsa) : |
610 | | PK_Ops::Verification_with_EMSA(emsa, true), |
611 | | RSA_Public_Operation(rsa) |
612 | 6.23k | { |
613 | 6.23k | } |
614 | | |
615 | 6.23k | bool with_recovery() const override { return true; } |
616 | | |
617 | | secure_vector<uint8_t> verify_mr(const uint8_t input[], size_t input_len) override |
618 | 6.23k | { |
619 | 6.23k | BigInt input_bn(input, input_len); |
620 | 6.23k | return BigInt::encode_locked(public_op(input_bn)); |
621 | 6.23k | } |
622 | | }; |
623 | | |
624 | | class RSA_KEM_Encryption_Operation final : public PK_Ops::KEM_Encryption_with_KDF, |
625 | | private RSA_Public_Operation |
626 | | { |
627 | | public: |
628 | | |
629 | | RSA_KEM_Encryption_Operation(const RSA_PublicKey& key, |
630 | | const std::string& kdf) : |
631 | | PK_Ops::KEM_Encryption_with_KDF(kdf), |
632 | 0 | RSA_Public_Operation(key) {} |
633 | | |
634 | | private: |
635 | | void raw_kem_encrypt(secure_vector<uint8_t>& out_encapsulated_key, |
636 | | secure_vector<uint8_t>& raw_shared_key, |
637 | | Botan::RandomNumberGenerator& rng) override |
638 | 0 | { |
639 | 0 | const BigInt r = BigInt::random_integer(rng, 1, get_n()); |
640 | 0 | const BigInt c = public_op(r); |
641 | |
|
642 | 0 | out_encapsulated_key = BigInt::encode_locked(c); |
643 | 0 | raw_shared_key = BigInt::encode_locked(r); |
644 | 0 | } |
645 | | }; |
646 | | |
647 | | } |
648 | | |
649 | | std::unique_ptr<PK_Ops::Encryption> |
650 | | RSA_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/, |
651 | | const std::string& params, |
652 | | const std::string& provider) const |
653 | 0 | { |
654 | 0 | if(provider == "base" || provider.empty()) |
655 | 0 | return std::make_unique<RSA_Encryption_Operation>(*this, params); |
656 | 0 | throw Provider_Not_Found(algo_name(), provider); |
657 | 0 | } |
658 | | |
659 | | std::unique_ptr<PK_Ops::KEM_Encryption> |
660 | | RSA_PublicKey::create_kem_encryption_op(RandomNumberGenerator& /*rng*/, |
661 | | const std::string& params, |
662 | | const std::string& provider) const |
663 | 0 | { |
664 | 0 | if(provider == "base" || provider.empty()) |
665 | 0 | return std::make_unique<RSA_KEM_Encryption_Operation>(*this, params); |
666 | 0 | throw Provider_Not_Found(algo_name(), provider); |
667 | 0 | } |
668 | | |
669 | | std::unique_ptr<PK_Ops::Verification> |
670 | | RSA_PublicKey::create_verification_op(const std::string& params, |
671 | | const std::string& provider) const |
672 | 6.23k | { |
673 | 6.23k | if(provider == "base" || provider.empty()) |
674 | 6.23k | return std::make_unique<RSA_Verify_Operation>(*this, params); |
675 | | |
676 | 0 | throw Provider_Not_Found(algo_name(), provider); |
677 | 6.23k | } |
678 | | |
679 | | std::unique_ptr<PK_Ops::Decryption> |
680 | | RSA_PrivateKey::create_decryption_op(RandomNumberGenerator& rng, |
681 | | const std::string& params, |
682 | | const std::string& provider) const |
683 | 0 | { |
684 | 0 | if(provider == "base" || provider.empty()) |
685 | 0 | return std::make_unique<RSA_Decryption_Operation>(*this, params, rng); |
686 | | |
687 | 0 | throw Provider_Not_Found(algo_name(), provider); |
688 | 0 | } |
689 | | |
690 | | std::unique_ptr<PK_Ops::KEM_Decryption> |
691 | | RSA_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& rng, |
692 | | const std::string& params, |
693 | | const std::string& provider) const |
694 | 0 | { |
695 | 0 | if(provider == "base" || provider.empty()) |
696 | 0 | return std::make_unique<RSA_KEM_Decryption_Operation>(*this, params, rng); |
697 | | |
698 | 0 | throw Provider_Not_Found(algo_name(), provider); |
699 | 0 | } |
700 | | |
701 | | std::unique_ptr<PK_Ops::Signature> |
702 | | RSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng, |
703 | | const std::string& params, |
704 | | const std::string& provider) const |
705 | 0 | { |
706 | 0 | if(provider == "base" || provider.empty()) |
707 | 0 | return std::make_unique<RSA_Signature_Operation>(*this, params, rng); |
708 | | |
709 | 0 | throw Provider_Not_Found(algo_name(), provider); |
710 | 0 | } |
711 | | |
712 | | } |