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>
20#if defined(BOTAN_HAS_THREAD_UTILS)
21 #include <botan/internal/thread_pool.h>
26class RSA_Public_Data
final
29 RSA_Public_Data(BigInt&& n, BigInt&& 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())
37 BigInt public_op(
const BigInt& m)
const
39 const size_t powm_window = 1;
44 const BigInt& get_n()
const {
return m_n; }
45 const BigInt& get_e()
const {
return m_e; }
46 size_t public_modulus_bits()
const {
return m_public_modulus_bits; }
47 size_t public_modulus_bytes()
const {
return m_public_modulus_bytes; }
52 std::shared_ptr<const Montgomery_Params> m_monty_n;
53 size_t m_public_modulus_bits;
54 size_t m_public_modulus_bytes;
57class RSA_Private_Data
final
60 RSA_Private_Data(BigInt&& d, BigInt&& p, BigInt&& q,
61 BigInt&& d1, BigInt&& d2, BigInt&& c) :
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)),
76 const BigInt& get_d()
const {
return m_d; }
77 const BigInt& get_p()
const {
return m_p; }
78 const BigInt& get_q()
const {
return m_q; }
79 const BigInt& get_d1()
const {
return m_d1; }
80 const BigInt& get_d2()
const {
return m_d2; }
81 const BigInt& get_c()
const {
return m_c; }
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;
109 if(n.is_negative() || n.is_even() || n.bits() < 5 || e.is_negative() || e.is_even())
111 m_public = std::make_shared<RSA_Public_Data>(std::move(n), std::move(e));
115 const std::vector<uint8_t>& key_bits)
124 init(std::move(n), std::move(e));
131 init(std::move(n), std::move(e));
136 return m_public->public_modulus_bits();
151 std::vector<uint8_t> output;
180 .
encode(
static_cast<size_t>(0))
203 m_private = std::make_shared<RSA_Private_Data>(
204 std::move(d), std::move(p), std::move(q), std::move(d1), std::move(d2), std::move(c));
210 BigInt n, e, d, p, q, d1, d2, c;
227 RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q),
228 std::move(d1), std::move(d2), std::move(c));
247 const BigInt p_minus_1 = p - 1;
248 const BigInt q_minus_1 = q - 1;
252 const BigInt phi_n =
lcm(p_minus_1, q_minus_1);
262 RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q),
263 std::move(d1), std::move(d2), std::move(c));
270 size_t bits,
size_t exp)
275 if(exp < 3 || exp % 2 == 0)
278 BigInt n, e, d, p, q, d1, d2, c;
282 const size_t p_bits = (bits + 1) / 2;
283 const size_t q_bits = bits - p_bits;
285 for(
size_t attempt = 0; ; ++attempt)
294 const BigInt diff = p - q;
295 if(diff.
bits() < (bits/2) - 100)
306 const BigInt p_minus_1 = p - 1;
307 const BigInt q_minus_1 = q - 1;
309 const BigInt phi_n =
lcm(p_minus_1, q_minus_1);
319 RSA_PrivateKey::init(std::move(d), std::move(p), std::move(q),
320 std::move(d1), std::move(d2), std::move(c));
325 return std::make_unique<RSA_PublicKey>(
get_n(),
get_e());
352 const size_t prob = (strong) ? 128 : 12;
375class RSA_Private_Operation
378 size_t public_modulus_bits()
const {
return m_public->public_modulus_bits(); }
379 size_t public_modulus_bytes()
const {
return m_public->public_modulus_bytes(); }
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 [this](const BigInt& k) {
return m_public->public_op(k); },
386 [
this](
const BigInt& k) {
return inverse_mod(k, m_public->get_n()); }),
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)
393 secure_vector<uint8_t> raw_op(
const uint8_t input[],
size_t input_len)
395 const BigInt input_bn(input, input_len);
396 if(input_bn >= m_public->get_n())
397 throw Invalid_Argument(
"RSA private op - input is too large");
402 const BigInt recovered = m_blinder.unblind(rsa_private_op(m_blinder.blind(input_bn)));
403 BOTAN_ASSERT(input_bn == m_public->public_op(recovered),
"RSA consistency check");
409 BigInt rsa_private_op(
const BigInt& m)
const
417 static constexpr size_t powm_window = 4;
420 const BigInt d1_mask(m_blinder.rng(), m_blinding_bits);
422#if defined(BOTAN_HAS_THREAD_UTILS) && !defined(BOTAN_HAS_VALGRIND)
423 #define BOTAN_RSA_USE_ASYNC
426#if defined(BOTAN_RSA_USE_ASYNC)
436 const BigInt masked_d1 = m_private->get_d1() + (d1_mask * (m_private->get_p() - 1));
437 auto powm_d1_p =
monty_precompute(m_private->m_monty_p, m_private->m_mod_p.reduce(m), powm_window);
438 BigInt j1 =
monty_execute(*powm_d1_p, masked_d1, m_max_d1_bits);
440#if defined(BOTAN_RSA_USE_ASYNC)
445 const BigInt d2_mask(m_blinder.rng(), m_blinding_bits);
446 const BigInt masked_d2 = m_private->get_d2() + (d2_mask * (m_private->get_q() - 1));
447 auto powm_d2_q =
monty_precompute(m_private->m_monty_q, m_private->m_mod_q.reduce(m), powm_window);
448 const BigInt j2 =
monty_execute(*powm_d2_q, masked_d2, m_max_d2_bits);
450#if defined(BOTAN_RSA_USE_ASYNC)
451 BigInt j1 = future_j1.get();
467 j1 = m_private->m_mod_p.multiply(m_private->m_mod_p.reduce((m_private->get_p() + j1) - j2), m_private->get_c());
468 return j1*m_private->get_q() + j2;
471 std::shared_ptr<const RSA_Public_Data> m_public;
472 std::shared_ptr<const RSA_Private_Data> m_private;
476 const size_t m_blinding_bits;
477 const size_t m_max_d1_bits;
478 const size_t m_max_d2_bits;
481class RSA_Signature_Operation
final :
public PK_Ops::Signature_with_EMSA,
482 private RSA_Private_Operation
485 size_t max_input_bits()
const override {
return public_modulus_bits() - 1; }
487 size_t signature_length()
const override {
return public_modulus_bytes(); }
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)
495 secure_vector<uint8_t> raw_sign(
const uint8_t input[],
size_t input_len,
496 RandomNumberGenerator& )
override
498 return raw_op(input, input_len);
502class RSA_Decryption_Operation
final :
public PK_Ops::Decryption_with_EME,
503 private RSA_Private_Operation
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)
513 size_t plaintext_length(
size_t )
const override {
return public_modulus_bytes(); }
515 secure_vector<uint8_t> raw_decrypt(
const uint8_t input[],
size_t input_len)
override
517 return raw_op(input, input_len);
521class RSA_KEM_Decryption_Operation
final :
public PK_Ops::KEM_Decryption_with_KDF,
522 private RSA_Private_Operation
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)
533 secure_vector<uint8_t>
534 raw_kem_decrypt(
const uint8_t encap_key[],
size_t len)
override
536 return raw_op(encap_key, len);
543class RSA_Public_Operation
546 explicit RSA_Public_Operation(
const RSA_PublicKey& rsa) :
547 m_public(rsa.public_data())
550 size_t get_max_input_bits()
const
552 const size_t n_bits = m_public->public_modulus_bits();
564 BigInt public_op(
const BigInt& m)
const
566 if(m >= m_public->get_n())
567 throw Invalid_Argument(
"RSA public op - input is too large");
569 return m_public->public_op(m);
572 size_t public_modulus_bytes()
const {
return m_public->public_modulus_bytes(); }
574 const BigInt& get_n()
const {
return m_public->get_n(); }
576 std::shared_ptr<const RSA_Public_Data> m_public;
579class RSA_Encryption_Operation
final :
public PK_Ops::Encryption_with_EME,
580 private RSA_Public_Operation
584 RSA_Encryption_Operation(
const RSA_PublicKey& rsa,
const std::string& eme) :
585 PK_Ops::Encryption_with_EME(eme),
586 RSA_Public_Operation(rsa)
590 size_t ciphertext_length(
size_t )
const override {
return public_modulus_bytes(); }
592 size_t max_raw_input_bits()
const override {
return get_max_input_bits(); }
594 secure_vector<uint8_t> raw_encrypt(
const uint8_t input[],
size_t input_len,
595 RandomNumberGenerator& )
override
597 BigInt input_bn(input, input_len);
602class RSA_Verify_Operation
final :
public PK_Ops::Verification_with_EMSA,
603 private RSA_Public_Operation
607 size_t max_input_bits()
const override {
return get_max_input_bits(); }
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)
615 bool with_recovery()
const override {
return true; }
617 secure_vector<uint8_t> verify_mr(
const uint8_t input[],
size_t input_len)
override
619 BigInt input_bn(input, input_len);
624class RSA_KEM_Encryption_Operation
final :
public PK_Ops::KEM_Encryption_with_KDF,
625 private RSA_Public_Operation
629 RSA_KEM_Encryption_Operation(
const RSA_PublicKey& key,
630 const std::string& kdf) :
631 PK_Ops::KEM_Encryption_with_KDF(kdf),
632 RSA_Public_Operation(key) {}
635 void raw_kem_encrypt(secure_vector<uint8_t>& out_encapsulated_key,
636 secure_vector<uint8_t>& raw_shared_key,
640 const BigInt c = public_op(r);
649std::unique_ptr<PK_Ops::Encryption>
651 const std::string& params,
652 const std::string& provider)
const
654 if(provider ==
"base" || provider.empty())
655 return std::make_unique<RSA_Encryption_Operation>(*
this, params);
659std::unique_ptr<PK_Ops::KEM_Encryption>
661 const std::string& params,
662 const std::string& provider)
const
664 if(provider ==
"base" || provider.empty())
665 return std::make_unique<RSA_KEM_Encryption_Operation>(*
this, params);
669std::unique_ptr<PK_Ops::Verification>
671 const std::string& provider)
const
673 if(provider ==
"base" || provider.empty())
674 return std::make_unique<RSA_Verify_Operation>(*
this, params);
679std::unique_ptr<PK_Ops::Decryption>
681 const std::string& params,
682 const std::string& provider)
const
684 if(provider ==
"base" || provider.empty())
685 return std::make_unique<RSA_Decryption_Operation>(*
this, params, rng);
690std::unique_ptr<PK_Ops::KEM_Decryption>
692 const std::string& params,
693 const std::string& provider)
const
695 if(provider ==
"base" || provider.empty())
696 return std::make_unique<RSA_KEM_Decryption_Operation>(*
this, params, rng);
701std::unique_ptr<PK_Ops::Signature>
703 const std::string& params,
704 const std::string& provider)
const
706 if(provider ==
"base" || provider.empty())
707 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)
BER_Decoder & decode(bool &out)
BER_Decoder & decode_and_check(const T &expected, const std::string &error_msg)
BER_Decoder start_sequence()
static BigInt random_integer(RandomNumberGenerator &rng, const BigInt &min, const BigInt &max)
static secure_vector< uint8_t > encode_locked(const BigInt &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)
virtual OID get_oid() const
std::unique_ptr< PK_Ops::Decryption > create_decryption_op(RandomNumberGenerator &rng, const std::string ¶ms, const std::string &provider) const override
const BigInt & get_q() const
std::shared_ptr< const RSA_Private_Data > private_data() const
const BigInt & get_c() const
std::unique_ptr< PK_Ops::Signature > create_signature_op(RandomNumberGenerator &rng, const std::string ¶ms, const std::string &provider) const override
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
RSA_PrivateKey(const AlgorithmIdentifier &alg_id, const secure_vector< uint8_t > &key_bits)
std::unique_ptr< Public_Key > public_key() const override
std::unique_ptr< PK_Ops::KEM_Decryption > create_kem_decryption_op(RandomNumberGenerator &rng, const std::string ¶ms, const std::string &provider) const override
const BigInt & get_d1() const
std::unique_ptr< PK_Ops::KEM_Encryption > create_kem_encryption_op(RandomNumberGenerator &rng, const std::string ¶ms, const std::string &provider) const override
void init(BigInt &&n, BigInt &&e)
size_t key_length() const override
std::string algo_name() const override
std::unique_ptr< PK_Ops::Verification > create_verification_op(const std::string ¶ms, const std::string &provider) const override
std::unique_ptr< PK_Ops::Encryption > create_encryption_op(RandomNumberGenerator &rng, const std::string ¶ms, const std::string &provider) const override
const BigInt & get_n() const
size_t estimated_strength() 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 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(* final)(unsigned char *, CTX *)
std::string to_string(const BER_Object &obj)
bool signature_consistency_check(RandomNumberGenerator &rng, const Private_Key &private_key, const Public_Key &public_key, const std::string &padding)
secure_vector< uint8_t > decode(DataSource &source, std::string &label)
BigInt lcm(const BigInt &a, const BigInt &b)
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)