Well guys.. Here goes my first post here :)
I've coded few ECC methods that are very frequently used in Cryptography.
I've tested the code with the examples posted in certicom website & it works well.
But then I implemented ECDSA_Sign() --> Elliptic Curve Digital Signature Algorithm using my own written methods, & I get a crash in a NTL InvMod() function, in my PointDouble() function.
I cant understand whats going wrong.
Some help & guidance will come in handy.
Note that I am originally a Delphi coder, and started C++ only a week ago.
Here is the Code for you guys to check ::
//The algorithms are implemented with the help of "Guide To Elliptic Curve Cryptography".//
//.......................................................................................//
#include <windows.h>
#include "commctrl.h"
#include "shellapi.h"
#include <string>
#include <sstream>
#include <stdio.h>
#include <conio.h>
#include <time.h>
#define NTL_NO_MIN_MAX
#include <NTL/ZZ.h>
#include <NTL/ZZ_p.h>
#include <NTL/tools.h>
NTL_CLIENT
HINSTANCE hInst;
using namespace std;
ZZ SquareMod(ZZ a, ZZ prime)
{
ZZ res;
res = to_ZZ(0);
res = MulMod(a, a, prime);
return res;
}
string ReverseString(string inData)
{
int i, len;
string outData = "";
len = inData.length();
for(i = len - 1; i >= 0; i--)
{
outData += inData[i];
}
return outData;
}
string BinaryEncode(ZZ num)
{
string bin, res;
ZZ bNum = num;
ZZ rem = to_ZZ(0);
ZZ base = to_ZZ(2);
stringstream ss;
while (bNum != 1)
{
bNum = bNum / 2;
rem = bNum % 2;
ss<<rem;
res = ss.str();
}
if ((num % base) != 0)
{
res = '1' + res;
}
else
{
res = '0' + res;
}
bin = ReverseString(res);
return bin;
}
struct ECPoint
{
ZZ XCoordinate, YCoordinate;
bool Infinity;
};
/*Copy a Point on an elliptic Curve to another point*/
ECPoint PointCopy(ECPoint Source)
{
ECPoint Destination;
Destination.Infinity = Source.Infinity;
Destination.XCoordinate = Source.XCoordinate;
Destination.YCoordinate = Source.YCoordinate;
return Destination;
}
/*. Doubles a point on a defined Elliptic Curve over GF(p).
. 2*Point = Doubled .
........................................................*/
ECPoint EC_PointDouble(ECPoint A, ZZ prime, ZZ a)
{
ECPoint DoubledPoint;
ZZ Zero;
Zero = to_ZZ(0);
int cmp = 1;
if (A.Infinity)
{
DoubledPoint = PointCopy(A);
return DoubledPoint;
}
else
{
cmp = compare(A.YCoordinate, Zero);
if (cmp == 0)
{
DoubledPoint.Infinity = true;
DoubledPoint.XCoordinate = DoubledPoint.YCoordinate = Zero;
Zero.kill();
return DoubledPoint;
}
else
{
Zero.kill();
ZZ XSqr, tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7, tmp8;
// Init Variable
XSqr = to_ZZ(0);
tmp1 = to_ZZ(0);
tmp2 = to_ZZ(0);
tmp3 = to_ZZ(0);
tmp4 = to_ZZ(0);
tmp5 = to_ZZ(0);
tmp6 = to_ZZ(0);
tmp7 = to_ZZ(0);
tmp8 = to_ZZ(0);
// Init Variable
DoubledPoint.Infinity = false;
XSqr = SquareMod(A.XCoordinate , prime);
tmp1 = AddMod(XSqr, XSqr, prime);
tmp2 = AddMod(tmp1, XSqr, prime); // 3X1^2
tmp3 = AddMod(tmp2, a, prime); // 3X1^2 + a
tmp1.kill();
tmp1 = AddMod(A.YCoordinate, A.YCoordinate, prime); // tmp1 = 2Y1
if (tmp1 < 0)
{
tmp1 = prime + tmp1;
}
tmp4 = InvMod(tmp1, prime); // 2Y1 ^ -1 mod prime //This is causing the prob
tmp5 = MulMod(tmp3, tmp4, prime); // tmp5 = [(3X1^2 + a)/2Y1]
tmp6 = SquareMod(tmp5, prime); // tmp6 = [(3X1^2 + a)/2Y1] ^ 2 mod prime
tmp7 = AddMod(A.XCoordinate, A.XCoordinate, prime); // tmp7 = 2X1 mod prime
tmp7 = -tmp7; // tmp7 = -2X1
tmp8 = AddMod(tmp6, tmp7, prime); // tmp8 = [(3X1^2 + a)/2Y1] ^ 2 mod prime - (2X1)
if (tmp8 < 0)
{
tmp8 = prime + tmp8;
}
DoubledPoint.XCoordinate = tmp8;
tmp6.kill();
tmp7.kill();
tmp8 = -tmp8;
tmp6 = AddMod(A.XCoordinate, tmp8, prime);
tmp7 = MulMod(tmp5, tmp6, prime);
tmp6.kill();
tmp8.kill();
tmp6 = A.YCoordinate;
tmp6 = -tmp6;
tmp8 = AddMod(tmp7, tmp6, prime);
if (tmp8 < 0)
{
tmp8 = prime + tmp8;
}
DoubledPoint.YCoordinate = tmp8;
tmp6.kill();
tmp7.kill();
tmp8.kill();
tmp4.kill();
return DoubledPoint;
}
}
}
/*...............................................................................
. Adds two points on an elliptic curve [y2 = x^3 + ax + b (mod p)] over GF(p) .
. a is the coefficient of x in the equation. .
. prime is the prime field over which the Elliptic Curve has been formed. .
................................................................................*/
ECPoint EC_AddPoints(ECPoint A, ECPoint B, ZZ prime, ZZ a)
{
ECPoint Sum;
ZZ Zero = to_ZZ(0);
Sum.XCoordinate = to_ZZ(0);
Sum.YCoordinate = to_ZZ(0);
Sum.Infinity = false;
if (A.Infinity)
{
Sum = PointCopy(B);
return Sum;
}
else if (B.Infinity)
{
Sum = PointCopy(A);
return Sum;
}
int com1,com2;
com1 = com2 = 1;
com1 = compare(A.XCoordinate, B.XCoordinate);
com2 = compare(A.YCoordinate, B.YCoordinate);
if ((com1 == 0) && (com2 == 0))
{
Sum = EC_PointDouble(A, prime, a);
return Sum;
}
else if ((com1 == 0) || (com2 == 0))
{
Sum.Infinity = true;
Sum.XCoordinate = Sum.YCoordinate = Zero;
return Sum;
}
else
{
ZZ tmp1, tmp2, tmp3, tmp4, tmp5, tmp6, tmp7, tmp8, tmp9;
tmp1 = tmp2 = tmp3 = tmp4 = tmp5 = tmp6 = tmp7 = tmp8 = tmp9 = to_ZZ(0);
tmp1 = A.YCoordinate;
tmp1 = -tmp1;
tmp2 = AddMod(B.YCoordinate, tmp1, prime); // y2 - y1
tmp3 = A.XCoordinate;
tmp3 = -tmp3;
tmp4 = AddMod(B.XCoordinate, tmp3, prime); // x2 - x1
if (tmp4 < 0)
{
tmp4 = prime + tmp4;
}
tmp5 = InvMod(tmp4, prime); // tmp5 = 1/x2 - x1
tmp6 = MulMod(tmp5, tmp2, prime); // tmp6 = (Y2 - Y1)/(X2 - X1)
tmp7 = SquareMod(tmp6, prime); // [(Y2 - Y1)/(X2 - X1)]^2
tmp1.kill();
tmp2.kill();
tmp3.kill();
tmp4.kill();
tmp5.kill();
tmp1 = A.XCoordinate;
tmp1 = -tmp1;
tmp2 = B.XCoordinate;
tmp2 = -tmp2;
tmp3 = AddMod(tmp2, tmp1, prime);
tmp4 = AddMod(tmp3, tmp7, prime);
if (tmp4 < 0)
{
tmp4 = prime + tmp4;
}
Sum.XCoordinate = tmp4;
tmp1.kill();
tmp2.kill();
tmp3.kill();
tmp4.kill();
tmp7.kill();
tmp1 = Sum.XCoordinate;
tmp1 = -tmp1;
tmp2 = AddMod(A.XCoordinate, tmp1, prime);
tmp3 = MulMod(tmp2, tmp6, prime);
tmp1.kill();
tmp2.kill();
tmp1 = A.YCoordinate;
tmp1 = -tmp1;
tmp2 = AddMod(tmp3, tmp1, prime);
if (tmp2 < 0)
{
tmp2 = prime + tmp2;
}
Sum.YCoordinate = tmp2;
tmp1.kill();
tmp2.kill();
return Sum;
}
}
/* K*Point = New_Point --> Scalar Multiplication of an EC point. */
ECPoint EC_KMult(ZZ K, ECPoint P, ZZ prime, ZZ a)
{
string binK = "";
char ch = ' ';
binK = BinaryEncode(K);
int blen = 0;
blen = binK.length();
ECPoint multiple, tmp;
multiple.Infinity = true;
multiple.XCoordinate = to_ZZ(0);
multiple.YCoordinate = to_ZZ(0);
for(int i = 0; i < blen; i++)
{
ch = binK[i];
if (ch == '1')
{
tmp = EC_AddPoints(multiple, P, prime, a);
multiple.XCoordinate.kill();
multiple.YCoordinate.kill();
multiple = PointCopy(tmp);
tmp.XCoordinate.kill();
tmp.YCoordinate.kill();
}
if (i < blen-1)
{
tmp = EC_PointDouble(multiple, prime, a);
multiple.XCoordinate.kill();
multiple.YCoordinate.kill();
multiple = PointCopy(tmp);
tmp.XCoordinate.kill();
tmp.YCoordinate.kill();
}
}
if (multiple.XCoordinate < 0)
{
multiple.XCoordinate = prime + multiple.XCoordinate;
}
if (multiple.YCoordinate < 0)
{
multiple.YCoordinate = prime + multiple.YCoordinate;
}
return multiple;
}
//......................................................................................................................//
void ECDSA_Sign(char *Data, char *r, char *s)
{
int eq = 1;
ZZ zero = to_ZZ(0);
ZZ e = to_ZZ(Data);
ZZ n = to_ZZ("40");
ZZ p = to_ZZ("29");
ZZ a = to_ZZ("-3");
ZZ k = to_ZZ("4"); // private key
Sign:
SetSeed(to_ZZ(clock()));
ZZ K = RandomBnd(n);
ECPoint R, x;
x.Infinity = false;
ZZ tmp = to_ZZ(0);
ZZ tmp1, tmp2, tmp3, S;
tmp1 = tmp2 = tmp3 = to_ZZ(0);
R.Infinity = false;
R.XCoordinate = to_ZZ("2");
R.YCoordinate = to_ZZ("10");
x = EC_KMult(K, R, p, a); // K*R= x
tmp = x.XCoordinate % n; // tmp = xCoordinate mod n
eq = compare(tmp, zero);
if (eq == 0)
{
eq = 1;
goto Sign;
}
stringstream ss, sss;
string st, str;
ss << tmp;
st = ss.str();
strcpy(r, st.c_str());
S = InvMod(K, n);
tmp1 = MulMod(k, tmp, n);
tmp2 = AddMod(tmp1, e, n);
tmp3 = MulMod(tmp2, S, n);
eq = compare(tmp, zero);
if (eq == 0)
{
eq = 1;
goto Sign;
}
sss << tmp3;
str = sss.str();
strcpy(s, str.c_str());
tmp1.kill();
tmp2.kill();
tmp3.kill();
tmp.kill();
zero.kill();
}
int main()
{
char m[100], r[100], s[100];
memset(m, 0, 100);
memset(r, 0, 100);
memset(s, 0, 100);
string in;
cout<<"Enter the data to sign : \n";
cin>>in;
strcpy(m,in.c_str());
ECDSA_Sign(m, r, s);
cout<<r;
cout<<"\n";
cout<<s;
//.....................................................................................................//
//verified using : http://www.certicom.com/index.php/52-the-elliptic-curve-discrete-logarithm-problem //
/*ZZ prm = to_ZZ(23); //prime
ZZ a = to_ZZ(9); //curve param a
ZZ k = to_ZZ(9); //scalar value
ECPoint pt, rs;
pt.Infinity = false;
rs.Infinity = false;
pt.XCoordinate = 16;
pt.YCoordinate = 5;
rs = EC_KMult(k, pt, prm, a);
cout<<"XCoordinate = ";
cout<<rs.XCoordinate;
cout<<"\n";
cout<<"YCoordinate = ";
cout<<rs.YCoordinate;*/
getch();
}
Incase reading the code from here is problematic, I am attaching the .cpp file.
Source.cpp
Best Regards
KKR