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())
59 GetField().DEREncode(bt);
61 GetField().DEREncodeElement(seq, m_a);
62 GetField().DEREncodeElement(seq, m_b);
69 return DecodePoint(P, store, encodedPointLen);
75 if (encodedPointLen < 1 || !bt.
Get(type))
86 if (encodedPointLen != EncodedPointSize(
true))
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))
107 if (encodedPointLen != EncodedPointSize(
false))
110 unsigned int len = GetField().MaxElementByteLength();
127 bt.
Put(2 + P.y.GetBit(0));
128 P.x.Encode(bt, GetField().MaxElementByteLength());
132 unsigned int len = GetField().MaxElementByteLength();
139 void ECP::EncodePoint(byte *encodedPoint,
const Point &P,
bool compressed)
const 141 ArraySink sink(encodedPoint, EncodedPointSize(compressed));
142 EncodePoint(sink, P, compressed);
143 CRYPTOPP_ASSERT(sink.TotalPutLength() == EncodedPointSize(compressed));
151 if (!DecodePoint(P, str, str.
size()))
159 EncodePoint(str, P, compressed);
167 bool pass = p.
IsOdd();
168 pass = pass && !m_a.IsNegative() && m_a<p && !m_b.
IsNegative() && m_b<p;
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))
225 return GetField().Equal(P.y, Q.y) ? Double(P) :
Identity();
227 FieldElement t = GetField().Subtract(Q.y, P.y);
228 t = GetField().Divide(t, GetField().Subtract(Q.x, P.x));
229 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().
Square(t), P.x), Q.x);
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);
243 t = GetField().Divide(t, GetField().Double(P.y));
244 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().
Square(t), P.x), P.x);
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++)
388 exponents.push_back(
WindowSlider(*expBegin++, InversionIsFast(), 5));
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.
const Integer & Square(const Integer &a) const
Square an element 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.
const char * Identity()
ConstByteArrayParameter.
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.
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.
const Integer & Identity() const
Provides the Identity element.
Point BERDecodePoint(BufferedTransformation &bt) const
BER Decodes an elliptic curve point.
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.
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.
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.
the value is positive or 0
bool IsOdd() const
Determines if the Integer is odd parity.
virtual bool IsMontgomeryRepresentation() const
Retrieves the representation.