//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
			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();
}