Security Scol plugin
ecp.cpp
1// ecp.cpp - originally written and placed in the public domain by Wei Dai
2
3#include "pch.h"
4
5#ifndef CRYPTOPP_IMPORTS
6
7#include "ecp.h"
8#include "asn.h"
9#include "integer.h"
10#include "nbtheory.h"
11#include "modarith.h"
12#include "filters.h"
13#include "algebra.cpp"
14
15ANONYMOUS_NAMESPACE_BEGIN
16
17using CryptoPP::ECP;
18using CryptoPP::Integer;
19using CryptoPP::ModularArithmetic;
20
21#if defined(HAVE_GCC_INIT_PRIORITY)
22 #define INIT_ATTRIBUTE __attribute__ ((init_priority (CRYPTOPP_INIT_PRIORITY + 50)))
23 const ECP::Point g_identity INIT_ATTRIBUTE = ECP::Point();
24#elif defined(HAVE_MSC_INIT_PRIORITY)
25 #pragma warning(disable: 4075)
26 #pragma init_seg(".CRT$XCU")
27 const ECP::Point g_identity;
28 #pragma warning(default: 4075)
29#elif defined(HAVE_XLC_INIT_PRIORITY)
30 #pragma priority(290)
31 const ECP::Point g_identity;
32#endif
33
34inline ECP::Point ToMontgomery(const ModularArithmetic &mr, const ECP::Point &P)
35{
36 return P.identity ? P : ECP::Point(mr.ConvertIn(P.x), mr.ConvertIn(P.y));
37}
38
39inline ECP::Point FromMontgomery(const ModularArithmetic &mr, const ECP::Point &P)
40{
41 return P.identity ? P : ECP::Point(mr.ConvertOut(P.x), mr.ConvertOut(P.y));
42}
43
44inline Integer IdentityToInteger(bool val)
45{
46 return val ? Integer::One() : Integer::Zero();
47}
48
50{
52 ProjectivePoint(const Integer &x, const Integer &y, const Integer &z)
53 : x(x), y(y), z(z) {}
54
55 Integer x, y, z;
56};
57
58ANONYMOUS_NAMESPACE_END
59
60NAMESPACE_BEGIN(CryptoPP)
61
62ECP::ECP(const ECP &ecp, bool convertToMontgomeryRepresentation)
63{
64 if (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation())
65 {
66 m_fieldPtr.reset(new MontgomeryRepresentation(ecp.GetField().GetModulus()));
67 m_a = GetField().ConvertIn(ecp.m_a);
68 m_b = GetField().ConvertIn(ecp.m_b);
69 }
70 else
71 operator=(ecp);
72}
73
75 : m_fieldPtr(new Field(bt))
76{
77 BERSequenceDecoder seq(bt);
78 GetField().BERDecodeElement(seq, m_a);
79 GetField().BERDecodeElement(seq, m_b);
80 // skip optional seed
81 if (!seq.EndReached())
82 {
83 SecByteBlock seed;
84 unsigned int unused;
85 BERDecodeBitString(seq, seed, unused);
86 }
87 seq.MessageEnd();
88}
89
91{
92 GetField().DEREncode(bt);
93 DERSequenceEncoder seq(bt);
94 GetField().DEREncodeElement(seq, m_a);
95 GetField().DEREncodeElement(seq, m_b);
96 seq.MessageEnd();
97}
98
99bool ECP::DecodePoint(ECP::Point &P, const byte *encodedPoint, size_t encodedPointLen) const
100{
101 StringStore store(encodedPoint, encodedPointLen);
102 return DecodePoint(P, store, encodedPointLen);
103}
104
105bool ECP::DecodePoint(ECP::Point &P, BufferedTransformation &bt, size_t encodedPointLen) const
106{
107 byte type;
108 if (encodedPointLen < 1 || !bt.Get(type))
109 return false;
110
111 switch (type)
112 {
113 case 0:
114 P.identity = true;
115 return true;
116 case 2:
117 case 3:
118 {
119 if (encodedPointLen != EncodedPointSize(true))
120 return false;
121
122 Integer p = FieldSize();
123
124 P.identity = false;
125 P.x.Decode(bt, GetField().MaxElementByteLength());
126 P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
127
128 if (Jacobi(P.y, p) !=1)
129 return false;
130
131 P.y = ModularSquareRoot(P.y, p);
132
133 if ((type & 1) != P.y.GetBit(0))
134 P.y = p-P.y;
135
136 return true;
137 }
138 case 4:
139 {
140 if (encodedPointLen != EncodedPointSize(false))
141 return false;
142
143 unsigned int len = GetField().MaxElementByteLength();
144 P.identity = false;
145 P.x.Decode(bt, len);
146 P.y.Decode(bt, len);
147 return true;
148 }
149 default:
150 return false;
151 }
152}
153
154void ECP::EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
155{
156 if (P.identity)
157 NullStore().TransferTo(bt, EncodedPointSize(compressed));
158 else if (compressed)
159 {
160 bt.Put((byte)(2U + P.y.GetBit(0)));
161 P.x.Encode(bt, GetField().MaxElementByteLength());
162 }
163 else
164 {
165 unsigned int len = GetField().MaxElementByteLength();
166 bt.Put(4U); // uncompressed
167 P.x.Encode(bt, len);
168 P.y.Encode(bt, len);
169 }
170}
171
172void ECP::EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
173{
174 ArraySink sink(encodedPoint, EncodedPointSize(compressed));
175 EncodePoint(sink, P, compressed);
176 CRYPTOPP_ASSERT(sink.TotalPutLength() == EncodedPointSize(compressed));
177}
178
180{
181 SecByteBlock str;
182 BERDecodeOctetString(bt, str);
183 Point P;
184 if (!DecodePoint(P, str, str.size()))
186 return P;
187}
188
189void ECP::DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
190{
191 SecByteBlock str(EncodedPointSize(compressed));
192 EncodePoint(str, P, compressed);
193 DEREncodeOctetString(bt, str);
194}
195
196bool ECP::ValidateParameters(RandomNumberGenerator &rng, unsigned int level) const
197{
198 Integer p = FieldSize();
199
200 bool pass = p.IsOdd();
201 pass = pass && !m_a.IsNegative() && m_a<p && !m_b.IsNegative() && m_b<p;
202
203 if (level >= 1)
204 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
205
206 if (level >= 2)
207 pass = pass && VerifyPrime(rng, p);
208
209 return pass;
210}
211
212bool ECP::VerifyPoint(const Point &P) const
213{
214 const FieldElement &x = P.x, &y = P.y;
215 Integer p = FieldSize();
216 return P.identity ||
217 (!x.IsNegative() && x<p && !y.IsNegative() && y<p
218 && !(((x*x+m_a)*x+m_b-y*y)%p));
219}
220
221bool ECP::Equal(const Point &P, const Point &Q) const
222{
223 if (P.identity && Q.identity)
224 return true;
225
226 if (P.identity && !Q.identity)
227 return false;
228
229 if (!P.identity && Q.identity)
230 return false;
231
232 return (GetField().Equal(P.x,Q.x) && GetField().Equal(P.y,Q.y));
233}
234
236{
237#if defined(HAVE_GCC_INIT_PRIORITY) || defined(HAVE_MSC_INIT_PRIORITY) || defined(HAVE_XLC_INIT_PRIORITY)
238 return g_identity;
239#elif defined(CRYPTOPP_CXX11_STATIC_INIT)
240 static const ECP::Point g_identity;
241 return g_identity;
242#else
243 return Singleton<Point>().Ref();
244#endif
245}
246
247const ECP::Point& ECP::Inverse(const Point &P) const
248{
249 if (P.identity)
250 return P;
251 else
252 {
253 m_R.identity = false;
254 m_R.x = P.x;
255 m_R.y = GetField().Inverse(P.y);
256 return m_R;
257 }
258}
259
260const ECP::Point& ECP::Add(const Point &P, const Point &Q) const
261{
262 if (P.identity) return Q;
263 if (Q.identity) return P;
264 if (GetField().Equal(P.x, Q.x))
265 return GetField().Equal(P.y, Q.y) ? Double(P) : Identity();
266
267 FieldElement t = GetField().Subtract(Q.y, P.y);
268 t = GetField().Divide(t, GetField().Subtract(Q.x, P.x));
269 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().Square(t), P.x), Q.x);
270 m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y);
271
272 m_R.x.swap(x);
273 m_R.identity = false;
274 return m_R;
275}
276
277const ECP::Point& ECP::Double(const Point &P) const
278{
279 if (P.identity || P.y==GetField().Identity()) return Identity();
280
281 FieldElement t = GetField().Square(P.x);
282 t = GetField().Add(GetField().Add(GetField().Double(t), t), m_a);
283 t = GetField().Divide(t, GetField().Double(P.y));
284 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().Square(t), P.x), P.x);
285 m_R.y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.y);
286
287 m_R.x.swap(x);
288 m_R.identity = false;
289 return m_R;
290}
291
292template <class T, class Iterator> void ParallelInvert(const AbstractRing<T> &ring, Iterator begin, Iterator end)
293{
294 size_t n = end-begin;
295 if (n == 1)
296 *begin = ring.MultiplicativeInverse(*begin);
297 else if (n > 1)
298 {
299 std::vector<T> vec((n+1)/2);
300 unsigned int i;
301 Iterator it;
302
303 for (i=0, it=begin; i<n/2; i++, it+=2)
304 vec[i] = ring.Multiply(*it, *(it+1));
305 if (n%2 == 1)
306 vec[n/2] = *it;
307
308 ParallelInvert(ring, vec.begin(), vec.end());
309
310 for (i=0, it=begin; i<n/2; i++, it+=2)
311 {
312 if (!vec[i])
313 {
314 *it = ring.MultiplicativeInverse(*it);
315 *(it+1) = ring.MultiplicativeInverse(*(it+1));
316 }
317 else
318 {
319 std::swap(*it, *(it+1));
320 *it = ring.Multiply(*it, vec[i]);
321 *(it+1) = ring.Multiply(*(it+1), vec[i]);
322 }
323 }
324 if (n%2 == 1)
325 *it = vec[n/2];
326 }
327}
328
330{
331public:
332 ProjectiveDoubling(const ModularArithmetic &m_mr, const Integer &m_a, const Integer &m_b, const ECPPoint &Q)
333 : mr(m_mr)
334 {
335 CRYPTOPP_UNUSED(m_b);
336 if (Q.identity)
337 {
338 sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity();
339 aZ4 = P.z = mr.Identity();
340 }
341 else
342 {
343 P.x = Q.x;
344 P.y = Q.y;
345 sixteenY4 = P.z = mr.MultiplicativeIdentity();
346 aZ4 = m_a;
347 }
348 }
349
350 void Double()
351 {
352 twoY = mr.Double(P.y);
353 P.z = mr.Multiply(P.z, twoY);
354 fourY2 = mr.Square(twoY);
355 S = mr.Multiply(fourY2, P.x);
356 aZ4 = mr.Multiply(aZ4, sixteenY4);
357 M = mr.Square(P.x);
358 M = mr.Add(mr.Add(mr.Double(M), M), aZ4);
359 P.x = mr.Square(M);
360 mr.Reduce(P.x, S);
361 mr.Reduce(P.x, S);
362 mr.Reduce(S, P.x);
363 P.y = mr.Multiply(M, S);
364 sixteenY4 = mr.Square(fourY2);
365 mr.Reduce(P.y, mr.Half(sixteenY4));
366 }
367
368 const ModularArithmetic &mr;
370 Integer sixteenY4, aZ4, twoY, fourY2, S, M;
371};
372
374{
375 ZIterator() {}
376 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
377 Integer& operator*() {return it->z;}
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;
382};
383
384ECP::Point ECP::ScalarMultiply(const Point &P, const Integer &k) const
385{
386 Element result;
387 if (k.BitCount() <= 5)
389 else
390 ECP::SimultaneousMultiply(&result, P, &k, 1);
391 return result;
392}
393
394void ECP::SimultaneousMultiply(ECP::Point *results, const ECP::Point &P, const Integer *expBegin, unsigned int expCount) const
395{
396 if (!GetField().IsMontgomeryRepresentation())
397 {
398 ECP ecpmr(*this, true);
399 const ModularArithmetic &mr = ecpmr.GetField();
400 ecpmr.SimultaneousMultiply(results, ToMontgomery(mr, P), expBegin, expCount);
401 for (unsigned int i=0; i<expCount; i++)
402 results[i] = FromMontgomery(mr, results[i]);
403 return;
404 }
405
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);
413 unsigned int i;
414
415 for (i=0; i<expCount; i++)
416 {
417 CRYPTOPP_ASSERT(expBegin->NotNegative());
418 exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 5));
419 exponents[i].FindNextWindow();
420 }
421
422 unsigned int expBitPosition = 0;
423 bool notDone = true;
424
425 while (notDone)
426 {
427 notDone = false;
428 bool baseAdded = false;
429 for (i=0; i<expCount; i++)
430 {
431 if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
432 {
433 if (!baseAdded)
434 {
435 bases.push_back(rd.P);
436 baseAdded =true;
437 }
438
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);
442
443 exponents[i].FindNextWindow();
444 }
445 notDone = notDone || !exponents[i].finished;
446 }
447
448 if (notDone)
449 {
450 rd.Double();
451 expBitPosition++;
452 }
453 }
454
455 // convert from projective to affine coordinates
456 ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
457 for (i=0; i<bases.size(); i++)
458 {
459 if (bases[i].z.NotZero())
460 {
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);
465 }
466 }
467
468 std::vector<BaseAndExponent<Point, Integer> > finalCascade;
469 for (i=0; i<expCount; i++)
470 {
471 finalCascade.resize(baseIndices[i].size());
472 for (unsigned int j=0; j<baseIndices[i].size(); j++)
473 {
474 ProjectivePoint &base = bases[baseIndices[i][j]];
475 if (base.z.IsZero())
476 finalCascade[j].base.identity = true;
477 else
478 {
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);
483 else
484 finalCascade[j].base.y = base.y;
485 }
486 finalCascade[j].exponent = Integer(Integer::POSITIVE, 0, exponentWindows[i][j]);
487 }
488 results[i] = GeneralCascadeMultiplication(*this, finalCascade.begin(), finalCascade.end());
489 }
490}
491
492ECP::Point ECP::CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
493{
494 if (!GetField().IsMontgomeryRepresentation())
495 {
496 ECP ecpmr(*this, true);
497 const ModularArithmetic &mr = ecpmr.GetField();
498 return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));
499 }
500 else
502}
503
504NAMESPACE_END
505
506#endif
Classes and functions for working with ANS.1 objects.
void BERDecodeError()
Raises a BERDecodeErr.
Definition asn.h:104
virtual Element CascadeScalarMultiply(const Element &x, const Integer &e1, const Element &y, const Integer &e2) const
TODO.
Definition algebra.cpp:97
virtual void SimultaneousMultiply(Element *results, const Element &base, const Integer *exponents, unsigned int exponentsCount) const
Multiplies a base to multiple exponents in a group.
Definition algebra.cpp:256
virtual const Element & Subtract(const Element &a, const Element &b) const
Subtracts elements in the group.
Definition algebra.cpp:20
Abstract ring.
Definition algebra.h:119
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.
Definition filters.h:1200
lword TotalPutLength()
Provides the number of bytes written to the Sink.
Definition filters.h:1222
bool EndReached() const
Determine end of stream.
Definition asn.cpp:527
void MessageEnd()
Signals the end of messages to the object.
Definition asn.cpp:553
BER Sequence Decoder.
Definition asn.h:525
Interface for buffered transformations.
Definition cryptlib.h:1652
virtual size_t Get(byte &outByte)
Retrieve a 8-bit byte.
Definition cryptlib.cpp:528
lword TransferTo(BufferedTransformation &target, lword transferMax=LWORD_MAX, const std::string &channel=DEFAULT_CHANNEL)
move transferMax bytes of the buffered output to target as input
Definition cryptlib.h:1991
size_t Put(byte inByte, bool blocking=true)
Input a byte for processing.
Definition cryptlib.h:1673
void MessageEnd()
Signals the end of messages to the object.
Definition asn.cpp:624
DER Sequence Encoder.
Definition asn.h:557
Elliptic Curve over GF(p), where p is prime.
Definition ecp.h:27
bool InversionIsFast() const
Determine if inversion is fast.
Definition ecp.h:75
void EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
Encodes an elliptic curve point.
Definition ecp.cpp:172
ECP()
Construct an ECP.
Definition ecp.h:36
bool Equal(const Point &P, const Point &Q) const
Compare two points.
Definition ecp.cpp:221
void DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
DER Encodes an elliptic curve point.
Definition ecp.cpp:189
bool VerifyPoint(const Point &P) const
Verifies points on elliptic curve.
Definition ecp.cpp:212
unsigned int EncodedPointSize(bool compressed=false) const
Determines encoded point size.
Definition ecp.h:90
bool DecodePoint(Point &P, BufferedTransformation &bt, size_t len) const
Decodes an elliptic curve point.
Definition ecp.cpp:105
const Point & Inverse(const Point &P) const
Inverts the element in the group.
Definition ecp.cpp:247
Point BERDecodePoint(BufferedTransformation &bt) const
BER Decodes an elliptic curve point.
Definition ecp.cpp:179
void DEREncode(BufferedTransformation &bt) const
DER Encode.
Definition ecp.cpp:90
const Point & Add(const Point &P, const Point &Q) const
Adds elements in the group.
Definition ecp.cpp:260
const Point & Identity() const
Provides the Identity element.
Definition ecp.cpp:235
Multiple precision integer with arithmetic operations.
Definition integer.h:50
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Definition integer.cpp:3364
bool NotNegative() const
Determines if the Integer is non-negative.
Definition integer.h:344
static const Integer &CRYPTOPP_API One()
Integer representing 1.
Definition integer.cpp:4920
void swap(Integer &a)
Swaps this Integer with another Integer.
Definition integer.cpp:3173
bool IsNegative() const
Determines if the Integer is negative.
Definition integer.h:341
@ POSITIVE
the value is positive or 0
Definition integer.h:75
bool IsOdd() const
Determines if the Integer is odd parity.
Definition integer.h:356
Ring of congruence classes modulo n.
Definition modarith.h:44
const Integer & Square(const Integer &a) const
Square an element in the ring.
Definition modarith.h:197
const Integer & Inverse(const Integer &a) const
Inverts the element in the ring.
Definition integer.cpp:4655
void BERDecodeElement(BufferedTransformation &in, Element &a) const
Decodes element in DER format.
Definition integer.cpp:4565
unsigned int MaxElementByteLength() const
Provides the maximum byte size of an element in the ring.
Definition modarith.h:248
void DEREncodeElement(BufferedTransformation &out, const Element &a) const
Encodes element in DER format.
Definition integer.cpp:4560
bool Equal(const Integer &a, const Integer &b) const
Compare two elements for equality.
Definition modarith.h:135
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
Definition modarith.h:190
virtual Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.
Definition modarith.h:123
const Integer & Subtract(const Integer &a, const Integer &b) const
Subtracts elements in the ring.
Definition integer.cpp:4621
const Integer & Divide(const Integer &a, const Integer &b) const
Divides elements in the ring.
Definition modarith.h:218
const Integer & Add(const Integer &a, const Integer &b) const
Adds elements in the ring.
Definition integer.cpp:4581
virtual Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
Definition modarith.h:115
void DEREncode(BufferedTransformation &bt) const
Encodes in DER format.
Definition integer.cpp:4552
Performs modular arithmetic in Montgomery representation for increased speed.
Definition modarith.h:296
Empty store.
Definition filters.h:1321
Interface for random number generators.
Definition cryptlib.h:1435
size_type size() const
Provides the count of elements in the SecBlock.
Definition secblock.h:867
Restricts the instantiation of a class to one static object without locks.
Definition misc.h:307
CRYPTOPP_NOINLINE const T & Ref(CRYPTOPP_NOINLINE_DOTDOTDOT) const
Return a reference to the inner Singleton object.
Definition misc.h:327
Square block cipher.
Definition square.h:25
String-based implementation of Store interface.
Definition filters.h:1259
unsigned int word32
32-bit unsigned datatype
Definition config_int.h:62
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.
Classes and functions for number theoretic operations.
Precompiled header file.
Elliptical Curve Point over GF(p), where p is prime.
Definition ecpoint.h:21