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