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))
642 bt.
Put((
byte)(2U + 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();
699 (!x.IsNegative() && x<p && !y.
IsNegative() && y<p
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));
748 const ECP::Point& ECP::Double(
const Point &P)
const
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) {}
839 Integer& operator*() {
return it->z;}
840 int operator-(
ZIterator it2) {
return int(it-it2.it);}
842 ZIterator& operator+=(
int i) {it+=i;
return *
this;}
843 std::vector<ProjectivePoint>::iterator it;
852 ECP::SimultaneousMultiply(&result, P, &k, 1);
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++)
921 if (bases[i].z.NotZero())
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));
Classes and functions for working with ANS.1 objects.
size_t BERDecodeOctetString(BufferedTransformation &bt, SecByteBlock &str)
BER decode octet string.
size_t BERDecodeBitString(BufferedTransformation &bt, SecByteBlock &str, unsigned int &unusedBits)
DER decode bit string.
size_t DEREncodeOctetString(BufferedTransformation &bt, const byte *str, size_t strLen)
DER encode octet string.
void BERDecodeError()
Raises a BERDecodeErr.
virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
virtual void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Multiplies a base to multiple exponents in a group.
virtual const Element & Multiply(const Element &a, const Element &b) const =0
Multiplies elements in the group.
virtual const Element & MultiplicativeInverse(const Element &a) const =0
Calculate the multiplicative inverse of an element in the group.
Copy input to a memory buffer.
lword TotalPutLength()
Provides the number of bytes written to the Sink.
Elliptic Curve over GF(p), where p is prime.
bool InversionIsFast() const
Determine if inversion is fast.
void EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
Encodes an elliptic curve point.
bool Equal(const Point &P, const Point &Q) const
Compare two elements for equality.
void DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
DER Encodes an elliptic curve point.
bool VerifyPoint(const Point &P) const
Verifies points on elliptic curve.
unsigned int EncodedPointSize(bool compressed=false) const
Determines encoded point size.
bool DecodePoint(Point &P, BufferedTransformation &bt, size_t len) const
Decodes an elliptic curve point.
const Point & Inverse(const Point &P) const
Inverts the element in the group.
Point BERDecodePoint(BufferedTransformation &bt) const
BER Decodes an elliptic curve point.
void DEREncode(BufferedTransformation &bt) const
Encode the fields fieldID and curve of the sequence ECParameters.
const Point & Add(const Point &P, const Point &Q) const
Adds elements in the group.
const Point & Identity() const
Provides the Identity element.
Multiple precision integer with arithmetic operations.
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
bool NotNegative() const
Determines if the Integer is non-negative.
static const Integer & One()
Integer representing 1.
bool IsNegative() const
Determines if the Integer is negative.
@ POSITIVE
the value is positive or 0
bool IsOdd() const
Determines if the Integer is odd parity.
Ring of congruence classes modulo n.
const Integer & Double(const Integer &a) const
Doubles an element in the ring.
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
const Integer & MultiplicativeInverse(const Integer &a) const
Calculate the multiplicative inverse of an element in the ring.
const Integer & Half(const Integer &a) const
Divides an element by 2.
const Integer & Inverse(const Integer &a) const
Inverts the element in the ring.
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
void BERDecodeElement(BufferedTransformation &in, Element &a) const
Decodes element in DER format.
const Integer & Divide(const Integer &a, const Integer &b) const
Divides elements in the ring.
unsigned int MaxElementByteLength() const
Provides the maximum byte size of an element in the ring.
void DEREncodeElement(BufferedTransformation &out, const Element &a) const
Encodes element in DER format.
const Integer & GetModulus() const
Retrieves the modulus.
virtual bool IsMontgomeryRepresentation() const
Retrieves the representation.
const Integer & Square(const Integer &a) const
Square an element in the ring.
bool Equal(const Integer &a, const Integer &b) const
Compare two elements for equality.
const Integer & Identity() const
Provides the Identity element.
virtual Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.
const Integer & Subtract(const Integer &a, const Integer &b) const
Subtracts elements in the ring.
const Integer & Add(const Integer &a, const Integer &b) const
Adds elements in the ring.
const Integer & MultiplicativeIdentity() const
Retrieves the multiplicative identity.
virtual Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
void DEREncode(BufferedTransformation &bt) const
Encodes in DER format.
Performs modular arithmetic in Montgomery representation for increased speed.
Interface for random number generators.
size_type size() const
Provides the count of elements in the SecBlock.
Restricts the instantiation of a class to one static object without locks.
const T & Ref(...) const
Return a reference to the inner Singleton object.
String-based implementation of Store interface.
Classes for Elliptic Curves over prime fields.
Implementation of BufferedTransformation's attachment interface.
Multiple precision integer with arithmetic operations.
Class file for performing modular arithmetic.
Crypto++ library namespace.
Classes and functions for number theoretic operations.
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
Integer ModularSquareRoot(const Integer &a, const Integer &p)
Extract a modular square root.
int Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
Elliptical Curve Point over GF(p), where p is prime.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.