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
61 struct AdditionFunction
63 explicit AdditionFunction(
const ECP::Field& field,
110 AdditionFunction::AdditionFunction(
const ECP::Field& field,
112 : field(field), a(a), b(b), R(r), m_alpha(static_cast<Alpha>(0))
116 m_alpha = A_Montgomery;
124 else if (a == -3 || (a - field.
GetModulus()) == -3)
141 const Integer x = P.x * IdentityToInteger(!P.identity);
142 const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
143 const Integer z = 1 * IdentityToInteger(!P.identity);
145 ProjectivePoint p(x, y, z), r;
151 t3 = field.
Add(t3, t3);
153 Z3 = field.
Add(Z3, Z3);
156 X3 = field.
Add(Y3, Y3);
157 Y3 = field.
Add(X3, Y3);
159 Y3 = field.
Add(t1, Y3);
162 t3 = field.
Add(t2, t2);
163 t2 = field.
Add(t2, t3);
167 t3 = field.
Add(Z3, Z3);
168 Z3 = field.
Add(Z3, t3);
169 t3 = field.
Add(t0, t0);
170 t0 = field.
Add(t3, t0);
173 Y3 = field.
Add(Y3, t0);
175 t0 = field.
Add(t0, t0);
179 Z3 = field.
Add(Z3, Z3);
180 Z3 = field.
Add(Z3, Z3);
186 R.x = X3*Z3.NotZero();
187 R.y = Y3*Z3.NotZero();
188 R.identity = Z3.IsZero();
192 else if (m_alpha == A_0)
198 const Integer x = P.x * IdentityToInteger(!P.identity);
199 const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
200 const Integer z = 1 * IdentityToInteger(!P.identity);
202 ProjectivePoint p(x, y, z), r;
205 Z3 = field.
Add(t0, t0);
206 Z3 = field.
Add(Z3, Z3);
207 Z3 = field.
Add(Z3, Z3);
212 Y3 = field.
Add(t0, t2);
214 t1 = field.
Add(t2, t2);
215 t2 = field.
Add(t1, t2);
218 Y3 = field.
Add(X3, Y3);
221 X3 = field.
Add(X3, X3);
227 R.x = X3*Z3.NotZero();
228 R.y = Y3*Z3.NotZero();
229 R.identity = Z3.IsZero();
233 else if (m_alpha == A_Star)
239 const Integer x = P.x * IdentityToInteger(!P.identity);
240 const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
241 const Integer z = 1 * IdentityToInteger(!P.identity);
243 ProjectivePoint p(x, y, z), r;
246 Z3 = field.
Add(t0, t0);
247 Z3 = field.
Add(Z3, Z3);
248 Z3 = field.
Add(Z3, Z3);
253 Y3 = field.
Add(t0, t2);
255 t1 = field.
Add(t2, t2);
256 t2 = field.
Add(t1, t2);
259 Y3 = field.
Add(X3, Y3);
262 X3 = field.
Add(X3, X3);
268 R.x = X3*Z3.NotZero();
269 R.y = Y3*Z3.NotZero();
270 R.identity = Z3.IsZero();
277 bool identity = !!(P.identity + (P.y == field.
Identity()));
287 R.x *= IdentityToInteger(!identity);
288 R.y *= IdentityToInteger(!identity);
289 R.identity = identity;
301 const Integer x1 = P.x * IdentityToInteger(!P.identity);
302 const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
303 const Integer z1 = 1 * IdentityToInteger(!P.identity);
305 const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
306 const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
307 const Integer z2 = 1 * IdentityToInteger(!Q.identity);
309 ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;
317 t4 = field.
Add(t0, t1);
319 t4 = field.
Add(Y1, Z1);
320 X3 = field.
Add(Y2, Z2);
322 X3 = field.
Add(t1, t2);
324 X3 = field.
Add(X1, Z1);
325 Y3 = field.
Add(X2, Z2);
327 Y3 = field.
Add(t0, t2);
331 Z3 = field.
Add(X3, X3);
332 X3 = field.
Add(X3, Z3);
334 X3 = field.
Add(t1, X3);
336 t1 = field.
Add(t2, t2);
337 t2 = field.
Add(t1, t2);
340 t1 = field.
Add(Y3, Y3);
341 Y3 = field.
Add(t1, Y3);
342 t1 = field.
Add(t0, t0);
343 t0 = field.
Add(t1, t0);
348 Y3 = field.
Add(Y3, t2);
353 Z3 = field.
Add(Z3, t1);
359 R.x = X3*Z3.NotZero();
360 R.y = Y3*Z3.NotZero();
361 R.identity = Z3.IsZero();
365 else if (m_alpha == A_0)
371 const Integer x1 = P.x * IdentityToInteger(!P.identity);
372 const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
373 const Integer z1 = 1 * IdentityToInteger(!P.identity);
375 const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
376 const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
377 const Integer z2 = 1 * IdentityToInteger(!Q.identity);
379 ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;
382 Z3 = field.
Add(t0, t0);
383 Z3 = field.
Add(Z3, Z3);
384 Z3 = field.
Add(Z3, Z3);
389 Y3 = field.
Add(t0, t2);
391 t1 = field.
Add(t2, t2);
392 t2 = field.
Add(t1, t2);
395 Y3 = field.
Add(X3, Y3);
398 X3 = field.
Add(X3, X3);
404 R.x = X3*Z3.NotZero();
405 R.y = Y3*Z3.NotZero();
406 R.identity = Z3.IsZero();
410 else if (m_alpha == A_Star)
416 const Integer x1 = P.x * IdentityToInteger(!P.identity);
417 const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
418 const Integer z1 = 1 * IdentityToInteger(!P.identity);
420 const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
421 const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
422 const Integer z2 = 1 * IdentityToInteger(!Q.identity);
424 ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;
432 t4 = field.
Add(t0, t1);
434 t4 = field.
Add(X1, Z1);
437 t5 = field.
Add(t0, t2);
439 t5 = field.
Add(Y1, Z1);
440 X3 = field.
Add(Y2, Z2);
442 X3 = field.
Add(t1, t2);
446 Z3 = field.
Add(X3, Z3);
448 Z3 = field.
Add(t1, Z3);
450 t1 = field.
Add(t0, t0);
451 t1 = field.
Add(t1, t0);
454 t1 = field.
Add(t1, t2);
457 t4 = field.
Add(t4, t2);
459 Y3 = field.
Add(Y3, t0);
465 Z3 = field.
Add(Z3, t0);
471 R.x = X3*Z3.NotZero();
472 R.y = Y3*Z3.NotZero();
473 R.identity = Z3.IsZero();
482 bool return_Q = P.identity;
483 bool return_P = Q.identity;
484 bool double_P = field.
Equal(P.x, Q.x) && field.
Equal(P.y, Q.y);
485 bool identity = field.
Equal(P.x, Q.x) && !field.
Equal(P.y, Q.y);
488 identity = !!((double_P * (P.identity + (P.y == field.
Identity()))) + identity);
511 R.x = R.x * IdentityToInteger(!identity);
512 R.y = R.y * IdentityToInteger(!identity);
513 R.identity = identity;
540 ANONYMOUS_NAMESPACE_END
544 ECP::
ECP(const
ECP &ecp,
bool convertToMontgomeryRepresentation)
546 if (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation())
549 m_a = GetField().ConvertIn(ecp.m_a);
550 m_b = GetField().ConvertIn(ecp.m_b);
557 : m_fieldPtr(new
Field(bt))
563 if (!seq.EndReached())
590 if (encodedPointLen < 1 || !bt.
Get(type))
607 P.x.Decode(bt, GetField().MaxElementByteLength());
608 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
615 if ((type & 1) != P.y.GetBit(0))
642 bt.
Put((
byte)(2U + P.y.GetBit(0)));
643 P.x.Encode(bt, GetField().MaxElementByteLength());
682 bool pass = p.
IsOdd();
686 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
699 (!x.IsNegative() && x<p && !y.
IsNegative() && y<p
700 && !(((x*x+m_a)*x+m_b-y*y)%p));
705 if (P.identity && Q.identity)
708 if (P.identity && !Q.identity)
711 if (!P.identity && Q.identity)
714 return (GetField().
Equal(P.x,Q.x) && GetField().
Equal(P.y,Q.y));
719 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
721 #elif defined(CRYPTOPP_CXX11_DYNAMIC_INIT)
735 m_R.identity =
false;
737 m_R.y = GetField().
Inverse(P.y);
744 AdditionFunction add(GetField(), m_a, m_b, m_R);
745 return (m_R = add(P, Q));
750 AdditionFunction add(GetField(), m_a, m_b, m_R);
751 return (m_R = add(P));
754 template <
class T,
class Iterator>
void ParallelInvert(
const AbstractRing<T> &ring, Iterator begin, Iterator end)
756 size_t n = end-begin;
761 std::vector<T> vec((n+1)/2);
765 for (i=0, it=begin; i<n/2; i++, it+=2)
766 vec[i] = ring.
Multiply(*it, *(it+1));
770 ParallelInvert(ring, vec.begin(), vec.end());
772 for (i=0, it=begin; i<n/2; i++, it+=2)
781 std::swap(*it, *(it+1));
783 *(it+1) = ring.
Multiply(*(it+1), vec[i]);
797 CRYPTOPP_UNUSED(m_b);
826 sixteenY4 = mr.
Square(fourY2);
832 Integer sixteenY4, aZ4, twoY, fourY2, S, M;
838 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
839 Integer& operator*() {
return it->z;}
840 int operator-(
ZIterator it2) {
return int(it-it2.it);}
842 ZIterator& operator+=(
int i) {it+=i;
return *
this;}
843 std::vector<ProjectivePoint>::iterator it;
858 if (!GetField().IsMontgomeryRepresentation())
860 ECP ecpmr(*
this,
true);
863 for (
unsigned int i=0; i<expCount; i++)
864 results[i] = FromMontgomery(mr, results[i]);
869 std::vector<ProjectivePoint> bases;
870 std::vector<WindowSlider> exponents;
871 exponents.reserve(expCount);
872 std::vector<std::vector<word32> > baseIndices(expCount);
873 std::vector<std::vector<bool> > negateBase(expCount);
874 std::vector<std::vector<word32> > exponentWindows(expCount);
877 for (i=0; i<expCount; i++)
880 exponents.push_back(
WindowSlider(*expBegin++, InversionIsFast(), 5));
881 exponents[i].FindNextWindow();
884 unsigned int expBitPosition = 0;
890 bool baseAdded =
false;
891 for (i=0; i<expCount; i++)
893 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
897 bases.push_back(rd.P);
901 exponentWindows[i].push_back(exponents[i].expWindow);
902 baseIndices[i].push_back((word32)bases.size()-1);
903 negateBase[i].push_back(exponents[i].negateNext);
905 exponents[i].FindNextWindow();
907 notDone = notDone || !exponents[i].finished;
919 for (i=0; i<bases.size(); i++)
921 if (bases[i].z.NotZero())
923 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
924 bases[i].z = GetField().
Square(bases[i].z);
925 bases[i].x = GetField().
Multiply(bases[i].x, bases[i].z);
926 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
930 std::vector<BaseAndExponent<Point, Integer> > finalCascade;
931 for (i=0; i<expCount; i++)
933 finalCascade.resize(baseIndices[i].size());
934 for (
unsigned int j=0; j<baseIndices[i].size(); j++)
936 ProjectivePoint &base = bases[baseIndices[i][j]];
938 finalCascade[j].base.identity =
true;
941 finalCascade[j].base.identity =
false;
942 finalCascade[j].base.x = base.x;
943 if (negateBase[i][j])
944 finalCascade[j].base.y = GetField().
Inverse(base.y);
946 finalCascade[j].base.y = base.y;
950 results[i] = GeneralCascadeMultiplication(*
this, finalCascade.begin(), finalCascade.end());
956 if (!GetField().IsMontgomeryRepresentation())
958 ECP ecpmr(*
this,
true);
960 return FromMontgomery(mr, ecpmr.
CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));