$ 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; }