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));
25 return P.identity ? P :
ECP::Point(mr.ConvertOut(P.x), mr.ConvertOut(P.y));
29 ECP::ECP(
const ECP &ecp,
bool convertToMontgomeryRepresentation)
31 if (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation())
34 m_a = GetField().ConvertIn(ecp.m_a);
35 m_b = GetField().ConvertIn(ecp.m_b);
42 : m_fieldPtr(new Field(bt))
45 GetField().BERDecodeElement(seq, m_a);
46 GetField().BERDecodeElement(seq, m_b);
48 if (!seq.EndReached())
52 BERDecodeBitString(seq, seed, unused);
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));
149 BERDecodeOctetString(bt, str);
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));
207 const ECP::Point& ECP::Inverse(
const Point &P)
const 213 m_R.identity =
false;
215 m_R.y = GetField().Inverse(P.y);
220 const ECP::Point& ECP::Add(
const Point &P,
const Point &Q)
const 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;
237 const ECP::Point& ECP::Double(
const Point &P)
const 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;
256 *begin = ring.MultiplicativeInverse(*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)
274 *it = ring.MultiplicativeInverse(*it);
275 *(it+1) = ring.MultiplicativeInverse(*(it+1));
279 std::swap(*it, *(it+1));
280 *it = ring.Multiply(*it, vec[i]);
281 *(it+1) = ring.Multiply(*(it+1), vec[i]);
289 struct ProjectivePoint
293 : x(x), y(y), z(z) {}
298 class ProjectiveDoubling
302 : mr(mr), firstDoubling(true), negated(false)
304 CRYPTOPP_UNUSED(m_b);
307 sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity();
308 aZ4 = P.z = mr.Identity();
314 sixteenY4 = P.z = mr.MultiplicativeIdentity();
321 twoY = mr.Double(P.y);
322 P.z = mr.Multiply(P.z, twoY);
323 fourY2 = mr.Square(twoY);
324 S = mr.Multiply(fourY2, P.x);
325 aZ4 = mr.Multiply(aZ4, sixteenY4);
327 M = mr.Add(mr.Add(mr.Double(M), M), aZ4);
332 P.y = mr.Multiply(M, S);
333 sixteenY4 = mr.Square(fourY2);
334 mr.Reduce(P.y, mr.Half(sixteenY4));
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;
360 ECP::SimultaneousMultiply(&result, P, &k, 1);
366 if (!GetField().IsMontgomeryRepresentation())
368 ECP ecpmr(*
this,
true);
370 ecpmr.SimultaneousMultiply(results, ToMontgomery(mr, P), expBegin, expCount);
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++)
387 assert(expBegin->NotNegative());
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));
inline::Integer operator*(const ::Integer &a, const ::Integer &b)
Restricts the instantiation of a class to one static object without locks.
bool GetBit(size_t i) const
return the i-th bit, i=0 being the least significant bit
Classes for Elliptic Curves over prime fields.
Elliptic Curve over GF(p), where p is prime.
size_type size() const
Provides the count of elements in the SecBlock.
Ring of congruence classes modulo n.
Interface for random number generators.
SecByteBlock is a SecBlock<byte> typedef.
unsigned int BitCount() const
number of significant bits = floor(log2(abs(*this))) + 1
Copy input to a memory buffer.
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a prime number.
Multiple precision integer with arithmetic operations.
string-based implementation of Store interface
Classes and functions for working with ANS.1 objects.
Implementation of BufferedTransformation's attachment interface in cryptlib.h.
Classes and functions for number theoretic operations.
size_t DEREncodeOctetString(BufferedTransformation &out, const byte *str, size_t strLen)
ASN Strings.
Performs modular arithmetic in Montgomery representation for increased speed.
void Decode(const byte *input, size_t inputLen, Signedness sign=UNSIGNED)
Decode from big-endian byte array.
Class file for performing modular arithmetic.
Crypto++ library namespace.
the value is positive or 0