$ 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;
}
Jon's FOSS Blog 