- Main Page
- Namespaces
- Classes
- Files

# 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         AlgorithmParameters 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