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())
567 if (encodedPointLen < 1 || !bt.
Get(type))
584 P.x.Decode(bt, GetField().MaxElementByteLength());
585 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
592 if ((type & 1) != P.y.GetBit(0))
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 659 bool pass = p.
IsOdd();
663 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
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
767 CRYPTOPP_UNUSED(m_b);
796 sixteenY4 = mr.
Square(fourY2);
802 Integer sixteenY4, aZ4, twoY, fourY2, S, M;
808 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
810 int operator-(ZIterator it2) {
return int(it-it2.it);}
811 ZIterator
operator+(
int i) {
return ZIterator(it+i);}
812 ZIterator& operator+=(
int i) {it+=i;
return *
this;}
813 std::vector<ProjectivePoint>::iterator it;
828 if (!GetField().IsMontgomeryRepresentation())
830 ECP ecpmr(*
this,
true);
833 for (
unsigned int i=0; i<expCount; i++)
834 results[i] = FromMontgomery(mr, results[i]);
838 ProjectiveDoubling rd(GetField(), m_a, m_b, P);
839 std::vector<ProjectivePoint> bases;
840 std::vector<WindowSlider> exponents;
841 exponents.reserve(expCount);
842 std::vector<std::vector<word32> > baseIndices(expCount);
843 std::vector<std::vector<bool> > negateBase(expCount);
844 std::vector<std::vector<word32> > exponentWindows(expCount);
847 for (i=0; i<expCount; i++)
851 exponents[i].FindNextWindow();
854 unsigned int expBitPosition = 0;
860 bool baseAdded =
false;
861 for (i=0; i<expCount; i++)
863 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
867 bases.push_back(rd.P);
871 exponentWindows[i].push_back(exponents[i].expWindow);
872 baseIndices[i].push_back((word32)bases.size()-1);
873 negateBase[i].push_back(exponents[i].negateNext);
875 exponents[i].FindNextWindow();
877 notDone = notDone || !exponents[i].finished;
888 ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
889 for (i=0; i<bases.size(); i++)
891 if (bases[i].z.NotZero())
893 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
894 bases[i].z = GetField().
Square(bases[i].z);
895 bases[i].x = GetField().
Multiply(bases[i].x, bases[i].z);
896 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
900 std::vector<BaseAndExponent<Point, Integer> > finalCascade;
901 for (i=0; i<expCount; i++)
903 finalCascade.resize(baseIndices[i].size());
904 for (
unsigned int j=0; j<baseIndices[i].size(); j++)
906 ProjectivePoint &base = bases[baseIndices[i][j]];
908 finalCascade[j].base.identity =
true;
911 finalCascade[j].base.identity =
false;
912 finalCascade[j].base.x = base.x;
913 if (negateBase[i][j])
914 finalCascade[j].base.y = GetField().
Inverse(base.y);
916 finalCascade[j].base.y = base.y;
920 results[i] = GeneralCascadeMultiplication(*
this, finalCascade.begin(), finalCascade.end());
926 if (!GetField().IsMontgomeryRepresentation())
928 ECP ecpmr(*
this,
true);
930 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.
bool VerifyPoint(const Point &P) const
Verifies points on elliptic curve.
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
inline ::Integer operator*(const ::Integer &a, const ::Integer &b)
Multiplication.
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.
Elliptical Curve Point over GF(p), where p is prime.
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 & Inverse(const Integer &a) const
Inverts the element in the ring.
bool InversionIsFast() const
Determine if inversion is fast.
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.
unsigned int MaxElementByteLength() const
Provides the maximum byte size 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.
int Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
bool DecodePoint(Point &P, BufferedTransformation &bt, size_t len) const
Decodes an elliptic curve point.
Integer ModularSquareRoot(const Integer &a, const Integer &p)
Extract a modular square root.
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.
Point BERDecodePoint(BufferedTransformation &bt) const
BER Decodes an elliptic curve point.
void DEREncodeElement(BufferedTransformation &out, const Element &a) const
Encodes element in DER format.
Copy input to a memory buffer.
inline ::Integer operator-(const ::Integer &a, const ::Integer &b)
Subtraction.
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 number is probably prime.
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
Divides an element by 2.
Point CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
TODO.
String-based implementation of Store interface.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
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.
void DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
DER Encodes an elliptic curve point.
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.
void EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
Encodes an elliptic curve point.
const Point & Add(const Point &P, const Point &Q) const
Adds elements in the group.
size_t DEREncodeOctetString(BufferedTransformation &bt, const byte *str, size_t strLen)
DER encode octet string.
Multiple precision integer with arithmetic operations.
unsigned int EncodedPointSize(bool compressed=false) const
Determines encoded point size.
size_t BERDecodeBitString(BufferedTransformation &bt, SecByteBlock &str, unsigned int &unusedBits)
DER decode bit string.
Class file for performing modular arithmetic.
Crypto++ library namespace.
void DEREncode(BufferedTransformation &bt) const
Encode the fields fieldID and curve of the sequence ECParameters.
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.
const T & Ref(...) const
Return a reference to the inner Singleton object.
size_type size() const
Provides the count of elements in the SecBlock.
void DEREncode(BufferedTransformation &bt) const
Encodes in DER format.
the value is positive or 0
bool IsOdd() const
Determines if the Integer is odd parity.
virtual bool IsMontgomeryRepresentation() const
Retrieves the representation.