00001
00002
00003 #include "pch.h"
00004 #include "ecp.h"
00005 #include "asn.h"
00006 #include "nbtheory.h"
00007
00008 #include "algebra.cpp"
00009 #include "eprecomp.cpp"
00010
00011 NAMESPACE_BEGIN(CryptoPP)
00012
00013 ANONYMOUS_NAMESPACE_BEGIN
00014 static inline ECP::Point ToMontgomery(const ModularArithmetic &mr, const ECP::Point &P)
00015 {
00016 return P.identity ? P : ECP::Point(mr.ConvertIn(P.x), mr.ConvertIn(P.y));
00017 }
00018
00019 static inline ECP::Point FromMontgomery(const ModularArithmetic &mr, const ECP::Point &P)
00020 {
00021 return P.identity ? P : ECP::Point(mr.ConvertOut(P.x), mr.ConvertOut(P.y));
00022 }
00023 NAMESPACE_END
00024
00025 ECP::ECP(const ECP &ecp, bool convertToMontgomeryRepresentation)
00026 {
00027 if (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation())
00028 {
00029 m_fieldPtr.reset(new MontgomeryRepresentation(ecp.GetField().GetModulus()));
00030 m_a = GetField().ConvertIn(ecp.m_a);
00031 m_b = GetField().ConvertIn(ecp.m_b);
00032 }
00033 else
00034 operator=(ecp);
00035 }
00036
00037 ECP::ECP(BufferedTransformation &bt)
00038 : m_fieldPtr(new Field(bt))
00039 {
00040 BERSequenceDecoder seq(bt);
00041 GetField().BERDecodeElement(seq, m_a);
00042 GetField().BERDecodeElement(seq, m_b);
00043
00044 if (!seq.EndReached())
00045 BERDecodeOctetString(seq, TheBitBucket());
00046 seq.MessageEnd();
00047 }
00048
00049 void ECP::DEREncode(BufferedTransformation &bt) const
00050 {
00051 GetField().DEREncode(bt);
00052 DERSequenceEncoder seq(bt);
00053 GetField().DEREncodeElement(seq, m_a);
00054 GetField().DEREncodeElement(seq, m_b);
00055 seq.MessageEnd();
00056 }
00057
00058 bool ECP::DecodePoint(ECP::Point &P, const byte *encodedPoint, unsigned int encodedPointLen) const
00059 {
00060 StringStore store(encodedPoint, encodedPointLen);
00061 return DecodePoint(P, store, encodedPointLen);
00062 }
00063
00064 bool ECP::DecodePoint(ECP::Point &P, BufferedTransformation &bt, unsigned int encodedPointLen) const
00065 {
00066 byte type;
00067 if (encodedPointLen < 1 || !bt.Get(type))
00068 return false;
00069
00070 switch (type)
00071 {
00072 case 0:
00073 P.identity = true;
00074 return true;
00075 case 2:
00076 case 3:
00077 {
00078 if (encodedPointLen != EncodedPointSize(true))
00079 return false;
00080
00081 Integer p = FieldSize();
00082
00083 P.identity = false;
00084 P.x.Decode(bt, GetField().MaxElementByteLength());
00085 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
00086
00087 if (Jacobi(P.y, p) !=1)
00088 return false;
00089
00090 P.y = ModularSquareRoot(P.y, p);
00091
00092 if ((type & 1) != P.y.GetBit(0))
00093 P.y = p-P.y;
00094
00095 return true;
00096 }
00097 case 4:
00098 {
00099 if (encodedPointLen != EncodedPointSize(false))
00100 return false;
00101
00102 unsigned int len = GetField().MaxElementByteLength();
00103 P.identity = false;
00104 P.x.Decode(bt, len);
00105 P.y.Decode(bt, len);
00106 return true;
00107 }
00108 default:
00109 return false;
00110 }
00111 }
00112
00113 void ECP::EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
00114 {
00115 if (P.identity)
00116 NullStore().TransferTo(bt, EncodedPointSize(compressed));
00117 else if (compressed)
00118 {
00119 bt.Put(2 + P.y.GetBit(0));
00120 P.x.Encode(bt, GetField().MaxElementByteLength());
00121 }
00122 else
00123 {
00124 unsigned int len = GetField().MaxElementByteLength();
00125 bt.Put(4);
00126 P.x.Encode(bt, len);
00127 P.y.Encode(bt, len);
00128 }
00129 }
00130
00131 void ECP::EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
00132 {
00133 ArraySink sink(encodedPoint, EncodedPointSize(compressed));
00134 EncodePoint(sink, P, compressed);
00135 assert(sink.TotalPutLength() == EncodedPointSize(compressed));
00136 }
00137
00138 ECP::Point ECP::BERDecodePoint(BufferedTransformation &bt) const
00139 {
00140 SecByteBlock str;
00141 BERDecodeOctetString(bt, str);
00142 Point P;
00143 if (!DecodePoint(P, str, str.size()))
00144 BERDecodeError();
00145 return P;
00146 }
00147
00148 void ECP::DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
00149 {
00150 SecByteBlock str(EncodedPointSize(compressed));
00151 EncodePoint(str, P, compressed);
00152 DEREncodeOctetString(bt, str);
00153 }
00154
00155 bool ECP::ValidateParameters(RandomNumberGenerator &rng, unsigned int level) const
00156 {
00157 Integer p = FieldSize();
00158
00159 bool pass = p.IsOdd();
00160 pass = pass && !m_a.IsNegative() && m_a<p && !m_b.IsNegative() && m_b<p;
00161
00162 if (level >= 1)
00163 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
00164
00165 if (level >= 2)
00166 pass = pass && VerifyPrime(rng, p);
00167
00168 return pass;
00169 }
00170
00171 bool ECP::VerifyPoint(const Point &P) const
00172 {
00173 const FieldElement &x = P.x, &y = P.y;
00174 Integer p = FieldSize();
00175 return P.identity ||
00176 (!x.IsNegative() && x<p && !y.IsNegative() && y<p
00177 && !(((x*x+m_a)*x+m_b-y*y)%p));
00178 }
00179
00180 bool ECP::Equal(const Point &P, const Point &Q) const
00181 {
00182 if (P.identity && Q.identity)
00183 return true;
00184
00185 if (P.identity && !Q.identity)
00186 return false;
00187
00188 if (!P.identity && Q.identity)
00189 return false;
00190
00191 return (GetField().Equal(P.x,Q.x) && GetField().Equal(P.y,Q.y));
00192 }
00193
00194 const ECP::Point& ECP::Identity() const
00195 {
00196 static const Point zero;
00197 return zero;
00198 }
00199
00200 const ECP::Point& ECP::Inverse(const Point &P) const
00201 {
00202 if (P.identity)
00203 return P;
00204 else
00205 {
00206 m_R.identity = false;
00207 m_R.x = P.x;
00208 m_R.y = GetField().Inverse(P.y);
00209 return m_R;
00210 }
00211 }
00212
00213 const ECP::Point& ECP::Add(const Point &P, const Point &Q) const
00214 {
00215 if (P.identity) return Q;
00216 if (Q.identity) return P;
00217 if (GetField().Equal(P.x, Q.x))
00218 return GetField().Equal(P.y, Q.y) ? Double(P) : Identity();
00219
00220 FieldElement t = GetField().Subtract(Q.y, P.y);
00221 t = GetField().Divide(t, GetField().Subtract(Q.x, P.x));
00222 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().Square(t), P.x), Q.x);
00223 m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y);
00224
00225 m_R.x.swap(x);
00226 m_R.identity = false;
00227 return m_R;
00228 }
00229
00230 const ECP::Point& ECP::Double(const Point &P) const
00231 {
00232 if (P.identity || P.y==GetField().Identity()) return Identity();
00233
00234 FieldElement t = GetField().Square(P.x);
00235 t = GetField().Add(GetField().Add(GetField().Double(t), t), m_a);
00236 t = GetField().Divide(t, GetField().Double(P.y));
00237 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().Square(t), P.x), P.x);
00238 m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y);
00239
00240 m_R.x.swap(x);
00241 m_R.identity = false;
00242 return m_R;
00243 }
00244
00245 template <class T, class Iterator> void ParallelInvert(const AbstractRing<T> &ring, Iterator begin, Iterator end)
00246 {
00247 unsigned int n = end-begin;
00248 if (n == 1)
00249 *begin = ring.MultiplicativeInverse(*begin);
00250 else if (n > 1)
00251 {
00252 std::vector<T> vec((n+1)/2);
00253 unsigned int i;
00254 Iterator it;
00255
00256 for (i=0, it=begin; i<n/2; i++, it+=2)
00257 vec[i] = ring.Multiply(*it, *(it+1));
00258 if (n%2 == 1)
00259 vec[n/2] = *it;
00260
00261 ParallelInvert(ring, vec.begin(), vec.end());
00262
00263 for (i=0, it=begin; i<n/2; i++, it+=2)
00264 {
00265 if (!vec[i])
00266 {
00267 *it = ring.MultiplicativeInverse(*it);
00268 *(it+1) = ring.MultiplicativeInverse(*(it+1));
00269 }
00270 else
00271 {
00272 std::swap(*it, *(it+1));
00273 *it = ring.Multiply(*it, vec[i]);
00274 *(it+1) = ring.Multiply(*(it+1), vec[i]);
00275 }
00276 }
00277 if (n%2 == 1)
00278 *it = vec[n/2];
00279 }
00280 }
00281
00282 struct ProjectivePoint
00283 {
00284 ProjectivePoint() {}
00285 ProjectivePoint(const Integer &x, const Integer &y, const Integer &z)
00286 : x(x), y(y), z(z) {}
00287
00288 Integer x,y,z;
00289 };
00290
00291 class ProjectiveDoubling
00292 {
00293 public:
00294 ProjectiveDoubling(const ModularArithmetic &mr, const Integer &m_a, const Integer &m_b, const ECPPoint &Q)
00295 : mr(mr), firstDoubling(true), negated(false)
00296 {
00297 if (Q.identity)
00298 {
00299 sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity();
00300 aZ4 = P.z = mr.Identity();
00301 }
00302 else
00303 {
00304 P.x = Q.x;
00305 P.y = Q.y;
00306 sixteenY4 = P.z = mr.MultiplicativeIdentity();
00307 aZ4 = m_a;
00308 }
00309 }
00310
00311 void Double()
00312 {
00313 twoY = mr.Double(P.y);
00314 P.z = mr.Multiply(P.z, twoY);
00315 fourY2 = mr.Square(twoY);
00316 S = mr.Multiply(fourY2, P.x);
00317 aZ4 = mr.Multiply(aZ4, sixteenY4);
00318 M = mr.Square(P.x);
00319 M = mr.Add(mr.Add(mr.Double(M), M), aZ4);
00320 P.x = mr.Square(M);
00321 mr.Reduce(P.x, S);
00322 mr.Reduce(P.x, S);
00323 mr.Reduce(S, P.x);
00324 P.y = mr.Multiply(M, S);
00325 sixteenY4 = mr.Square(fourY2);
00326 mr.Reduce(P.y, mr.Half(sixteenY4));
00327 }
00328
00329 const ModularArithmetic &mr;
00330 ProjectivePoint P;
00331 bool firstDoubling, negated;
00332 Integer sixteenY4, aZ4, twoY, fourY2, S, M;
00333 };
00334
00335 struct ZIterator
00336 {
00337 ZIterator() {}
00338 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
00339 Integer& operator*() {return it->z;}
00340 int operator-(ZIterator it2) {return it-it2.it;}
00341 ZIterator operator+(int i) {return ZIterator(it+i);}
00342 ZIterator& operator+=(int i) {it+=i; return *this;}
00343 std::vector<ProjectivePoint>::iterator it;
00344 };
00345
00346 ECP::Point ECP::ScalarMultiply(const Point &P, const Integer &k) const
00347 {
00348 Element result;
00349 if (k.BitCount() <= 5)
00350 AbstractGroup<ECPPoint>::SimultaneousMultiply(&result, P, &k, 1);
00351 else
00352 ECP::SimultaneousMultiply(&result, P, &k, 1);
00353 return result;
00354 }
00355
00356 void ECP::SimultaneousMultiply(ECP::Point *results, const ECP::Point &P, const Integer *expBegin, unsigned int expCount) const
00357 {
00358 if (!GetField().IsMontgomeryRepresentation())
00359 {
00360 ECP ecpmr(*this, true);
00361 const ModularArithmetic &mr = ecpmr.GetField();
00362 ecpmr.SimultaneousMultiply(results, ToMontgomery(mr, P), expBegin, expCount);
00363 for (unsigned int i=0; i<expCount; i++)
00364 results[i] = FromMontgomery(mr, results[i]);
00365 return;
00366 }
00367
00368 ProjectiveDoubling rd(GetField(), m_a, m_b, P);
00369 std::vector<ProjectivePoint> bases;
00370 std::vector<WindowSlider> exponents;
00371 exponents.reserve(expCount);
00372 std::vector<std::vector<unsigned int> > baseIndices(expCount);
00373 std::vector<std::vector<bool> > negateBase(expCount);
00374 std::vector<std::vector<unsigned int> > exponentWindows(expCount);
00375 unsigned int i;
00376
00377 for (i=0; i<expCount; i++)
00378 {
00379 assert(expBegin->NotNegative());
00380 exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 5));
00381 exponents[i].FindNextWindow();
00382 }
00383
00384 unsigned int expBitPosition = 0;
00385 bool notDone = true;
00386
00387 while (notDone)
00388 {
00389 notDone = false;
00390 bool baseAdded = false;
00391 for (i=0; i<expCount; i++)
00392 {
00393 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
00394 {
00395 if (!baseAdded)
00396 {
00397 bases.push_back(rd.P);
00398 baseAdded =true;
00399 }
00400
00401 exponentWindows[i].push_back(exponents[i].expWindow);
00402 baseIndices[i].push_back(bases.size()-1);
00403 negateBase[i].push_back(exponents[i].negateNext);
00404
00405 exponents[i].FindNextWindow();
00406 }
00407 notDone = notDone || !exponents[i].finished;
00408 }
00409
00410 if (notDone)
00411 {
00412 rd.Double();
00413 expBitPosition++;
00414 }
00415 }
00416
00417
00418 ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
00419 for (i=0; i<bases.size(); i++)
00420 {
00421 if (bases[i].z.NotZero())
00422 {
00423 bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
00424 bases[i].z = GetField().Square(bases[i].z);
00425 bases[i].x = GetField().Multiply(bases[i].x, bases[i].z);
00426 bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
00427 }
00428 }
00429
00430 std::vector<BaseAndExponent<Point, word> > finalCascade;
00431 for (i=0; i<expCount; i++)
00432 {
00433 finalCascade.resize(baseIndices[i].size());
00434 for (unsigned int j=0; j<baseIndices[i].size(); j++)
00435 {
00436 ProjectivePoint &base = bases[baseIndices[i][j]];
00437 if (base.z.IsZero())
00438 finalCascade[j].base.identity = true;
00439 else
00440 {
00441 finalCascade[j].base.identity = false;
00442 finalCascade[j].base.x = base.x;
00443 if (negateBase[i][j])
00444 finalCascade[j].base.y = GetField().Inverse(base.y);
00445 else
00446 finalCascade[j].base.y = base.y;
00447 }
00448 finalCascade[j].exponent = exponentWindows[i][j];
00449 }
00450 results[i] = GeneralCascadeMultiplication(*this, finalCascade.begin(), finalCascade.end());
00451 }
00452 }
00453
00454 ECP::Point ECP::CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
00455 {
00456 if (!GetField().IsMontgomeryRepresentation())
00457 {
00458 ECP ecpmr(*this, true);
00459 const ModularArithmetic &mr = ecpmr.GetField();
00460 return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));
00461 }
00462 else
00463 return AbstractGroup<Point>::CascadeScalarMultiply(P, k1, Q, k2);
00464 }
00465
00466
00467
00468 void EcPrecomputation<ECP>::SetCurve(const ECP &ec)
00469 {
00470 m_ec.reset(new ECP(ec, true));
00471 m_ecOriginal = ec;
00472 }
00473
00474 template class AbstractGroup<ECP::Point>;
00475 template class DL_FixedBasePrecomputationImpl<ECP::Point>;
00476
00477 NAMESPACE_END