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