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)
196 const Integer x = P.x * IdentityToInteger(!P.identity);
197 const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
198 const Integer z = 1 * IdentityToInteger(!P.identity);
200 ProjectivePoint p(x, y, z), r;
204 Z3 = field.
Add(t0, t0);
205 Z3 = field.
Add(Z3, Z3);
206 Z3 = field.
Add(Z3, Z3);
211 Y3 = field.
Add(t0, t2);
213 t1 = field.
Add(t2, t2);
214 t2 = field.
Add(t1, t2);
217 Y3 = field.
Add(X3, Y3);
220 X3 = field.
Add(X3, X3);
226 R.x = X3*Z3.NotZero();
227 R.y = Y3*Z3.NotZero();
228 R.identity = Z3.IsZero();
234 else if (m_alpha == A_Star)
238 const Integer x = P.x * IdentityToInteger(!P.identity);
239 const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
240 const Integer z = 1 * IdentityToInteger(!P.identity);
242 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();
278 bool identity = !!(P.identity + (P.y == field.
Identity()));
288 R.x *= IdentityToInteger(!identity);
289 R.y *= IdentityToInteger(!identity);
290 R.identity = identity;
302 const Integer x1 = P.x * IdentityToInteger(!P.identity);
303 const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
304 const Integer z1 = 1 * IdentityToInteger(!P.identity);
306 const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
307 const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
308 const Integer z2 = 1 * IdentityToInteger(!Q.identity);
310 ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;
318 t4 = field.
Add(t0, t1);
320 t4 = field.
Add(Y1, Z1);
321 X3 = field.
Add(Y2, Z2);
323 X3 = field.
Add(t1, t2);
325 X3 = field.
Add(X1, Z1);
326 Y3 = field.
Add(X2, Z2);
328 Y3 = field.
Add(t0, t2);
332 Z3 = field.
Add(X3, X3);
333 X3 = field.
Add(X3, Z3);
335 X3 = field.
Add(t1, X3);
337 t1 = field.
Add(t2, t2);
338 t2 = field.
Add(t1, t2);
341 t1 = field.
Add(Y3, Y3);
342 Y3 = field.
Add(t1, Y3);
343 t1 = field.
Add(t0, t0);
344 t0 = field.
Add(t1, t0);
349 Y3 = field.
Add(Y3, t2);
354 Z3 = field.
Add(Z3, t1);
360 R.x = X3*Z3.NotZero();
361 R.y = Y3*Z3.NotZero();
362 R.identity = Z3.IsZero();
366 else if (m_alpha == A_0)
370 const Integer x1 = P.x * IdentityToInteger(!P.identity);
371 const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
372 const Integer z1 = 1 * IdentityToInteger(!P.identity);
374 const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
375 const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
376 const Integer z2 = 1 * IdentityToInteger(!Q.identity);
378 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();
412 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;
433 t4 = field.
Add(t0, t1);
435 t4 = field.
Add(X1, Z1);
438 t5 = field.
Add(t0, t2);
440 t5 = field.
Add(Y1, Z1);
441 X3 = field.
Add(Y2, Z2);
443 X3 = field.
Add(t1, t2);
447 Z3 = field.
Add(X3, Z3);
449 Z3 = field.
Add(t1, Z3);
451 t1 = field.
Add(t0, t0);
452 t1 = field.
Add(t1, t0);
455 t1 = field.
Add(t1, t2);
458 t4 = field.
Add(t4, t2);
460 Y3 = field.
Add(Y3, t0);
466 Z3 = field.
Add(Z3, t0);
472 R.x = X3*Z3.NotZero();
473 R.y = Y3*Z3.NotZero();
474 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);
512 R.x = R.x * IdentityToInteger(!identity);
513 R.y = R.y * IdentityToInteger(!identity);
514 R.identity = identity;
541 ANONYMOUS_NAMESPACE_END
545 ECP::
ECP(const
ECP &ecp,
bool convertToMontgomeryRepresentation)
547 if (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation())
550 m_a = GetField().ConvertIn(ecp.m_a);
551 m_b = GetField().ConvertIn(ecp.m_b);
558 : m_fieldPtr(new
Field(bt))
591 if (encodedPointLen < 1 || !bt.
Get(type))
608 P.x.Decode(bt, GetField().MaxElementByteLength());
609 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
616 if ((type & 1) != P.y.GetBit(0))
643 bt.
Put((
byte)(2U + P.y.GetBit(0)));
644 P.x.Encode(bt, GetField().MaxElementByteLength());
683 bool pass = p.
IsOdd();
687 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
700 (!x.IsNegative() && x<p && !y.
IsNegative() && y<p
701 && !(((x*x+m_a)*x+m_b-y*y)%p));
706 if (P.identity && Q.identity)
709 if (P.identity && !Q.identity)
712 if (!P.identity && Q.identity)
715 return (GetField().
Equal(P.x,Q.x) && GetField().
Equal(P.y,Q.y));
720 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
722 #elif defined(CRYPTOPP_CXX11_STATIC_INIT)
736 m_R.identity =
false;
738 m_R.y = GetField().
Inverse(P.y);
745 AdditionFunction add(GetField(), m_a, m_b, m_R);
746 return (m_R = add(P, Q));
749 const ECP::Point& ECP::Double(
const Point &P)
const
751 AdditionFunction add(GetField(), m_a, m_b, m_R);
752 return (m_R = add(P));
755 template <
class T,
class Iterator>
void ParallelInvert(
const AbstractRing<T> &ring, Iterator begin, Iterator end)
757 size_t n = end-begin;
762 std::vector<T> vec((n+1)/2);
766 for (i=0, it=begin; i<n/2; i++, it+=2)
767 vec[i] = ring.
Multiply(*it, *(it+1));
771 ParallelInvert(ring, vec.begin(), vec.end());
773 for (i=0, it=begin; i<n/2; i++, it+=2)
784 *(it+1) = ring.
Multiply(*(it+1), vec[i]);
798 CRYPTOPP_UNUSED(m_b);
827 sixteenY4 = mr.
Square(fourY2);
833 Integer sixteenY4, aZ4, twoY, fourY2, S, M;
839 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
840 Integer& operator*() {
return it->z;}
841 int operator-(
ZIterator it2) {
return int(it-it2.it);}
843 ZIterator& operator+=(
int i) {it+=i;
return *
this;}
844 std::vector<ProjectivePoint>::iterator it;
853 ECP::SimultaneousMultiply(&result, P, &k, 1);
859 if (!GetField().IsMontgomeryRepresentation())
861 ECP ecpmr(*
this,
true);
864 for (
unsigned int i=0; i<expCount; i++)
865 results[i] = FromMontgomery(mr, results[i]);
870 std::vector<ProjectivePoint> bases;
871 std::vector<WindowSlider> exponents;
872 exponents.reserve(expCount);
873 std::vector<std::vector<word32> > baseIndices(expCount);
874 std::vector<std::vector<bool> > negateBase(expCount);
875 std::vector<std::vector<word32> > exponentWindows(expCount);
878 for (i=0; i<expCount; i++)
881 exponents.push_back(
WindowSlider(*expBegin++, InversionIsFast(), 5));
882 exponents[i].FindNextWindow();
885 unsigned int expBitPosition = 0;
891 bool baseAdded =
false;
892 for (i=0; i<expCount; i++)
894 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
898 bases.push_back(rd.P);
902 exponentWindows[i].push_back(exponents[i].expWindow);
903 baseIndices[i].push_back((word32)bases.size()-1);
904 negateBase[i].push_back(exponents[i].negateNext);
906 exponents[i].FindNextWindow();
908 notDone = notDone || !exponents[i].finished;
920 for (i=0; i<bases.size(); i++)
922 if (bases[i].z.NotZero())
924 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
925 bases[i].z = GetField().
Square(bases[i].z);
926 bases[i].x = GetField().
Multiply(bases[i].x, bases[i].z);
927 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
931 std::vector<BaseAndExponent<Point, Integer> > finalCascade;
932 for (i=0; i<expCount; i++)
934 finalCascade.resize(baseIndices[i].size());
935 for (
unsigned int j=0; j<baseIndices[i].size(); j++)
937 ProjectivePoint &base = bases[baseIndices[i][j]];
939 finalCascade[j].base.identity =
true;
942 finalCascade[j].base.identity =
false;
943 finalCascade[j].base.x = base.x;
944 if (negateBase[i][j])
945 finalCascade[j].base.y = GetField().
Inverse(base.y);
947 finalCascade[j].base.y = base.y;
951 results[i] = GeneralCascadeMultiplication(*
this, finalCascade.begin(), finalCascade.end());
957 if (!GetField().IsMontgomeryRepresentation())
959 ECP ecpmr(*
this,
true);
961 return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));