#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int mod = 0x7F;
// int mod = 23;
unsigned char PointSet[0x80];

// model 'y^2 = x^3 + a*x + b' ;
// using 'y^2 = x^3 + x + 1' ;
int A = 1;
int B = 1;

typedef struct point{
	int x;
	int y;
}Point;

typedef struct ciphercouple{
	Point C1;
	Point C2;
	struct ciphercouple* Next;
}CipherCouple;

typedef struct decodeStrings{
	char* strings;
	unsigned int length;
}DecodeStrings;

Point ZeroPoint = {0, 0};

int mmod(int num, int p)
{
	int result = num % p;

	if(result >= 0)
		return result;
	else
		return result + p;
}


// x/y mod p = result
// enumberate m to solve
// x + y*m mod p == 0
int fraction_mod(int x, int y, int p)
{
	if(y == 0)
		goto _Traced;

	for(int m=0; m<p; m++)
	{
		if(mmod((x + y*m), p) == 0)
			return p-m;
	}
	
_Traced:
	//printf("faction_mod traced[%d/%d]\n", x, y);
	return -1;
}

// P(x1, y1) + Q(x2, y2) = R(x3, y3)
// P == Q && k = (3 * x^2 + a)/(2 * y)
// P != Q && k = (y2-y1)/(x2-x1)
// x3 = (k^2 - x1- x2) mod p;
// y3 = (k*(x1 - x3) - y1) mod p;
Point PointAdd(Point P, Point Q, int p)
{
	Point result;
	int k;

	if(!memcmp(&P, &ZeroPoint, sizeof(Point)))
		return Q;
	else if(!memcmp(&Q, &ZeroPoint, sizeof(Point)))
		return P;
	else if(!memcmp(&P, &Q, sizeof(Point)))
		k = fraction_mod(3 * P.x * P.x + A, 2 * P.y, p);
	else
		k = fraction_mod(Q.y - P.y, Q.x - P.x, p);

	if(k == -1)
	{
		result.x = 0;
		result.y = 0;
	}
	else
	{
		result.x = mmod((k*k - P.x - Q.x), p);
		result.y = mmod((k*(P.x - result.x) - P.y), p);
	}
	
	return result;
}

Point PointSub(Point P, Point Q, int p)
{
	Q.y = (-Q.y);
	return PointAdd(P, Q, p);
}

// 3G = 2G + G
// 2G = G + G  
// 3G = (G + G) + G  (3, 2)
Point PointMulti(unsigned int r, Point G, int p)
{
	Point result;
	result.x = G.x;
	result.y = G.y;

	if(r > 1)
		return PointAdd(result, PointMulti(r-1, G, p), p);
	else
		return result;
}

void InitECCKeys(unsigned int k, Point G,  Point* K, int p)
{
	Point* pK = K;
	*pK = PointMulti(k, G, p);
}

CipherCouple* ECCEncode(Point K, Point G, unsigned int r, char* strings, int p)
{
	char* ptr = strings;
	int i = 0;
	Point Cipher;
	CipherCouple* retCipher = (CipherCouple*)malloc(sizeof(CipherCouple));

	if(!retCipher)	return NULL;
	CipherCouple* ptrCipher = retCipher;

	while(*ptr)
	{
		Cipher.x = *ptr;
		Cipher.y = PointSet[*ptr];
		ptrCipher->C1 = PointMulti(r, G, p);
		ptrCipher->C2 = PointAdd(Cipher, PointMulti(r, K, p), p);
		ptrCipher->Next = (CipherCouple*)malloc(sizeof(CipherCouple));
		ptrCipher = ptrCipher->Next;

		//i++;
		ptr++;
	}

	return retCipher;
}

DecodeStrings* ECCDecode(unsigned int k, CipherCouple* C, int p)
{
	char* retStrings = (char*)malloc(1024);
	char* ptrStrings = retStrings;
	int i = 0;
	Point M;
	CipherCouple* ptrCipher = C;
	DecodeStrings* retDecodeString = (DecodeStrings*)malloc(sizeof(DecodeStrings));

	if(!retStrings || !retDecodeString)	return NULL;

	while(ptrCipher->Next)
	{
		M = PointSub(ptrCipher->C2, PointMulti(k, ptrCipher->C1, p), p);
		*ptrStrings = M.x;

		i++;
		ptrStrings++;
		ptrCipher = ptrCipher->Next;
	}

	retDecodeString->strings = retStrings;
	retDecodeString->length = i;

	return retDecodeString;
}

// y^2 = x^3 + a*x + b
// y^2 = x^3 + x + 1
void InitPointSet(int p)
{
	int n = 0;
	memset(PointSet, 0xFF, sizeof(PointSet));
	for(int i = 0; i <= p; i++)
	{
		for(int y = 0; y <= p; y++)
		{
			if(mmod(pow(i, 3) + i*A + B, p) == mmod(pow(y, 2), p))
			{
				PointSet[i] = (unsigned char)y;
				break;
			}
		}
	}
}

int ECCOrder(Point G, int max, int p)
{
	int n;
	Point tmpPoint;

	for(n = 0; n < max; n++)
	{
		tmpPoint = PointMulti(n, G, p);
		if(!memcmp(&tmpPoint, &ZeroPoint, sizeof(Point)))
			return n;
	}

	return -1;
}

int main()
{
	Point K, G;
	unsigned int k, r, n;
	unsigned int less;
	CipherCouple* Ciphers;

	// set generator to {30, 19} on GFp
	G.x = 30;
	G.y = 19;

	printf("use EC: y^2 = x^3 + %d*x + %d\n", A, B);
	printf("use G{%d, %d}\n", G.x, G.y);
	InitPointSet(mod);
	n = ECCOrder(G, mod, mod);
	if(n != -1)
	{
		printf("The order of G is: %d\n", n);
		k = n-1;
		r = n-2;
	}
	else
	{
		printf("Order of G not found!\n");
		return 1;
	}

	InitECCKeys(k, G, &K, mod);
	printf("private key: %d\trandom num: %d\n", k, r);
	printf("public key K{%d, %d}\n", K.x, K.y);

	// encoding the input
	//Ciphers = ECCEncode(K, G, r, "hello,world", mod);
	Ciphers = ECCEncode(K, G, r, "AAAAAAAAAA", mod);

	// output the decode
	DecodeStrings* ptrStrings = ECCDecode(k, Ciphers, mod);
	printf("decode: %s\n", ptrStrings->strings);

	free(ptrStrings->strings);
	free(ptrStrings);
	free(Ciphers);

	return 0;
}