00001
00002
00003
#include "pch.h"
00004
#include "ecp.h"
00005
#include "asn.h"
00006
#include "nbtheory.h"
00007
00008
#include "algebra.cpp"
00009
#include "eprecomp.cpp"
00010
00011 NAMESPACE_BEGIN(CryptoPP)
00012
00013 ANONYMOUS_NAMESPACE_BEGIN
00014 static inline
ECP::Point ToMontgomery(const
ModularArithmetic &mr, const
ECP::Point &P)
00015 {
00016
return P.identity ? P :
ECP::Point(mr.ConvertIn(P.x), mr.ConvertIn(P.y));
00017 }
00018
00019
static inline ECP::Point FromMontgomery(
const ModularArithmetic &mr,
const ECP::Point &P)
00020 {
00021
return P.
identity ? P :
ECP::Point(mr.
ConvertOut(P.
x), mr.
ConvertOut(P.
y));
00022 }
00023 NAMESPACE_END
00024
00025 ECP::ECP(
const ECP &ecp,
bool convertToMontgomeryRepresentation)
00026 {
00027
if (convertToMontgomeryRepresentation && !ecp.
GetField().
IsMontgomeryRepresentation())
00028 {
00029 m_fieldPtr.reset(
new MontgomeryRepresentation(ecp.
GetField().
GetModulus()));
00030 m_a = GetField().
ConvertIn(ecp.
m_a);
00031 m_b = GetField().ConvertIn(ecp.
m_b);
00032 }
00033
else
00034 operator=(ecp);
00035 }
00036
00037 ECP::ECP(
BufferedTransformation &bt)
00038 : m_fieldPtr(new Field(bt))
00039 {
00040
BERSequenceDecoder seq(bt);
00041 GetField().BERDecodeElement(seq, m_a);
00042 GetField().BERDecodeElement(seq, m_b);
00043
00044
if (!seq.
EndReached())
00045 BERDecodeOctetString(seq, TheBitBucket());
00046 seq.
MessageEnd();
00047 }
00048
00049
void ECP::DEREncode(
BufferedTransformation &bt)
const
00050
{
00051 GetField().
DEREncode(bt);
00052
DERSequenceEncoder seq(bt);
00053 GetField().
DEREncodeElement(seq, m_a);
00054 GetField().
DEREncodeElement(seq, m_b);
00055 seq.
MessageEnd();
00056 }
00057
00058
bool ECP::DecodePoint(
ECP::Point &P,
const byte *encodedPoint,
unsigned int encodedPointLen)
const
00059
{
00060
StringStore store(encodedPoint, encodedPointLen);
00061
return DecodePoint(P, store, encodedPointLen);
00062 }
00063
00064
bool ECP::DecodePoint(
ECP::Point &P,
BufferedTransformation &bt,
unsigned int encodedPointLen)
const
00065
{
00066 byte type;
00067
if (encodedPointLen < 1 || !bt.
Get(type))
00068
return false;
00069
00070
switch (type)
00071 {
00072
case 0:
00073 P.
identity =
true;
00074
return true;
00075
case 2:
00076
case 3:
00077 {
00078
if (encodedPointLen != EncodedPointSize(
true))
00079
return false;
00080
00081
Integer p = FieldSize();
00082
00083 P.
identity =
false;
00084 P.
x.
Decode(bt, GetField().MaxElementByteLength());
00085 P.
y = ((P.
x*P.
x+m_a)*P.
x+m_b) % p;
00086
00087
if (Jacobi(P.
y, p) !=1)
00088
return false;
00089
00090 P.
y = ModularSquareRoot(P.
y, p);
00091
00092
if ((type & 1) != P.
y.
GetBit(0))
00093 P.
y = p-P.
y;
00094
00095
return true;
00096 }
00097
case 4:
00098 {
00099
if (encodedPointLen != EncodedPointSize(
false))
00100
return false;
00101
00102
unsigned int len = GetField().
MaxElementByteLength();
00103 P.
identity =
false;
00104 P.
x.
Decode(bt, len);
00105 P.
y.
Decode(bt, len);
00106
return true;
00107 }
00108
default:
00109
return false;
00110 }
00111 }
00112
00113
void ECP::EncodePoint(
BufferedTransformation &bt,
const Point &P,
bool compressed)
const
00114
{
00115
if (P.identity)
00116
NullStore().TransferTo(bt, EncodedPointSize(compressed));
00117
else if (compressed)
00118 {
00119 bt.
Put(2 + P.y.GetBit(0));
00120 P.x.Encode(bt, GetField().MaxElementByteLength());
00121 }
00122
else
00123 {
00124
unsigned int len = GetField().
MaxElementByteLength();
00125 bt.
Put(4);
00126 P.x.Encode(bt, len);
00127 P.y.Encode(bt, len);
00128 }
00129 }
00130
00131
void ECP::EncodePoint(byte *encodedPoint,
const Point &P,
bool compressed)
const
00132
{
00133
ArraySink sink(encodedPoint, EncodedPointSize(compressed));
00134 EncodePoint(sink, P, compressed);
00135 assert(sink.
TotalPutLength() == EncodedPointSize(compressed));
00136 }
00137
00138
ECP::Point ECP::BERDecodePoint(
BufferedTransformation &bt)
const
00139
{
00140
SecByteBlock str;
00141 BERDecodeOctetString(bt, str);
00142 Point P;
00143
if (!DecodePoint(P, str, str.
size()))
00144 BERDecodeError();
00145
return P;
00146 }
00147
00148
void ECP::DEREncodePoint(
BufferedTransformation &bt,
const Point &P,
bool compressed)
const
00149
{
00150
SecByteBlock str(EncodedPointSize(compressed));
00151 EncodePoint(str, P, compressed);
00152 DEREncodeOctetString(bt, str);
00153 }
00154
00155
bool ECP::ValidateParameters(
RandomNumberGenerator &rng,
unsigned int level)
const
00156
{
00157
Integer p = FieldSize();
00158
00159
bool pass = p.
IsOdd();
00160 pass = pass && !m_a.
IsNegative() && m_a<p && !m_b.
IsNegative() && m_b<p;
00161
00162
if (level >= 1)
00163 pass = pass && ((4*m_a*m_a*m_a+27*m_b*m_b)%p).IsPositive();
00164
00165
if (level >= 2)
00166 pass = pass && VerifyPrime(rng, p);
00167
00168
return pass;
00169 }
00170
00171
bool ECP::VerifyPoint(
const Point &P)
const
00172
{
00173
const FieldElement &x = P.x, &y = P.y;
00174
Integer p = FieldSize();
00175
return P.identity ||
00176 (!x.IsNegative() && x<p && !y.
IsNegative() && y<p
00177 && !(((x*x+m_a)*x+m_b-y*y)%p));
00178 }
00179
00180
bool ECP::Equal(
const Point &P,
const Point &Q)
const
00181
{
00182
if (P.identity && Q.identity)
00183
return true;
00184
00185
if (P.identity && !Q.identity)
00186
return false;
00187
00188
if (!P.identity && Q.identity)
00189
return false;
00190
00191
return (GetField().
Equal(P.x,Q.x) && GetField().
Equal(P.y,Q.y));
00192 }
00193
00194
const ECP::Point& ECP::Identity()
const
00195
{
00196
static const Point zero;
00197
return zero;
00198 }
00199
00200
const ECP::Point& ECP::Inverse(
const Point &P)
const
00201
{
00202
if (P.identity)
00203
return P;
00204
else
00205 {
00206 m_R.
identity =
false;
00207 m_R.
x = P.x;
00208 m_R.
y = GetField().
Inverse(P.y);
00209
return m_R;
00210 }
00211 }
00212
00213
const ECP::Point& ECP::Add(
const Point &P,
const Point &Q)
const
00214
{
00215
if (P.identity)
return Q;
00216
if (Q.identity)
return P;
00217
if (GetField().
Equal(P.x, Q.x))
00218
return GetField().
Equal(P.y, Q.y) ? Double(P) : Identity();
00219
00220 FieldElement t = GetField().
Subtract(Q.y, P.y);
00221 t = GetField().Divide(t, GetField().Subtract(Q.x, P.x));
00222 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().
Square(t), P.x), Q.x);
00223 m_R.
y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.
y);
00224
00225 m_R.
x.
swap(x);
00226 m_R.
identity =
false;
00227
return m_R;
00228 }
00229
00230
const ECP::Point& ECP::Double(
const Point &P)
const
00231
{
00232
if (P.identity || P.y==GetField().Identity())
return Identity();
00233
00234 FieldElement t = GetField().Square(P.x);
00235 t = GetField().Add(GetField().Add(GetField().Double(t), t), m_a);
00236 t = GetField().Divide(t, GetField().Double(P.y));
00237 FieldElement x = GetField().Subtract(GetField().Subtract(GetField().
Square(t), P.x), P.x);
00238 m_R.
y = GetField().Subtract(GetField().Multiply(t, GetField().Subtract(P.x, x)), P.
y);
00239
00240 m_R.
x.
swap(x);
00241 m_R.
identity =
false;
00242
return m_R;
00243 }
00244
00245
template <
class T,
class Iterator>
void ParallelInvert(
const AbstractRing<T> &ring, Iterator begin, Iterator end)
00246 {
00247
unsigned int n = end-begin;
00248
if (n == 1)
00249 *begin = ring.
MultiplicativeInverse(*begin);
00250
else if (n > 1)
00251 {
00252 std::vector<T> vec((n+1)/2);
00253
unsigned int i;
00254 Iterator it;
00255
00256
for (i=0, it=begin; i<n/2; i++, it+=2)
00257 vec[i] = ring.
Multiply(*it, *(it+1));
00258
if (n%2 == 1)
00259 vec[n/2] = *it;
00260
00261 ParallelInvert(ring, vec.begin(), vec.end());
00262
00263
for (i=0, it=begin; i<n/2; i++, it+=2)
00264 {
00265
if (!vec[i])
00266 {
00267 *it = ring.
MultiplicativeInverse(*it);
00268 *(it+1) = ring.
MultiplicativeInverse(*(it+1));
00269 }
00270
else
00271 {
00272 std::swap(*it, *(it+1));
00273 *it = ring.
Multiply(*it, vec[i]);
00274 *(it+1) = ring.
Multiply(*(it+1), vec[i]);
00275 }
00276 }
00277
if (n%2 == 1)
00278 *it = vec[n/2];
00279 }
00280 }
00281
00282
struct ProjectivePoint
00283 {
00284 ProjectivePoint() {}
00285 ProjectivePoint(
const Integer &x,
const Integer &y,
const Integer &z)
00286 : x(x), y(y), z(z) {}
00287
00288
Integer x,y,z;
00289 };
00290
00291
class ProjectiveDoubling
00292 {
00293
public:
00294 ProjectiveDoubling(
const ModularArithmetic &mr,
const Integer &m_a,
const Integer &m_b,
const ECPPoint &Q)
00295 : mr(mr), firstDoubling(true), negated(false)
00296 {
00297
if (Q.identity)
00298 {
00299 sixteenY4 = P.x = P.y = mr.
MultiplicativeIdentity();
00300 aZ4 = P.z = mr.
Identity();
00301 }
00302
else
00303 {
00304 P.x = Q.x;
00305 P.y = Q.y;
00306 sixteenY4 = P.z = mr.
MultiplicativeIdentity();
00307 aZ4 = m_a;
00308 }
00309 }
00310
00311
void Double()
00312 {
00313 twoY = mr.Double(P.y);
00314 P.z = mr.Multiply(P.z, twoY);
00315 fourY2 = mr.Square(twoY);
00316 S = mr.Multiply(fourY2, P.x);
00317 aZ4 = mr.Multiply(aZ4, sixteenY4);
00318 M = mr.Square(P.x);
00319 M = mr.Add(mr.Add(mr.Double(M), M), aZ4);
00320 P.x = mr.Square(M);
00321 mr.Reduce(P.x, S);
00322 mr.Reduce(P.x, S);
00323 mr.Reduce(S, P.x);
00324 P.y = mr.Multiply(M, S);
00325 sixteenY4 = mr.Square(fourY2);
00326 mr.Reduce(P.y, mr.Half(sixteenY4));
00327 }
00328
00329
const ModularArithmetic &mr;
00330 ProjectivePoint P;
00331
bool firstDoubling, negated;
00332
Integer sixteenY4, aZ4, twoY, fourY2, S, M;
00333 };
00334
00335
struct ZIterator
00336 {
00337 ZIterator() {}
00338 ZIterator(std::vector<ProjectivePoint>::iterator it) : it(it) {}
00339
Integer& operator*() {
return it->z;}
00340
int operator-(ZIterator it2) {
return it-it2.it;}
00341 ZIterator operator+(
int i) {
return ZIterator(it+i);}
00342 ZIterator& operator+=(
int i) {it+=i;
return *
this;}
00343 std::vector<ProjectivePoint>::iterator it;
00344 };
00345
00346
ECP::Point ECP::ScalarMultiply(
const Point &P,
const Integer &k)
const
00347
{
00348 Element result;
00349
if (k.
BitCount() <= 5)
00350
AbstractGroup<ECPPoint>::SimultaneousMultiply(&result, P, &k, 1);
00351
else
00352 ECP::SimultaneousMultiply(&result, P, &k, 1);
00353
return result;
00354 }
00355
00356
void ECP::SimultaneousMultiply(
ECP::Point *results,
const ECP::Point &P,
const Integer *expBegin,
unsigned int expCount)
const
00357
{
00358
if (!GetField().IsMontgomeryRepresentation())
00359 {
00360
ECP ecpmr(*
this,
true);
00361
const ModularArithmetic &mr = ecpmr.
GetField();
00362 ecpmr.
SimultaneousMultiply(results, ToMontgomery(mr, P), expBegin, expCount);
00363
for (
unsigned int i=0; i<expCount; i++)
00364 results[i] = FromMontgomery(mr, results[i]);
00365
return;
00366 }
00367
00368 ProjectiveDoubling rd(GetField(), m_a, m_b, P);
00369 std::vector<ProjectivePoint> bases;
00370 std::vector<WindowSlider> exponents;
00371 exponents.reserve(expCount);
00372 std::vector<std::vector<unsigned int> > baseIndices(expCount);
00373 std::vector<std::vector<bool> > negateBase(expCount);
00374 std::vector<std::vector<unsigned int> > exponentWindows(expCount);
00375
unsigned int i;
00376
00377
for (i=0; i<expCount; i++)
00378 {
00379 assert(expBegin->
NotNegative());
00380 exponents.push_back(WindowSlider(*expBegin++, InversionIsFast(), 5));
00381 exponents[i].FindNextWindow();
00382 }
00383
00384
unsigned int expBitPosition = 0;
00385
bool notDone =
true;
00386
00387
while (notDone)
00388 {
00389 notDone =
false;
00390
bool baseAdded =
false;
00391
for (i=0; i<expCount; i++)
00392 {
00393
if (!exponents[i].finished && expBitPosition == exponents[i].windowBegin)
00394 {
00395
if (!baseAdded)
00396 {
00397 bases.push_back(rd.P);
00398 baseAdded =
true;
00399 }
00400
00401 exponentWindows[i].push_back(exponents[i].expWindow);
00402 baseIndices[i].push_back(bases.size()-1);
00403 negateBase[i].push_back(exponents[i].negateNext);
00404
00405 exponents[i].FindNextWindow();
00406 }
00407 notDone = notDone || !exponents[i].finished;
00408 }
00409
00410
if (notDone)
00411 {
00412 rd.Double();
00413 expBitPosition++;
00414 }
00415 }
00416
00417
00418 ParallelInvert(GetField(), ZIterator(bases.begin()), ZIterator(bases.end()));
00419
for (i=0; i<bases.size(); i++)
00420 {
00421
if (bases[i].z.NotZero())
00422 {
00423 bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
00424 bases[i].z = GetField().Square(bases[i].z);
00425 bases[i].x = GetField().Multiply(bases[i].x, bases[i].z);
00426 bases[i].y = GetField().Multiply(bases[i].y, bases[i].z);
00427 }
00428 }
00429
00430 std::vector<BaseAndExponent<Point, word> > finalCascade;
00431
for (i=0; i<expCount; i++)
00432 {
00433 finalCascade.resize(baseIndices[i].size());
00434
for (
unsigned int j=0; j<baseIndices[i].size(); j++)
00435 {
00436 ProjectivePoint &base = bases[baseIndices[i][j]];
00437
if (base.z.IsZero())
00438 finalCascade[j].base.identity =
true;
00439
else
00440 {
00441 finalCascade[j].base.identity =
false;
00442 finalCascade[j].base.x = base.x;
00443
if (negateBase[i][j])
00444 finalCascade[j].base.y = GetField().Inverse(base.y);
00445
else
00446 finalCascade[j].base.y = base.y;
00447 }
00448 finalCascade[j].exponent = exponentWindows[i][j];
00449 }
00450 results[i] = GeneralCascadeMultiplication(*
this, finalCascade.begin(), finalCascade.end());
00451 }
00452 }
00453
00454
ECP::Point ECP::CascadeScalarMultiply(
const Point &P,
const Integer &k1,
const Point &Q,
const Integer &k2)
const
00455
{
00456
if (!GetField().IsMontgomeryRepresentation())
00457 {
00458
ECP ecpmr(*
this,
true);
00459
const ModularArithmetic &mr = ecpmr.
GetField();
00460
return FromMontgomery(mr, ecpmr.
CascadeScalarMultiply(ToMontgomery(mr, P), k1, ToMontgomery(mr, Q), k2));
00461 }
00462
else
00463
return AbstractGroup<Point>::CascadeScalarMultiply(P, k1, Q, k2);
00464 }
00465
00466
00467
00468
void EcPrecomputation<ECP>::SetCurve(
const ECP &ec)
00469 {
00470 m_ec.reset(
new ECP(ec,
true));
00471 m_ecOriginal = ec;
00472 }
00473
00474
template class AbstractGroup<ECP::Point>;
00475
template class DL_FixedBasePrecomputationImpl<ECP::Point>;
00476
00477 NAMESPACE_END