5 #ifndef CRYPTOPP_IMPORTS
13 #include "algebra.cpp"
17 ANONYMOUS_NAMESPACE_BEGIN
29 ECP::ECP(
const ECP &ecp,
bool convertToMontgomeryRepresentation)
42 : m_fieldPtr(new Field(bt))
45 GetField().BERDecodeElement(seq, m_a);
46 GetField().BERDecodeElement(seq, m_b);
48 if (!seq.EndReached())
66 bool ECP::DecodePoint(
ECP::Point &P,
const byte *encodedPoint,
size_t encodedPointLen)
const
69 return DecodePoint(P, store, encodedPointLen);
75 if (encodedPointLen < 1 || !bt.
Get(type))
86 if (encodedPointLen != EncodedPointSize(
true))
92 P.x.Decode(bt, GetField().MaxElementByteLength());
93 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
95 if (Jacobi(P.y, p) !=1)
98 P.y = ModularSquareRoot(P.y, p);
100 if ((type & 1) != P.y.GetBit(0))
107 if (encodedPointLen != EncodedPointSize(
false))
127 bt.
Put(2 + P.y.GetBit(0));
128 P.x.Encode(bt, GetField().MaxElementByteLength());
139 void ECP::EncodePoint(
byte *encodedPoint,
const Point &P,
bool compressed)
const
141 ArraySink sink(encodedPoint, EncodedPointSize(compressed));
142 EncodePoint(sink, P, compressed);
143 CRYPTOPP_ASSERT(sink.TotalPutLength() == EncodedPointSize(compressed));
151 if (!DecodePoint(P, str, str.
size()))
159 EncodePoint(str, P, compressed);
167 bool pass = p.
IsOdd();
171 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
179 bool ECP::VerifyPoint(
const Point &P)
const
181 const FieldElement &x = P.x, &y = P.y;
184 (!x.IsNegative() && x<p && !y.
IsNegative() && y<p
185 && !(((x*x+m_a)*x+m_b-y*y)%p));
188 bool ECP::Equal(
const Point &P,
const Point &Q)
const
190 if (P.identity && Q.identity)
193 if (P.identity && !Q.identity)
196 if (!P.identity && Q.identity)
199 return (GetField().
Equal(P.x,Q.x) && GetField().
Equal(P.y,Q.y));
213 m_R.identity =
false;
215 m_R.y = GetField().
Inverse(P.y);
222 if (P.identity)
return Q;
223 if (Q.identity)
return P;
224 if (GetField().
Equal(P.x, Q.x))
225 return GetField().
Equal(P.y, Q.y) ?
Double(P) : Identity();
227 FieldElement t = GetField().
Subtract(Q.y, P.y);
230 m_R.y = GetField().
Subtract(GetField().Multiply(t, GetField().
Subtract(P.x, x)), P.y);
233 m_R.identity =
false;
239 if (P.identity || P.y==GetField().Identity())
return Identity();
241 FieldElement t = GetField().
Square(P.x);
242 t = GetField().
Add(GetField().
Add(GetField().
Double(t), t), m_a);
245 m_R.y = GetField().
Subtract(GetField().Multiply(t, GetField().
Subtract(P.x, x)), P.y);
248 m_R.identity =
false;
252 template <
class T,
class Iterator>
void ParallelInvert(
const AbstractRing<T> &ring, Iterator begin, Iterator end)
254 size_t n = end-begin;
259 std::vector<T> vec((n+1)/2);
263 for (i=0, it=begin; i<n/2; i++, it+=2)
264 vec[i] = ring.
Multiply(*it, *(it+1));
268 ParallelInvert(ring, vec.begin(), vec.end());
270 for (i=0, it=begin; i<n/2; i++, it+=2)
279 std::swap(*it, *(it+1));
281 *(it+1) = ring.
Multiply(*(it+1), vec[i]);
289 struct ProjectivePoint
293 : x(x), y(y), z(z) {}
298 class ProjectiveDoubling
302 : mr(m_mr), firstDoubling(true), negated(false)
304 CRYPTOPP_UNUSED(m_b);
307 sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity();
308 aZ4 = P.z = mr.Identity();
314 sixteenY4 = P.z = mr.MultiplicativeIdentity();
321 twoY = mr.Double(P.y);
322 P.z = mr.Multiply(P.z, twoY);
323 fourY2 = mr.Square(twoY);
324 S = mr.Multiply(fourY2, P.x);
325 aZ4 = mr.Multiply(aZ4, sixteenY4);
327 M = mr.Add(mr.Add(mr.Double(M), M), aZ4);
332 P.y = mr.Multiply(M, S);
333 sixteenY4 = mr.Square(fourY2);
334 mr.Reduce(P.y, mr.Half(sixteenY4));
339 bool firstDoubling, negated;
340 Integer sixteenY4, aZ4, twoY, fourY2, S, M;
346 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
348 int operator-(ZIterator it2) {
return int(it-it2.it);}
349 ZIterator
operator+(
int i) {
return ZIterator(it+i);}
350 ZIterator& operator+=(
int i) {it+=i;
return *
this;}
351 std::vector<ProjectivePoint>::iterator it;
366 if (!GetField().IsMontgomeryRepresentation())
368 ECP ecpmr(*
this,
true);
371 for (
unsigned int i=0; i<expCount; i++)
372 results[i] = FromMontgomery(mr, results[i]);
376 ProjectiveDoubling rd(GetField(), m_a, m_b, P);
377 std::vector<ProjectivePoint> bases;
378 std::vector<WindowSlider> exponents;
379 exponents.reserve(expCount);
380 std::vector<std::vector<word32> > baseIndices(expCount);
381 std::vector<std::vector<bool> > negateBase(expCount);
382 std::vector<std::vector<word32> > exponentWindows(expCount);
385 for (i=0; i<expCount; i++)
388 exponents.push_back(
WindowSlider(*expBegin++, InversionIsFast(), 5));
389 exponents[i].FindNextWindow();
392 unsigned int expBitPosition = 0;
398 bool baseAdded =
false;
399 for (i=0; i<expCount; i++)
401 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
405 bases.push_back(rd.P);
409 exponentWindows[i].push_back(exponents[i].expWindow);
410 baseIndices[i].push_back((word32)bases.size()-1);
411 negateBase[i].push_back(exponents[i].negateNext);
413 exponents[i].FindNextWindow();
415 notDone = notDone || !exponents[i].finished;
426 ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
427 for (i=0; i<bases.size(); i++)
429 if (bases[i].z.NotZero())
431 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
432 bases[i].z = GetField().
Square(bases[i].z);
433 bases[i].x = GetField().
Multiply(bases[i].x, bases[i].z);
434 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
438 std::vector<BaseAndExponent<Point, Integer> > finalCascade;
439 for (i=0; i<expCount; i++)
441 finalCascade.resize(baseIndices[i].size());
442 for (
unsigned int j=0; j<baseIndices[i].size(); j++)
444 ProjectivePoint &base = bases[baseIndices[i][j]];
446 finalCascade[j].base.identity =
true;
449 finalCascade[j].base.identity =
false;
450 finalCascade[j].base.x = base.x;
451 if (negateBase[i][j])
452 finalCascade[j].base.y = GetField().
Inverse(base.y);
454 finalCascade[j].base.y = base.y;
458 results[i] = GeneralCascadeMultiplication(*
this, finalCascade.begin(), finalCascade.end());
464 if (!GetField().IsMontgomeryRepresentation())
466 ECP ecpmr(*
this,
true);
468 return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));