A Basic ECC Crypto C Library

$ gcc -Wall -O2 -o crypto.out crypto.c 
$ ./crypto.out pgen 

x: [0][7][8]=[4880449572248532107701327692677150037572104965674444437385142643512]
y^2: [0][8][8]=[55380869580354224246510320945966028555317502525493429017926966133843051295792]
y: [0][8][8]=[29139577269574826820926935201858599433659429201914524387051377879407947248399]

$ ./crypto.out ecdh 

  1*(y^2) = x^3 + 486662*(x^2) + x (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949)
    17101372528228046186917539708449150102286202153232625914396359604563
      * P(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)

      = Q(x, y) = (38616894501258673852970036866543659072635089662921568068340331697101576554270, 11643169480892671629858370512120070259223559167488419079368716073871895962191)


  1*(y^2) = x^3 + 486662*(x^2) + x (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949)
    12761708460950637051849206961623904377595162559992784492118523127724
      * P(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)

      = Q(x, y) = (32477568348650104756356831653582245276448206004887493791495532411741897328458, 28063399834915231969701720976238207473037393607389857712493721633327966471074)


  1*(y^2) = x^3 + 486662*(x^2) + x (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949)
    17101372528228046186917539708449150102286202153232625914396359604563
      * P(x, y) = (32477568348650104756356831653582245276448206004887493791495532411741897328458, 28063399834915231969701720976238207473037393607389857712493721633327966471074)

      = Q(x, y) = (50351522368134241142819091458530332577142187603512687882689541070260459723459, 50221873001104206223375144395698504985316658966829066883833880358017679689691)


  1*(y^2) = x^3 + 486662*(x^2) + x (mod 57896044618658097711785492504343953926634992332820282019728792003956564819949)
    12761708460950637051849206961623904377595162559992784492118523127724
      * P(x, y) = (38616894501258673852970036866543659072635089662921568068340331697101576554270, 11643169480892671629858370512120070259223559167488419079368716073871895962191)

      = Q(x, y) = (50351522368134241142819091458530332577142187603512687882689541070260459723459, 50221873001104206223375144395698504985316658966829066883833880358017679689691)

$ ./crypto.out psig 1234
Sign:

d=[0][7][8]=[6538729008379423383518670268808646995288081785172776771199052697947]
P=(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)
dP=(x, y) = (14803911054618354585053684993263408691271520722671720792800356230205975217771, 11341018286853926408444620055947798723342444873304700039478772171855673884697)

h=[0][1][1]=[1234]

k=[0][7][8]=[8232207578348459001023088138872857936131335029042440438075457201646]
kP=(x, y) = (31369530948108575720266905846722071920323191212477028674668598541699791483098, 9139751042718096616566254849289158387164951389944576741553517798024823610265)
r=[0][15][40]=[149879290832663482850783820956010355668942537394521944880131051841396204961042266046319521062426903751537961621638691535228251607511236059222514]

Verify:

P=(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)
dP=(x, y) = (14803911054618354585053684993263408691271520722671720792800356230205975217771, 11341018286853926408444620055947798723342444873304700039478772171855673884697)

h=[0][1][1]=[1234]

kP=(x, y) = (31369530948108575720266905846722071920323191212477028674668598541699791483098, 9139751042718096616566254849289158387164951389944576741553517798024823610265)
r=[0][15][40]=[149879290832663482850783820956010355668942537394521944880131051841396204961042266046319521062426903751537961621638691535228251607511236059222514]

(ek+hd)P=(x, y) = (51608966471038425598161188547671772160458281462630354621077601757763167308540, 17341325372123419326180270058693292718501038313000707228169935748980907943680)
==
rP=(x, y) = (51608966471038425598161188547671772160458281462630354621077601757763167308540, 17341325372123419326180270058693292718501038313000707228169935748980907943680)

[GOOD]
$ ./crypto.out penc 1234
Encrypt:

P=(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)
dP=(x, y) = (19547865285467707344496388019666506767309887017163137556078134582670804301851, 36180672281078333342162157694938953906019362565570590334768364807054263309922)

h=[0][1][1]=[1234]

k=[0][7][8]=[3873062938517225834483697070677896532844396051944377142545351178872]
kP=(x, y) = (31307487414183777373465427652384958249613501222520858769326720798351611112341, 42327343332069595141617190350930625663948508466032477124028143798481079201841)
kdP=(x, y) = (17546014782981223520910010062776248455503090940217295620750099274078977893385, 40213720617506594547897783150731613585768378209283692064354760696398013829358)

Decrypt:

P=(x, y) = (9, 43114425171068552920764898935933967039370386198203806730763910166200978582548)
dP=(x, y) = (19547865285467707344496388019666506767309887017163137556078134582670804301851, 36180672281078333342162157694938953906019362565570590334768364807054263309922)

d=[0][7][8]=[22873181922607864299317581582398892665871088710637471622228302193764]
dkP=(x, y) = (17546014782981223520910010062776248455503090940217295620750099274078977892151, 40213720617506594547897783150731613585768378209283692064354760696398013829358)

t=[0][1][8]=[1234]

$ 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>

#include "../lib/sha256.c"
#include "../lib/aes256.c"
#include "../lib/ec.c"

bnum *bnrnd(int size)
{
	FILE *f;
	bnum *r;
	
	r = bninit(size);
	f = fopen("/dev/urandom", "r");
	fread(r->nums, sizeof(unsigned int), size - 1, f);
	fclose(f);
	r->leng = size;
	while ((r->leng > 1) && (r->nums[r->leng - 1] == 0)) { r->leng -= 1; }
	
	return r;
}

void eccp(ecc *e, char *xs)
{
	int psiz = (e->p)->size;
	bnum *x = bninit(psiz), *y = bninit(psiz), *t;
	
	bnum *xa = bninit(psiz * 4), *xx = bninit(psiz * 4);
	bnum *yy = bninit(psiz * 4), *vv = bninit(psiz * 4);
	
	if (xs != NULL) { t = bndec(xs); }
	else { t = bnrnd(psiz); }
	bncopy(t, x);
	
	while (1)
	{
		// yy = ((x * (x * x)) + (a * (x * x)) + x) % m
		bnzero(xx); bnmul(x, x, xx);
		bnzero(xa); bnmul(xx, e->a, xa);
		bnzero(vv); bnmul(x, xx, vv);
		
		bnzero(yy); bnadd(vv, xa, yy, 1); bnadd(yy, x, vv, 1);
		bndiv(vv, e->p, xx, t);
		// todo: divide t by b?
		
		printf("\n");
		bnout("x: ", x, "\n");
		bnout("y^2: ", t, "\n");
		
		if (sqrtmod(t, e->p, y) == 0) { break; }
		
		if (x != NULL) { bnfree(x); }
		x = bnrnd(psiz);
	}
	
	bnout("y: ", y, "\n\n");
	// note: another y point == p - y
	
	bnzero(yy); bncopy(t, yy);
	bnzero(vv); bnmul(y, y, vv);
	bnzero(xx); bndiv(vv, e->p, xa, xx);
	
	bnfree(xa); bnfree(vv); bnfree(t);
	
	if (bncmp(xx, yy) != 0)
	{
		bnout("y^2: ",xx," != "); bnout("y^2: ",yy,"\n");
	}
	
	bnfree(xx); bnfree(yy);
	bnfree(x); bnfree(y);
}

/*
Curve25519: a=486662, b=1, p=2^255 - 19
ECC DH: o * (n * P) == onP == noP == n * (o * P)
*/

char *ecdh(ecc *e, char *n, int o)
{
	char *r = n;
	bnum *m;
	ecc *f;
	
	if (r == NULL)
	{
		m = bnrnd((e->p)->size);
		r = bnstr(m);
	}
	
	else
	{
		m = bndec(n);
	}
	
	f = ecdup(e);
	pmul(m, e, f);
	
	if (o == 1)
	{
		char v[2050];
		bzero(v, 2050 * sizeof(char));
		strncat(v, "    "       , max(0, 2048 - strlen(v)));
		strncat(v, r            , max(0, 2048 - strlen(v)));
		strncat(v, "\n      * P", max(0, 2048 - strlen(v)));
		printf("\n");
		ecout(1,v,e,"\n\n");
		ecout(0,"      = Q",f,"\n");
		printf("\n");
	}
	
	bnfree(e->x); e->x = bndup(f->x);
	bnfree(e->y); e->y = bndup(f->y);
	bnfree(m);
	ecfree(f);
	
	return r;
}

/*
ECC - Private Sign / Public Verify

* initialize
- generate secret key          : d
- publish                      : P, dP

* private sign
- hash message                 : h = SHA256(m)
- secret unique multiplier     : k
- calculate public multipliers : kP
                               : e = hP(x)
                               : r = ((e * k) + (h * d))
- publish                      : kP, r

* public verify
                               : e = hP(x)
-                              : (e * kP) + (h * dP) == rP
*/

int ecsig(ecc *e, bnum *d, ecc *dp, char *hh, ecc *kp, bnum *r, int o)
{
	int a = 0, psiz = (e->p)->size;
	bnum *k, *h;
	bnum *t = bninit(psiz * 5), *u = bninit(psiz * 5);
	ecc *hp = ecdup(e), *ekp = ecdup(e), *hdp = ecdup(e), *ekhdp = ecdup(e), *rp = ecdup(e);
	ect *tadd = etinit(e);
	
	if (hh != NULL)
	{
		if (((kp->x)->leng == 1) && ((kp->x)->nums[0] == 0))
		{
			if ((d->leng == 1) && (d->nums[0] == 0))
			{
				k = bnrnd(psiz); bncopy(k, d); bnfree(k);
				pmul(d, e, dp);
				
				if (o == 1) { bnout("d=", d, "\n"); }
			}
		}
		
		if (o == 1)
		{
			ecout(0, "P=", e, "\n");
			ecout(0, "dP=", dp, "\n\n");
		}
		
		h = bndec(hh);
		pmul(h, e, hp);
		
		if (o == 1) { bnout("h=", h, "\n\n"); }
		
		if (((kp->x)->leng == 1) && ((kp->x)->nums[0] == 0))
		{
			k = bnrnd(psiz);
			pmul(k, e, kp);
			
			if (o == 1) { bnout("k=", k, "\n"); }
			
			bnzero(t); bnmul(hp->x, k, t);
			bnzero(u); bnmul(h, d, u);
			bnadd(t, u, r, 1);
			
			bnfree(k);
		}
		
		if (o == 1)
		{
			ecout(0, "kP=", kp, "\n");
			bnout("r=", r, "\n\n");
		}
		
		pmul(hp->x, kp, ekp);
		pmul(h, dp, hdp);
		padd(ekp, hdp, ekhdp, tadd);
		pmul(r, e, rp);
		
		if ((d->leng == 1) && (d->nums[0] == 0))
		{
			if (o == 1)
			{
				ecout(0, "(ek+hd)P=", ekhdp, "\n==\n");
				ecout(0, "rP=", rp, "\n\n");
			}
		}
		
		if (bncmp(ekhdp->x, rp->x) == 0)
		{
			if (bncmp(ekhdp->y, rp->y) == 0)
			{
				a = 1;
			}
		}
		
		bnfree(h);
	}
	
	bnfree(t); bnfree(u);
	ecfree(hp); ecfree(ekp); ecfree(hdp); ecfree(ekhdp); ecfree(rp);
	etfree(tadd);
	
	return a;
}

/*
ECC ElGamal - Public Encrypt / Private Decrypt

* initialize
- generate secret integer  : d
- publish                  : P, dP

* public encrypt
- generate secret key      : t = (SHA256(pwd) || tmpkey)
- secret unique multiplier : k = rand()
- public key encrypt       : r = k * P        = kP
                           : s = t + (k * dP) = t + kdP = kdP(x + t, y + t)
- encrypt optional message : i = rand()
                           : e = AES256CBC(m, i, t)
- publish                  : [ (r, s) , (i, e) ]

* private decrypt
- private key decrypt      : u = s - (d * r)
                               = (t + kdP) - (d * kP)
                               = kdP(x + t, y + t) - dkP(x, y)
                               = kdP(x - x + t)
                               = t
*/

void ecenc(ecc *e, bnum *d, ecc *dp, char *hh, ecc *kp, ecc *kdp, int o)
{
	int psiz = (e->p)->size;
	bnum *k, *h, *t;
	ecc *dkp;
	
	if (hh != NULL)
	{
		if ((d->leng == 1) && (d->nums[0] == 0))
		{
			k = bnrnd(psiz); bncopy(k, d); bnfree(k); k = NULL;
			pmul(d, e, dp);
		}
		
		if (o == 1)
		{
			ecout(0, "P=", e, "\n");
			ecout(0, "dP=", dp, "\n\n");
		}
		
		h = bndec(hh);
		
		if (((kp->x)->leng == 1) && ((kp->x)->nums[0] == 0))
		{
			if (o == 1) { bnout("h=", h, "\n\n"); }
			
			k = bnrnd(psiz);
			pmul(k, e, kp);
			
			pmul(k, dp, kdp);
			t = kdp->x; kdp->x = bninit(psiz + 1); bncopy(t, kdp->x); bnfree(t);
			bnadd(kdp->x, h, kdp->x, 1);
			
			if (o == 1)
			{
				bnout("k=", k, "\n");
				ecout(0, "kP=", kp, "\n");
				ecout(0, "kdP=", kdp, "\n\n");
			}
			
			bnfree(k);
		}
		
		else
		{
			dkp = ecdup(e);
			pmul(d, kp, dkp);
			t = bninit(psiz); bnsub(kdp->x, dkp->x, t, 1);
			
			if (o == 1)
			{
				bnout("d=", d, "\n");
				ecout(0, "dkP=", dkp, "\n\n");
				bnout("t=", t, "\n\n");
			}
			
			bnfree(t);
			ecfree(dkp);
		}
		
		bnfree(h);
	}
}

int main(int argc, char **argv)
{
	char *a = "486662", *b = "1", *p = "57896044618658097711785492504343953926634992332820282019728792003956564819949";
	char *x = "9", *y = "43114425171068552920764898935933967039370386198203806730763910166200978582548";
	char *n, *m, *z = NULL;
	char hash[256];
	unsigned char msg[16], key[256];
	bnum *d, *r, *s;
	bnum *t, *u, *v, *w;
	ecc *e, *f, *dp, *kp, *kdp;
	
	if (argc > 2) { z = argv[2]; }
	
	t = bndec(p);
	u = bninit(t->size); w = bndec(x); bncopy(w, u); bnfree(w);
	v = bninit(t->size); w = bndec(y); bncopy(w, v); bnfree(w);
	e = ecinit(bndec(a), bndec(b), t, u, v);
	
	if (strcmp(argv[1], "pgen") == 0)
	{
		eccp(e, z);
	}
	
	if (strcmp(argv[1], "pmul") == 0)
	{
		ecdh(e, argv[2], 1);
	}
	
	if (strcmp(argv[1], "ecdh") == 0)
	{
		f = ecdup(e);
		
		n = ecdh(e, NULL, 1);
		m = ecdh(f, NULL, 1);
		
		t = e->x; u = e->y;
		e->x = f->x; e->y = f->y;
		f->x = t; f->y = u;
		
		ecdh(e, n, 1);
		ecdh(f, m, 1);
		
		free(n); free(m);
		ecfree(f);
	}
	
	if (strcmp(argv[1], "psig") == 0)
	{
		d = bninit((e->p)->size);
		dp = ecdup(e); kp = ecdup(e);
		r = bninit((e->p)->size * 5);
		s = bninit((e->p)->size * 5);
		
		printf("Sign:\n\n");
		(kp->x)->leng = 1; (kp->x)->nums[0] = 0;
		(kp->y)->leng = 1; (kp->y)->nums[0] = 0;
		ecsig(e, d, dp, z, kp, r, 1);
		
		printf("Verify:\n\n");
		bnzero(d);
		if (ecsig(e, d, dp, z, kp, r, 1) != 0) { printf("[GOOD]\n"); }
		else { printf("\n[FAILED]\n"); }
		
		bnfree(d); bnfree(r); bnfree(s);
		ecfree(dp); ecfree(kp);
	}
	
	if (strcmp(argv[1], "penc") == 0)
	{
		d = bninit((e->p)->size);
		dp = ecdup(e); kp = ecdup(e); kdp = ecdup(e);
		
		printf("Encrypt:\n\n");
		(kp->x)->leng = 1; (kp->x)->nums[0] = 0;
		(kp->y)->leng = 1; (kp->y)->nums[0] = 0;
		ecenc(e, d, dp, z, kp, kdp, 1);
		
		printf("Decrypt:\n\n");
		ecenc(e, d, dp, z, kp, kdp, 1);
		
		bnfree(d);
		ecfree(dp); ecfree(kp); ecfree(kdp);
	}
	
	if (strcmp(argv[1], "hash") == 0)
	{
		sha256 hobj;
		sha256init(&hobj);
		sha256update(&hobj, (unsigned char *)argv[2], strlen(argv[2]));
		sha256final(&hobj, hash);
		printf("%s\n", hash);
	}
	
	if (strcmp(argv[1], "menc") == 0)
	{
		bzero(key, 256);
		strcpy((char *)key, argv[3]);
		aes256keys(key);
		
		bzero(msg, 16);
		strcpy((char *)msg, argv[2]);
		aes256core(msg, key, 0);
		
		int i;
		for (i = 0; i < 16; ++i) { printf("%02x", msg[i]); }
		printf("\n");
	}
	
	ecfree(e);
	
	return 0;
}

Advertisements
A Basic ECC Crypto C Library

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s