Main Page | Namespace List | Class Hierarchy | Alphabetical List | Compound List | File List | Namespace Members | Compound Members | File Members

rsa.cpp

00001 // rsa.cpp - written and placed in the public domain by Wei Dai
00002 
00003 #include "pch.h"
00004 #include "rsa.h"
00005 #include "asn.h"
00006 #include "oids.h"
00007 #include "modarith.h"
00008 #include "nbtheory.h"
00009 #include "sha.h"
00010 #include "algparam.h"
00011 #include "fips140.h"
00012 #include "randpool.h"
00013 
00014 NAMESPACE_BEGIN(CryptoPP)
00015 
00016 byte OAEP_P_DEFAULT[1];
00017 
00018 #ifndef NDEBUG
00019 void RSA_TestInstantiations()
00020 {
00021         RSASSA<PKCS1v15, SHA>::Verifier x1(1, 1);
00022         RSASSA<PKCS1v15, SHA>::Signer x2(NullRNG(), 1);
00023         RSASSA<PKCS1v15, SHA>::Verifier x3(x2);
00024         RSASSA<PKCS1v15, SHA>::Verifier x4(x2.GetKey());
00025         RSASSA<PKCS1v15, SHA>::Verifier x5(x3);
00026         RSASSA<PKCS1v15, SHA>::Signer x6 = x2;
00027         RSAES<PKCS1v15>::Encryptor x7(x2);
00028         RSAES<PKCS1v15>::Encryptor x8(x3);
00029         RSAES<OAEP<SHA> >::Encryptor x9(x2);
00030 
00031         x6 = x2;
00032 #ifndef __MWERKS__
00033         x3 = x2;
00034 #endif
00035         x4 = x2.GetKey();
00036 }
00037 #endif
00038 
00039 #ifndef CRYPTOPP_IMPORTS
00040 
00041 OID RSAFunction::GetAlgorithmID() const
00042 {
00043         return ASN1::rsaEncryption();
00044 }
00045 
00046 void RSAFunction::BERDecodeKey(BufferedTransformation &bt)
00047 {
00048         BERSequenceDecoder seq(bt);
00049                 m_n.BERDecode(seq);
00050                 m_e.BERDecode(seq);
00051         seq.MessageEnd();
00052 }
00053 
00054 void RSAFunction::DEREncodeKey(BufferedTransformation &bt) const
00055 {
00056         DERSequenceEncoder seq(bt);
00057                 m_n.DEREncode(seq);
00058                 m_e.DEREncode(seq);
00059         seq.MessageEnd();
00060 }
00061 
00062 Integer RSAFunction::ApplyFunction(const Integer &x) const
00063 {
00064         DoQuickSanityCheck();
00065         return a_exp_b_mod_c(x, m_e, m_n);
00066 }
00067 
00068 bool RSAFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
00069 {
00070         bool pass = true;
00071         pass = pass && m_n > Integer::One() && m_n.IsOdd();
00072         pass = pass && m_e > Integer::One() && m_e.IsOdd() && m_e < m_n;
00073         return pass;
00074 }
00075 
00076 bool RSAFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
00077 {
00078         return GetValueHelper(this, name, valueType, pValue).Assignable()
00079                 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus)
00080                 CRYPTOPP_GET_FUNCTION_ENTRY(PublicExponent)
00081                 ;
00082 }
00083 
00084 void RSAFunction::AssignFrom(const NameValuePairs &source)
00085 {
00086         AssignFromHelper(this, source)
00087                 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus)
00088                 CRYPTOPP_SET_FUNCTION_ENTRY(PublicExponent)
00089                 ;
00090 }
00091 
00092 // *****************************************************************************
00093 
00094 class RSAPrimeSelector : public PrimeSelector
00095 {
00096 public:
00097         RSAPrimeSelector(const Integer &e) : m_e(e) {}
00098         bool IsAcceptable(const Integer &candidate) const {return RelativelyPrime(m_e, candidate-Integer::One());}
00099         Integer m_e;
00100 };
00101 
00102 void InvertibleRSAFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg)
00103 {
00104         int modulusSize = 2048;
00105         alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize);
00106 
00107         if (modulusSize < 16)
00108                 throw InvalidArgument("InvertibleRSAFunction: specified modulus size is too small");
00109 
00110         m_e = alg.GetValueWithDefault("PublicExponent", Integer(17));
00111 
00112         if (m_e < 3 || m_e.IsEven())
00113                 throw InvalidArgument("InvertibleRSAFunction: invalid public exponent");
00114 
00115         RSAPrimeSelector selector(m_e);
00116         const NameValuePairs &primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize)
00117                 ("PointerToPrimeSelector", selector.GetSelectorPointer());
00118         m_p.GenerateRandom(rng, primeParam);
00119         m_q.GenerateRandom(rng, primeParam);
00120 
00121         m_d = EuclideanMultiplicativeInverse(m_e, LCM(m_p-1, m_q-1));
00122         assert(m_d.IsPositive());
00123 
00124         m_dp = m_d % (m_p-1);
00125         m_dq = m_d % (m_q-1);
00126         m_n = m_p * m_q;
00127         m_u = m_q.InverseMod(m_p);
00128 
00129         if (FIPS_140_2_ComplianceEnabled())
00130         {
00131                 RSASSA<PKCS1v15, SHA>::Signer signer(*this);
00132                 RSASSA<PKCS1v15, SHA>::Verifier verifier(signer);
00133                 SignaturePairwiseConsistencyTest(signer, verifier);
00134 
00135                 RSAES<OAEP<SHA> >::Decryptor decryptor(*this);
00136                 RSAES<OAEP<SHA> >::Encryptor encryptor(decryptor);
00137                 EncryptionPairwiseConsistencyTest(encryptor, decryptor);
00138         }
00139 }
00140 
00141 void InvertibleRSAFunction::Initialize(RandomNumberGenerator &rng, unsigned int keybits, const Integer &e)
00142 {
00143         GenerateRandom(rng, MakeParameters("ModulusSize", (int)keybits)("PublicExponent", e+e.IsEven()));
00144 }
00145 
00146 void InvertibleRSAFunction::BERDecodeKey(BufferedTransformation &bt)
00147 {
00148         BERSequenceDecoder privateKey(bt);
00149                 word32 version;
00150                 BERDecodeUnsigned<word32>(privateKey, version, INTEGER, 0, 0);  // check version
00151                 m_n.BERDecode(privateKey);
00152                 m_e.BERDecode(privateKey);
00153                 m_d.BERDecode(privateKey);
00154                 m_p.BERDecode(privateKey);
00155                 m_q.BERDecode(privateKey);
00156                 m_dp.BERDecode(privateKey);
00157                 m_dq.BERDecode(privateKey);
00158                 m_u.BERDecode(privateKey);
00159         privateKey.MessageEnd();
00160 }
00161 
00162 void InvertibleRSAFunction::DEREncodeKey(BufferedTransformation &bt) const
00163 {
00164         DERSequenceEncoder privateKey(bt);
00165                 DEREncodeUnsigned<word32>(privateKey, 0);       // version
00166                 m_n.DEREncode(privateKey);
00167                 m_e.DEREncode(privateKey);
00168                 m_d.DEREncode(privateKey);
00169                 m_p.DEREncode(privateKey);
00170                 m_q.DEREncode(privateKey);
00171                 m_dp.DEREncode(privateKey);
00172                 m_dq.DEREncode(privateKey);
00173                 m_u.DEREncode(privateKey);
00174         privateKey.MessageEnd();
00175 }
00176 
00177 Integer InvertibleRSAFunction::CalculateInverse(const Integer &x) const 
00178 {
00179         DoQuickSanityCheck();
00180         ModularArithmetic modn(m_n);
00181         Integer r, rInv;
00182         // seed rng with private key and ciphertext
00183         RandomPool rng;
00184         m_d.DEREncode(rng);
00185         x.DEREncode(rng);
00186         do {    // do this loop for people using small numbers for testing
00187                 r.Randomize(rng, Integer::One(), m_n - Integer::One());
00188                 rInv = modn.MultiplicativeInverse(r);
00189         } while (rInv.IsZero());
00190         Integer re = modn.Exponentiate(r, m_e);
00191         re = modn.Multiply(re, x);                      // blind
00192         // here we follow the notation of PKCS #1 and let u=q inverse mod p
00193         // but in ModRoot, u=p inverse mod q, so we reverse the order of p and q
00194         Integer y = ModularRoot(re, m_dq, m_dp, m_q, m_p, m_u);
00195         y = modn.Multiply(y, rInv);                             // unblind
00196         if (modn.Exponentiate(y, m_e) != x)             // check
00197                 throw Exception(Exception::OTHER_ERROR, "InvertibleRSAFunction: computational error during private key operation");
00198         return y;
00199 }
00200 
00201 bool InvertibleRSAFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const
00202 {
00203         bool pass = RSAFunction::Validate(rng, level);
00204         pass = pass && m_p > Integer::One() && m_p.IsOdd() && m_p < m_n;
00205         pass = pass && m_q > Integer::One() && m_q.IsOdd() && m_q < m_n;
00206         pass = pass && m_d > Integer::One() && m_d.IsOdd() && m_d < m_n;
00207         pass = pass && m_dp > Integer::One() && m_dp.IsOdd() && m_dp < m_p;
00208         pass = pass && m_dq > Integer::One() && m_dq.IsOdd() && m_dq < m_q;
00209         pass = pass && m_u.IsPositive() && m_u < m_p;
00210         if (level >= 1)
00211         {
00212                 pass = pass && m_p * m_q == m_n;
00213                 pass = pass && m_e*m_d % LCM(m_p-1, m_q-1) == 1;
00214                 pass = pass && m_dp == m_d%(m_p-1) && m_dq == m_d%(m_q-1);
00215                 pass = pass && m_u * m_q % m_p == 1;
00216         }
00217         if (level >= 2)
00218                 pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2);
00219         return pass;
00220 }
00221 
00222 bool InvertibleRSAFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const
00223 {
00224         return GetValueHelper<RSAFunction>(this, name, valueType, pValue).Assignable()
00225                 CRYPTOPP_GET_FUNCTION_ENTRY(Prime1)
00226                 CRYPTOPP_GET_FUNCTION_ENTRY(Prime2)
00227                 CRYPTOPP_GET_FUNCTION_ENTRY(PrivateExponent)
00228                 CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime1PrivateExponent)
00229                 CRYPTOPP_GET_FUNCTION_ENTRY(ModPrime2PrivateExponent)
00230                 CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
00231                 ;
00232 }
00233 
00234 void InvertibleRSAFunction::AssignFrom(const NameValuePairs &source)
00235 {
00236         AssignFromHelper<RSAFunction>(this, source)
00237                 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1)
00238                 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2)
00239                 CRYPTOPP_SET_FUNCTION_ENTRY(PrivateExponent)
00240                 CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime1PrivateExponent)
00241                 CRYPTOPP_SET_FUNCTION_ENTRY(ModPrime2PrivateExponent)
00242                 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1)
00243                 ;
00244 }
00245 
00246 #endif
00247 
00248 /*
00249 bool RSAFunctionInverse_NonCRT::Validate(RandomNumberGenerator &rng, unsigned int level) const
00250 {
00251         bool pass = true;
00252         pass = pass && m_n > Integer::One() && m_n.IsOdd();
00253         pass = pass && m_d > Integer::One() && m_d.IsOdd() && m_d < m_n;
00254         return pass;
00255 }
00256 */
00257 
00258 NAMESPACE_END

Generated on Tue Jul 8 23:34:24 2003 for Crypto++ by doxygen 1.3.2