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