5#ifndef CRYPTOPP_IMPORTS
15ANONYMOUS_NAMESPACE_BEGIN
18using CryptoPP::ModularArithmetic;
20#if defined(HAVE_GCC_INIT_PRIORITY)
21 const ECP::Point g_identity __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 51))) =
ECP::Point();
22#elif defined(HAVE_MSC_INIT_PRIORITY)
23 #pragma warning(disable: 4075)
24 #pragma init_seg(".CRT$XCU")
26 #pragma warning(default: 4075)
27#elif defined(HAVE_XLC_INIT_PRIORITY)
42ANONYMOUS_NAMESPACE_END
46ECP::
ECP(const
ECP &ecp,
bool convertToMontgomeryRepresentation)
48 if (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation())
51 m_a = GetField().ConvertIn(ecp.m_a);
52 m_b = GetField().ConvertIn(ecp.m_b);
59 : m_fieldPtr(new
Field(bt))
65 if (!seq.EndReached())
69 BERDecodeBitString(seq, seed, unused);
92 if (encodedPointLen < 1 || !bt.
Get(type))
109 P.x.Decode(bt, GetField().MaxElementByteLength());
110 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
112 if (Jacobi(P.y, p) !=1)
115 P.y = ModularSquareRoot(P.y, p);
117 if ((type & 1) != P.y.GetBit(0))
144 bt.
Put((
byte)(2U + P.y.GetBit(0)));
145 P.x.Encode(bt, GetField().MaxElementByteLength());
166 BERDecodeOctetString(bt, str);
177 DEREncodeOctetString(bt, str);
184 bool pass = p.
IsOdd();
188 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
191 pass = pass && VerifyPrime(rng, p);
201 (!x.IsNegative() && x<p && !y.
IsNegative() && y<p
202 && !(((x*x+m_a)*x+m_b-y*y)%p));
207 if (P.identity && Q.identity)
210 if (P.identity && !Q.identity)
213 if (!P.identity && Q.identity)
216 return (GetField().
Equal(P.x,Q.x) && GetField().
Equal(P.y,Q.y));
221#if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
223#elif defined(CRYPTOPP_CXX11_DYNAMIC_INIT)
237 m_R.identity =
false;
239 m_R.y = GetField().
Inverse(P.y);
246 if (P.identity)
return Q;
247 if (Q.identity)
return P;
248 if (GetField().
Equal(P.x, Q.x))
254 m_R.y = GetField().
Subtract(GetField().Multiply(t, GetField().
Subtract(P.x, x)), P.y);
257 m_R.identity =
false;
261const ECP::Point& ECP::Double(
const Point &P)
const
265 FieldElement t = GetField().
Square(P.x);
266 t = GetField().
Add(GetField().
Add(GetField().Double(t), t), m_a);
267 t = GetField().
Divide(t, GetField().Double(P.y));
269 m_R.y = GetField().
Subtract(GetField().Multiply(t, GetField().
Subtract(P.x, x)), P.y);
272 m_R.identity =
false;
276template <
class T,
class Iterator>
void ParallelInvert(
const AbstractRing<T> &ring, Iterator begin, Iterator end)
278 size_t n = end-begin;
283 std::vector<T> vec((n+1)/2);
287 for (i=0, it=begin; i<n/2; i++, it+=2)
288 vec[i] = ring.
Multiply(*it, *(it+1));
292 ParallelInvert(ring, vec.begin(), vec.end());
294 for (i=0, it=begin; i<n/2; i++, it+=2)
303 std::swap(*it, *(it+1));
305 *(it+1) = ring.
Multiply(*(it+1), vec[i]);
317 : x(x), y(y), z(z) {}
326 : mr(m_mr), firstDoubling(
true), negated(
false)
328 CRYPTOPP_UNUSED(m_b);
357 sixteenY4 = mr.
Square(fourY2);
363 bool firstDoubling, negated;
364 Integer sixteenY4, aZ4, twoY, fourY2, S, M;
370 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
371 Integer& operator*() {
return it->z;}
372 int operator-(
ZIterator it2) {
return int(it-it2.it);}
374 ZIterator& operator+=(
int i) {it+=i;
return *
this;}
375 std::vector<ProjectivePoint>::iterator it;
384 ECP::SimultaneousMultiply(&result, P, &k, 1);
390 if (!GetField().IsMontgomeryRepresentation())
392 ECP ecpmr(*
this,
true);
395 for (
unsigned int i=0; i<expCount; i++)
396 results[i] = FromMontgomery(mr, results[i]);
401 std::vector<ProjectivePoint> bases;
402 std::vector<WindowSlider> exponents;
403 exponents.reserve(expCount);
404 std::vector<std::vector<word32> > baseIndices(expCount);
405 std::vector<std::vector<bool> > negateBase(expCount);
406 std::vector<std::vector<word32> > exponentWindows(expCount);
409 for (i=0; i<expCount; i++)
413 exponents[i].FindNextWindow();
416 unsigned int expBitPosition = 0;
422 bool baseAdded =
false;
423 for (i=0; i<expCount; i++)
425 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
429 bases.push_back(rd.P);
433 exponentWindows[i].push_back(exponents[i].expWindow);
434 baseIndices[i].push_back((word32)bases.size()-1);
435 negateBase[i].push_back(exponents[i].negateNext);
437 exponents[i].FindNextWindow();
439 notDone = notDone || !exponents[i].finished;
451 for (i=0; i<bases.size(); i++)
453 if (bases[i].z.NotZero())
455 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
456 bases[i].z = GetField().
Square(bases[i].z);
457 bases[i].x = GetField().
Multiply(bases[i].x, bases[i].z);
458 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
462 std::vector<BaseAndExponent<Point, Integer> > finalCascade;
463 for (i=0; i<expCount; i++)
465 finalCascade.resize(baseIndices[i].size());
466 for (
unsigned int j=0; j<baseIndices[i].size(); j++)
470 finalCascade[j].base.identity =
true;
473 finalCascade[j].base.identity =
false;
474 finalCascade[j].base.x = base.x;
475 if (negateBase[i][j])
476 finalCascade[j].base.y = GetField().
Inverse(base.y);
478 finalCascade[j].base.y = base.y;
482 results[i] = GeneralCascadeMultiplication(*
this, finalCascade.begin(), finalCascade.end());
488 if (!GetField().IsMontgomeryRepresentation())
490 ECP ecpmr(*
this,
true);
492 return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));
Classes and functions for working with ANS.1 objects.
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 & 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.
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.
void swap(Integer &a)
Swaps this Integer with another Integer.
bool IsZero() const
Determines if the Integer is 0.
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 & MultiplicativeIdentity() const
Retrieves the multiplicative identity.
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
const Integer & Half(const Integer &a) const
Divides an element by 2.
const Integer & Square(const Integer &a) const
Square an element in the ring.
const Integer & Double(const Integer &a) const
Doubles an element in the ring.
const Integer & Inverse(const Integer &a) const
Inverts the element in the ring.
void BERDecodeElement(BufferedTransformation &in, Element &a) const
Decodes element in DER format.
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.
bool Equal(const Integer &a, const Integer &b) const
Compare two elements for equality.
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
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 & Divide(const Integer &a, const Integer &b) const
Divides elements in the ring.
const Integer & Add(const Integer &a, const Integer &b) const
Adds elements in the ring.
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.
Elliptical Curve Point over GF(p), where p is prime.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.