5 #ifndef CRYPTOPP_IMPORTS
13 #include "algebra.cpp"
17 ANONYMOUS_NAMESPACE_BEGIN
29 inline Integer IdentityToInteger(
bool val)
34 struct ProjectivePoint
46 struct AdditionFunction
48 explicit AdditionFunction(
const ECP::Field& field,
95 AdditionFunction::AdditionFunction(
const ECP::Field& field,
97 : field(field), a(a), b(b), R(r), m_alpha(static_cast<Alpha>(0))
101 m_alpha = A_Montgomery;
109 else if (a == -3 || (a - field.
GetModulus()) == -3)
126 const Integer x = P.x * IdentityToInteger(!P.identity);
127 const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
128 const Integer z = 1 * IdentityToInteger(!P.identity);
130 ProjectivePoint p(x, y, z), r;
136 t3 = field.
Add(t3, t3);
138 Z3 = field.
Add(Z3, Z3);
141 X3 = field.
Add(Y3, Y3);
142 Y3 = field.
Add(X3, Y3);
144 Y3 = field.
Add(t1, Y3);
147 t3 = field.
Add(t2, t2);
148 t2 = field.
Add(t2, t3);
152 t3 = field.
Add(Z3, Z3);
153 Z3 = field.
Add(Z3, t3);
154 t3 = field.
Add(t0, t0);
155 t0 = field.
Add(t3, t0);
158 Y3 = field.
Add(Y3, t0);
160 t0 = field.
Add(t0, t0);
164 Z3 = field.
Add(Z3, Z3);
165 Z3 = field.
Add(Z3, Z3);
171 R.x = X3*Z3.NotZero();
172 R.y = Y3*Z3.NotZero();
173 R.identity = Z3.IsZero();
177 else if (m_alpha == A_0)
181 const Integer x = P.x * IdentityToInteger(!P.identity);
182 const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
183 const Integer z = 1 * IdentityToInteger(!P.identity);
185 ProjectivePoint p(x, y, z), r;
189 Z3 = field.
Add(t0, t0);
190 Z3 = field.
Add(Z3, Z3);
191 Z3 = field.
Add(Z3, Z3);
196 Y3 = field.
Add(t0, t2);
198 t1 = field.
Add(t2, t2);
199 t2 = field.
Add(t1, t2);
202 Y3 = field.
Add(X3, Y3);
205 X3 = field.
Add(X3, X3);
211 R.x = X3*Z3.NotZero();
212 R.y = Y3*Z3.NotZero();
213 R.identity = Z3.IsZero();
217 else if (m_alpha == A_Star)
221 const Integer x = P.x * IdentityToInteger(!P.identity);
222 const Integer y = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
223 const Integer z = 1 * IdentityToInteger(!P.identity);
225 ProjectivePoint p(x, y, z), r;
229 Z3 = field.
Add(t0, t0);
230 Z3 = field.
Add(Z3, Z3);
231 Z3 = field.
Add(Z3, Z3);
236 Y3 = field.
Add(t0, t2);
238 t1 = field.
Add(t2, t2);
239 t2 = field.
Add(t1, t2);
242 Y3 = field.
Add(X3, Y3);
245 X3 = field.
Add(X3, X3);
251 R.x = X3*Z3.NotZero();
252 R.y = Y3*Z3.NotZero();
253 R.identity = Z3.IsZero();
260 bool identity = !!(P.identity + (P.y == field.
Identity()));
270 R.x *= IdentityToInteger(!identity);
271 R.y *= IdentityToInteger(!identity);
272 R.identity = identity;
284 const Integer x1 = P.x * IdentityToInteger(!P.identity);
285 const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
286 const Integer z1 = 1 * IdentityToInteger(!P.identity);
288 const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
289 const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
290 const Integer z2 = 1 * IdentityToInteger(!Q.identity);
292 ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;
300 t4 = field.
Add(t0, t1);
302 t4 = field.
Add(Y1, Z1);
303 X3 = field.
Add(Y2, Z2);
305 X3 = field.
Add(t1, t2);
307 X3 = field.
Add(X1, Z1);
308 Y3 = field.
Add(X2, Z2);
310 Y3 = field.
Add(t0, t2);
314 Z3 = field.
Add(X3, X3);
315 X3 = field.
Add(X3, Z3);
317 X3 = field.
Add(t1, X3);
319 t1 = field.
Add(t2, t2);
320 t2 = field.
Add(t1, t2);
323 t1 = field.
Add(Y3, Y3);
324 Y3 = field.
Add(t1, Y3);
325 t1 = field.
Add(t0, t0);
326 t0 = field.
Add(t1, t0);
331 Y3 = field.
Add(Y3, t2);
336 Z3 = field.
Add(Z3, t1);
342 R.x = X3*Z3.NotZero();
343 R.y = Y3*Z3.NotZero();
344 R.identity = Z3.IsZero();
348 else if (m_alpha == A_0)
352 const Integer x1 = P.x * IdentityToInteger(!P.identity);
353 const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
354 const Integer z1 = 1 * IdentityToInteger(!P.identity);
356 const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
357 const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
358 const Integer z2 = 1 * IdentityToInteger(!Q.identity);
360 ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;
364 Z3 = field.
Add(t0, t0);
365 Z3 = field.
Add(Z3, Z3);
366 Z3 = field.
Add(Z3, Z3);
371 Y3 = field.
Add(t0, t2);
373 t1 = field.
Add(t2, t2);
374 t2 = field.
Add(t1, t2);
377 Y3 = field.
Add(X3, Y3);
380 X3 = field.
Add(X3, X3);
386 R.x = X3*Z3.NotZero();
387 R.y = Y3*Z3.NotZero();
388 R.identity = Z3.IsZero();
392 else if (m_alpha == A_Star)
396 const Integer x1 = P.x * IdentityToInteger(!P.identity);
397 const Integer y1 = P.y * IdentityToInteger(!P.identity) + 1 * IdentityToInteger(P.identity);
398 const Integer z1 = 1 * IdentityToInteger(!P.identity);
400 const Integer x2 = Q.x * IdentityToInteger(!Q.identity);
401 const Integer y2 = Q.y * IdentityToInteger(!Q.identity) + 1 * IdentityToInteger(Q.identity);
402 const Integer z2 = 1 * IdentityToInteger(!Q.identity);
404 ProjectivePoint p(x1, y1, z1), q(x2, y2, z2), r;
413 t4 = field.
Add(t0, t1);
415 t4 = field.
Add(X1, Z1);
418 t5 = field.
Add(t0, t2);
420 t5 = field.
Add(Y1, Z1);
421 X3 = field.
Add(Y2, Z2);
423 X3 = field.
Add(t1, t2);
427 Z3 = field.
Add(X3, Z3);
429 Z3 = field.
Add(t1, Z3);
431 t1 = field.
Add(t0, t0);
432 t1 = field.
Add(t1, t0);
435 t1 = field.
Add(t1, t2);
438 t4 = field.
Add(t4, t2);
440 Y3 = field.
Add(Y3, t0);
446 Z3 = field.
Add(Z3, t0);
452 R.x = X3*Z3.NotZero();
453 R.y = Y3*Z3.NotZero();
454 R.identity = Z3.IsZero();
461 bool return_Q = P.identity;
462 bool return_P = Q.identity;
463 bool double_P = field.
Equal(P.x, Q.x) && field.
Equal(P.y, Q.y);
464 bool identity = field.
Equal(P.x, Q.x) && !field.
Equal(P.y, Q.y);
467 identity = !!((double_P * (P.identity + (P.y == field.
Identity()))) + identity);
491 R.x = R.x * IdentityToInteger(!identity);
492 R.y = R.y * IdentityToInteger(!identity);
493 R.identity = identity;
521 ECP::ECP(
const ECP &ecp,
bool convertToMontgomeryRepresentation)
534 : m_fieldPtr(new Field(bt))
537 GetField().BERDecodeElement(seq, m_a);
538 GetField().BERDecodeElement(seq, m_b);
540 if (!seq.EndReached())
558 bool ECP::DecodePoint(
ECP::Point &P,
const byte *encodedPoint,
size_t encodedPointLen)
const
561 return DecodePoint(P, store, encodedPointLen);
567 if (encodedPointLen < 1 || !bt.
Get(type))
578 if (encodedPointLen != EncodedPointSize(
true))
584 P.x.Decode(bt, GetField().MaxElementByteLength());
585 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
587 if (Jacobi(P.y, p) !=1)
590 P.y = ModularSquareRoot(P.y, p);
592 if ((type & 1) != P.y.GetBit(0))
599 if (encodedPointLen != EncodedPointSize(
false))
619 bt.
Put(2 + P.y.GetBit(0));
620 P.x.Encode(bt, GetField().MaxElementByteLength());
631 void ECP::EncodePoint(
byte *encodedPoint,
const Point &P,
bool compressed)
const
633 ArraySink sink(encodedPoint, EncodedPointSize(compressed));
634 EncodePoint(sink, P, compressed);
635 assert(sink.TotalPutLength() == EncodedPointSize(compressed));
643 if (!DecodePoint(P, str, str.
size()))
651 EncodePoint(str, P, compressed);
659 bool pass = p.
IsOdd();
663 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
671 bool ECP::VerifyPoint(
const Point &P)
const
673 const FieldElement &x = P.x, &y = P.y;
676 (!x.IsNegative() && x<p && !y.
IsNegative() && y<p
677 && !(((x*x+m_a)*x+m_b-y*y)%p));
680 bool ECP::Equal(
const Point &P,
const Point &Q)
const
682 if (P.identity && Q.identity)
685 if (P.identity && !Q.identity)
688 if (!P.identity && Q.identity)
691 return (GetField().
Equal(P.x,Q.x) && GetField().
Equal(P.y,Q.y));
705 m_R.identity =
false;
707 m_R.y = GetField().
Inverse(P.y);
714 AdditionFunction add(GetField(), m_a, m_b, m_R);
715 return (m_R = add(P, Q));
718 const ECP::Point& ECP::Double(
const Point &P)
const
720 AdditionFunction add(GetField(), m_a, m_b, m_R);
721 return (m_R = add(P));
724 template <
class T,
class Iterator>
void ParallelInvert(
const AbstractRing<T> &ring, Iterator begin, Iterator end)
726 size_t n = end-begin;
731 std::vector<T> vec((n+1)/2);
735 for (i=0, it=begin; i<n/2; i++, it+=2)
736 vec[i] = ring.
Multiply(*it, *(it+1));
740 ParallelInvert(ring, vec.begin(), vec.end());
742 for (i=0, it=begin; i<n/2; i++, it+=2)
751 std::swap(*it, *(it+1));
753 *(it+1) = ring.
Multiply(*(it+1), vec[i]);
761 class ProjectiveDoubling
765 : mr(m_mr), firstDoubling(true), negated(false)
767 CRYPTOPP_UNUSED(m_b);
770 sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity();
771 aZ4 = P.z = mr.Identity();
777 sixteenY4 = P.z = mr.MultiplicativeIdentity();
784 twoY = mr.Double(P.y);
785 P.z = mr.Multiply(P.z, twoY);
786 fourY2 = mr.Square(twoY);
787 S = mr.Multiply(fourY2, P.x);
788 aZ4 = mr.Multiply(aZ4, sixteenY4);
790 M = mr.Add(mr.Add(mr.Double(M), M), aZ4);
795 P.y = mr.Multiply(M, S);
796 sixteenY4 = mr.Square(fourY2);
797 mr.Reduce(P.y, mr.Half(sixteenY4));
802 bool firstDoubling, negated;
803 Integer sixteenY4, aZ4, twoY, fourY2, S, M;
809 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
811 int operator-(ZIterator it2) {
return int(it-it2.it);}
812 ZIterator
operator+(
int i) {
return ZIterator(it+i);}
813 ZIterator& operator+=(
int i) {it+=i;
return *
this;}
814 std::vector<ProjectivePoint>::iterator it;
823 ECP::SimultaneousMultiply(&result, P, &k, 1);
829 if (!GetField().IsMontgomeryRepresentation())
831 ECP ecpmr(*
this,
true);
834 for (
unsigned int i=0; i<expCount; i++)
835 results[i] = FromMontgomery(mr, results[i]);
839 ProjectiveDoubling rd(GetField(), m_a, m_b, P);
840 std::vector<ProjectivePoint> bases;
841 std::vector<WindowSlider> exponents;
842 exponents.reserve(expCount);
843 std::vector<std::vector<word32> > baseIndices(expCount);
844 std::vector<std::vector<bool> > negateBase(expCount);
845 std::vector<std::vector<word32> > exponentWindows(expCount);
848 for (i=0; i<expCount; i++)
851 exponents.push_back(
WindowSlider(*expBegin++, InversionIsFast(), 5));
852 exponents[i].FindNextWindow();
855 unsigned int expBitPosition = 0;
861 bool baseAdded =
false;
862 for (i=0; i<expCount; i++)
864 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
868 bases.push_back(rd.P);
872 exponentWindows[i].push_back(exponents[i].expWindow);
873 baseIndices[i].push_back((word32)bases.size()-1);
874 negateBase[i].push_back(exponents[i].negateNext);
876 exponents[i].FindNextWindow();
878 notDone = notDone || !exponents[i].finished;
889 ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
890 for (i=0; i<bases.size(); i++)
892 if (bases[i].z.NotZero())
894 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
895 bases[i].z = GetField().
Square(bases[i].z);
896 bases[i].x = GetField().
Multiply(bases[i].x, bases[i].z);
897 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
901 std::vector<BaseAndExponent<Point, Integer> > finalCascade;
902 for (i=0; i<expCount; i++)
904 finalCascade.resize(baseIndices[i].size());
905 for (
unsigned int j=0; j<baseIndices[i].size(); j++)
907 ProjectivePoint &base = bases[baseIndices[i][j]];
909 finalCascade[j].base.identity =
true;
912 finalCascade[j].base.identity =
false;
913 finalCascade[j].base.x = base.x;
914 if (negateBase[i][j])
915 finalCascade[j].base.y = GetField().
Inverse(base.y);
917 finalCascade[j].base.y = base.y;
921 results[i] = GeneralCascadeMultiplication(*
this, finalCascade.begin(), finalCascade.end());
927 if (!GetField().IsMontgomeryRepresentation())
929 ECP ecpmr(*
this,
true);
931 return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));