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));
const Integer & Double(const Integer &a) const
Doubles an element in the ring.
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
inline ::Integer operator*(const ::Integer &a, const ::Integer &b)
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.
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.
bool IsNegative() const
Determines if the Integer is negative.
Ring of congruence classes modulo n.
Interface for random number generators.
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.
Copy input to a memory buffer.
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 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.
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
TODO.
Point CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
TODO.
String-based implementation of Store interface.
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.
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.
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.
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.