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