5 #ifndef CRYPTOPP_IMPORTS 13 #include "algebra.cpp" 15 ANONYMOUS_NAMESPACE_BEGIN
18 using CryptoPP::Integer;
19 using CryptoPP::ModularArithmetic;
21 #if defined(HAVE_GCC_INIT_PRIORITY) 22 #define INIT_ATTRIBUTE __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 50))) 24 #elif defined(HAVE_MSC_INIT_PRIORITY) 25 #pragma warning(disable: 4075) 26 #pragma init_seg(".CRT$XCU") 28 #pragma warning(default: 4075) 29 #elif defined(HAVE_XLC_INIT_PRIORITY) 44 inline Integer IdentityToInteger(
bool val)
49 struct ProjectivePoint
58 ANONYMOUS_NAMESPACE_END
62 ECP::ECP(
const ECP &ecp,
bool convertToMontgomeryRepresentation)
75 : m_fieldPtr(new Field(bt))
78 GetField().BERDecodeElement(seq, m_a);
79 GetField().BERDecodeElement(seq, m_b);
81 if (!seq.EndReached())
108 if (encodedPointLen < 1 || !bt.
Get(type))
125 P.x.Decode(bt, GetField().MaxElementByteLength());
126 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
133 if ((type & 1) != P.y.GetBit(0))
160 bt.
Put((
byte)(2U + P.y.GetBit(0)));
161 P.x.Encode(bt, GetField().MaxElementByteLength());
200 bool pass = p.
IsOdd();
204 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
214 const FieldElement &x = P.x, &y = P.y;
217 (!x.IsNegative() && x<p && !y.
IsNegative() && y<p
218 && !(((x*x+m_a)*x+m_b-y*y)%p));
221 bool ECP::Equal(
const Point &P,
const Point &Q)
const 223 if (P.identity && Q.identity)
226 if (P.identity && !Q.identity)
229 if (!P.identity && Q.identity)
232 return (GetField().
Equal(P.x,Q.x) && GetField().
Equal(P.y,Q.y));
237 #if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY) 239 #elif defined(CRYPTOPP_CXX11_STATIC_INIT) 253 m_R.identity =
false;
255 m_R.y = GetField().
Inverse(P.y);
262 if (P.identity)
return Q;
263 if (Q.identity)
return P;
264 if (GetField().
Equal(P.x, Q.x))
267 FieldElement t = GetField().
Subtract(Q.y, P.y);
270 m_R.y = GetField().
Subtract(GetField().Multiply(t, GetField().
Subtract(P.x, x)), P.y);
273 m_R.identity =
false;
281 FieldElement t = GetField().
Square(P.x);
282 t = GetField().
Add(GetField().
Add(GetField().
Double(t), t), m_a);
285 m_R.y = GetField().
Subtract(GetField().Multiply(t, GetField().
Subtract(P.x, x)), P.y);
288 m_R.identity =
false;
292 template <
class T,
class Iterator>
void ParallelInvert(
const AbstractRing<T> &ring, Iterator begin, Iterator end)
294 size_t n = end-begin;
299 std::vector<T> vec((n+1)/2);
303 for (i=0, it=begin; i<n/2; i++, it+=2)
304 vec[i] = ring.
Multiply(*it, *(it+1));
308 ParallelInvert(ring, vec.begin(), vec.end());
310 for (i=0, it=begin; i<n/2; i++, it+=2)
321 *(it+1) = ring.
Multiply(*(it+1), vec[i]);
329 class ProjectiveDoubling
335 CRYPTOPP_UNUSED(m_b);
364 sixteenY4 = mr.
Square(fourY2);
370 Integer sixteenY4, aZ4, twoY, fourY2, S, M;
376 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
378 int operator-(ZIterator it2) {
return int(it-it2.it);}
379 ZIterator
operator+(
int i) {
return ZIterator(it+i);}
380 ZIterator& operator+=(
int i) {it+=i;
return *
this;}
381 std::vector<ProjectivePoint>::iterator it;
396 if (!GetField().IsMontgomeryRepresentation())
398 ECP ecpmr(*
this,
true);
401 for (
unsigned int i=0; i<expCount; i++)
402 results[i] = FromMontgomery(mr, results[i]);
406 ProjectiveDoubling rd(GetField(), m_a, m_b, P);
407 std::vector<ProjectivePoint> bases;
408 std::vector<WindowSlider> exponents;
409 exponents.reserve(expCount);
410 std::vector<std::vector<word32> > baseIndices(expCount);
411 std::vector<std::vector<bool> > negateBase(expCount);
412 std::vector<std::vector<word32> > exponentWindows(expCount);
415 for (i=0; i<expCount; i++)
419 exponents[i].FindNextWindow();
422 unsigned int expBitPosition = 0;
428 bool baseAdded =
false;
429 for (i=0; i<expCount; i++)
431 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
435 bases.push_back(rd.P);
439 exponentWindows[i].push_back(exponents[i].expWindow);
440 baseIndices[i].push_back((
word32)bases.size()-1);
441 negateBase[i].push_back(exponents[i].negateNext);
443 exponents[i].FindNextWindow();
445 notDone = notDone || !exponents[i].finished;
456 ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
457 for (i=0; i<bases.size(); i++)
459 if (bases[i].z.NotZero())
461 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
462 bases[i].z = GetField().
Square(bases[i].z);
463 bases[i].x = GetField().
Multiply(bases[i].x, bases[i].z);
464 bases[i].y = GetField().
Multiply(bases[i].y, bases[i].z);
468 std::vector<BaseAndExponent<Point, Integer> > finalCascade;
469 for (i=0; i<expCount; i++)
471 finalCascade.resize(baseIndices[i].size());
472 for (
unsigned int j=0; j<baseIndices[i].size(); j++)
474 ProjectivePoint &base = bases[baseIndices[i][j]];
476 finalCascade[j].base.identity =
true;
479 finalCascade[j].base.identity =
false;
480 finalCascade[j].base.x = base.x;
481 if (negateBase[i][j])
482 finalCascade[j].base.y = GetField().
Inverse(base.y);
484 finalCascade[j].base.y = base.y;
488 results[i] = GeneralCascadeMultiplication(*
this, finalCascade.begin(), finalCascade.end());
494 if (!GetField().IsMontgomeryRepresentation())
496 ECP ecpmr(*
this,
true);
498 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.
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.
static const Integer & One()
Integer representing 1.
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.
const Integer & Half(const Integer &a) const
Divides an element by 2.
Classes for Elliptic Curves over prime fields.
const Point & Identity() const
Provides the Identity element.
Elliptic Curve over GF(p), where p is prime.
unsigned int word32
32-bit unsigned datatype
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 InversionIsFast() const
Determine if inversion is fast.
unsigned int MaxElementByteLength() const
Provides the maximum byte size of an element in the ring.
const Integer & Subtract(const Integer &a, const Integer &b) const
Subtracts elements in the ring.
bool IsNegative() const
Determines if the Integer is negative.
Ring of congruence classes modulo n.
Interface for random number generators.
bool DecodePoint(Point &P, BufferedTransformation &bt, size_t len) const
Decodes an elliptic curve point.
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.
CRYPTOPP_DLL bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
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.
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 points.
virtual const Element & MultiplicativeInverse(const Element &a) const =0
Calculate the multiplicative inverse of an element in the group.
CRYPTOPP_DLL size_t DEREncodeOctetString(BufferedTransformation &bt, const byte *str, size_t strLen)
DER encode octet string.
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.
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.
CRYPTOPP_DLL size_t BERDecodeOctetString(BufferedTransformation &bt, SecByteBlock &str)
BER decode octet string.
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.
Integer & Reduce(Integer &a, const Integer &b) const
TODO.
unsigned char byte
8-bit unsigned datatype
CRYPTOPP_DLL int Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
CRYPTOPP_DLL size_t BERDecodeBitString(BufferedTransformation &bt, SecByteBlock &str, unsigned int &unusedBits)
DER decode bit string.
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.
Multiple precision integer with arithmetic operations.
unsigned int EncodedPointSize(bool compressed=false) const
Determines encoded point size.
Class file for performing modular arithmetic.
Crypto++ library namespace.
const Integer & Add(const Integer &a, const Integer &b) const
Adds elements in the ring.
void DEREncode(BufferedTransformation &bt) const
DER Encode.
void swap(::SecBlock< T, A > &a, ::SecBlock< T, A > &b)
Swap two SecBlocks.
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.
CRYPTOPP_DLL Integer ModularSquareRoot(const Integer &a, const Integer &p)
Extract a modular square root.
size_type size() const
Provides the count of elements in the SecBlock.
const Integer & Inverse(const Integer &a) const
Inverts the element in the ring.
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.