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)
526 m_a = GetField().ConvertIn(ecp.m_a);
527 m_b = GetField().ConvertIn(ecp.m_b);
534 : m_fieldPtr(new Field(bt))
537 GetField().BERDecodeElement(seq, m_a);
538 GetField().BERDecodeElement(seq, m_b);
540 if (!seq.EndReached())
551 GetField().DEREncode(bt);
553 GetField().DEREncodeElement(seq, m_a);
554 GetField().DEREncodeElement(seq, m_b);
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))
602 unsigned int len = GetField().MaxElementByteLength();
619 bt.
Put(2 + P.y.GetBit(0));
620 P.x.Encode(bt, GetField().MaxElementByteLength());
624 unsigned int len = 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();
660 pass = pass && !m_a.IsNegative() && m_a<p && !m_b.
IsNegative() && m_b<p;
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));
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);
796 sixteenY4 = mr.
Square(fourY2);
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;
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++)
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));
const Integer & Double(const Integer &a) const
Doubles an element in the ring.
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
bool NotZero() const
Determines if the Integer is non-0.
inline ::Integer operator*(const ::Integer &a, const ::Integer &b)
bool Equal(const Integer &a, const Integer &b) const
Compare two elements for equality.
const Integer & Square(const Integer &a) const
Square an element in the ring.
const Integer & Divide(const Integer &a, const Integer &b) const
Divides elements in the ring.
Restricts the instantiation of a class to one static object without locks.
virtual const Element & Multiply(const Element &a, const Element &b) const =0
Multiplies elements in the group.
Classes for Elliptic Curves over prime fields.
const Point & Identity() const
Provides the Identity element.
Elliptic Curve over GF(p), where p is prime.
virtual Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.
const Point & Inverse(const Point &P) const
Inverts the element in the group.
const Integer & Subtract(const Integer &a, const Integer &b) const
Subtracts elements in the ring.
const Integer & MultiplicativeInverse(const Integer &a) const
Calculate the multiplicative inverse of an element in the ring.
bool IsNegative() const
Determines if the Integer is negative.
Ring of congruence classes modulo n.
Interface for random number generators.
bool IsPositive() const
Determines if the Integer is positive.
bool NotNegative() const
Determines if the Integer is non-negative.
virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
const Integer & Add(const Integer &a, const Integer &b) const
Adds elements in the ring.
static const Integer & One()
Integer representing 1.
const Integer & Identity() const
Provides the Identity element.
Copy input to a memory buffer.
size_t BERDecodeOctetString(BufferedTransformation &bt, SecByteBlock &str)
BER decode octet string.
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
Point ScalarMultiply(const Point &P, const Integer &k) const
Performs a scalar multiplication.
bool Equal(const Point &P, const Point &Q) const
Compare two elements for equality.
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a prime number.
virtual const Element & MultiplicativeInverse(const Element &a) const =0
Calculate the multiplicative inverse of an element in the group.
Multiple precision integer with arithmetic operations.
OID operator+(const OID &lhs, unsigned long rhs)
Append a value to an OID.
const Integer & GetModulus() const
Retrieves the modulus.
const Integer & Half(const Integer &a) const
TODO.
Point CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
TODO.
String-based implementation of Store interface.
void BERDecodeError()
Raises a BERDecodeErr.
virtual Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
Classes and functions for working with ANS.1 objects.
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Implementation of BufferedTransformation's attachment interface.
Classes and functions for number theoretic operations.
virtual void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Multiplies a base to multiple exponents in a group.
const Point & Double(const Point &P) const
Doubles an element in the group.
Performs modular arithmetic in Montgomery representation for increased speed.
const Point & Add(const Point &P, const Point &Q) const
Adds elements in the group.
void Decode(const byte *input, size_t inputLen, Signedness sign=UNSIGNED)
Decode from big-endian byte array.
size_t DEREncodeOctetString(BufferedTransformation &bt, const byte *str, size_t strLen)
DER encode octet string.
Multiple precision integer with arithmetic operations.
size_t BERDecodeBitString(BufferedTransformation &bt, SecByteBlock &str, unsigned int &unusedBits)
DER decode bit string.
Class file for performing modular arithmetic.
Crypto++ library namespace.
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
const Integer & MultiplicativeIdentity() const
Retrieves the multiplicative identity.
void SimultaneousMultiply(Point *results, const Point &base, const Integer *exponents, unsigned int exponentsCount) const
Multiplies a base to multiple exponents in a group.
size_type size() const
Provides the count of elements in the SecBlock.
the value is positive or 0
bool IsOdd() const
Determines if the Integer is odd parity.
virtual bool IsMontgomeryRepresentation() const
Retrieves the representation.