5 #ifndef CRYPTOPP_IMPORTS 13 #include "algebra.cpp" 17 ANONYMOUS_NAMESPACE_BEGIN
20 return P.identity ? P :
ECP::Point(mr.ConvertIn(P.x), mr.ConvertIn(P.y));
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);
66 bool ECP::DecodePoint(
ECP::Point &P,
const byte *encodedPoint,
size_t encodedPointLen)
const 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;
95 if (Jacobi(P.y, p) !=1)
98 P.y = ModularSquareRoot(P.y, 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 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();
179 bool ECP::VerifyPoint(
const Point &P)
const 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;
239 if (P.identity || P.y==GetField().Identity())
return Identity();
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));
virtual void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Multiplies a base to multiple exponents in a group.
bool Equal(const Point &P, const Point &Q) const
Compare two elements for equality.
inline::Integer operator*(const ::Integer &a, const ::Integer &b)
const Integer & GetModulus() const
Retrieves the modulus.
Restricts the instantiation of a class to one static object without locks.
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
bool IsOdd() const
Determines if the Integer is odd parity.
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.
const Integer & MultiplicativeIdentity() const
Retrieves the multiplicative identity.
const Point & Identity() const
Provides the Identity element.
size_type size() const
Provides the count of elements in the SecBlock.
const Integer & Square(const Integer &a) const
Square an element in the ring.
Ring of congruence classes modulo n.
Interface for random number generators.
void SimultaneousMultiply(Point *results, const Point &base, const Integer *exponents, unsigned int exponentsCount) const
Multiplies a base to multiple exponents in a group.
const Integer & Add(const Integer &a, const Integer &b) const
Adds elements in the ring.
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
virtual Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
const Point & Add(const Point &P, const Point &Q) const
Adds elements in the group.
Copy input to a memory buffer.
virtual Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
bool IsPositive() const
Determines if the Integer is positive.
size_t BERDecodeOctetString(BufferedTransformation &bt, SecByteBlock &str)
BER decode octet string.
bool IsNegative() const
Determines if the Integer is negative.
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a prime number.
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.
const Integer & Double(const Integer &a) const
Doubles an element in the ring.
OID operator+(const OID &lhs, unsigned long rhs)
Append a value to an OID.
String-based implementation of Store interface.
Point CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
TODO.
void BERDecodeError()
Raises a BERDecodeErr.
Classes and functions for working with ANS.1 objects.
Implementation of BufferedTransformation's attachment interface.
Classes and functions for number theoretic operations.
const Integer & Half(const Integer &a) const
TODO.
Performs modular arithmetic in Montgomery representation for increased speed.
Point ScalarMultiply(const Point &P, const Integer &k) const
Performs a scalar multiplication.
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.
virtual bool IsMontgomeryRepresentation() const
Retrieves the representation.
const Integer & Identity() const
Provides the Identity element.
virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
const Point & Inverse(const Point &P) const
Inverts the element in the group.
const Point & Double(const Point &P) const
Doubles an element in the group.
the value is positive or 0
bool NotNegative() const
Determines if the Integer is non-negative.