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

rabin.cpp

00001 // rabin.cpp - written and placed in the public domain by Wei Dai 00002 00003 #include "pch.h" 00004 #include "rabin.h" 00005 #include "nbtheory.h" 00006 #include "asn.h" 00007 #include "sha.h" 00008 #include "modarith.h" 00009 00010 #include "oaep.cpp" 00011 00012 NAMESPACE_BEGIN(CryptoPP) 00013 00014 void RabinFunction::BERDecode(BufferedTransformation &bt) 00015 { 00016 BERSequenceDecoder seq(bt); 00017 m_n.BERDecode(seq); 00018 m_r.BERDecode(seq); 00019 m_s.BERDecode(seq); 00020 seq.MessageEnd(); 00021 } 00022 00023 void RabinFunction::DEREncode(BufferedTransformation &bt) const 00024 { 00025 DERSequenceEncoder seq(bt); 00026 m_n.DEREncode(seq); 00027 m_r.DEREncode(seq); 00028 m_s.DEREncode(seq); 00029 seq.MessageEnd(); 00030 } 00031 00032 Integer RabinFunction::ApplyFunction(const Integer &in) const 00033 { 00034 DoQuickSanityCheck(); 00035 00036 Integer out = in.Squared()%m_n; 00037 if (in.IsOdd()) 00038 out = out*m_r%m_n; 00039 if (Jacobi(in, m_n)==-1) 00040 out = out*m_s%m_n; 00041 return out; 00042 } 00043 00044 bool RabinFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const 00045 { 00046 bool pass = true; 00047 pass = pass && m_n > Integer::One() && m_n%4 == 1; 00048 pass = pass && m_r > Integer::One() && m_r < m_n; 00049 pass = pass && m_s > Integer::One() && m_s < m_n; 00050 if (level >= 1) 00051 pass = pass && Jacobi(m_r, m_n) == -1 && Jacobi(m_s, m_n) == -1; 00052 return pass; 00053 } 00054 00055 bool RabinFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const 00056 { 00057 return GetValueHelper(this, name, valueType, pValue).Assignable() 00058 CRYPTOPP_GET_FUNCTION_ENTRY(Modulus) 00059 CRYPTOPP_GET_FUNCTION_ENTRY(QuadraticResidueModPrime1) 00060 CRYPTOPP_GET_FUNCTION_ENTRY(QuadraticResidueModPrime2) 00061 ; 00062 } 00063 00064 void RabinFunction::AssignFrom(const NameValuePairs &source) 00065 { 00066 AssignFromHelper(this, source) 00067 CRYPTOPP_SET_FUNCTION_ENTRY(Modulus) 00068 CRYPTOPP_SET_FUNCTION_ENTRY(QuadraticResidueModPrime1) 00069 CRYPTOPP_SET_FUNCTION_ENTRY(QuadraticResidueModPrime2) 00070 ; 00071 } 00072 00073 // ***************************************************************************** 00074 // private key operations: 00075 00076 // generate a random private key 00077 void InvertibleRabinFunction::GenerateRandom(RandomNumberGenerator &rng, const NameValuePairs &alg) 00078 { 00079 int modulusSize = 2048; 00080 alg.GetIntValue("ModulusSize", modulusSize) || alg.GetIntValue("KeySize", modulusSize); 00081 00082 if (modulusSize < 16) 00083 throw InvalidArgument("InvertibleRabinFunction: specified modulus size is too small"); 00084 00085 // VC70 workaround: putting these after primeParam causes overlapped stack allocation 00086 bool rFound=false, sFound=false; 00087 Integer t=2; 00088 00089 const NameValuePairs &primeParam = MakeParametersForTwoPrimesOfEqualSize(modulusSize) 00090 ("EquivalentTo", 3)("Mod", 4); 00091 m_p.GenerateRandom(rng, primeParam); 00092 m_q.GenerateRandom(rng, primeParam); 00093 00094 while (!(rFound && sFound)) 00095 { 00096 int jp = Jacobi(t, m_p); 00097 int jq = Jacobi(t, m_q); 00098 00099 if (!rFound && jp==1 && jq==-1) 00100 { 00101 m_r = t; 00102 rFound = true; 00103 } 00104 00105 if (!sFound && jp==-1 && jq==1) 00106 { 00107 m_s = t; 00108 sFound = true; 00109 } 00110 00111 ++t; 00112 } 00113 00114 m_n = m_p * m_q; 00115 m_u = m_q.InverseMod(m_p); 00116 } 00117 00118 void InvertibleRabinFunction::BERDecode(BufferedTransformation &bt) 00119 { 00120 BERSequenceDecoder seq(bt); 00121 m_n.BERDecode(seq); 00122 m_r.BERDecode(seq); 00123 m_s.BERDecode(seq); 00124 m_p.BERDecode(seq); 00125 m_q.BERDecode(seq); 00126 m_u.BERDecode(seq); 00127 seq.MessageEnd(); 00128 } 00129 00130 void InvertibleRabinFunction::DEREncode(BufferedTransformation &bt) const 00131 { 00132 DERSequenceEncoder seq(bt); 00133 m_n.DEREncode(seq); 00134 m_r.DEREncode(seq); 00135 m_s.DEREncode(seq); 00136 m_p.DEREncode(seq); 00137 m_q.DEREncode(seq); 00138 m_u.DEREncode(seq); 00139 seq.MessageEnd(); 00140 } 00141 00142 Integer InvertibleRabinFunction::CalculateInverse(RandomNumberGenerator &rng, const Integer &in) const 00143 { 00144 DoQuickSanityCheck(); 00145 00146 ModularArithmetic modn(m_n); 00147 Integer r(rng, Integer::One(), m_n - Integer::One()); 00148 r = modn.Square(r); 00149 Integer r2 = modn.Square(r); 00150 Integer c = modn.Multiply(in, r2); // blind 00151 00152 Integer cp=c%m_p, cq=c%m_q; 00153 00154 int jp = Jacobi(cp, m_p); 00155 int jq = Jacobi(cq, m_q); 00156 00157 if (jq==-1) 00158 { 00159 cp = cp*EuclideanMultiplicativeInverse(m_r, m_p)%m_p; 00160 cq = cq*EuclideanMultiplicativeInverse(m_r, m_q)%m_q; 00161 } 00162 00163 if (jp==-1) 00164 { 00165 cp = cp*EuclideanMultiplicativeInverse(m_s, m_p)%m_p; 00166 cq = cq*EuclideanMultiplicativeInverse(m_s, m_q)%m_q; 00167 } 00168 00169 cp = ModularSquareRoot(cp, m_p); 00170 cq = ModularSquareRoot(cq, m_q); 00171 00172 if (jp==-1) 00173 cp = m_p-cp; 00174 00175 Integer out = CRT(cq, m_q, cp, m_p, m_u); 00176 00177 out = modn.Divide(out, r); // unblind 00178 00179 if ((jq==-1 && out.IsEven()) || (jq==1 && out.IsOdd())) 00180 out = m_n-out; 00181 00182 return out; 00183 } 00184 00185 bool InvertibleRabinFunction::Validate(RandomNumberGenerator &rng, unsigned int level) const 00186 { 00187 bool pass = RabinFunction::Validate(rng, level); 00188 pass = pass && m_p > Integer::One() && m_p%4 == 3 && m_p < m_n; 00189 pass = pass && m_q > Integer::One() && m_q%4 == 3 && m_q < m_n; 00190 pass = pass && m_u.IsPositive() && m_u < m_p; 00191 if (level >= 1) 00192 { 00193 pass = pass && m_p * m_q == m_n; 00194 pass = pass && m_u * m_q % m_p == 1; 00195 pass = pass && Jacobi(m_r, m_p) == 1; 00196 pass = pass && Jacobi(m_r, m_q) == -1; 00197 pass = pass && Jacobi(m_s, m_p) == -1; 00198 pass = pass && Jacobi(m_s, m_q) == 1; 00199 } 00200 if (level >= 2) 00201 pass = pass && VerifyPrime(rng, m_p, level-2) && VerifyPrime(rng, m_q, level-2); 00202 return pass; 00203 } 00204 00205 bool InvertibleRabinFunction::GetVoidValue(const char *name, const std::type_info &valueType, void *pValue) const 00206 { 00207 return GetValueHelper<RabinFunction>(this, name, valueType, pValue).Assignable() 00208 CRYPTOPP_GET_FUNCTION_ENTRY(Prime1) 00209 CRYPTOPP_GET_FUNCTION_ENTRY(Prime2) 00210 CRYPTOPP_GET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1) 00211 ; 00212 } 00213 00214 void InvertibleRabinFunction::AssignFrom(const NameValuePairs &source) 00215 { 00216 AssignFromHelper<RabinFunction>(this, source) 00217 CRYPTOPP_SET_FUNCTION_ENTRY(Prime1) 00218 CRYPTOPP_SET_FUNCTION_ENTRY(Prime2) 00219 CRYPTOPP_SET_FUNCTION_ENTRY(MultiplicativeInverseOfPrime2ModPrime1) 00220 ; 00221 } 00222 00223 NAMESPACE_END

Generated on Wed Jul 28 08:07:08 2004 for Crypto++ by doxygen 1.3.7