source: git/src-cryptopp/ecp.cpp

Last change on this file was e230cb0, checked in by David Stainton <dstainton415@…>, at 2016-10-12T13:27:29Z

Add cryptopp from tag CRYPTOPP_5_6_5
  • Property mode set to 100644
File size: 11.9 KB
Line 
1// ecp.cpp - 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
15NAMESPACE_BEGIN(CryptoPP)
16
17ANONYMOUS_NAMESPACE_BEGIN
18static inline ECP::Point ToMontgomery(const ModularArithmetic &mr, const ECP::Point &P)
19{
20        return P.identity ? P : ECP::Point(mr.ConvertIn(P.x), mr.ConvertIn(P.y));
21}
22
23static inline ECP::Point FromMontgomery(const ModularArithmetic &mr, const ECP::Point &P)
24{
25        return P.identity ? P : ECP::Point(mr.ConvertOut(P.x), mr.ConvertOut(P.y));
26}
27NAMESPACE_END
28
29ECP::ECP(const ECP &ecp, bool convertToMontgomeryRepresentation)
30{
31        if (convertToMontgomeryRepresentation && !ecp.GetField().IsMontgomeryRepresentation())
32        {
33                m_fieldPtr.reset(new MontgomeryRepresentation(ecp.GetField().GetModulus()));
34                m_a = GetField().ConvertIn(ecp.m_a);
35                m_b = GetField().ConvertIn(ecp.m_b);
36        }
37        else
38                operator=(ecp);
39}
40
41ECP::ECP(BufferedTransformation &bt)
42        : m_fieldPtr(new Field(bt))
43{
44        BERSequenceDecoder seq(bt);
45        GetField().BERDecodeElement(seq, m_a);
46        GetField().BERDecodeElement(seq, m_b);
47        // skip optional seed
48        if (!seq.EndReached())
49        {
50                SecByteBlock seed;
51                unsigned int unused;
52                BERDecodeBitString(seq, seed, unused);
53        }
54        seq.MessageEnd();
55}
56
57void ECP::DEREncode(BufferedTransformation &bt) const
58{
59        GetField().DEREncode(bt);
60        DERSequenceEncoder seq(bt);
61        GetField().DEREncodeElement(seq, m_a);
62        GetField().DEREncodeElement(seq, m_b);
63        seq.MessageEnd();
64}
65
66bool ECP::DecodePoint(ECP::Point &P, const byte *encodedPoint, size_t encodedPointLen) const
67{
68        StringStore store(encodedPoint, encodedPointLen);
69        return DecodePoint(P, store, encodedPointLen);
70}
71
72bool ECP::DecodePoint(ECP::Point &P, BufferedTransformation &bt, size_t encodedPointLen) const
73{
74        byte type;
75        if (encodedPointLen < 1 || !bt.Get(type))
76                return false;
77
78        switch (type)
79        {
80        case 0:
81                P.identity = true;
82                return true;
83        case 2:
84        case 3:
85        {
86                if (encodedPointLen != EncodedPointSize(true))
87                        return false;
88
89                Integer p = FieldSize();
90
91                P.identity = false;
92                P.x.Decode(bt, GetField().MaxElementByteLength());
93                P.y = ((P.x*P.x+m_a)*P.x+m_b) % p;
94
95                if (Jacobi(P.y, p) !=1)
96                        return false;
97
98                P.y = ModularSquareRoot(P.y, p);
99
100                if ((type & 1) != P.y.GetBit(0))
101                        P.y = p-P.y;
102
103                return true;
104        }
105        case 4:
106        {
107                if (encodedPointLen != EncodedPointSize(false))
108                        return false;
109
110                unsigned int len = GetField().MaxElementByteLength();
111                P.identity = false;
112                P.x.Decode(bt, len);
113                P.y.Decode(bt, len);
114                return true;
115        }
116        default:
117                return false;
118        }
119}
120
121void ECP::EncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
122{
123        if (P.identity)
124                NullStore().TransferTo(bt, EncodedPointSize(compressed));
125        else if (compressed)
126        {
127                bt.Put(2 + P.y.GetBit(0));
128                P.x.Encode(bt, GetField().MaxElementByteLength());
129        }
130        else
131        {
132                unsigned int len = GetField().MaxElementByteLength();
133                bt.Put(4);      // uncompressed
134                P.x.Encode(bt, len);
135                P.y.Encode(bt, len);
136        }
137}
138
139void ECP::EncodePoint(byte *encodedPoint, const Point &P, bool compressed) const
140{
141        ArraySink sink(encodedPoint, EncodedPointSize(compressed));
142        EncodePoint(sink, P, compressed);
143        CRYPTOPP_ASSERT(sink.TotalPutLength() == EncodedPointSize(compressed));
144}
145
146ECP::Point ECP::BERDecodePoint(BufferedTransformation &bt) const
147{
148        SecByteBlock str;
149        BERDecodeOctetString(bt, str);
150        Point P;
151        if (!DecodePoint(P, str, str.size()))
152                BERDecodeError();
153        return P;
154}
155
156void ECP::DEREncodePoint(BufferedTransformation &bt, const Point &P, bool compressed) const
157{
158        SecByteBlock str(EncodedPointSize(compressed));
159        EncodePoint(str, P, compressed);
160        DEREncodeOctetString(bt, str);
161}
162
163bool ECP::ValidateParameters(RandomNumberGenerator &rng, unsigned int level) const
164{
165        Integer p = FieldSize();
166
167        bool pass = p.IsOdd();
168        pass = pass && !m_a.IsNegative() && m_a<p && !m_b.IsNegative() && m_b<p;
169
170        if (level >= 1)
171                pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
172
173        if (level >= 2)
174                pass = pass && VerifyPrime(rng, p);
175
176        return pass;
177}
178
179bool ECP::VerifyPoint(const Point &P) const
180{
181        const FieldElement &x = P.x, &y = P.y;
182        Integer p = FieldSize();
183        return P.identity ||
184                (!x.IsNegative() && x<p && !y.IsNegative() && y<p
185                && !(((x*x+m_a)*x+m_b-y*y)%p));
186}
187
188bool ECP::Equal(const Point &P, const Point &Q) const
189{
190        if (P.identity && Q.identity)
191                return true;
192
193        if (P.identity && !Q.identity)
194                return false;
195
196        if (!P.identity && Q.identity)
197                return false;
198
199        return (GetField().Equal(P.x,Q.x) && GetField().Equal(P.y,Q.y));
200}
201
202const ECP::Point& ECP::Identity() const
203{
204        return Singleton<Point>().Ref();
205}
206
207const ECP::Point& ECP::Inverse(const Point &P) const
208{
209        if (P.identity)
210                return P;
211        else
212        {
213                m_R.identity = false;
214                m_R.x = P.x;
215                m_R.y = GetField().Inverse(P.y);
216                return m_R;
217        }
218}
219
220const ECP::Point& ECP::Add(const Point &P, const Point &Q) const
221{
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();
226
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);
231
232        m_R.x.swap(x);
233        m_R.identity = false;
234        return m_R;
235}
236
237const ECP::Point& ECP::Double(const Point &P) const
238{
239        if (P.identity || P.y==GetField().Identity()) return Identity();
240
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);
246
247        m_R.x.swap(x);
248        m_R.identity = false;
249        return m_R;
250}
251
252template <class T, class Iterator> void ParallelInvert(const AbstractRing<T> &ring, Iterator begin, Iterator end)
253{
254        size_t n = end-begin;
255        if (n == 1)
256                *begin = ring.MultiplicativeInverse(*begin);
257        else if (n > 1)
258        {
259                std::vector<T> vec((n+1)/2);
260                unsigned int i;
261                Iterator it;
262
263                for (i=0, it=begin; i<n/2; i++, it+=2)
264                        vec[i] = ring.Multiply(*it, *(it+1));
265                if (n%2 == 1)
266                        vec[n/2] = *it;
267
268                ParallelInvert(ring, vec.begin(), vec.end());
269
270                for (i=0, it=begin; i<n/2; i++, it+=2)
271                {
272                        if (!vec[i])
273                        {
274                                *it = ring.MultiplicativeInverse(*it);
275                                *(it+1) = ring.MultiplicativeInverse(*(it+1));
276                        }
277                        else
278                        {
279                                std::swap(*it, *(it+1));
280                                *it = ring.Multiply(*it, vec[i]);
281                                *(it+1) = ring.Multiply(*(it+1), vec[i]);
282                        }
283                }
284                if (n%2 == 1)
285                        *it = vec[n/2];
286        }
287}
288
289struct ProjectivePoint
290{
291        ProjectivePoint() {}
292        ProjectivePoint(const Integer &x, const Integer &y, const Integer &z)
293                : x(x), y(y), z(z)      {}
294
295        Integer x,y,z;
296};
297
298class ProjectiveDoubling
299{
300public:
301        ProjectiveDoubling(const ModularArithmetic &m_mr, const Integer &m_a, const Integer &m_b, const ECPPoint &Q)
302                : mr(m_mr), firstDoubling(true), negated(false)
303        {
304                CRYPTOPP_UNUSED(m_b);
305                if (Q.identity)
306                {
307                        sixteenY4 = P.x = P.y = mr.MultiplicativeIdentity();
308                        aZ4 = P.z = mr.Identity();
309                }
310                else
311                {
312                        P.x = Q.x;
313                        P.y = Q.y;
314                        sixteenY4 = P.z = mr.MultiplicativeIdentity();
315                        aZ4 = m_a;
316                }
317        }
318
319        void Double()
320        {
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);
326                M = mr.Square(P.x);
327                M = mr.Add(mr.Add(mr.Double(M), M), aZ4);
328                P.x = mr.Square(M);
329                mr.Reduce(P.x, S);
330                mr.Reduce(P.x, S);
331                mr.Reduce(S, P.x);
332                P.y = mr.Multiply(M, S);
333                sixteenY4 = mr.Square(fourY2);
334                mr.Reduce(P.y, mr.Half(sixteenY4));
335        }
336
337        const ModularArithmetic &mr;
338        ProjectivePoint P;
339        bool firstDoubling, negated;
340        Integer sixteenY4, aZ4, twoY, fourY2, S, M;
341};
342
343struct ZIterator
344{
345        ZIterator() {}
346        ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
347        Integer& operator*() {return it->z;}
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;
352};
353
354ECP::Point ECP::ScalarMultiply(const Point &P, const Integer &k) const
355{
356        Element result;
357        if (k.BitCount() <= 5)
358                AbstractGroup<ECPPoint>::SimultaneousMultiply(&result, P, &k, 1);
359        else
360                ECP::SimultaneousMultiply(&result, P, &k, 1);
361        return result;
362}
363
364void ECP::SimultaneousMultiply(ECP::Point *results, const ECP::Point &P, const Integer *expBegin, unsigned int expCount) const
365{
366        if (!GetField().IsMontgomeryRepresentation())
367        {
368                ECP ecpmr(*this, true);
369                const ModularArithmetic &mr = ecpmr.GetField();
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]);
373                return;
374        }
375
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);
383        unsigned int i;
384
385        for (i=0; i<expCount; i++)
386        {
387                CRYPTOPP_ASSERT(expBegin->NotNegative());
388                exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 5));
389                exponents[i].FindNextWindow();
390        }
391
392        unsigned int expBitPosition = 0;
393        bool notDone = true;
394
395        while (notDone)
396        {
397                notDone = false;
398                bool baseAdded = false;
399                for (i=0; i<expCount; i++)
400                {
401                        if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
402                        {
403                                if (!baseAdded)
404                                {
405                                        bases.push_back(rd.P);
406                                        baseAdded =true;
407                                }
408
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);
412
413                                exponents[i].FindNextWindow();
414                        }
415                        notDone = notDone || !exponents[i].finished;
416                }
417
418                if (notDone)
419                {
420                        rd.Double();
421                        expBitPosition++;
422                }
423        }
424
425        // convert from projective to affine coordinates
426        ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
427        for (i=0; i<bases.size(); i++)
428        {
429                if (bases[i].z.NotZero())
430                {
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);
435                }
436        }
437
438        std::vector<BaseAndExponent<Point, Integer> > finalCascade;
439        for (i=0; i<expCount; i++)
440        {
441                finalCascade.resize(baseIndices[i].size());
442                for (unsigned int j=0; j<baseIndices[i].size(); j++)
443                {
444                        ProjectivePoint &base = bases[baseIndices[i][j]];
445                        if (base.z.IsZero())
446                                finalCascade[j].base.identity = true;
447                        else
448                        {
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);
453                                else
454                                        finalCascade[j].base.y = base.y;
455                        }
456                        finalCascade[j].exponent = Integer(Integer::POSITIVE, 0, exponentWindows[i][j]);
457                }
458                results[i] = GeneralCascadeMultiplication(*this, finalCascade.begin(), finalCascade.end());
459        }
460}
461
462ECP::Point ECP::CascadeScalarMultiply(const Point &P, const Integer &k1, const Point &Q, const Integer &k2) const
463{
464        if (!GetField().IsMontgomeryRepresentation())
465        {
466                ECP ecpmr(*this, true);
467                const ModularArithmetic &mr = ecpmr.GetField();
468                return FromMontgomery(mr, ecpmr.CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));
469        }
470        else
471                return AbstractGroup<Point>::CascadeScalarMultiply(P, k1, Q, k2);
472}
473
474NAMESPACE_END
475
476#endif
Note: See TracBrowser for help on using the repository browser.