5 #ifndef CRYPTOPP_IMPORTS
11 #include "algebra.cpp"
13 NAMESPACE_BEGIN(CryptoPP)
15 ANONYMOUS_NAMESPACE_BEGIN
18 return P.identity ? P :
ECP::Point(mr.ConvertIn(P.x), mr.ConvertIn(P.y));
23 return P.identity ? P :
ECP::Point(mr.ConvertOut(P.x), mr.ConvertOut(P.y));
27 ECP::ECP(
const ECP &ecp,
bool convertToMontgomeryRepresentation)
29 if (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation())
32 m_a = GetField().ConvertIn(ecp.m_a);
33 m_b = GetField().ConvertIn(ecp.m_b);
40 : m_fieldPtr(new Field(bt))
43 GetField().BERDecodeElement(seq, m_a);
44 GetField().BERDecodeElement(seq, m_b);
46 if (!seq.EndReached())
50 BERDecodeBitString(seq, seed, unused);
57 GetField().DEREncode(bt);
59 GetField().DEREncodeElement(seq, m_a);
60 GetField().DEREncodeElement(seq, m_b);
64 bool ECP::DecodePoint(
ECP::Point &P,
const byte *encodedPoint,
size_t encodedPointLen)
const
67 return DecodePoint(P, store, encodedPointLen);
73 if (encodedPointLen < 1 || !bt.
Get(type))
84 if (encodedPointLen != EncodedPointSize(
true))
90 P.x.Decode(bt, GetField().MaxElementByteLength());
91 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
93 if (Jacobi(P.y, p) !=1)
96 P.y = ModularSquareRoot(P.y, p);
98 if ((type & 1) != P.y.
GetBit(0))
105 if (encodedPointLen != EncodedPointSize(
false))
108 unsigned int len = GetField().MaxElementByteLength();
125 bt.
Put(2 + P.y.GetBit(0));
126 P.x.Encode(bt, GetField().MaxElementByteLength());
130 unsigned int len = GetField().MaxElementByteLength();
137 void ECP::EncodePoint(byte *encodedPoint,
const Point &P,
bool compressed)
const
139 ArraySink sink(encodedPoint, EncodedPointSize(compressed));
140 EncodePoint(sink, P, compressed);
141 assert(sink.TotalPutLength() == EncodedPointSize(compressed));
147 BERDecodeOctetString(bt, str);
149 if (!DecodePoint(P, str, str.size()))
157 EncodePoint(str, P, compressed);
158 DEREncodeOctetString(bt, str);
165 bool pass = p.IsOdd();
166 pass = pass && !m_a.IsNegative() && m_a<p && !m_b.IsNegative() && m_b<p;
169 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
172 pass = pass && VerifyPrime(rng, p);
177 bool ECP::VerifyPoint(
const Point &P)
const
179 const FieldElement &x = P.x, &y = P.y;
182 (!x.IsNegative() && x<p && !y.IsNegative() && y<p
183 && !(((x*x+m_a)*x+m_b-y*y)%p));
186 bool ECP::Equal(
const Point &P,
const Point &Q)
const
188 if (P.identity && Q.identity)
191 if (P.identity && !Q.identity)
194 if (!P.identity && Q.identity)
197 return (GetField().Equal(P.x,Q.x) && GetField().Equal(P.y,Q.y));
205 const ECP::Point& ECP::Inverse(
const Point &P)
const
211 m_R.identity =
false;
213 m_R.y = GetField().Inverse(P.y);
218 const ECP::Point& ECP::Add(
const Point &P,
const Point &Q)
const
220 if (P.identity)
return Q;
221 if (Q.identity)
return P;
222 if (GetField().Equal(P.x, Q.x))
223 return GetField().Equal(P.y, Q.y) ? Double(P) : Identity();
225 FieldElement t = GetField().Subtract(Q.y, P.y);
226 t = GetField().Divide(t, GetField().Subtract(Q.x, P.x));
227 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().
Square(t), P.x), Q.x);
228 m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y);
231 m_R.identity =
false;
235 const ECP::Point& ECP::Double(
const Point &P)
const
237 if (P.identity || P.y==GetField().Identity())
return Identity();
239 FieldElement t = GetField().Square(P.x);
240 t = GetField().Add(GetField().Add(GetField().Double(t), t), m_a);
241 t = GetField().Divide(t, GetField().Double(P.y));
242 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().
Square(t), P.x), P.x);
243 m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y);
246 m_R.identity =
false;
250 template <
class T,
class Iterator>
void ParallelInvert(
const AbstractRing<T> &ring, Iterator begin, Iterator end)
252 size_t n = end-begin;
254 *begin = ring.MultiplicativeInverse(*begin);
257 std::vector<T> vec((n+1)/2);
261 for (i=0, it=begin; i<n/2; i++, it+=2)
262 vec[i] = ring.Multiply(*it, *(it+1));
266 ParallelInvert(ring, vec.begin(), vec.end());
268 for (i=0, it=begin; i<n/2; i++, it+=2)
272 *it = ring.MultiplicativeInverse(*it);
273 *(it+1) = ring.MultiplicativeInverse(*(it+1));
277 std::swap(*it, *(it+1));
278 *it = ring.Multiply(*it, vec[i]);
279 *(it+1) = ring.Multiply(*(it+1), vec[i]);
287 struct ProjectivePoint
291 : x(x), y(y), z(z) {}
296 class ProjectiveDoubling
300 : mr(mr), firstDoubling(true), negated(false)
304 sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity();
305 aZ4 = P.z = mr.Identity();
311 sixteenY4 = P.z = mr.MultiplicativeIdentity();
318 twoY = mr.Double(P.y);
319 P.z = mr.Multiply(P.z, twoY);
320 fourY2 = mr.Square(twoY);
321 S = mr.Multiply(fourY2, P.x);
322 aZ4 = mr.Multiply(aZ4, sixteenY4);
324 M = mr.Add(mr.Add(mr.Double(M), M), aZ4);
329 P.y = mr.Multiply(M, S);
330 sixteenY4 = mr.Square(fourY2);
331 mr.Reduce(P.y, mr.Half(sixteenY4));
336 bool firstDoubling, negated;
337 Integer sixteenY4, aZ4, twoY, fourY2, S, M;
343 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
344 Integer& operator*() {
return it->z;}
345 int operator-(ZIterator it2) {
return int(it-it2.it);}
346 ZIterator operator+(
int i) {
return ZIterator(it+i);}
347 ZIterator& operator+=(
int i) {it+=i;
return *
this;}
348 std::vector<ProjectivePoint>::iterator it;
357 ECP::SimultaneousMultiply(&result, P, &k, 1);
363 if (!GetField().IsMontgomeryRepresentation())
365 ECP ecpmr(*
this,
true);
367 ecpmr.SimultaneousMultiply(results, ToMontgomery(mr, P), expBegin, expCount);
368 for (
unsigned int i=0; i<expCount; i++)
369 results[i] = FromMontgomery(mr, results[i]);
373 ProjectiveDoubling rd(GetField(), m_a, m_b, P);
374 std::vector<ProjectivePoint> bases;
375 std::vector<WindowSlider> exponents;
376 exponents.reserve(expCount);
377 std::vector<std::vector<word32> > baseIndices(expCount);
378 std::vector<std::vector<bool> > negateBase(expCount);
379 std::vector<std::vector<word32> > exponentWindows(expCount);
382 for (i=0; i<expCount; i++)
384 assert(expBegin->NotNegative());
385 exponents.push_back(
WindowSlider(*expBegin++, InversionIsFast(), 5));
386 exponents[i].FindNextWindow();
389 unsigned int expBitPosition = 0;
395 bool baseAdded =
false;
396 for (i=0; i<expCount; i++)
398 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
402 bases.push_back(rd.P);
406 exponentWindows[i].push_back(exponents[i].expWindow);
407 baseIndices[i].push_back((word32)bases.size()-1);
408 negateBase[i].push_back(exponents[i].negateNext);
410 exponents[i].FindNextWindow();
412 notDone = notDone || !exponents[i].finished;
423 ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
424 for (i=0; i<bases.size(); i++)
426 if (bases[i].z.NotZero())
428 bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
429 bases[i].z = GetField().Square(bases[i].z);
430 bases[i].x = GetField().Multiply(bases[i].x, bases[i].z);
431 bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
435 std::vector<BaseAndExponent<Point, Integer> > finalCascade;
436 for (i=0; i<expCount; i++)
438 finalCascade.resize(baseIndices[i].size());
439 for (
unsigned int j=0; j<baseIndices[i].size(); j++)
441 ProjectivePoint &base = bases[baseIndices[i][j]];
443 finalCascade[j].base.identity =
true;
446 finalCascade[j].base.identity =
false;
447 finalCascade[j].base.x = base.x;
448 if (negateBase[i][j])
449 finalCascade[j].base.y = GetField().Inverse(base.y);
451 finalCascade[j].base.y = base.y;
453 finalCascade[j].exponent =
Integer(Integer::POSITIVE, 0, exponentWindows[i][j]);
455 results[i] = GeneralCascadeMultiplication(*
this, finalCascade.begin(), finalCascade.end());
461 if (!GetField().IsMontgomeryRepresentation())
463 ECP ecpmr(*
this,
true);
465 return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));