10#include <botan/ber_dec.h>
11#include <botan/der_enc.h>
12#include <botan/reducer.h>
13#include <botan/internal/blinding.h>
14#include <botan/internal/divide.h>
15#include <botan/internal/emsa.h>
16#include <botan/internal/fmt.h>
17#include <botan/internal/keypair.h>
18#include <botan/internal/monty.h>
19#include <botan/internal/monty_exp.h>
20#include <botan/internal/parsing.h>
21#include <botan/internal/pk_ops_impl.h>
22#include <botan/internal/pss_params.h>
23#include <botan/internal/workfactor.h>
25#if defined(BOTAN_HAS_THREAD_UTILS)
26 #include <botan/internal/thread_pool.h>
31class RSA_Public_Data
final {
33 RSA_Public_Data(BigInt&& n, BigInt&& e) :
36 m_monty_n(std::make_shared<Montgomery_Params>(m_n)),
37 m_public_modulus_bits(m_n.bits()),
38 m_public_modulus_bytes(m_n.bytes()) {}
40 BigInt public_op(
const BigInt& m)
const {
41 const size_t powm_window = 1;
46 const BigInt& get_n()
const {
return m_n; }
48 const BigInt& get_e()
const {
return m_e; }
50 size_t public_modulus_bits()
const {
return m_public_modulus_bits; }
52 size_t public_modulus_bytes()
const {
return m_public_modulus_bytes; }
57 std::shared_ptr<const Montgomery_Params> m_monty_n;
58 size_t m_public_modulus_bits;
59 size_t m_public_modulus_bytes;
62class RSA_Private_Data
final {
64 RSA_Private_Data(BigInt&& d, BigInt&& p, BigInt&& q, BigInt&& d1, BigInt&& d2, BigInt&& c) :
73 m_monty_p(std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
74 m_monty_q(std::make_shared<Montgomery_Params>(m_q, m_mod_q)),
76 m_q_bits(m_q.bits()) {}
78 const BigInt& get_d()
const {
return m_d; }
80 const BigInt& get_p()
const {
return m_p; }
82 const BigInt& get_q()
const {
return m_q; }
84 const BigInt& get_d1()
const {
return m_d1; }
86 const BigInt& get_d2()
const {
return m_d2; }
88 const BigInt& get_c()
const {
return m_c; }
90 const Modular_Reducer& mod_p()
const {
return m_mod_p; }
92 const Modular_Reducer& mod_q()
const {
return m_mod_q; }
94 const std::shared_ptr<const Montgomery_Params>& monty_p()
const {
return m_monty_p; }
96 const std::shared_ptr<const Montgomery_Params>& monty_q()
const {
return m_monty_q; }
98 size_t p_bits()
const {
return m_p_bits; }
100 size_t q_bits()
const {
return m_q_bits; }
110 Modular_Reducer m_mod_p;
111 Modular_Reducer m_mod_q;
112 std::shared_ptr<const Montgomery_Params> m_monty_p;
113 std::shared_ptr<const Montgomery_Params> m_monty_q;
125 }
else if(field ==
"e") {
141 if(n.is_negative() || n.is_even() || n.bits() < 5 || e.is_negative() || e.is_even()) {
144 m_public = std::make_shared<RSA_Public_Data>(std::move(n), std::move(e));
151 init(std::move(n), std::move(e));
162 init(std::move(n), std::move(e));
166 return m_public->public_modulus_bits();
178 std::vector<uint8_t> output;
202 .
encode(
static_cast<size_t>(0))
216 return m_private->get_p();
220 return m_private->get_q();
224 return m_private->get_d();
228 return m_private->get_c();
232 return m_private->get_d1();
236 return m_private->get_d2();
240 m_private = std::make_shared<RSA_Private_Data>(
241 std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
245 BigInt n, e, d, p, q, d1, d2, c;
262 RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
278 const BigInt p_minus_1 = p - 1;
279 const BigInt q_minus_1 = q - 1;
282 const BigInt phi_n =
lcm(p_minus_1, q_minus_1);
292 RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
303 if(exp < 3 || exp % 2 == 0) {
307 const size_t p_bits = (bits + 1) / 2;
308 const size_t q_bits = bits - p_bits;
313 for(
size_t attempt = 0;; ++attempt) {
322 const BigInt diff = p - q;
323 if(diff.
bits() < (bits / 2) - 100) {
329 if(n.
bits() != bits) {
336 const BigInt p_minus_1 = p - 1;
337 const BigInt q_minus_1 = q - 1;
339 const BigInt phi_n =
lcm(p_minus_1, q_minus_1);
350 RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
355 return m_private->get_p();
356 }
else if(field ==
"q") {
357 return m_private->get_q();
358 }
else if(field ==
"d") {
359 return m_private->get_d();
360 }
else if(field ==
"c") {
361 return m_private->get_c();
362 }
else if(field ==
"d1") {
363 return m_private->get_d1();
364 }
else if(field ==
"d2") {
365 return m_private->get_d2();
372 return std::make_unique<RSA_PublicKey>(
get_n(),
get_e());
405 const size_t prob = (strong) ? 128 : 12;
430class RSA_Private_Operation {
432 size_t public_modulus_bits()
const {
return m_public->public_modulus_bits(); }
434 size_t public_modulus_bytes()
const {
return m_public->public_modulus_bytes(); }
436 explicit RSA_Private_Operation(
const RSA_PrivateKey& rsa, RandomNumberGenerator& rng) :
437 m_public(rsa.public_data()),
438 m_private(rsa.private_data()),
442 [this](const BigInt& k) {
return m_public->public_op(k); },
443 [
this](
const BigInt& k) {
return inverse_mod(k, m_public->get_n()); }),
445 m_max_d1_bits(m_private->p_bits() + m_blinding_bits),
446 m_max_d2_bits(m_private->q_bits() + m_blinding_bits) {}
448 void raw_op(std::span<uint8_t> out, std::span<const uint8_t> input) {
449 if(input.size() > public_modulus_bytes()) {
450 throw Decoding_Error(
"RSA input is too long for this key");
452 const BigInt input_bn(input.data(), input.size());
453 if(input_bn >= m_public->get_n()) {
454 throw Decoding_Error(
"RSA input is too large for this key");
459 const BigInt recovered = m_blinder.unblind(rsa_private_op(m_blinder.blind(input_bn)));
460 BOTAN_ASSERT(input_bn == m_public->public_op(recovered),
"RSA consistency check");
461 BOTAN_ASSERT(m_public->public_modulus_bytes() == out.size(),
"output size check");
465 secure_vector<uint8_t> raw_op(
const uint8_t input[],
size_t input_len) {
466 secure_vector<uint8_t> out(m_public->public_modulus_bytes());
467 raw_op(out, {input, input_len});
472 BigInt rsa_private_op(
const BigInt& m)
const {
479 static constexpr size_t powm_window = 4;
482 const BigInt d1_mask(m_blinder.rng(), m_blinding_bits);
484#if defined(BOTAN_HAS_THREAD_UTILS) && !defined(BOTAN_HAS_VALGRIND)
485 #define BOTAN_RSA_USE_ASYNC
488#if defined(BOTAN_RSA_USE_ASYNC)
498 const BigInt masked_d1 = m_private->get_d1() + (d1_mask * (m_private->get_p() - 1));
499 auto powm_d1_p =
monty_precompute(m_private->monty_p(), m_private->mod_p().reduce(m), powm_window);
500 BigInt j1 =
monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
502#if defined(BOTAN_RSA_USE_ASYNC)
507 const BigInt d2_mask(m_blinder.rng(), m_blinding_bits);
508 const BigInt masked_d2 = m_private->get_d2() + (d2_mask * (m_private->get_q() - 1));
509 auto powm_d2_q =
monty_precompute(m_private->monty_q(), m_private->mod_q().reduce(m), powm_window);
510 const BigInt j2 =
monty_execute(*powm_d2_q, masked_d2, m_max_d2_bits);
512#if defined(BOTAN_RSA_USE_ASYNC)
513 BigInt j1 = future_j1.get();
530 m_private->mod_p().multiply(m_private->mod_p().reduce((m_private->get_p() + j1) - j2), m_private->get_c());
531 return j1 * m_private->get_q() + j2;
534 std::shared_ptr<const RSA_Public_Data> m_public;
535 std::shared_ptr<const RSA_Private_Data> m_private;
539 const size_t m_blinding_bits;
540 const size_t m_max_d1_bits;
541 const size_t m_max_d2_bits;
544class RSA_Signature_Operation
final :
public PK_Ops::Signature,
545 private RSA_Private_Operation {
547 void update(
const uint8_t msg[],
size_t msg_len)
override { m_emsa->update(msg, msg_len); }
549 secure_vector<uint8_t> sign(RandomNumberGenerator& rng)
override {
550 const size_t max_input_bits = public_modulus_bits() - 1;
551 const auto msg = m_emsa->raw_data();
552 const auto padded = m_emsa->encoding_of(msg, max_input_bits, rng);
553 return raw_op(padded.data(), padded.size());
556 size_t signature_length()
const override {
return public_modulus_bytes(); }
558 AlgorithmIdentifier algorithm_identifier()
const override;
560 std::string hash_function()
const override {
return m_emsa->hash_function(); }
562 RSA_Signature_Operation(
const RSA_PrivateKey& rsa, std::string_view padding, RandomNumberGenerator& rng) :
563 RSA_Private_Operation(rsa, rng), m_emsa(EMSA::create_or_throw(padding)) {}
566 std::unique_ptr<EMSA> m_emsa;
569AlgorithmIdentifier RSA_Signature_Operation::algorithm_identifier()
const {
570 const std::string emsa_name = m_emsa->name();
573 const std::string full_name =
"RSA/" + emsa_name;
576 }
catch(Lookup_Error&) {}
578 if(emsa_name.starts_with(
"EMSA4(")) {
580 return AlgorithmIdentifier(
"RSA/EMSA4", parameters);
583 throw Not_Implemented(
"No algorithm identifier defined for RSA with " + emsa_name);
586class RSA_Decryption_Operation
final :
public PK_Ops::Decryption_with_EME,
587 private RSA_Private_Operation {
589 RSA_Decryption_Operation(
const RSA_PrivateKey& rsa, std::string_view eme, RandomNumberGenerator& rng) :
590 PK_Ops::Decryption_with_EME(eme), RSA_Private_Operation(rsa, rng) {}
592 size_t plaintext_length(
size_t )
const override {
return public_modulus_bytes(); }
594 secure_vector<uint8_t> raw_decrypt(
const uint8_t input[],
size_t input_len)
override {
595 return raw_op(input, input_len);
599class RSA_KEM_Decryption_Operation
final :
public PK_Ops::KEM_Decryption_with_KDF,
600 private RSA_Private_Operation {
602 RSA_KEM_Decryption_Operation(
const RSA_PrivateKey& key, std::string_view kdf, RandomNumberGenerator& rng) :
603 PK_Ops::KEM_Decryption_with_KDF(kdf), RSA_Private_Operation(key, rng) {}
605 size_t raw_kem_shared_key_length()
const override {
return public_modulus_bytes(); }
607 size_t encapsulated_key_length()
const override {
return public_modulus_bytes(); }
609 void raw_kem_decrypt(std::span<uint8_t> out_shared_key, std::span<const uint8_t> encapsulated_key)
override {
610 raw_op(out_shared_key, encapsulated_key);
617class RSA_Public_Operation {
619 explicit RSA_Public_Operation(
const RSA_PublicKey& rsa) : m_public(rsa.public_data()) {}
621 size_t public_modulus_bits()
const {
return m_public->public_modulus_bits(); }
624 BigInt public_op(
const BigInt& m)
const {
625 if(m >= m_public->get_n()) {
626 throw Decoding_Error(
"RSA public op - input is too large");
629 return m_public->public_op(m);
632 size_t public_modulus_bytes()
const {
return m_public->public_modulus_bytes(); }
634 const BigInt& get_n()
const {
return m_public->get_n(); }
637 std::shared_ptr<const RSA_Public_Data> m_public;
640class RSA_Encryption_Operation
final :
public PK_Ops::Encryption_with_EME,
641 private RSA_Public_Operation {
643 RSA_Encryption_Operation(
const RSA_PublicKey& rsa, std::string_view eme) :
644 PK_Ops::Encryption_with_EME(eme), RSA_Public_Operation(rsa) {}
646 size_t ciphertext_length(
size_t )
const override {
return public_modulus_bytes(); }
648 size_t max_ptext_input_bits()
const override {
return public_modulus_bits() - 1; }
650 secure_vector<uint8_t> raw_encrypt(
const uint8_t input[],
652 RandomNumberGenerator& )
override {
653 BigInt input_bn(input, input_len);
658class RSA_Verify_Operation
final :
public PK_Ops::Verification,
659 private RSA_Public_Operation {
661 void update(
const uint8_t msg[],
size_t msg_len)
override { m_emsa->update(msg, msg_len); }
663 bool is_valid_signature(
const uint8_t sig[],
size_t sig_len)
override {
664 const auto msg = m_emsa->raw_data();
665 const auto message_repr = recover_message_repr(sig, sig_len);
666 return m_emsa->verify(message_repr, msg, public_modulus_bits() - 1);
669 RSA_Verify_Operation(
const RSA_PublicKey& rsa, std::string_view padding) :
670 RSA_Public_Operation(rsa), m_emsa(EMSA::create_or_throw(padding)) {}
672 std::string hash_function()
const override {
return m_emsa->hash_function(); }
675 std::vector<uint8_t> recover_message_repr(
const uint8_t input[],
size_t input_len) {
676 if(input_len > public_modulus_bytes()) {
677 throw Decoding_Error(
"RSA signature too large to be valid for this key");
679 BigInt input_bn(input, input_len);
683 std::unique_ptr<EMSA> m_emsa;
686class RSA_KEM_Encryption_Operation
final :
public PK_Ops::KEM_Encryption_with_KDF,
687 private RSA_Public_Operation {
689 RSA_KEM_Encryption_Operation(
const RSA_PublicKey& key, std::string_view kdf) :
690 PK_Ops::KEM_Encryption_with_KDF(kdf), RSA_Public_Operation(key) {}
693 size_t raw_kem_shared_key_length()
const override {
return public_modulus_bytes(); }
695 size_t encapsulated_key_length()
const override {
return public_modulus_bytes(); }
697 void raw_kem_encrypt(std::span<uint8_t> out_encapsulated_key,
698 std::span<uint8_t> raw_shared_key,
699 RandomNumberGenerator& rng)
override {
701 const BigInt c = public_op(r);
711 std::string_view params,
712 std::string_view provider)
const {
713 if(provider ==
"base" || provider.empty()) {
714 return std::make_unique<RSA_Encryption_Operation>(*
this, params);
720 std::string_view provider)
const {
721 if(provider ==
"base" || provider.empty()) {
722 return std::make_unique<RSA_KEM_Encryption_Operation>(*
this, params);
728 std::string_view provider)
const {
729 if(provider ==
"base" || provider.empty()) {
730 return std::make_unique<RSA_Verify_Operation>(*
this, params);
741 if(sig_info.empty() || sig_info.size() != 2 || sig_info[0] !=
"RSA") {
742 throw Decoding_Error(
"Unknown AlgorithmIdentifier for RSA X.509 signatures");
745 std::string padding = sig_info[1];
747 if(padding ==
"EMSA4") {
750 throw Decoding_Error(
"PSS params must be provided");
756 const std::string hash_algo = pss_params.hash_function();
757 if(hash_algo !=
"SHA-1" && hash_algo !=
"SHA-224" && hash_algo !=
"SHA-256" && hash_algo !=
"SHA-384" &&
758 hash_algo !=
"SHA-512") {
759 throw Decoding_Error(
"Unacceptable hash for PSS signatures");
762 if(pss_params.mgf_function() !=
"MGF1") {
763 throw Decoding_Error(
"Unacceptable MGF for PSS signatures");
770 if(pss_params.hash_algid() != pss_params.mgf_hash_algid()) {
771 throw Decoding_Error(
"Unacceptable MGF hash for PSS signatures");
774 if(pss_params.trailer_field() != 1) {
775 throw Decoding_Error(
"Unacceptable trailer field for PSS signatures");
778 padding +=
fmt(
"({},MGF1,{})", hash_algo, pss_params.salt_length());
787 std::string_view provider)
const {
788 if(provider ==
"base" || provider.empty()) {
789 return std::make_unique<RSA_Verify_Operation>(*
this, parse_rsa_signature_algorithm(alg_id));
796 std::string_view params,
797 std::string_view provider)
const {
798 if(provider ==
"base" || provider.empty()) {
799 return std::make_unique<RSA_Decryption_Operation>(*
this, params, rng);
806 std::string_view params,
807 std::string_view provider)
const {
808 if(provider ==
"base" || provider.empty()) {
809 return std::make_unique<RSA_KEM_Decryption_Operation>(*
this, params, rng);
816 std::string_view params,
817 std::string_view provider)
const {
818 if(provider ==
"base" || provider.empty()) {
819 return std::make_unique<RSA_Signature_Operation>(*
this, params, rng);
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ASSERT(expr, assertion_made)
const std::vector< uint8_t > & parameters() const
virtual const BigInt & get_int_field(std::string_view field) const
virtual OID object_identifier() const
BER_Decoder & decode(bool &out)
BER_Decoder start_sequence()
BER_Decoder & decode_and_check(const T &expected, std::string_view error_msg)
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
static std::vector< uint8_t > encode(const BigInt &n)
static BigInt from_u64(uint64_t n)
static secure_vector< uint8_t > encode_1363(const BigInt &n, size_t bytes)
secure_vector< uint8_t > get_contents()
DER_Encoder & start_sequence()
DER_Encoder & encode(bool b)
std::string to_formatted_string() const
static OID from_string(std::string_view str)
std::vector< uint8_t > serialize() const
static PSS_Params from_emsa_name(std::string_view emsa_name)
const BigInt & get_q() const
const BigInt & get_int_field(std::string_view field) const override
std::shared_ptr< const RSA_Private_Data > private_data() const
std::unique_ptr< PK_Ops::Decryption > create_decryption_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
const BigInt & get_c() const
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
RSA_PrivateKey(const AlgorithmIdentifier &alg_id, std::span< const uint8_t > key_bits)
const BigInt & get_p() const
const BigInt & get_d2() const
bool check_key(RandomNumberGenerator &rng, bool) const override
const BigInt & get_d() const
secure_vector< uint8_t > private_key_bits() const override
std::unique_ptr< PK_Ops::KEM_Decryption > create_kem_decryption_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
std::unique_ptr< Public_Key > public_key() const override
const BigInt & get_d1() const
std::unique_ptr< PK_Ops::Encryption > create_encryption_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
void init(BigInt &&n, BigInt &&e)
size_t key_length() const override
std::unique_ptr< PK_Ops::Verification > create_verification_op(std::string_view params, std::string_view provider) const override
std::string algo_name() const override
std::unique_ptr< PK_Ops::Verification > create_x509_verification_op(const AlgorithmIdentifier &alg_id, std::string_view provider) const override
const BigInt & get_int_field(std::string_view field) const override
const BigInt & get_n() const
size_t estimated_strength() const override
std::unique_ptr< PK_Ops::KEM_Encryption > create_kem_encryption_op(std::string_view params, std::string_view provider) const override
AlgorithmIdentifier algorithm_identifier() const override
std::vector< uint8_t > public_key_bits() const override
std::shared_ptr< const RSA_Public_Data > m_public
std::shared_ptr< const RSA_Public_Data > public_data() const
const BigInt & get_e() const
bool supports_operation(PublicKeyOperation op) const override
bool check_key(RandomNumberGenerator &rng, bool) const override
auto run(F &&f, Args &&... args) -> std::future< typename std::invoke_result< F, Args... >::type >
static Thread_Pool & global_instance()
int(* update)(CTX *, const void *, CC_LONG len)
int(* final)(unsigned char *, CTX *)
bool signature_consistency_check(RandomNumberGenerator &rng, const Private_Key &private_key, const Public_Key &public_key, std::string_view padding)
std::string fmt(std::string_view format, const T &... args)
BigInt lcm(const BigInt &a, const BigInt &b)
std::vector< std::string > split_on(std::string_view str, char delim)
size_t low_zero_bits(const BigInt &n)
bool is_prime(const BigInt &n, RandomNumberGenerator &rng, size_t prob, bool is_random)
BigInt ct_modulo(const BigInt &x, const BigInt &y)
BigInt generate_rsa_prime(RandomNumberGenerator &keygen_rng, RandomNumberGenerator &prime_test_rng, size_t bits, const BigInt &coprime, size_t prob)
BigInt monty_execute_vartime(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k)
size_t if_work_factor(size_t bits)
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
std::vector< T, secure_allocator< T > > secure_vector
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(const std::shared_ptr< const Montgomery_Params > ¶ms, const BigInt &g, size_t window_bits, bool const_time)