5 #ifndef CRYPTOPP_IMPORTS 13 #include "algebra.cpp" 17 ANONYMOUS_NAMESPACE_BEGIN
29 ECP::ECP(
const ECP &ecp,
bool convertToMontgomeryRepresentation)
42 : m_fieldPtr(new Field(bt))
45 GetField().BERDecodeElement(seq, m_a);
46 GetField().BERDecodeElement(seq, m_b);
48 if (!seq.EndReached())
75 if (encodedPointLen < 1 || !bt.
Get(type))
92 P.x.Decode(bt, GetField().MaxElementByteLength());
93 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
100 if ((type & 1) != P.y.GetBit(0))
127 bt.
Put(2 + P.y.GetBit(0));
128 P.x.Encode(bt, GetField().MaxElementByteLength());
139 void ECP::EncodePoint(byte *encodedPoint,
const Point &P,
bool compressed)
const 167 bool pass = p.
IsOdd();
171 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
181 const FieldElement &x = P.x, &y = P.y;
184 (!x.IsNegative() && x<p && !y.
IsNegative() && y<p
185 && !(((x*x+m_a)*x+m_b-y*y)%p));
188 bool ECP::Equal(
const Point &P,
const Point &Q)
const 190 if (P.identity && Q.identity)
193 if (P.identity && !Q.identity)
196 if (!P.identity && Q.identity)
199 return (GetField().
Equal(P.x,Q.x) && GetField().
Equal(P.y,Q.y));
213 m_R.identity =
false;
215 m_R.y = GetField().
Inverse(P.y);
222 if (P.identity)
return Q;
223 if (Q.identity)
return P;
224 if (GetField().
Equal(P.x, Q.x))
227 FieldElement t = GetField().
Subtract(Q.y, P.y);
230 m_R.y = GetField().
Subtract(GetField().Multiply(t, GetField().
Subtract(P.x, x)), P.y);
233 m_R.identity =
false;
241 FieldElement t = GetField().
Square(P.x);
242 t = GetField().
Add(GetField().
Add(GetField().
Double(t), t), m_a);
245 m_R.y = GetField().
Subtract(GetField().Multiply(t, GetField().
Subtract(P.x, x)), P.y);
248 m_R.identity =
false;
252 template <
class T,
class Iterator>
void ParallelInvert(
const AbstractRing<T> &ring, Iterator begin, Iterator end)
254 size_t n = end-begin;
259 std::vector<T> vec((n+1)/2);
263 for (i=0, it=begin; i<n/2; i++, it+=2)
264 vec[i] = ring.
Multiply(*it, *(it+1));
268 ParallelInvert(ring, vec.begin(), vec.end());
270 for (i=0, it=begin; i<n/2; i++, it+=2)
279 std::swap(*it, *(it+1));
281 *(it+1) = ring.
Multiply(*(it+1), vec[i]);
289 struct ProjectivePoint
293 : x(x), y(y), z(z) {}
298 class ProjectiveDoubling
302 : mr(m_mr), firstDoubling(true), negated(false)
304 CRYPTOPP_UNUSED(m_b);
333 sixteenY4 = mr.
Square(fourY2);
339 bool firstDoubling, negated;
340 Integer sixteenY4, aZ4, twoY, fourY2, S, M;
346 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
348 int operator-(ZIterator it2) {
return int(it-it2.it);}
349 ZIterator
operator+(
int i) {
return ZIterator(it+i);}
350 ZIterator& operator+=(
int i) {it+=i;
return *
this;}
351 std::vector<ProjectivePoint>::iterator it;
366 if (!GetField().IsMontgomeryRepresentation())
368 ECP ecpmr(*
this,
true);
371 for (
unsigned int i=0; i<expCount; i++)
372 results[i] = FromMontgomery(mr, results[i]);
376 ProjectiveDoubling rd(GetField(), m_a, m_b, P);
377 std::vector<ProjectivePoint> bases;
378 std::vector<WindowSlider> exponents;
379 exponents.reserve(expCount);
380 std::vector<std::vector<word32> > baseIndices(expCount);
381 std::vector<std::vector<bool> > negateBase(expCount);
382 std::vector<std::vector<word32> > exponentWindows(expCount);
385 for (i=0; i<expCount; i++)
389 exponents[i].FindNextWindow();
392 unsigned int expBitPosition = 0;
398 bool baseAdded =
false;
399 for (i=0; i<expCount; i++)
401 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
405 bases.push_back(rd.P);
409 exponentWindows[i].push_back(exponents[i].expWindow);
410 baseIndices[i].push_back((word32)bases.size()-1);
411 negateBase[i].push_back(exponents[i].negateNext);
413 exponents[i].FindNextWindow();
415 notDone = notDone || !exponents[i].finished;
426 ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
427 for (i=0; i<bases.size(); i++)
429 if (bases[i].z.NotZero())
431 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
432 bases[i].z = GetField().
Square(bases[i].z);
433 bases[i].x = GetField().
Multiply(bases[i].x, bases[i].z);
434 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
438 std::vector<BaseAndExponent<Point, Integer> > finalCascade;
439 for (i=0; i<expCount; i++)
441 finalCascade.resize(baseIndices[i].size());
442 for (
unsigned int j=0; j<baseIndices[i].size(); j++)
444 ProjectivePoint &base = bases[baseIndices[i][j]];
446 finalCascade[j].base.identity =
true;
449 finalCascade[j].base.identity =
false;
450 finalCascade[j].base.x = base.x;
451 if (negateBase[i][j])
452 finalCascade[j].base.y = GetField().
Inverse(base.y);
454 finalCascade[j].base.y = base.y;
458 results[i] = GeneralCascadeMultiplication(*
this, finalCascade.begin(), finalCascade.end());
464 if (!GetField().IsMontgomeryRepresentation())
466 ECP ecpmr(*
this,
true);
468 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 & Subtract(const Element &a, const Element &b) const
Subtracts elements in the group.
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.
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.
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.
void swap(Integer &a)
Swaps this Integer with another Integer.
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.
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.