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

Generated on Sat Aug 28 17:24:56 2004 for Crypto++ by doxygen 1.3.8