1// rsa.cpp - written and placed in the public domain by Wei Dai 2 3#include "pch.h" 4#include "rsa.h" 5#include "asn.h" 6#include "oids.h" 7#include "modarith.h" 8#include "nbtheory.h" 9#include "sha.h" 10#include "algparam.h" 11#include "fips140.h" 12 13#if !defined(NDEBUG) && !defined(CRYPTOPP_IS_DLL) 14#include "pssr.h" 15NAMESPACE_BEGIN(CryptoPP) 16void RSA_TestInstantiations() 17{ 18 RSASS<PKCS1v15, SHA>::Verifier x1(1, 1); 19 RSASS<PKCS1v15, SHA>::Signer x2(NullRNG(), 1); 20 RSASS<PKCS1v15, SHA>::Verifier x3(x2); 21 RSASS<PKCS1v15, SHA>::Verifier x4(x2.GetKey()); 22 RSASS<PSS, SHA>::Verifier x5(x3); 23#ifndef __MWERKS__ 24 RSASS<PSSR, SHA>::Signer x6 = x2; 25 x3 = x2; 26 x6 = x2; 27#endif 28 RSAES<PKCS1v15>::Encryptor x7(x2); 29#ifndef __GNUC__ 30 RSAES<PKCS1v15>::Encryptor x8(x3); 31#endif 32 RSAES<OAEP<SHA> >::Encryptor x9(x2); 33 34 x4 = x2.GetKey(); 35} 36NAMESPACE_END 37#endif 38 39#ifndef CRYPTOPP_IMPORTS 40 41NAMESPACE_BEGIN(CryptoPP) 42 43OID RSAFunction::GetAlgorithmID() const 44{ 45 return ASN1::rsaEncryption(); 46} 47 48void RSAFunction::BERDecodePublicKey(BufferedTransformation &bt, bool, size_t) 49{ 50 BERSequenceDecoder seq(bt); 51 m_n.BERDecode(seq); 52 m_e.BERDecode(seq); 53 seq.MessageEnd(); 54} 55 56void RSAFunction::DEREncodePublicKey(BufferedTransformation &bt) const 57{ 58 DERSequenceEncoder seq(bt); 59 m_n.DEREncode(seq); 60 m_e.DEREncode(seq); 61 seq.MessageEnd(); 62} 63 64Integer RSAFunction::ApplyFunction(const Integer &x) const 65{ 66 DoQuickSanityCheck(); 67 return a_exp_b_mod_c(x, m_e, m_n); 68} 69 70bool RSAFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const 71{ 72 bool pass = true; 73 pass = pass && m_n > Integer::One() && m_n.IsOdd(); 74 pass = pass && m_e > Integer::One() && m_e.IsOdd() && m_e < m_n; 75 return pass; 76} 77 78bool RSAFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const 79{ 80 return GetValueHelper(this, name, valueType, pValue).Assignable() 81 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus) 82 CRYPTOPP_GET_FUNCTION_ENTRY(PublicExponent) 83 ; 84} 85 86void RSAFunction::AssignFrom(const NameValuePairs &source) 87{ 88 AssignFromHelper(this, source) 89 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus) 90 CRYPTOPP_SET_FUNCTION_ENTRY(PublicExponent) 91 ; 92} 93 94// ***************************************************************************** 95 96class RSAPrimeSelector : public PrimeSelector 97{ 98public: 99 RSAPrimeSelector(const Integer &e) : m_e(e) {} 100 bool IsAcceptable(const Integer &candidate) const {return RelativelyPrime(m_e, candidate-Integer::One());} 101 Integer m_e; 102}; 103 104void InvertibleRSAFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg) 105{ 106 int modulusSize = 2048; 107 alg.GetIntValue(Name::ModulusSize(), modulusSize) || alg.GetIntValue(Name::KeySize(), modulusSize); 108 109 if (modulusSize < 16) 110 throw InvalidArgument("InvertibleRSAFunction: specified modulus size is too small"); 111 112 m_e = alg.GetValueWithDefault(Name::PublicExponent(), Integer(17)); 113 114 if (m_e < 3 || m_e.IsEven()) 115 throw InvalidArgument("InvertibleRSAFunction: invalid public exponent"); 116 117 RSAPrimeSelector selector(m_e); 118 AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize) 119 (Name::PointerToPrimeSelector(), selector.GetSelectorPointer()); 120 m_p.GenerateRandom(rng, primeParam); 121 m_q.GenerateRandom(rng, primeParam); 122 123 m_d = m_e.InverseMod(LCM(m_p-1, m_q-1)); 124 assert(m_d.IsPositive()); 125 126 m_dp = m_d % (m_p-1); 127 m_dq = m_d % (m_q-1); 128 m_n = m_p * m_q; 129 m_u = m_q.InverseMod(m_p); 130 131 if (FIPS_140_2_ComplianceEnabled()) 132 { 133 RSASS<PKCS1v15, SHA>::Signer signer(*this); 134 RSASS<PKCS1v15, SHA>::Verifier verifier(signer); 135 SignaturePairwiseConsistencyTest_FIPS_140_Only(signer, verifier); 136 137 RSAES<OAEP<SHA> >::Decryptor decryptor(*this); 138 RSAES<OAEP<SHA> >::Encryptor encryptor(decryptor); 139 EncryptionPairwiseConsistencyTest_FIPS_140_Only(encryptor, decryptor); 140 } 141} 142 143void InvertibleRSAFunction::Initialize(RandomNumberGenerator &rng, unsigned int keybits, const Integer &e) 144{ 145 GenerateRandom(rng, MakeParameters(Name::ModulusSize(), (int)keybits)(Name::PublicExponent(), e+e.IsEven())); 146} 147 148void InvertibleRSAFunction::Initialize(const Integer &n, const Integer &e, const Integer &d) 149{ 150 if (n.IsEven() || e.IsEven() | d.IsEven()) 151 throw InvalidArgument("InvertibleRSAFunction: input is not a valid RSA private key"); 152 153 m_n = n; 154 m_e = e; 155 m_d = d; 156 157 Integer r = --(d*e); 158 unsigned int s = 0; 159 while (r.IsEven()) 160 { 161 r >>= 1; 162 s++; 163 } 164 165 ModularArithmetic modn(n); 166 for (Integer i = 2; ; ++i) 167 { 168 Integer a = modn.Exponentiate(i, r); 169 if (a == 1) 170 continue; 171 Integer b; 172 unsigned int j = 0; 173 while (a != n-1) 174 { 175 b = modn.Square(a); 176 if (b == 1) 177 { 178 m_p = GCD(a-1, n); 179 m_q = n/m_p; 180 m_dp = m_d % (m_p-1); 181 m_dq = m_d % (m_q-1); 182 m_u = m_q.InverseMod(m_p); 183 return; 184 } 185 if (++j == s) 186 throw InvalidArgument("InvertibleRSAFunction: input is not a valid RSA private key"); 187 a = b; 188 } 189 } 190} 191 192void InvertibleRSAFunction::BERDecodePrivateKey(BufferedTransformation &bt, bool, size_t) 193{ 194 BERSequenceDecoder privateKey(bt); 195 word32 version; 196 BERDecodeUnsigned<word32>(privateKey, version, INTEGER, 0, 0); // check version 197 m_n.BERDecode(privateKey); 198 m_e.BERDecode(privateKey); 199 m_d.BERDecode(privateKey); 200 m_p.BERDecode(privateKey); 201 m_q.BERDecode(privateKey); 202 m_dp.BERDecode(privateKey); 203 m_dq.BERDecode(privateKey); 204 m_u.BERDecode(privateKey); 205 privateKey.MessageEnd(); 206} 207 208void InvertibleRSAFunction::DEREncodePrivateKey(BufferedTransformation &bt) const 209{ 210 DERSequenceEncoder privateKey(bt); 211 DEREncodeUnsigned<word32>(privateKey, 0); // version 212 m_n.DEREncode(privateKey); 213 m_e.DEREncode(privateKey); 214 m_d.DEREncode(privateKey); 215 m_p.DEREncode(privateKey); 216 m_q.DEREncode(privateKey); 217 m_dp.DEREncode(privateKey); 218 m_dq.DEREncode(privateKey); 219 m_u.DEREncode(privateKey); 220 privateKey.MessageEnd(); 221} 222 223Integer InvertibleRSAFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const 224{ 225 DoQuickSanityCheck(); 226 ModularArithmetic modn(m_n); 227 Integer r, rInv; 228 do { // do this in a loop for people using small numbers for testing 229 r.Randomize(rng, Integer::One(), m_n - Integer::One()); 230 rInv = modn.MultiplicativeInverse(r); 231 } while (rInv.IsZero()); 232 Integer re = modn.Exponentiate(r, m_e); 233 re = modn.Multiply(re, x); // blind 234 // here we follow the notation of PKCS #1 and let u=q inverse mod p 235 // but in ModRoot, u=p inverse mod q, so we reverse the order of p and q 236 Integer y = ModularRoot(re, m_dq, m_dp, m_q, m_p, m_u); 237 y = modn.Multiply(y, rInv); // unblind 238 if (modn.Exponentiate(y, m_e) != x) // check 239 throw Exception(Exception::OTHER_ERROR, "InvertibleRSAFunction: computational error during private key operation"); 240 return y; 241} 242 243bool InvertibleRSAFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const 244{ 245 bool pass = RSAFunction::Validate(rng, level); 246 pass = pass && m_p > Integer::One() && m_p.IsOdd() && m_p < m_n; 247 pass = pass && m_q > Integer::One() && m_q.IsOdd() && m_q < m_n; 248 pass = pass && m_d > Integer::One() && m_d.IsOdd() && m_d < m_n; 249 pass = pass && m_dp > Integer::One() && m_dp.IsOdd() && m_dp < m_p; 250 pass = pass && m_dq > Integer::One() && m_dq.IsOdd() && m_dq < m_q; 251 pass = pass && m_u.IsPositive() && m_u < m_p; 252 if (level >= 1) 253 { 254 pass = pass && m_p * m_q == m_n; 255 pass = pass && m_e*m_d % LCM(m_p-1, m_q-1) == 1; 256 pass = pass && m_dp == m_d%(m_p-1) && m_dq == m_d%(m_q-1); 257 pass = pass && m_u * m_q % m_p == 1; 258 } 259 if (level >= 2) 260 pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2); 261 return pass; 262} 263 264bool InvertibleRSAFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const 265{ 266 return GetValueHelper<RSAFunction>(this, name, valueType, pValue).Assignable() 267 CRYPTOPP_GET_FUNCTION_ENTRY(Prime1) 268 CRYPTOPP_GET_FUNCTION_ENTRY(Prime2) 269 CRYPTOPP_GET_FUNCTION_ENTRY(PrivateExponent) 270 CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime1PrivateExponent) 271 CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime2PrivateExponent) 272 CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1) 273 ; 274} 275 276void InvertibleRSAFunction::AssignFrom(const NameValuePairs &source) 277{ 278 AssignFromHelper<RSAFunction>(this, source) 279 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1) 280 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2) 281 CRYPTOPP_SET_FUNCTION_ENTRY(PrivateExponent) 282 CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime1PrivateExponent) 283 CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime2PrivateExponent) 284 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1) 285 ; 286} 287 288// ***************************************************************************** 289 290Integer RSAFunction_ISO::ApplyFunction(const Integer &x) const 291{ 292 Integer t = RSAFunction::ApplyFunction(x); 293 return t % 16 == 12 ? t : m_n - t; 294} 295 296Integer InvertibleRSAFunction_ISO::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const 297{ 298 Integer t = InvertibleRSAFunction::CalculateInverse(rng, x); 299 return STDMIN(t, m_n-t); 300} 301 302NAMESPACE_END 303 304#endif 305