Crypto++
|
00001 // rw.cpp - written and placed in the public domain by Wei Dai 00002 00003 #include "pch.h" 00004 #include "rw.h" 00005 #include "nbtheory.h" 00006 #include "asn.h" 00007 00008 #ifndef CRYPTOPP_IMPORTS 00009 00010 NAMESPACE_BEGIN(CryptoPP) 00011 00012 void RWFunction::BERDecode(BufferedTransformation &bt) 00013 { 00014 BERSequenceDecoder seq(bt); 00015 m_n.BERDecode(seq); 00016 seq.MessageEnd(); 00017 } 00018 00019 void RWFunction::DEREncode(BufferedTransformation &bt) const 00020 { 00021 DERSequenceEncoder seq(bt); 00022 m_n.DEREncode(seq); 00023 seq.MessageEnd(); 00024 } 00025 00026 Integer RWFunction::ApplyFunction(const Integer &in) const 00027 { 00028 DoQuickSanityCheck(); 00029 00030 Integer out = in.Squared()%m_n; 00031 const word r = 12; 00032 // this code was written to handle both r = 6 and r = 12, 00033 // but now only r = 12 is used in P1363 00034 const word r2 = r/2; 00035 const word r3a = (16 + 5 - r) % 16; // n%16 could be 5 or 13 00036 const word r3b = (16 + 13 - r) % 16; 00037 const word r4 = (8 + 5 - r/2) % 8; // n%8 == 5 00038 switch (out % 16) 00039 { 00040 case r: 00041 break; 00042 case r2: 00043 case r2+8: 00044 out <<= 1; 00045 break; 00046 case r3a: 00047 case r3b: 00048 out.Negate(); 00049 out += m_n; 00050 break; 00051 case r4: 00052 case r4+8: 00053 out.Negate(); 00054 out += m_n; 00055 out <<= 1; 00056 break; 00057 default: 00058 out = Integer::Zero(); 00059 } 00060 return out; 00061 } 00062 00063 bool RWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const 00064 { 00065 bool pass = true; 00066 pass = pass && m_n > Integer::One() && m_n%8 == 5; 00067 return pass; 00068 } 00069 00070 bool RWFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const 00071 { 00072 return GetValueHelper(this, name, valueType, pValue).Assignable() 00073 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus) 00074 ; 00075 } 00076 00077 void RWFunction::AssignFrom(const NameValuePairs &source) 00078 { 00079 AssignFromHelper(this, source) 00080 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus) 00081 ; 00082 } 00083 00084 // ***************************************************************************** 00085 // private key operations: 00086 00087 // generate a random private key 00088 void InvertibleRWFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg) 00089 { 00090 int modulusSize = 2048; 00091 alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize); 00092 00093 if (modulusSize < 16) 00094 throw InvalidArgument("InvertibleRWFunction: specified modulus length is too small"); 00095 00096 AlgorithmParameters primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize); 00097 m_p.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("EquivalentTo", 3)("Mod", 8))); 00098 m_q.GenerateRandom(rng, CombinedNameValuePairs(primeParam, MakeParameters("EquivalentTo", 7)("Mod", 8))); 00099 00100 m_n = m_p * m_q; 00101 m_u = m_q.InverseMod(m_p); 00102 } 00103 00104 void InvertibleRWFunction::BERDecode(BufferedTransformation &bt) 00105 { 00106 BERSequenceDecoder seq(bt); 00107 m_n.BERDecode(seq); 00108 m_p.BERDecode(seq); 00109 m_q.BERDecode(seq); 00110 m_u.BERDecode(seq); 00111 seq.MessageEnd(); 00112 } 00113 00114 void InvertibleRWFunction::DEREncode(BufferedTransformation &bt) const 00115 { 00116 DERSequenceEncoder seq(bt); 00117 m_n.DEREncode(seq); 00118 m_p.DEREncode(seq); 00119 m_q.DEREncode(seq); 00120 m_u.DEREncode(seq); 00121 seq.MessageEnd(); 00122 } 00123 00124 Integer InvertibleRWFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &x) const 00125 { 00126 DoQuickSanityCheck(); 00127 ModularArithmetic modn(m_n); 00128 Integer r, rInv; 00129 do { // do this in a loop for people using small numbers for testing 00130 r.Randomize(rng, Integer::One(), m_n - Integer::One()); 00131 rInv = modn.MultiplicativeInverse(r); 00132 } while (rInv.IsZero()); 00133 Integer re = modn.Square(r); 00134 re = modn.Multiply(re, x); // blind 00135 00136 Integer cp=re%m_p, cq=re%m_q; 00137 if (Jacobi(cp, m_p) * Jacobi(cq, m_q) != 1) 00138 { 00139 cp = cp.IsOdd() ? (cp+m_p) >> 1 : cp >> 1; 00140 cq = cq.IsOdd() ? (cq+m_q) >> 1 : cq >> 1; 00141 } 00142 00143 #pragma omp parallel 00144 #pragma omp sections 00145 { 00146 #pragma omp section 00147 cp = ModularSquareRoot(cp, m_p); 00148 #pragma omp section 00149 cq = ModularSquareRoot(cq, m_q); 00150 } 00151 00152 Integer y = CRT(cq, m_q, cp, m_p, m_u); 00153 y = modn.Multiply(y, rInv); // unblind 00154 y = STDMIN(y, m_n-y); 00155 if (ApplyFunction(y) != x) // check 00156 throw Exception(Exception::OTHER_ERROR, "InvertibleRWFunction: computational error during private key operation"); 00157 return y; 00158 } 00159 00160 bool InvertibleRWFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const 00161 { 00162 bool pass = RWFunction::Validate(rng, level); 00163 pass = pass && m_p > Integer::One() && m_p%8 == 3 && m_p < m_n; 00164 pass = pass && m_q > Integer::One() && m_q%8 == 7 && m_q < m_n; 00165 pass = pass && m_u.IsPositive() && m_u < m_p; 00166 if (level >= 1) 00167 { 00168 pass = pass && m_p * m_q == m_n; 00169 pass = pass && m_u * m_q % m_p == 1; 00170 } 00171 if (level >= 2) 00172 pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2); 00173 return pass; 00174 } 00175 00176 bool InvertibleRWFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const 00177 { 00178 return GetValueHelper<RWFunction>(this, name, valueType, pValue).Assignable() 00179 CRYPTOPP_GET_FUNCTION_ENTRY(Prime1) 00180 CRYPTOPP_GET_FUNCTION_ENTRY(Prime2) 00181 CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1) 00182 ; 00183 } 00184 00185 void InvertibleRWFunction::AssignFrom(const NameValuePairs &source) 00186 { 00187 AssignFromHelper<RWFunction>(this, source) 00188 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1) 00189 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2) 00190 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1) 00191 ; 00192 } 00193 00194 NAMESPACE_END 00195 00196 #endif