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))
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();
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) {}
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++)
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++)
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));
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.
bool NotZero() const
Determines if the Integer is non-0.
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.
Elliptic Curve over GF(p), where p is prime.
virtual Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.
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 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.
const Point & Identity() const
Provides the Identity element.
void DEREncodeElement(BufferedTransformation &out, const Element &a) const
Encodes element in DER format.
Point CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
TODO.
const Point & Inverse(const Point &P) const
Inverts the element in the group.
Copy input to a memory buffer.
inline ::Integer operator-(const ::Integer &a, const ::Integer &b)
Subtraction.
void BERDecodeElement(BufferedTransformation &in, Element &a) const
Decodes element in DER format.
Point ScalarMultiply(const Point &P, const Integer &k) const
Performs a scalar multiplication.
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.
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.
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.
void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const
Encode in big-endian format.
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.
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.
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.
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
void DEREncode(BufferedTransformation &bt) const
Encode the fields fieldID and curve of the sequence ECParameters.
const Integer & MultiplicativeIdentity() const
Retrieves the multiplicative identity.
Point BERDecodePoint(BufferedTransformation &bt) const
BER Decodes an elliptic curve point.
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.
lword TotalPutLength()
Provides the number of bytes written to the Sink.
void DEREncode(BufferedTransformation &bt) const
Encodes in DER format.
const Point & Add(const Point &P, const Point &Q) const
Adds elements in the group.
the value is positive or 0
bool IsOdd() const
Determines if the Integer is odd parity.
virtual bool IsMontgomeryRepresentation() const
Retrieves the representation.