Botan
1.11.15
|
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 }