Simplified ECC variant, written in C

[fugu]

 

So this is a little demo I've been working on that plays around with ECC Point Mathematics & encryption. Many of the demos I've found have been not functional from beginning to end, and although this is not going to be a secure version of ECC, it does demo some of the basic properties of it. I'm using pieces of existing code, along with my own to get it working.

Individual ECC curve properties as well as the public key/private key pair can be created with openssl:

CRYPTNAME=secp192k1 && openssl ecparam -name $CRYPTNAME -out $CRYPTNAME.pem && openssl ecparam -in $CRYPTNAME.pem -noout -text -C && openssl ecparam -in $CRYPTNAME.pem -genkey -noout -out $CRYPTNAME-key.pem && openssl ec -in $CRYPTNAME-key.pem -noout -text && rm -f $CRYPTNAME.pem $CRYPTNAME-key.pem

In real ECIES, a common point is derived on both the senders end, as well as the receivers end, which is used to agree upon symmetric key. Normally something like AES is used to encrypt the message with this key, but I'm just xor'ing the message to keep the example small.

Here it is:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<gmp.h>
#include<time.h>

struct Point{
	mpz_t x;
	mpz_t y;
};

struct Elliptic_Curve{
	mpz_t a;	//y^2 = x^3 + a*x + b
	mpz_t b;
	mpz_t p;
	mpz_t n;	//Order
	struct Point G;	//Base Point
	mpz_t h;	//Cofactor
};

void Point_Addition(struct Elliptic_Curve EC, struct Point P,struct Point Q, struct Point *R);
void Point_Doubling(struct Elliptic_Curve EC, struct Point P,struct Point *R);
void Scalar_Multiplication(struct Elliptic_Curve EC, mpz_t m, struct Point P, struct Point *R);

int main(int argc, char * argv[]){
	srand(time(NULL)); //not crypto secure
	struct Elliptic_Curve secp192k1;

	mpz_init(secp192k1.a);
	mpz_init(secp192k1.b);
	mpz_init(secp192k1.p);
	mpz_init(secp192k1.n);
	mpz_init(secp192k1.G.x);
	mpz_init(secp192k1.G.y);
	mpz_init(secp192k1.h);

	mpz_set_str(secp192k1.a,"0", 16); //Elliptic Curve P-192
	mpz_set_str(secp192k1.b,"3", 16);
	mpz_set_str(secp192k1.p,"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFEE37", 16);
	mpz_set_str(secp192k1.n,"FFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D", 16);
	mpz_set_str(secp192k1.G.x,"DB4FF10EC057E9AE26B07D0280B7F4341DA5D1B1EAE06C7D", 16);
	mpz_set_str(secp192k1.G.y,"9B2F2F6D9C5628A7844163D015BE86344082AA88D95E2F9D", 16);
	mpz_set_str(secp192k1.h,"1", 16);

	mpz_t da;		//priv
	struct Point Qa;	//pub

	mpz_init(da);
	mpz_init(Qa.x);
	mpz_init(Qa.y);

	mpz_set_str(da,  "e03a7a761dc3f4b5ff363906af1a1bfb97e1cbfc837834ed", 16); //private key, a random integer from "0" to "n"
	mpz_set_str(Qa.x,"8d4af03e8368921895af8c777fac221439604811d2359249", 16); //public key x
	mpz_set_str(Qa.y,"6f35647c10df80325be5cc48c5a2a218525db549d3d5839c", 16); //public key y

	mpz_t encoded_message;
	mpz_init(encoded_message);

	mpz_set_ui(encoded_message,0);

	unsigned char ary[] = "Hello World! 1234567890";
	mpz_import(encoded_message, sizeof(ary), 1, sizeof(ary[0]), 1, 0, (const void *)ary);
	printf("#############################################################################\nary = %s\n", ary);

	struct Point R;
	mpz_init(R.x);
	mpz_init(R.y);

	struct Point S;
	mpz_init(S.x);
	mpz_init(S.y);

	mpz_t r;
	mpz_init(r);

	gmp_randstate_t state;
	gmp_randinit_mt(state);
	gmp_randseed_ui(state,rand());
	mpz_urandomm(r,state,secp192k1.n);

	Scalar_Multiplication(secp192k1, r, secp192k1.G, &R);
	//R = r*G
	Scalar_Multiplication(secp192k1, r, Qa, &S);
	//S = r*Qa

	mpz_t e;
	mpz_init(e);
	mpz_xor(e,S.x,S.y);		//My simplifed variant of the symmetric encryption part, not standard for real ECIES, probably insecure
	mpz_xor(e,e,encoded_message);	//ciphertext = S.x ^ S.y ^ cleartext 

	gmp_printf("Qa.x = %Zx //Point Qa is the PUBLIC_KEY\nQa.y = %Zx\n", Qa.x, Qa.y);
	gmp_printf("Ciphertext Message => Rx = %Zx //Point R is the CHOOSEN_POINT\nCiphertext Message => Ry = %Zx\n", R.x, R.y);
	gmp_printf("Ciphertext Message =>  e = %Zx\n", e);

	//Only Rx, Ry, and e get sent over the wire
	printf("Decrypt 'e' From da && R... //da is the PRIVATE_KEY\n");

	struct Point newS;
	mpz_init(newS.x);
	mpz_init(newS.y);

	Scalar_Multiplication(secp192k1, da, R, &newS);

	mpz_t decoded_message;
	mpz_init(decoded_message);
	mpz_xor(decoded_message,newS.x,newS.y);	
	mpz_xor(decoded_message,decoded_message,e);	
	
	unsigned char *result = (unsigned char *)malloc(sizeof(unsigned char)*mpz_sizeinbase(decoded_message,8));	

	mpz_export(result, NULL, 1, sizeof(result[0]), 1, 0, decoded_message);
	printf("dec = %s\n\n", result);

	mpz_clear(secp192k1.a);
	mpz_clear(secp192k1.b);
	mpz_clear(secp192k1.p);
	mpz_clear(secp192k1.n);
	mpz_clear(secp192k1.G.x);
	mpz_clear(secp192k1.G.y);
	mpz_clear(secp192k1.h);
	mpz_clear(R.x);
	mpz_clear(R.y);
	mpz_clear(S.x);
	mpz_clear(S.y);
	mpz_clear(newS.x);
	mpz_clear(newS.y);
	mpz_clear(da);
	mpz_clear(e);
	mpz_clear(r);
	mpz_clear(encoded_message);
	mpz_clear(decoded_message);
	mpz_clear(Qa.x);
	mpz_clear(Qa.y);
	return 0;
}

void Point_Addition(struct Elliptic_Curve EC, struct Point P,struct Point Q,struct Point *R){
	mpz_mod(P.x,P.x,EC.p);
	mpz_mod(P.y,P.y,EC.p);
	mpz_mod(Q.x,Q.x,EC.p);
	mpz_mod(Q.y,Q.y,EC.p);
	mpz_t temp,slope;
	mpz_init(temp);
	mpz_init_set_ui(slope,0);
	if(mpz_cmp_ui(P.x,0)==0 && mpz_cmp_ui(P.y,0)==0){
		mpz_set(R->x,Q.x); mpz_set(R->y,Q.y);
		return;
	}
	if(mpz_cmp_ui(Q.x,0)==0 && mpz_cmp_ui(Q.y,0)==0){
		mpz_set(R->x,P.x);
		mpz_set(R->y,P.y);
		return;
	}
	if(mpz_cmp_ui(Q.y,0)!=0){
		mpz_sub(temp,EC.p,Q.y);
		mpz_mod(temp,temp,EC.p);
	}else
		mpz_set_ui(temp,0);
	if(mpz_cmp(P.y,temp)==0 && mpz_cmp(P.x,Q.x)==0){
		mpz_set_ui(R->x,0);
		mpz_set_ui(R->y,0);
		return;
	}
	if(mpz_cmp(P.x,Q.x)==0 && mpz_cmp(P.y,Q.y)==0){
		Point_Doubling(EC,P,R);
		return;
	}else{
		mpz_sub(temp,P.x,Q.x);
		mpz_mod(temp,temp,EC.p);
		mpz_invert(temp,temp,EC.p);
		mpz_sub(slope,P.y,Q.y);
		mpz_mul(slope,slope,temp);
		mpz_mod(slope,slope,EC.p);
		mpz_mul(R->x,slope,slope);
		mpz_sub(R->x,R->x,P.x);
		mpz_sub(R->x,R->x,Q.x);
		mpz_mod(R->x,R->x,EC.p);
		mpz_sub(temp,P.x,R->x);
		mpz_mul(R->y,slope,temp);
		mpz_sub(R->y,R->y,P.y);
		mpz_mod(R->y,R->y,EC.p);
		return;
	}
}

void Point_Doubling(struct Elliptic_Curve EC, struct Point P,struct Point *R){
	mpz_t slope,temp;
	mpz_init(temp);
	mpz_init(slope);
	if(mpz_cmp_ui(P.y,0)!=0){
		mpz_mul_ui(temp,P.y,2);
		mpz_invert(temp,temp,EC.p);
		mpz_mul(slope,P.x,P.x);
		mpz_mul_ui(slope,slope,3);
		mpz_add(slope,slope,EC.a);
		mpz_mul(slope,slope,temp);
		mpz_mod(slope,slope,EC.p);
		mpz_mul(R->x,slope,slope);
		mpz_sub(R->x,R->x,P.x);
		mpz_sub(R->x,R->x,P.x);
		mpz_mod(R->x,R->x,EC.p);
		mpz_sub(temp,P.x,R->x);
		mpz_mul(R->y,slope,temp);
		mpz_sub(R->y,R->y,P.y);
		mpz_mod(R->y,R->y,EC.p);
	}else{
		mpz_set_ui(R->x,0);
		mpz_set_ui(R->y,0);
	}
	
}

void Scalar_Multiplication(struct Elliptic_Curve EC, mpz_t m, struct Point P, struct Point *R){
	struct Point Q,T;
	mpz_init(Q.x);
	mpz_init(Q.y);
	mpz_init(T.x);
	mpz_init(T.y);
	long no_of_bits,loop;
	no_of_bits=mpz_sizeinbase(m,2);
	mpz_set_ui(R->x,0);
	mpz_set_ui(R->y,0);
	if(mpz_cmp_ui(m,0)==0)
		return;
	mpz_set(Q.x,P.x);
	mpz_set(Q.y,P.y);
	if(mpz_tstbit(m,0)==1){
		mpz_set(R->x,P.x);
		mpz_set(R->y,P.y);
	}
	for(loop=1;loop<no_of_bits;loop++){
		mpz_set_ui(T.x,0);
		mpz_set_ui(T.y,0);
		Point_Doubling(EC,Q,&T);
		mpz_set(Q.x,T.x);
		mpz_set(Q.y,T.y);
		mpz_set(T.x,R->x);
		mpz_set(T.y,R->y);
		if(mpz_tstbit(m,loop))
			Point_Addition(EC,T,Q,R);
	}
}

 

[cooper]

While I certainly appreciate the effort you've put into this, is there some document to reference that uses the same single-letter attributes to describe the same algorithmic elements? I mean, you already state in the struct that Eliptic_Curve.n is the order, so why not refer to that attribute as... well... order? Same for the others.

[fugu]

In many of the documents that I've been looking over, they talk about many of these things in terms of the mathematics, and I tend to see the same single letter variables being used over and over again. Some references will use different letters so its not always constant, but I was primarily going off of the site http://www.johannes-bauer.com/compsci/ecc/ for a majority of the concepts. The functions for point addition, point doubling, and scalar multiplication were pulled directly from "Implementation of Elliptic Curve Cryptography in C" by Kuldeep Bhardwaj and Sanjay Chaudhary, appendix A.

[cooper]

Nice. Thanks for that.