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>
29#if defined(BOTAN_HAS_THREAD_UTILS)
30 #include <botan/internal/thread_pool.h>
35class RSA_Public_Data final {
37 RSA_Public_Data(BigInt&& n, BigInt&& 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()) {}
45 BigInt public_op(
const BigInt& m)
const {
46 const size_t powm_window = 1;
51 const BigInt& get_n()
const {
return m_n; }
53 const BigInt& get_e()
const {
return m_e; }
55 size_t public_modulus_bits()
const {
return m_public_modulus_bits; }
57 size_t public_modulus_bytes()
const {
return m_public_modulus_bytes; }
59 const Montgomery_Params& monty_n()
const {
return m_monty_n; }
61 const Barrett_Reduction& reducer_mod_n()
const {
return m_mod_n; }
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;
72class RSA_Private_Data final {
74 RSA_Private_Data(BigInt&& d, BigInt&& p, BigInt&& q, BigInt&& d1, BigInt&& d2, BigInt&& c) :
83 m_c_monty(m_monty_p, m_c),
85 m_q_bits(m_q.bits()) {}
87 const BigInt& get_d()
const {
return m_d; }
89 const BigInt& get_p()
const {
return m_p; }
91 const BigInt& get_q()
const {
return m_q; }
93 const BigInt& get_d1()
const {
return m_d1; }
95 const BigInt& get_d2()
const {
return m_d2; }
97 const BigInt& get_c()
const {
return m_c; }
99 const Montgomery_Int& get_c_monty()
const {
return m_c_monty; }
101 const Montgomery_Params& monty_p()
const {
return m_monty_p; }
103 const Montgomery_Params& monty_q()
const {
return m_monty_q; }
105 size_t p_bits()
const {
return m_p_bits; }
107 size_t q_bits()
const {
return m_q_bits; }
109 bool primes_imbalanced()
const {
return p_bits() != q_bits(); }
119 const Montgomery_Params m_monty_p;
120 const Montgomery_Params m_monty_q;
121 Montgomery_Int m_c_monty;
133 }
else if(field ==
"e") {
141 return std::make_unique<RSA_PrivateKey>(rng,
m_public->public_modulus_bits(),
m_public->get_e().to_u32bit());
153 if(n.is_negative() || n.is_even() || n.bits() < 5 || e.is_negative() || e.is_even()) {
156 m_public = std::make_shared<RSA_Public_Data>(std::move(n), std::move(e));
164 init(std::move(n), std::move(e));
175 init(std::move(n), std::move(e));
179 return m_public->public_modulus_bits();
191 throw Not_Implemented(
"an RSA public key does not provide a raw binary representation.");
195 std::vector<uint8_t> output;
219 .
encode(
static_cast<size_t>(0))
233 return m_private->get_p();
237 return m_private->get_q();
241 return m_private->get_d();
245 return m_private->get_c();
249 return m_private->get_d1();
253 return m_private->get_d2();
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));
286 RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
302 const BigInt p_minus_1 = p - 1;
303 const BigInt q_minus_1 = q - 1;
306 const BigInt phi_n =
lcm(p_minus_1, q_minus_1);
316 RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
327 if(exp < 3 || exp % 2 == 0) {
331 const size_t p_bits = (bits + 1) / 2;
332 const size_t q_bits = bits - p_bits;
339 for(
size_t attempt = 0;; ++attempt) {
348 const BigInt diff = p - q;
349 if(diff.
bits() < (bits / 2) - 100) {
355 if(n.
bits() != bits) {
362 const BigInt p_minus_1 = p - 1;
363 const BigInt q_minus_1 = q - 1;
365 const BigInt phi_n =
lcm(p_minus_1, q_minus_1);
376 RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
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();
398 return std::make_unique<RSA_PublicKey>(
get_n(),
get_e());
431 const size_t prob = (strong) ? 128 : 12;
445#if defined(BOTAN_HAS_PSS) && defined(BOTAN_HAS_SHA_256)
446 const std::string padding =
"PSS(SHA-256)";
448 const std::string padding =
"Raw";
476 const size_t n_words = 2 * p_words;
514class RSA_Private_Operation {
516 size_t public_modulus_bits()
const {
return m_public->public_modulus_bits(); }
518 size_t public_modulus_bytes()
const {
return m_public->public_modulus_bytes(); }
520 explicit RSA_Private_Operation(
const RSA_PrivateKey& rsa, RandomNumberGenerator& rng) :
521 m_public(rsa.public_data()),
522 m_private(rsa.private_data()),
524 m_public->reducer_mod_n(),
526 [this](const BigInt& k) {
return m_public->public_op(k); },
529 m_max_d1_bits(m_private->p_bits() + m_blinding_bits),
530 m_max_d2_bits(m_private->q_bits() + m_blinding_bits) {}
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");
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");
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);
550 BigInt rsa_private_op(
const BigInt& m)
const {
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();
559 static constexpr size_t powm_window = 4;
562 const BigInt d1_mask(m_blinder.rng(), m_blinding_bits);
564#if defined(BOTAN_HAS_THREAD_UTILS) && !defined(BOTAN_HAS_VALGRIND)
565 #define BOTAN_RSA_USE_ASYNC
568#if defined(BOTAN_RSA_USE_ASYNC)
578 const BigInt masked_d1 = m_private->get_d1() + (d1_mask * (m_private->get_p() - 1));
580 auto j1 =
monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
582#if defined(BOTAN_RSA_USE_ASYNC)
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));
592#if defined(BOTAN_RSA_USE_ASYNC)
593 auto j1 = future_j1.get();
599 return crt_recombine(j1, j2_p, j2, m_private->get_c_monty(), m_private->get_p(), m_private->get_q());
602 std::shared_ptr<const RSA_Public_Data> m_public;
603 std::shared_ptr<const RSA_Private_Data> m_private;
607 const size_t m_blinding_bits;
608 const size_t m_max_d1_bits;
609 const size_t m_max_d2_bits;
613 private RSA_Private_Operation {
615 void update(std::span<const uint8_t> msg)
override { m_padding->
update(msg.data(), msg.size()); }
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);
622 std::vector<uint8_t> out(public_modulus_bytes());
627 size_t signature_length()
const override {
return public_modulus_bytes(); }
629 AlgorithmIdentifier algorithm_identifier()
const override;
631 std::string hash_function()
const override {
return m_padding->hash_function(); }
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)) {}
637 std::unique_ptr<SignaturePaddingScheme> m_padding;
641 const std::string padding_name = m_padding->name();
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&) {}
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);
654 throw Invalid_Argument(
fmt(
"Signatures using RSA/{} are not supported", padding_name));
657class RSA_Decryption_Operation final :
public PK_Ops::Decryption_with_EME,
658 private RSA_Private_Operation {
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) {}
663 size_t plaintext_length(
size_t )
const override {
return public_modulus_bytes(); }
665 secure_vector<uint8_t> raw_decrypt(std::span<const uint8_t> input)
override {
666 secure_vector<uint8_t> out(public_modulus_bytes());
672class RSA_KEM_Decryption_Operation final :
public PK_Ops::KEM_Decryption_with_KDF,
673 private RSA_Private_Operation {
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) {}
678 size_t raw_kem_shared_key_length()
const override {
return public_modulus_bytes(); }
680 size_t encapsulated_key_length()
const override {
return public_modulus_bytes(); }
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);
690class RSA_Public_Operation {
692 explicit RSA_Public_Operation(
const RSA_PublicKey& rsa) : m_public(rsa.public_data()) {}
694 size_t public_modulus_bits()
const {
return m_public->public_modulus_bits(); }
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");
702 return m_public->public_op(m);
705 size_t public_modulus_bytes()
const {
return m_public->public_modulus_bytes(); }
707 const BigInt& get_n()
const {
return m_public->get_n(); }
710 std::shared_ptr<const RSA_Public_Data> m_public;
713class RSA_Encryption_Operation final :
public PK_Ops::Encryption_with_EME,
714 private RSA_Public_Operation {
716 RSA_Encryption_Operation(
const RSA_PublicKey& rsa, std::string_view eme) :
717 PK_Ops::Encryption_with_EME(eme), RSA_Public_Operation(rsa) {}
719 size_t ciphertext_length(
size_t )
const override {
return public_modulus_bytes(); }
721 size_t max_ptext_input_bits()
const override {
return public_modulus_bits() - 1; }
723 std::vector<uint8_t> raw_encrypt(std::span<const uint8_t> input, RandomNumberGenerator& )
override {
724 BigInt input_bn(input);
725 return public_op(input_bn).serialize(public_modulus_bytes());
729class RSA_Verify_Operation final :
public PK_Ops::Verification,
730 private RSA_Public_Operation {
732 void update(std::span<const uint8_t> msg)
override { m_padding->update(msg.data(), msg.size()); }
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);
740 RSA_Verify_Operation(
const RSA_PublicKey& rsa, std::string_view padding) :
741 RSA_Public_Operation(rsa), m_padding(SignaturePaddingScheme::create_or_throw(padding)) {}
743 std::string hash_function()
const override {
return m_padding->hash_function(); }
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");
750 BigInt input_bn(input, input_len);
751 return public_op(input_bn).serialize();
754 std::unique_ptr<SignaturePaddingScheme> m_padding;
757class RSA_KEM_Encryption_Operation final :
public PK_Ops::KEM_Encryption_with_KDF,
758 private RSA_Public_Operation {
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) {}
764 size_t raw_kem_shared_key_length()
const override {
return public_modulus_bytes(); }
766 size_t encapsulated_key_length()
const override {
return public_modulus_bytes(); }
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);
774 c.serialize_to(out_encapsulated_key);
775 r.serialize_to(raw_shared_key);
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);
791 std::string_view provider)
const {
792 if(provider ==
"base" || provider.empty()) {
793 return std::make_unique<RSA_KEM_Encryption_Operation>(*
this, params);
799 std::string_view provider)
const {
800 if(provider ==
"base" || provider.empty()) {
801 return std::make_unique<RSA_Verify_Operation>(*
this, params);
812 if(sig_info.empty() || sig_info.size() != 2 || sig_info[0] !=
"RSA") {
813 throw Decoding_Error(
"Unknown AlgorithmIdentifier for RSA X.509 signatures");
816 std::string padding = sig_info[1];
818 if(padding ==
"PSS") {
821 throw Decoding_Error(
"PSS params must be provided");
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");
835 if(pss_params.mgf_function() !=
"MGF1") {
836 throw Decoding_Error(
"Unacceptable MGF for PSS signatures");
841 if(pss_params.hash_algid() != pss_params.mgf_hash_algid()) {
842 throw Decoding_Error(
"Unacceptable MGF hash for PSS signatures");
845 if(pss_params.trailer_field() != 1) {
846 throw Decoding_Error(
"Unacceptable trailer field for PSS signatures");
849 padding +=
fmt(
"({},MGF1,{})", hash_algo, pss_params.salt_length());
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));
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);
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);
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);
#define BOTAN_ASSERT_NOMSG(expr)
#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 _from_words(secure_vector< word > &words)
static BigInt from_u64(uint64_t n)
const word * _data() const
secure_vector< uint8_t > get_contents()
DER_Encoder & start_sequence()
DER_Encoder & encode(bool b)
static Montgomery_Int from_wide_int(const Montgomery_Params ¶ms, const BigInt &x)
const secure_vector< word > & repr() const
std::string to_formatted_string() const
virtual void update(std::span< const uint8_t > input)=0
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 strong) 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
bool check_key(RandomNumberGenerator &rng, bool strong) 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
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const override
std::vector< uint8_t > raw_public_key_bits() 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
auto run(F &&f, Args &&... args) -> std::future< std::invoke_result_t< F, Args... > >
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)
BigInt inverse_mod_secret_prime(const BigInt &x, const BigInt &p)
constexpr auto bigint_add2(W x[], size_t x_size, const W y[], size_t y_size) -> W
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)
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)
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)
BigInt ct_modulo(const BigInt &x, const BigInt &y)
BigInt compute_rsa_secret_exponent(const BigInt &e, const BigInt &phi_n, const BigInt &p, const BigInt &q)
BigInt generate_rsa_prime(RandomNumberGenerator &keygen_rng, RandomNumberGenerator &prime_test_rng, size_t bits, const BigInt &coprime, size_t prob)
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
BigInt inverse_mod_rsa_public_modulus(const BigInt &x, const BigInt &n)
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
Montgomery_Int monty_exp(const Montgomery_Params ¶ms_p, const BigInt &g, const BigInt &k, size_t max_k_bits)