Botan 3.9.0
Crypto and TLS for C&
rsa.cpp
Go to the documentation of this file.
1/*
2* RSA
3* (C) 1999-2010,2015,2016,2018,2019,2023 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#include <botan/rsa.h>
9
10#include <botan/ber_dec.h>
11#include <botan/der_enc.h>
12#include <botan/numthry.h>
13#include <botan/pss_params.h>
14#include <botan/internal/barrett.h>
15#include <botan/internal/blinding.h>
16#include <botan/internal/divide.h>
17#include <botan/internal/fmt.h>
18#include <botan/internal/keypair.h>
19#include <botan/internal/mod_inv.h>
20#include <botan/internal/monty.h>
21#include <botan/internal/monty_exp.h>
22#include <botan/internal/mp_core.h>
23#include <botan/internal/parsing.h>
24#include <botan/internal/pk_ops_impl.h>
25#include <botan/internal/sig_padding.h>
26#include <botan/internal/target_info.h>
27#include <botan/internal/workfactor.h>
28
29#if defined(BOTAN_HAS_THREAD_UTILS)
30 #include <botan/internal/thread_pool.h>
31#endif
32
33namespace Botan {
34
35class RSA_Public_Data final {
36 public:
37 RSA_Public_Data(BigInt&& n, BigInt&& e) :
38 m_n(std::move(n)),
39 m_e(std::move(e)),
40 m_mod_n(Barrett_Reduction::for_public_modulus(m_n)),
41 m_monty_n(m_n, m_mod_n),
42 m_public_modulus_bits(m_n.bits()),
43 m_public_modulus_bytes(m_n.bytes()) {}
44
45 BigInt public_op(const BigInt& m) const {
46 const size_t powm_window = 1;
47 auto powm_m_n = monty_precompute(m_monty_n, m, powm_window, false);
48 return monty_execute_vartime(*powm_m_n, m_e).value();
49 }
50
51 const BigInt& get_n() const { return m_n; }
52
53 const BigInt& get_e() const { return m_e; }
54
55 size_t public_modulus_bits() const { return m_public_modulus_bits; }
56
57 size_t public_modulus_bytes() const { return m_public_modulus_bytes; }
58
59 const Montgomery_Params& monty_n() const { return m_monty_n; }
60
61 const Barrett_Reduction& reducer_mod_n() const { return m_mod_n; }
62
63 private:
64 BigInt m_n;
65 BigInt m_e;
66 Barrett_Reduction m_mod_n;
67 const Montgomery_Params m_monty_n;
68 size_t m_public_modulus_bits;
69 size_t m_public_modulus_bytes;
70};
71
72class RSA_Private_Data final {
73 public:
74 RSA_Private_Data(BigInt&& d, BigInt&& p, BigInt&& q, BigInt&& d1, BigInt&& d2, BigInt&& c) :
75 m_d(std::move(d)),
76 m_p(std::move(p)),
77 m_q(std::move(q)),
78 m_d1(std::move(d1)),
79 m_d2(std::move(d2)),
80 m_c(std::move(c)),
81 m_monty_p(m_p),
82 m_monty_q(m_q),
83 m_c_monty(m_monty_p, m_c),
84 m_p_bits(m_p.bits()),
85 m_q_bits(m_q.bits()) {}
86
87 const BigInt& get_d() const { return m_d; }
88
89 const BigInt& get_p() const { return m_p; }
90
91 const BigInt& get_q() const { return m_q; }
92
93 const BigInt& get_d1() const { return m_d1; }
94
95 const BigInt& get_d2() const { return m_d2; }
96
97 const BigInt& get_c() const { return m_c; }
98
99 const Montgomery_Int& get_c_monty() const { return m_c_monty; }
100
101 const Montgomery_Params& monty_p() const { return m_monty_p; }
102
103 const Montgomery_Params& monty_q() const { return m_monty_q; }
104
105 size_t p_bits() const { return m_p_bits; }
106
107 size_t q_bits() const { return m_q_bits; }
108
109 bool primes_imbalanced() const { return p_bits() != q_bits(); }
110
111 private:
112 BigInt m_d;
113 BigInt m_p;
114 BigInt m_q;
115 BigInt m_d1;
116 BigInt m_d2;
117 BigInt m_c;
118
119 const Montgomery_Params m_monty_p;
120 const Montgomery_Params m_monty_q;
121 Montgomery_Int m_c_monty;
122 size_t m_p_bits;
123 size_t m_q_bits;
124};
125
126std::shared_ptr<const RSA_Public_Data> RSA_PublicKey::public_data() const {
127 return m_public;
128}
129
130const BigInt& RSA_PublicKey::get_int_field(std::string_view field) const {
131 if(field == "n") {
132 return m_public->get_n();
133 } else if(field == "e") {
134 return m_public->get_e();
135 } else {
136 return Public_Key::get_int_field(field);
137 }
138}
139
140std::unique_ptr<Private_Key> RSA_PublicKey::generate_another(RandomNumberGenerator& rng) const {
141 return std::make_unique<RSA_PrivateKey>(rng, m_public->public_modulus_bits(), m_public->get_e().to_u32bit());
142}
143
145 return m_public->get_n();
146}
147
149 return m_public->get_e();
150}
151
153 if(n.is_negative() || n.is_even() || n.bits() < 5 /* n >= 3*5 */ || e.is_negative() || e.is_even()) {
154 throw Decoding_Error("Invalid RSA public key parameters");
155 }
156 m_public = std::make_shared<RSA_Public_Data>(std::move(n), std::move(e));
157}
158
159RSA_PublicKey::RSA_PublicKey(const AlgorithmIdentifier& /*unused*/, std::span<const uint8_t> key_bits) {
160 BigInt n;
161 BigInt e;
162 BER_Decoder(key_bits).start_sequence().decode(n).decode(e).end_cons();
163
164 init(std::move(n), std::move(e));
165}
166
171
172RSA_PublicKey::RSA_PublicKey(const BigInt& modulus, const BigInt& exponent) {
173 BigInt n = modulus;
174 BigInt e = exponent;
175 init(std::move(n), std::move(e));
176}
177
179 return m_public->public_modulus_bits();
180}
181
185
189
190std::vector<uint8_t> RSA_PublicKey::raw_public_key_bits() const {
191 throw Not_Implemented("an RSA public key does not provide a raw binary representation.");
192}
193
194std::vector<uint8_t> RSA_PublicKey::public_key_bits() const {
195 std::vector<uint8_t> output;
196 DER_Encoder der(output);
198
199 return output;
200}
201
202/*
203* Check RSA Public Parameters
204*/
205bool RSA_PublicKey::check_key(RandomNumberGenerator& /*rng*/, bool /*strong*/) const {
206 if(get_n() < 35 || get_n().is_even() || get_e() < 3 || get_e().is_even()) {
207 return false;
208 }
209 return true;
210}
211
212std::shared_ptr<const RSA_Private_Data> RSA_PrivateKey::private_data() const {
213 return m_private;
214}
215
217 return DER_Encoder()
219 .encode(static_cast<size_t>(0))
220 .encode(get_n())
221 .encode(get_e())
222 .encode(get_d())
223 .encode(get_p())
224 .encode(get_q())
225 .encode(get_d1())
226 .encode(get_d2())
227 .encode(get_c())
228 .end_cons()
229 .get_contents();
230}
231
233 return m_private->get_p();
234}
235
237 return m_private->get_q();
238}
239
241 return m_private->get_d();
242}
243
245 return m_private->get_c();
246}
247
249 return m_private->get_d1();
250}
251
253 return m_private->get_d2();
254}
255
256void RSA_PrivateKey::init(BigInt&& d, BigInt&& p, BigInt&& q, BigInt&& d1, BigInt&& d2, BigInt&& c) {
257 m_private = std::make_shared<RSA_Private_Data>(
258 std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
259}
260
261RSA_PrivateKey::RSA_PrivateKey(const AlgorithmIdentifier& /*unused*/, std::span<const uint8_t> key_bits) {
262 BigInt n;
263 BigInt e;
264 BigInt d;
265 BigInt p;
266 BigInt q;
267 BigInt d1;
268 BigInt d2;
269 BigInt c;
270
271 BER_Decoder(key_bits)
273 .decode_and_check<size_t>(0, "Unknown PKCS #1 key format version")
274 .decode(n)
275 .decode(e)
276 .decode(d)
277 .decode(p)
278 .decode(q)
279 .decode(d1)
280 .decode(d2)
281 .decode(c)
282 .end_cons();
283
284 RSA_PublicKey::init(std::move(n), std::move(e));
285
286 RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
287}
288
290 const BigInt& prime1, const BigInt& prime2, const BigInt& exp, const BigInt& d_exp, const BigInt& mod) {
291 BigInt p = prime1;
292 BigInt q = prime2;
293 BigInt n = mod;
294 if(n.is_zero()) {
295 n = p * q;
296 }
297
298 BigInt e = exp;
299
300 BigInt d = d_exp;
301
302 const BigInt p_minus_1 = p - 1;
303 const BigInt q_minus_1 = q - 1;
304
305 if(d.is_zero()) {
306 const BigInt phi_n = lcm(p_minus_1, q_minus_1);
307 d = compute_rsa_secret_exponent(e, phi_n, p, q);
308 }
309
310 BigInt d1 = ct_modulo(d, p_minus_1);
311 BigInt d2 = ct_modulo(d, q_minus_1);
313
314 RSA_PublicKey::init(std::move(n), std::move(e));
315
316 RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
317}
318
319/*
320* Create a RSA private key
321*/
323 if(bits < 1024) {
324 throw Invalid_Argument(fmt("Cannot create an RSA key only {} bits long", bits));
325 }
326
327 if(exp < 3 || exp % 2 == 0) {
328 throw Invalid_Argument("Invalid RSA encryption exponent");
329 }
330
331 const size_t p_bits = (bits + 1) / 2;
332 const size_t q_bits = bits - p_bits;
333
334 BigInt p;
335 BigInt q;
336 BigInt n;
337 BigInt e = BigInt::from_u64(exp);
338
339 for(size_t attempt = 0;; ++attempt) {
340 if(attempt > 10) {
341 throw Internal_Error("RNG failure during RSA key generation");
342 }
343
344 // TODO could generate primes in thread pool
345 p = generate_rsa_prime(rng, rng, p_bits, e);
346 q = generate_rsa_prime(rng, rng, q_bits, e);
347
348 const BigInt diff = p - q;
349 if(diff.bits() < (bits / 2) - 100) {
350 continue;
351 }
352
353 n = p * q;
354
355 if(n.bits() != bits) {
356 continue;
357 }
358
359 break;
360 }
361
362 const BigInt p_minus_1 = p - 1;
363 const BigInt q_minus_1 = q - 1;
364
365 const BigInt phi_n = lcm(p_minus_1, q_minus_1);
366 // This is guaranteed because p,q == 3 mod 4
368
369 BigInt d = compute_rsa_secret_exponent(e, phi_n, p, q);
370 BigInt d1 = ct_modulo(d, p_minus_1);
371 BigInt d2 = ct_modulo(d, q_minus_1);
373
374 RSA_PublicKey::init(std::move(n), std::move(e));
375
376 RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
377}
378
379const BigInt& RSA_PrivateKey::get_int_field(std::string_view field) const {
380 if(field == "p") {
381 return m_private->get_p();
382 } else if(field == "q") {
383 return m_private->get_q();
384 } else if(field == "d") {
385 return m_private->get_d();
386 } else if(field == "c") {
387 return m_private->get_c();
388 } else if(field == "d1") {
389 return m_private->get_d1();
390 } else if(field == "d2") {
391 return m_private->get_d2();
392 } else {
393 return RSA_PublicKey::get_int_field(field);
394 }
395}
396
397std::unique_ptr<Public_Key> RSA_PrivateKey::public_key() const {
398 return std::make_unique<RSA_PublicKey>(get_n(), get_e());
399}
400
401/*
402* Check Private RSA Parameters
403*/
405 if(get_n() < 35 || get_n().is_even() || get_e() < 3 || get_e().is_even()) {
406 return false;
407 }
408
409 if(get_d() < 2 || get_p() < 3 || get_q() < 3) {
410 return false;
411 }
412
413 if(get_p() * get_q() != get_n()) {
414 return false;
415 }
416
417 if(get_p() == get_q()) {
418 return false;
419 }
420
421 if(get_d1() != ct_modulo(get_d(), get_p() - 1)) {
422 return false;
423 }
424 if(get_d2() != ct_modulo(get_d(), get_q() - 1)) {
425 return false;
426 }
428 return false;
429 }
430
431 const size_t prob = (strong) ? 128 : 12;
432
433 if(!is_prime(get_p(), rng, prob)) {
434 return false;
435 }
436 if(!is_prime(get_q(), rng, prob)) {
437 return false;
438 }
439
440 if(strong) {
441 if(ct_modulo(get_e() * get_d(), lcm(get_p() - 1, get_q() - 1)) != 1) {
442 return false;
443 }
444
445#if defined(BOTAN_HAS_PSS) && defined(BOTAN_HAS_SHA_256)
446 const std::string padding = "PSS(SHA-256)";
447#else
448 const std::string padding = "Raw";
449#endif
450
451 return KeyPair::signature_consistency_check(rng, *this, padding);
452 }
453
454 return true;
455}
456
457namespace {
458
459/*
460* To recover the final value from the CRT representation (j1,j2)
461* we use Garner's algorithm:
462* c = q^-1 mod p (this is precomputed)
463* h = c*(j1-j2) mod p
464* r = h*q + j2
465*/
466BigInt crt_recombine(const Montgomery_Int& j1,
467 const Montgomery_Int& j2_p,
468 const BigInt& j2,
469 const Montgomery_Int& c_monty,
470 const BigInt& p,
471 const BigInt& q) {
472 // We skip CRT entirely if the primes are not balanced (same bitlength) so q is also of this size
473 const size_t p_words = p.sig_words();
474 BOTAN_ASSERT_NOMSG(p_words == q.sig_words());
475
476 const size_t n_words = 2 * p_words;
477
478 // Ensure sufficient storage
479 BOTAN_ASSERT_NOMSG(j1.repr().size() >= p_words);
480 BOTAN_ASSERT_NOMSG(j2_p.repr().size() >= p_words);
481 BOTAN_ASSERT_NOMSG(j2.size() >= p_words);
482
483 /*
484 * Compute h = (j1 - j2) * c mod p
485 *
486 * This doesn't quite match up with the "Smooth-CRT" proposal; there we would
487 * multiply by a precomputed c * R2, which would have the effect of both
488 * multiplying by c and immediately converting from Montgomery to standard form.
489 */
490 secure_vector<word> ws(2 * p_words);
491
492 const Montgomery_Int h_monty = (j1 - j2_p).mul(c_monty, ws);
493
494 const BigInt h = h_monty.value();
495 // Montgomery_Int always returns values sized to the modulus
496 BOTAN_ASSERT_NOMSG(h.size() >= p_words);
497 BOTAN_DEBUG_ASSERT(h.sig_words() <= p_words);
498
499 // Compute r = h * q
500 secure_vector<word> r(2 * p_words);
501
502 bigint_mul(r.data(), r.size(), h._data(), h.size(), p_words, q._data(), q.size(), p_words, ws.data(), ws.size());
503
504 // r += j2
505 const word carry = bigint_add2(r.data(), n_words, j2._data(), p_words);
506 BOTAN_ASSERT_NOMSG(carry == 0); // should not be possible since it would imply r > the public modulus
507
508 return BigInt::_from_words(r);
509}
510
511/**
512* RSA private (decrypt/sign) operation
513*/
514class RSA_Private_Operation {
515 protected:
516 size_t public_modulus_bits() const { return m_public->public_modulus_bits(); }
517
518 size_t public_modulus_bytes() const { return m_public->public_modulus_bytes(); }
519
520 explicit RSA_Private_Operation(const RSA_PrivateKey& rsa, RandomNumberGenerator& rng) :
521 m_public(rsa.public_data()),
522 m_private(rsa.private_data()),
523 m_blinder(
524 m_public->reducer_mod_n(),
525 rng,
526 [this](const BigInt& k) { return m_public->public_op(k); },
527 [this](const BigInt& k) { return inverse_mod_rsa_public_modulus(k, m_public->get_n()); }),
528 m_blinding_bits(64),
529 m_max_d1_bits(m_private->p_bits() + m_blinding_bits),
530 m_max_d2_bits(m_private->q_bits() + m_blinding_bits) {}
531
532 void raw_op(std::span<uint8_t> out, std::span<const uint8_t> input) {
533 if(input.size() > public_modulus_bytes()) {
534 throw Decoding_Error("RSA input is too long for this key");
535 }
536 const BigInt input_bn(input.data(), input.size());
537 if(input_bn >= m_public->get_n()) {
538 throw Decoding_Error("RSA input is too large for this key");
539 }
540 // TODO: This should be a function on blinder
541 // BigInt Blinder::run_blinded_function(std::function<BigInt, BigInt> fn, const BigInt& input);
542
543 const BigInt recovered = m_blinder.unblind(rsa_private_op(m_blinder.blind(input_bn)));
544 BOTAN_ASSERT(input_bn == m_public->public_op(recovered), "RSA consistency check");
545 BOTAN_ASSERT(m_public->public_modulus_bytes() == out.size(), "output size check");
546 recovered.serialize_to(out);
547 }
548
549 private:
550 BigInt rsa_private_op(const BigInt& m) const {
551 /*
552 All normal implementations generate p/q of the same bitlength,
553 so this should rarely occur in practice
554 */
555 if(m_private->primes_imbalanced()) {
556 return monty_exp(m_public->monty_n(), m, m_private->get_d(), m_public->get_n().bits()).value();
557 }
558
559 static constexpr size_t powm_window = 4;
560
561 // Compute this in main thread to avoid racing on the rng
562 const BigInt d1_mask(m_blinder.rng(), m_blinding_bits);
563
564#if defined(BOTAN_HAS_THREAD_UTILS) && !defined(BOTAN_HAS_VALGRIND)
565 #define BOTAN_RSA_USE_ASYNC
566#endif
567
568#if defined(BOTAN_RSA_USE_ASYNC)
569 /*
570 * Precompute m.sig_words in the main thread before calling async. Otherwise
571 * the two threads race (during Barrett_Reduction::reduce) and while the output
572 * is correct in both threads, helgrind warns.
573 */
574 m.sig_words();
575
576 auto future_j1 = Thread_Pool::global_instance().run([this, &m, &d1_mask]() {
577#endif
578 const BigInt masked_d1 = m_private->get_d1() + (d1_mask * (m_private->get_p() - 1));
579 auto powm_d1_p = monty_precompute(Montgomery_Int::from_wide_int(m_private->monty_p(), m), powm_window);
580 auto j1 = monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
581
582#if defined(BOTAN_RSA_USE_ASYNC)
583 return j1;
584 });
585#endif
586
587 const BigInt d2_mask(m_blinder.rng(), m_blinding_bits);
588 const BigInt masked_d2 = m_private->get_d2() + (d2_mask * (m_private->get_q() - 1));
589 auto powm_d2_q = monty_precompute(Montgomery_Int::from_wide_int(m_private->monty_q(), m), powm_window);
590 const auto j2 = monty_execute(*powm_d2_q, masked_d2, m_max_d2_bits).value();
591
592#if defined(BOTAN_RSA_USE_ASYNC)
593 auto j1 = future_j1.get();
594#endif
595
596 // Reduce j2 modulo p
597 const auto j2_p = Montgomery_Int::from_wide_int(m_private->monty_p(), j2);
598
599 return crt_recombine(j1, j2_p, j2, m_private->get_c_monty(), m_private->get_p(), m_private->get_q());
600 }
601
602 std::shared_ptr<const RSA_Public_Data> m_public;
603 std::shared_ptr<const RSA_Private_Data> m_private;
604
605 // XXX could the blinder starting pair be shared?
606 Blinder m_blinder;
607 const size_t m_blinding_bits;
608 const size_t m_max_d1_bits;
609 const size_t m_max_d2_bits;
610};
611
612class RSA_Signature_Operation final : public PK_Ops::Signature,
613 private RSA_Private_Operation {
614 public:
615 void update(std::span<const uint8_t> msg) override { m_padding->update(msg.data(), msg.size()); }
616
617 std::vector<uint8_t> sign(RandomNumberGenerator& rng) override {
618 const size_t max_input_bits = public_modulus_bits() - 1;
619 const auto msg = m_padding->raw_data();
620 const auto padded = m_padding->encoding_of(msg, max_input_bits, rng);
621
622 std::vector<uint8_t> out(public_modulus_bytes());
623 raw_op(out, padded);
624 return out;
625 }
626
627 size_t signature_length() const override { return public_modulus_bytes(); }
628
629 AlgorithmIdentifier algorithm_identifier() const override;
630
631 std::string hash_function() const override { return m_padding->hash_function(); }
632
633 RSA_Signature_Operation(const RSA_PrivateKey& rsa, std::string_view padding, RandomNumberGenerator& rng) :
634 RSA_Private_Operation(rsa, rng), m_padding(SignaturePaddingScheme::create_or_throw(padding)) {}
635
636 private:
637 std::unique_ptr<SignaturePaddingScheme> m_padding;
638};
639
640AlgorithmIdentifier RSA_Signature_Operation::algorithm_identifier() const {
641 const std::string padding_name = m_padding->name();
642
643 try {
644 const std::string full_name = "RSA/" + padding_name;
645 const OID oid = OID::from_string(full_name);
646 return AlgorithmIdentifier(oid, AlgorithmIdentifier::USE_EMPTY_PARAM);
647 } catch(Lookup_Error&) {}
648
649 if(padding_name.starts_with("PSS(")) {
650 auto parameters = PSS_Params::from_padding_name(m_padding->name()).serialize();
651 return AlgorithmIdentifier("RSA/PSS", parameters);
652 }
653
654 throw Invalid_Argument(fmt("Signatures using RSA/{} are not supported", padding_name));
655}
656
657class RSA_Decryption_Operation final : public PK_Ops::Decryption_with_EME,
658 private RSA_Private_Operation {
659 public:
660 RSA_Decryption_Operation(const RSA_PrivateKey& rsa, std::string_view eme, RandomNumberGenerator& rng) :
661 PK_Ops::Decryption_with_EME(eme), RSA_Private_Operation(rsa, rng) {}
662
663 size_t plaintext_length(size_t /*ctext_len*/) const override { return public_modulus_bytes(); }
664
665 secure_vector<uint8_t> raw_decrypt(std::span<const uint8_t> input) override {
666 secure_vector<uint8_t> out(public_modulus_bytes());
667 raw_op(out, input);
668 return out;
669 }
670};
671
672class RSA_KEM_Decryption_Operation final : public PK_Ops::KEM_Decryption_with_KDF,
673 private RSA_Private_Operation {
674 public:
675 RSA_KEM_Decryption_Operation(const RSA_PrivateKey& key, std::string_view kdf, RandomNumberGenerator& rng) :
676 PK_Ops::KEM_Decryption_with_KDF(kdf), RSA_Private_Operation(key, rng) {}
677
678 size_t raw_kem_shared_key_length() const override { return public_modulus_bytes(); }
679
680 size_t encapsulated_key_length() const override { return public_modulus_bytes(); }
681
682 void raw_kem_decrypt(std::span<uint8_t> out_shared_key, std::span<const uint8_t> encapsulated_key) override {
683 raw_op(out_shared_key, encapsulated_key);
684 }
685};
686
687/**
688* RSA public (encrypt/verify) operation
689*/
690class RSA_Public_Operation {
691 public:
692 explicit RSA_Public_Operation(const RSA_PublicKey& rsa) : m_public(rsa.public_data()) {}
693
694 size_t public_modulus_bits() const { return m_public->public_modulus_bits(); }
695
696 protected:
697 BigInt public_op(const BigInt& m) const {
698 if(m >= m_public->get_n()) {
699 throw Decoding_Error("RSA public op - input is too large");
700 }
701
702 return m_public->public_op(m);
703 }
704
705 size_t public_modulus_bytes() const { return m_public->public_modulus_bytes(); }
706
707 const BigInt& get_n() const { return m_public->get_n(); }
708
709 private:
710 std::shared_ptr<const RSA_Public_Data> m_public;
711};
712
713class RSA_Encryption_Operation final : public PK_Ops::Encryption_with_EME,
714 private RSA_Public_Operation {
715 public:
716 RSA_Encryption_Operation(const RSA_PublicKey& rsa, std::string_view eme) :
717 PK_Ops::Encryption_with_EME(eme), RSA_Public_Operation(rsa) {}
718
719 size_t ciphertext_length(size_t /*ptext_len*/) const override { return public_modulus_bytes(); }
720
721 size_t max_ptext_input_bits() const override { return public_modulus_bits() - 1; }
722
723 std::vector<uint8_t> raw_encrypt(std::span<const uint8_t> input, RandomNumberGenerator& /*rng*/) override {
724 BigInt input_bn(input);
725 return public_op(input_bn).serialize(public_modulus_bytes());
726 }
727};
728
729class RSA_Verify_Operation final : public PK_Ops::Verification,
730 private RSA_Public_Operation {
731 public:
732 void update(std::span<const uint8_t> msg) override { m_padding->update(msg.data(), msg.size()); }
733
734 bool is_valid_signature(std::span<const uint8_t> sig) override {
735 const auto msg = m_padding->raw_data();
736 const auto message_repr = recover_message_repr(sig.data(), sig.size());
737 return m_padding->verify(message_repr, msg, public_modulus_bits() - 1);
738 }
739
740 RSA_Verify_Operation(const RSA_PublicKey& rsa, std::string_view padding) :
741 RSA_Public_Operation(rsa), m_padding(SignaturePaddingScheme::create_or_throw(padding)) {}
742
743 std::string hash_function() const override { return m_padding->hash_function(); }
744
745 private:
746 std::vector<uint8_t> recover_message_repr(const uint8_t input[], size_t input_len) {
747 if(input_len > public_modulus_bytes()) {
748 throw Decoding_Error("RSA signature too large to be valid for this key");
749 }
750 BigInt input_bn(input, input_len);
751 return public_op(input_bn).serialize();
752 }
753
754 std::unique_ptr<SignaturePaddingScheme> m_padding;
755};
756
757class RSA_KEM_Encryption_Operation final : public PK_Ops::KEM_Encryption_with_KDF,
758 private RSA_Public_Operation {
759 public:
760 RSA_KEM_Encryption_Operation(const RSA_PublicKey& key, std::string_view kdf) :
761 PK_Ops::KEM_Encryption_with_KDF(kdf), RSA_Public_Operation(key) {}
762
763 private:
764 size_t raw_kem_shared_key_length() const override { return public_modulus_bytes(); }
765
766 size_t encapsulated_key_length() const override { return public_modulus_bytes(); }
767
768 void raw_kem_encrypt(std::span<uint8_t> out_encapsulated_key,
769 std::span<uint8_t> raw_shared_key,
770 RandomNumberGenerator& rng) override {
771 const BigInt r = BigInt::random_integer(rng, BigInt::one(), get_n());
772 const BigInt c = public_op(r);
773
774 c.serialize_to(out_encapsulated_key);
775 r.serialize_to(raw_shared_key);
776 }
777};
778
779} // namespace
780
781std::unique_ptr<PK_Ops::Encryption> RSA_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/,
782 std::string_view params,
783 std::string_view provider) const {
784 if(provider == "base" || provider.empty()) {
785 return std::make_unique<RSA_Encryption_Operation>(*this, params);
786 }
787 throw Provider_Not_Found(algo_name(), provider);
788}
789
790std::unique_ptr<PK_Ops::KEM_Encryption> RSA_PublicKey::create_kem_encryption_op(std::string_view params,
791 std::string_view provider) const {
792 if(provider == "base" || provider.empty()) {
793 return std::make_unique<RSA_KEM_Encryption_Operation>(*this, params);
794 }
795 throw Provider_Not_Found(algo_name(), provider);
796}
797
798std::unique_ptr<PK_Ops::Verification> RSA_PublicKey::create_verification_op(std::string_view params,
799 std::string_view provider) const {
800 if(provider == "base" || provider.empty()) {
801 return std::make_unique<RSA_Verify_Operation>(*this, params);
802 }
803
804 throw Provider_Not_Found(algo_name(), provider);
805}
806
807namespace {
808
809std::string parse_rsa_signature_algorithm(const AlgorithmIdentifier& alg_id) {
810 const auto sig_info = split_on(alg_id.oid().to_formatted_string(), '/');
811
812 if(sig_info.empty() || sig_info.size() != 2 || sig_info[0] != "RSA") {
813 throw Decoding_Error("Unknown AlgorithmIdentifier for RSA X.509 signatures");
814 }
815
816 std::string padding = sig_info[1];
817
818 if(padding == "PSS") {
819 // "MUST contain RSASSA-PSS-params"
820 if(alg_id.parameters().empty()) {
821 throw Decoding_Error("PSS params must be provided");
822 }
823
824 PSS_Params pss_params(alg_id.parameters());
825
826 // hash_algo must be SHA1, SHA2-224, SHA2-256, SHA2-384 or SHA2-512
827 // We also support SHA-3 (is also supported by e.g. OpenSSL and bouncycastle)
828 const std::string hash_algo = pss_params.hash_function();
829 if(hash_algo != "SHA-1" && hash_algo != "SHA-224" && hash_algo != "SHA-256" && hash_algo != "SHA-384" &&
830 hash_algo != "SHA-512" && hash_algo != "SHA-3(224)" && hash_algo != "SHA-3(256)" &&
831 hash_algo != "SHA-3(384)" && hash_algo != "SHA-3(512)") {
832 throw Decoding_Error("Unacceptable hash for PSS signatures");
833 }
834
835 if(pss_params.mgf_function() != "MGF1") {
836 throw Decoding_Error("Unacceptable MGF for PSS signatures");
837 }
838
839 // For MGF1, it is strongly RECOMMENDED that the underlying hash
840 // function be the same as the one identified by hashAlgorithm
841 if(pss_params.hash_algid() != pss_params.mgf_hash_algid()) {
842 throw Decoding_Error("Unacceptable MGF hash for PSS signatures");
843 }
844
845 if(pss_params.trailer_field() != 1) {
846 throw Decoding_Error("Unacceptable trailer field for PSS signatures");
847 }
848
849 padding += fmt("({},MGF1,{})", hash_algo, pss_params.salt_length());
850 }
851
852 return padding;
853}
854
855} // namespace
856
857std::unique_ptr<PK_Ops::Verification> RSA_PublicKey::create_x509_verification_op(const AlgorithmIdentifier& alg_id,
858 std::string_view provider) const {
859 if(provider == "base" || provider.empty()) {
860 return std::make_unique<RSA_Verify_Operation>(*this, parse_rsa_signature_algorithm(alg_id));
861 }
862
863 throw Provider_Not_Found(algo_name(), provider);
864}
865
866std::unique_ptr<PK_Ops::Decryption> RSA_PrivateKey::create_decryption_op(RandomNumberGenerator& rng,
867 std::string_view params,
868 std::string_view provider) const {
869 if(provider == "base" || provider.empty()) {
870 return std::make_unique<RSA_Decryption_Operation>(*this, params, rng);
871 }
872
873 throw Provider_Not_Found(algo_name(), provider);
874}
875
876std::unique_ptr<PK_Ops::KEM_Decryption> RSA_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& rng,
877 std::string_view params,
878 std::string_view provider) const {
879 if(provider == "base" || provider.empty()) {
880 return std::make_unique<RSA_KEM_Decryption_Operation>(*this, params, rng);
881 }
882
883 throw Provider_Not_Found(algo_name(), provider);
884}
885
886std::unique_ptr<PK_Ops::Signature> RSA_PrivateKey::create_signature_op(RandomNumberGenerator& rng,
887 std::string_view params,
888 std::string_view provider) const {
889 if(provider == "base" || provider.empty()) {
890 return std::make_unique<RSA_Signature_Operation>(*this, params, rng);
891 }
892
893 throw Provider_Not_Found(algo_name(), provider);
894}
895
896} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:75
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:129
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:62
const std::vector< uint8_t > & parameters() const
Definition asn1_obj.h:481
const OID & oid() const
Definition asn1_obj.h:479
virtual const BigInt & get_int_field(std::string_view field) const
Definition pk_keys.cpp:18
virtual OID object_identifier() const
Definition pk_keys.cpp:22
BER_Decoder & decode(bool &out)
Definition ber_dec.h:188
BER_Decoder & end_cons()
Definition ber_dec.cpp:312
BER_Decoder start_sequence()
Definition ber_dec.h:125
BER_Decoder & decode_and_check(const T &expected, std::string_view error_msg)
Definition ber_dec.h:282
size_t sig_words() const
Definition bigint.h:615
size_t size() const
Definition bigint.h:609
static BigInt _from_words(secure_vector< word > &words)
Definition bigint.h:955
size_t bits() const
Definition bigint.cpp:311
static BigInt from_u64(uint64_t n)
Definition bigint.cpp:29
const word * _data() const
Definition bigint.h:936
bool is_zero() const
Definition bigint.h:457
secure_vector< uint8_t > get_contents()
Definition der_enc.cpp:134
DER_Encoder & start_sequence()
Definition der_enc.h:65
DER_Encoder & end_cons()
Definition der_enc.cpp:173
DER_Encoder & encode(bool b)
Definition der_enc.cpp:252
static Montgomery_Int from_wide_int(const Montgomery_Params &params, const BigInt &x)
Definition monty.cpp:207
const secure_vector< word > & repr() const
Definition monty.h:143
BigInt value() const
Definition monty.cpp:245
std::string to_formatted_string() const
Definition asn1_oid.cpp:139
virtual void update(std::span< const uint8_t > input)=0
const BigInt & get_q() const
Definition rsa.cpp:236
const BigInt & get_int_field(std::string_view field) const override
Definition rsa.cpp:379
std::shared_ptr< const RSA_Private_Data > private_data() const
Definition rsa.cpp:212
std::unique_ptr< PK_Ops::Decryption > create_decryption_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
Definition rsa.cpp:866
const BigInt & get_c() const
Definition rsa.cpp:244
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
Definition rsa.cpp:886
RSA_PrivateKey(const AlgorithmIdentifier &alg_id, std::span< const uint8_t > key_bits)
Definition rsa.cpp:261
const BigInt & get_p() const
Definition rsa.cpp:232
const BigInt & get_d2() const
Definition rsa.cpp:252
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition rsa.cpp:404
const BigInt & get_d() const
Definition rsa.cpp:240
secure_vector< uint8_t > private_key_bits() const override
Definition rsa.cpp:216
std::unique_ptr< PK_Ops::KEM_Decryption > create_kem_decryption_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
Definition rsa.cpp:876
std::unique_ptr< Public_Key > public_key() const override
Definition rsa.cpp:397
const BigInt & get_d1() const
Definition rsa.cpp:248
std::unique_ptr< PK_Ops::Encryption > create_encryption_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
Definition rsa.cpp:781
void init(BigInt &&n, BigInt &&e)
Definition rsa.cpp:152
size_t key_length() const override
Definition rsa.cpp:178
std::unique_ptr< PK_Ops::Verification > create_verification_op(std::string_view params, std::string_view provider) const override
Definition rsa.cpp:798
std::string algo_name() const override
Definition rsa.h:41
std::unique_ptr< PK_Ops::Verification > create_x509_verification_op(const AlgorithmIdentifier &alg_id, std::string_view provider) const override
Definition rsa.cpp:857
const BigInt & get_int_field(std::string_view field) const override
Definition rsa.cpp:130
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition rsa.cpp:205
const BigInt & get_n() const
Definition rsa.cpp:144
size_t estimated_strength() const override
Definition rsa.cpp:182
std::unique_ptr< PK_Ops::KEM_Encryption > create_kem_encryption_op(std::string_view params, std::string_view provider) const override
Definition rsa.cpp:790
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const override
Definition rsa.cpp:140
std::vector< uint8_t > raw_public_key_bits() const override
Definition rsa.cpp:190
AlgorithmIdentifier algorithm_identifier() const override
Definition rsa.cpp:186
std::vector< uint8_t > public_key_bits() const override
Definition rsa.cpp:194
std::shared_ptr< const RSA_Public_Data > m_public
Definition rsa.h:91
std::shared_ptr< const RSA_Public_Data > public_data() const
Definition rsa.cpp:126
const BigInt & get_e() const
Definition rsa.cpp:148
bool supports_operation(PublicKeyOperation op) const override
Definition rsa.cpp:167
auto run(F &&f, Args &&... args) -> std::future< std::invoke_result_t< F, Args... > >
Definition thread_pool.h:66
static Thread_Pool & global_instance()
bool signature_consistency_check(RandomNumberGenerator &rng, const Private_Key &private_key, const Public_Key &public_key, std::string_view padding)
Definition keypair.cpp:49
BigInt inverse_mod_secret_prime(const BigInt &x, const BigInt &p)
Definition mod_inv.cpp:280
constexpr auto bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) -> W
Definition mp_core.h:96
std::string fmt(std::string_view format, const T &... args)
Definition fmt.h:53
BigInt lcm(const BigInt &a, const BigInt &b)
Definition numthry.cpp:269
std::vector< std::string > split_on(std::string_view str, char delim)
Definition parsing.cpp:111
size_t low_zero_bits(const BigInt &n)
Definition numthry.cpp:167
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition mp_karat.cpp:283
Montgomery_Int monty_execute_vartime(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k)
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
Definition numthry.cpp:354
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:192
BigInt compute_rsa_secret_exponent(const BigInt &e, const BigInt &phi_n, const BigInt &p, const BigInt &q)
Definition mod_inv.cpp:330
PublicKeyOperation
Definition pk_keys.h:46
BigInt generate_rsa_prime(RandomNumberGenerator &keygen_rng, RandomNumberGenerator &prime_test_rng, size_t bits, const BigInt &coprime, size_t prob)
Definition make_prm.cpp:211
void carry(int64_t &h0, int64_t &h1)
Montgomery_Int monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:69
BigInt inverse_mod_rsa_public_modulus(const BigInt &x, const BigInt &n)
Definition mod_inv.cpp:295
size_t if_work_factor(size_t bits)
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(const Montgomery_Int &g, size_t window_bits, bool const_time)
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
Definition types.h:119
Montgomery_Int monty_exp(const Montgomery_Params &params_p, const BigInt &g, const BigInt &k, size_t max_k_bits)
Definition monty_exp.h:47