Botan  1.11.15
src/lib/pubkey/rsa/rsa.cpp
Go to the documentation of this file.
00001 /*
00002 * RSA
00003 * (C) 1999-2010 Jack Lloyd
00004 *
00005 * Botan is released under the Simplified BSD License (see license.txt)
00006 */
00007 
00008 #include <botan/internal/pk_utils.h>
00009 #include <botan/rsa.h>
00010 #include <botan/parsing.h>
00011 #include <botan/keypair.h>
00012 #include <botan/blinding.h>
00013 #include <botan/reducer.h>
00014 #include <future>
00015 
00016 namespace Botan {
00017 
00018 /*
00019 * Create a RSA private key
00020 */
00021 RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng,
00022                                size_t bits, size_t exp)
00023    {
00024    if(bits < 1024)
00025       throw Invalid_Argument(algo_name() + ": Can't make a key that is only " +
00026                              std::to_string(bits) + " bits long");
00027    if(exp < 3 || exp % 2 == 0)
00028       throw Invalid_Argument(algo_name() + ": Invalid encryption exponent");
00029 
00030    e = exp;
00031 
00032    do
00033       {
00034       p = random_prime(rng, (bits + 1) / 2, e);
00035       q = random_prime(rng, bits - p.bits(), e);
00036       n = p * q;
00037       } while(n.bits() != bits);
00038 
00039    d = inverse_mod(e, lcm(p - 1, q - 1));
00040    d1 = d % (p - 1);
00041    d2 = d % (q - 1);
00042    c = inverse_mod(q, p);
00043 
00044    gen_check(rng);
00045    }
00046 
00047 /*
00048 * Check Private RSA Parameters
00049 */
00050 bool RSA_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const
00051    {
00052    if(!IF_Scheme_PrivateKey::check_key(rng, strong))
00053       return false;
00054 
00055    if(!strong)
00056       return true;
00057 
00058    if((e * d) % lcm(p - 1, q - 1) != 1)
00059       return false;
00060 
00061    return KeyPair::signature_consistency_check(rng, *this, "EMSA4(SHA-1)");
00062    }
00063 
00064 namespace {
00065 
00066 /**
00067 * RSA private (decrypt/sign) operation
00068 */
00069 class RSA_Private_Operation
00070    {
00071    protected:
00072       size_t get_max_input_bits() const { return (n.bits() - 1); }
00073 
00074       RSA_Private_Operation(const RSA_PrivateKey& rsa) :
00075          n(rsa.get_n()),
00076          q(rsa.get_q()),
00077          c(rsa.get_c()),
00078          m_powermod_e_n(rsa.get_e(), rsa.get_n()),
00079          m_powermod_d1_p(rsa.get_d1(), rsa.get_p()),
00080          m_powermod_d2_q(rsa.get_d2(), rsa.get_q()),
00081          m_mod_p(rsa.get_p()),
00082          m_blinder(n,
00083                    [this](const BigInt& k) { return m_powermod_e_n(k); },
00084                    [this](const BigInt& k) { return inverse_mod(k, n); })
00085          {
00086          }
00087 
00088       BigInt blinded_private_op(const BigInt& m) const
00089          {
00090          return m_blinder.unblind(private_op(m_blinder.blind(m)));
00091          }
00092 
00093       BigInt private_op(const BigInt& m) const
00094          {
00095          if(m >= n)
00096             throw Invalid_Argument("RSA private op - input is too large");
00097 
00098          auto future_j1 = std::async(std::launch::async, m_powermod_d1_p, m);
00099          BigInt j2 = m_powermod_d2_q(m);
00100          BigInt j1 = future_j1.get();
00101 
00102          j1 = m_mod_p.reduce(sub_mul(j1, j2, c));
00103 
00104          return mul_add(j1, q, j2);
00105          }
00106 
00107       const BigInt& n;
00108       const BigInt& q;
00109       const BigInt& c;
00110       Fixed_Exponent_Power_Mod m_powermod_e_n, m_powermod_d1_p, m_powermod_d2_q;
00111       Modular_Reducer m_mod_p;
00112       Blinder m_blinder;
00113    };
00114 
00115 class RSA_Signature_Operation : public PK_Ops::Signature,
00116                                 private RSA_Private_Operation
00117    {
00118    public:
00119       typedef RSA_PrivateKey Key_Type;
00120 
00121       size_t max_input_bits() const override { return get_max_input_bits(); };
00122 
00123       RSA_Signature_Operation(const RSA_PrivateKey& rsa, const std::string&) :
00124          RSA_Private_Operation(rsa)
00125          {
00126          }
00127 
00128       secure_vector<byte> sign(const byte msg[], size_t msg_len,
00129                               RandomNumberGenerator&) override
00130          {
00131          /* We don't check signatures against powermod_e_n here because
00132          PK_Signer checks verification consistency for all signature
00133          algorithms.
00134          */
00135          const BigInt m(msg, msg_len);
00136          const BigInt x = blinded_private_op(m);
00137          return BigInt::encode_1363(x, n.bytes());
00138          }
00139    };
00140 
00141 class RSA_Decryption_Operation : public PK_Ops::Decryption,
00142                                  private RSA_Private_Operation
00143    {
00144    public:
00145       typedef RSA_PrivateKey Key_Type;
00146 
00147       size_t max_input_bits() const override { return get_max_input_bits(); };
00148 
00149       RSA_Decryption_Operation(const RSA_PrivateKey& rsa, const std::string&) :
00150          RSA_Private_Operation(rsa)
00151          {
00152          }
00153 
00154       secure_vector<byte> decrypt(const byte msg[], size_t msg_len) override
00155          {
00156          const BigInt m(msg, msg_len);
00157          const BigInt x = blinded_private_op(m);
00158          BOTAN_ASSERT(m == m_powermod_e_n(x), "RSA decrypt consistency check");
00159          return BigInt::encode_locked(x);
00160          }
00161    };
00162 
00163 
00164 /**
00165 * RSA public (encrypt/verify) operation
00166 */
00167 class RSA_Public_Operation
00168    {
00169    public:
00170       RSA_Public_Operation(const RSA_PublicKey& rsa) :
00171          n(rsa.get_n()), powermod_e_n(rsa.get_e(), rsa.get_n())
00172          {}
00173 
00174       size_t get_max_input_bits() const { return (n.bits() - 1); }
00175 
00176    protected:
00177       BigInt public_op(const BigInt& m) const
00178          {
00179          if(m >= n)
00180             throw Invalid_Argument("RSA public op - input is too large");
00181          return powermod_e_n(m);
00182          }
00183 
00184       const BigInt& n;
00185       Fixed_Exponent_Power_Mod powermod_e_n;
00186    };
00187 
00188 class RSA_Encryption_Operation : public PK_Ops::Encryption,
00189                                  private RSA_Public_Operation
00190    {
00191    public:
00192       typedef RSA_PublicKey Key_Type;
00193 
00194       RSA_Encryption_Operation(const RSA_PublicKey& rsa, const std::string&) :
00195          RSA_Public_Operation(rsa)
00196          {
00197          }
00198 
00199       size_t max_input_bits() const override { return get_max_input_bits(); };
00200 
00201       secure_vector<byte> encrypt(const byte msg[], size_t msg_len,
00202                                   RandomNumberGenerator&)
00203          {
00204          BigInt m(msg, msg_len);
00205          return BigInt::encode_1363(public_op(m), n.bytes());
00206          }
00207    };
00208 
00209 class RSA_Verify_Operation : public PK_Ops::Verification,
00210                              private RSA_Public_Operation
00211    {
00212    public:
00213       typedef RSA_PublicKey Key_Type;
00214 
00215       size_t max_input_bits() const override { return get_max_input_bits(); };
00216 
00217       RSA_Verify_Operation(const RSA_PublicKey& rsa, const std::string&) :
00218          RSA_Public_Operation(rsa)
00219          {
00220          }
00221 
00222       bool with_recovery() const override { return true; }
00223 
00224       secure_vector<byte> verify_mr(const byte msg[], size_t msg_len) override
00225          {
00226          BigInt m(msg, msg_len);
00227          return BigInt::encode_locked(public_op(m));
00228          }
00229    };
00230 
00231 BOTAN_REGISTER_PK_ENCRYPTION_OP("RSA", RSA_Encryption_Operation);
00232 BOTAN_REGISTER_PK_DECRYPTION_OP("RSA", RSA_Decryption_Operation);
00233 BOTAN_REGISTER_PK_SIGNATURE_OP("RSA", RSA_Signature_Operation);
00234 BOTAN_REGISTER_PK_VERIFY_OP("RSA", RSA_Verify_Operation);
00235 
00236 }
00237 
00238 }