5 #ifndef CRYPTOPP_IMPORTS
13 #include "algebra.cpp"
15 ANONYMOUS_NAMESPACE_BEGIN
18 using CryptoPP::Integer;
19 using CryptoPP::ModularArithmetic;
21 #if defined(HAVE_GCC_INIT_PRIORITY)
22 #define INIT_ATTRIBUTE __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 50)))
24 #elif defined(HAVE_MSC_INIT_PRIORITY)
25 #pragma warning(disable: 4075)
26 #pragma init_seg(".CRT$XCU")
28 #pragma warning(default: 4075)
29 #elif defined(HAVE_XLC_INIT_PRIORITY)
44 inline Integer IdentityToInteger(
bool val)
49 struct ProjectivePoint
58 ANONYMOUS_NAMESPACE_END
62 ECP::ECP(
const ECP &ecp,
bool convertToMontgomeryRepresentation)
75 : m_fieldPtr(new Field(bt))
78 GetField().BERDecodeElement(seq, m_a);
79 GetField().BERDecodeElement(seq, m_b);
81 if (!seq.EndReached())
108 if (encodedPointLen < 1 || !bt.
Get(type))
125 P.x.Decode(bt, GetField().MaxElementByteLength());
126 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
133 if ((type & 1) != P.y.GetBit(0))
160 bt.
Put((
byte)(2U + P.y.GetBit(0)));
161 P.x.Encode(bt, GetField().MaxElementByteLength());
172 void ECP::EncodePoint(
byte *encodedPoint,
const Point &P,
bool compressed)
const
200 bool pass = p.
IsOdd();
204 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
214 const FieldElement &x = P.x, &y = P.y;
217 (!x.IsNegative() && x<p && !y.
IsNegative() && y<p
218 && !(((x*x+m_a)*x+m_b-y*y)%p));
221 bool ECP::Equal(
const Point &P,
const Point &Q)
const
223 if (P.identity && Q.identity)
226 if (P.identity && !Q.identity)
229 if (!P.identity && Q.identity)
232 return (GetField().
Equal(P.x,Q.x) && GetField().
Equal(P.y,Q.y));
237 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
239 #elif defined(CRYPTOPP_CXX11_STATIC_INIT)
253 m_R.identity =
false;
255 m_R.y = GetField().
Inverse(P.y);
262 if (P.identity)
return Q;
263 if (Q.identity)
return P;
264 if (GetField().
Equal(P.x, Q.x))
265 return GetField().
Equal(P.y, Q.y) ? Double(P) : Identity();
267 FieldElement t = GetField().
Subtract(Q.y, P.y);
270 m_R.y = GetField().
Subtract(GetField().Multiply(t, GetField().
Subtract(P.x, x)), P.y);
273 m_R.identity =
false;
277 const ECP::Point& ECP::Double(
const Point &P)
const
279 if (P.identity || P.y==GetField().Identity())
return Identity();
281 FieldElement t = GetField().
Square(P.x);
282 t = GetField().
Add(GetField().
Add(GetField().Double(t), t), m_a);
283 t = GetField().
Divide(t, GetField().Double(P.y));
285 m_R.y = GetField().
Subtract(GetField().Multiply(t, GetField().
Subtract(P.x, x)), P.y);
288 m_R.identity =
false;
292 template <
class T,
class Iterator>
void ParallelInvert(
const AbstractRing<T> &ring, Iterator begin, Iterator end)
294 size_t n = end-begin;
299 std::vector<T> vec((n+1)/2);
303 for (i=0, it=begin; i<n/2; i++, it+=2)
304 vec[i] = ring.
Multiply(*it, *(it+1));
308 ParallelInvert(ring, vec.begin(), vec.end());
310 for (i=0, it=begin; i<n/2; i++, it+=2)
321 *(it+1) = ring.
Multiply(*(it+1), vec[i]);
329 class ProjectiveDoubling
335 CRYPTOPP_UNUSED(m_b);
338 sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity();
339 aZ4 = P.z = mr.Identity();
345 sixteenY4 = P.z = mr.MultiplicativeIdentity();
352 twoY = mr.Double(P.y);
353 P.z = mr.Multiply(P.z, twoY);
354 fourY2 = mr.Square(twoY);
355 S = mr.Multiply(fourY2, P.x);
356 aZ4 = mr.Multiply(aZ4, sixteenY4);
358 M = mr.Add(mr.Add(mr.Double(M), M), aZ4);
363 P.y = mr.Multiply(M, S);
364 sixteenY4 = mr.Square(fourY2);
365 mr.Reduce(P.y, mr.Half(sixteenY4));
370 Integer sixteenY4, aZ4, twoY, fourY2, S, M;
376 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
378 int operator-(ZIterator it2) {
return int(it-it2.it);}
379 ZIterator
operator+(
int i) {
return ZIterator(it+i);}
380 ZIterator& operator+=(
int i) {it+=i;
return *
this;}
381 std::vector<ProjectivePoint>::iterator it;
390 ECP::SimultaneousMultiply(&result, P, &k, 1);
396 if (!GetField().IsMontgomeryRepresentation())
398 ECP ecpmr(*
this,
true);
401 for (
unsigned int i=0; i<expCount; i++)
402 results[i] = FromMontgomery(mr, results[i]);
406 ProjectiveDoubling rd(GetField(), m_a, m_b, P);
407 std::vector<ProjectivePoint> bases;
408 std::vector<WindowSlider> exponents;
409 exponents.reserve(expCount);
410 std::vector<std::vector<word32> > baseIndices(expCount);
411 std::vector<std::vector<bool> > negateBase(expCount);
412 std::vector<std::vector<word32> > exponentWindows(expCount);
415 for (i=0; i<expCount; i++)
418 exponents.push_back(
WindowSlider(*expBegin++, InversionIsFast(), 5));
419 exponents[i].FindNextWindow();
422 unsigned int expBitPosition = 0;
428 bool baseAdded =
false;
429 for (i=0; i<expCount; i++)
431 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
435 bases.push_back(rd.P);
439 exponentWindows[i].push_back(exponents[i].expWindow);
440 baseIndices[i].push_back((
word32)bases.size()-1);
441 negateBase[i].push_back(exponents[i].negateNext);
443 exponents[i].FindNextWindow();
445 notDone = notDone || !exponents[i].finished;
456 ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
457 for (i=0; i<bases.size(); i++)
459 if (bases[i].z.NotZero())
461 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
462 bases[i].z = GetField().
Square(bases[i].z);
463 bases[i].x = GetField().
Multiply(bases[i].x, bases[i].z);
464 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
468 std::vector<BaseAndExponent<Point, Integer> > finalCascade;
469 for (i=0; i<expCount; i++)
471 finalCascade.resize(baseIndices[i].size());
472 for (
unsigned int j=0; j<baseIndices[i].size(); j++)
474 ProjectivePoint &base = bases[baseIndices[i][j]];
476 finalCascade[j].base.identity =
true;
479 finalCascade[j].base.identity =
false;
480 finalCascade[j].base.x = base.x;
481 if (negateBase[i][j])
482 finalCascade[j].base.y = GetField().
Inverse(base.y);
484 finalCascade[j].base.y = base.y;
488 results[i] = GeneralCascadeMultiplication(*
this, finalCascade.begin(), finalCascade.end());
494 if (!GetField().IsMontgomeryRepresentation())
496 ECP ecpmr(*
this,
true);
498 return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));