Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members

ecp.cpp

00001 // ecp.cpp - written and placed in the public domain by Wei Dai
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         // skip optional seed
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);      // uncompressed
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         // convert from projective to affine coordinates
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

Generated on Sun Mar 14 20:44:25 2004 for Crypto++ by doxygen 1.3.6-20040222