CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!
Path: blob/master/ext/libkirk/ec.c
Views: 1401
// Copyright 2007-2022 Segher Boessenkool <[email protected]>1// Licensed under the terms of the GNU GPL, either version 2 or version 32// https://www.gnu.org/licenses/old-licenses/gpl-2.0.txt3// https://www.gnu.org/licenses/gpl-3.0.html456// Modified for Kirk engine by setting single curve and internal function7// to support Kirk elliptic curve options.- July 201189#include <string.h>10#include <stdio.h>1112// Include definitions from kirk header13#include "kirk_engine.h"1415struct point {16u8 x[20];17u8 y[20];18};19// Simplified for use by Kirk Engine since it has only 1 curve2021u8 ec_p[20];22u8 ec_a[20];23u8 ec_b[20];24u8 ec_N[21];25struct point ec_G; // mon26struct point ec_Q; // mon27u8 ec_k[21];28293031void hex_dump(char *str, u8 *buf, int size)32{33int i;3435if(str)36printf("%s:", str);3738for(i=0; i<size; i++){39if((i%32)==0){40printf("\n%4X:", i);41}42printf(" %02X", buf[i]);43}44printf("\n\n");45}4647static void elt_copy(u8 *d, u8 *a)48{49memcpy(d, a, 20);50}5152static void elt_zero(u8 *d)53{54memset(d, 0, 20);55}5657static int elt_is_zero(u8 *d)58{59u32 i;6061for (i = 0; i < 20; i++)62if (d[i] != 0)63return 0;6465return 1;66}6768static void elt_add(u8 *d, u8 *a, u8 *b)69{70bn_add(d, a, b, ec_p, 20);71}7273static void elt_sub(u8 *d, u8 *a, u8 *b)74{75bn_sub(d, a, b, ec_p, 20);76}7778static void elt_mul(u8 *d, u8 *a, u8 *b)79{80bn_mon_mul(d, a, b, ec_p, 20);81}8283static void elt_square(u8 *d, u8 *a)84{85elt_mul(d, a, a);86}8788static void elt_inv(u8 *d, u8 *a)89{90u8 s[20];91elt_copy(s, a);92bn_mon_inv(d, s, ec_p, 20);93}9495static void point_to_mon(struct point *p)96{97bn_to_mon(p->x, ec_p, 20);98bn_to_mon(p->y, ec_p, 20);99}100101static void point_from_mon(struct point *p)102{103bn_from_mon(p->x, ec_p, 20);104bn_from_mon(p->y, ec_p, 20);105}106107#if 0108static int point_is_on_curve(u8 *p)109{110u8 s[20], t[20];111u8 *x, *y;112113x = p;114y = p + 20;115116elt_square(t, x);117elt_mul(s, t, x);118119elt_mul(t, x, ec_a);120elt_add(s, s, t);121122elt_add(s, s, ec_b);123124elt_square(t, y);125elt_sub(s, s, t);126127return elt_is_zero(s);128}129#endif130131static void point_zero(struct point *p)132{133elt_zero(p->x);134elt_zero(p->y);135}136137static int point_is_zero(struct point *p)138{139return elt_is_zero(p->x) && elt_is_zero(p->y);140}141142static void point_double(struct point *r, struct point *p)143{144u8 s[20], t[20];145struct point pp;146u8 *px, *py, *rx, *ry;147148pp = *p;149150px = pp.x;151py = pp.y;152rx = r->x;153ry = r->y;154155if (elt_is_zero(py)) {156point_zero(r);157return;158}159160elt_square(t, px); // t = px*px161elt_add(s, t, t); // s = 2*px*px162elt_add(s, s, t); // s = 3*px*px163elt_add(s, s, ec_a); // s = 3*px*px + a164elt_add(t, py, py); // t = 2*py165elt_inv(t, t); // t = 1/(2*py)166elt_mul(s, s, t); // s = (3*px*px+a)/(2*py)167168elt_square(rx, s); // rx = s*s169elt_add(t, px, px); // t = 2*px170elt_sub(rx, rx, t); // rx = s*s - 2*px171172elt_sub(t, px, rx); // t = -(rx-px)173elt_mul(ry, s, t); // ry = -s*(rx-px)174elt_sub(ry, ry, py); // ry = -s*(rx-px) - py175}176177static void point_add(struct point *r, struct point *p, struct point *q)178{179u8 s[20], t[20], u[20];180u8 *px, *py, *qx, *qy, *rx, *ry;181struct point pp, qq;182183pp = *p;184qq = *q;185186px = pp.x;187py = pp.y;188qx = qq.x;189qy = qq.y;190rx = r->x;191ry = r->y;192193if (point_is_zero(&pp)) {194elt_copy(rx, qx);195elt_copy(ry, qy);196return;197}198199if (point_is_zero(&qq)) {200elt_copy(rx, px);201elt_copy(ry, py);202return;203}204205elt_sub(u, qx, px);206207if (elt_is_zero(u)) {208elt_sub(u, qy, py);209if (elt_is_zero(u))210point_double(r, &pp);211else212point_zero(r);213214return;215}216217elt_inv(t, u); // t = 1/(qx-px)218elt_sub(u, qy, py); // u = qy-py219elt_mul(s, t, u); // s = (qy-py)/(qx-px)220221elt_square(rx, s); // rx = s*s222elt_add(t, px, qx); // t = px+qx223elt_sub(rx, rx, t); // rx = s*s - (px+qx)224225elt_sub(t, px, rx); // t = -(rx-px)226elt_mul(ry, s, t); // ry = -s*(rx-px)227elt_sub(ry, ry, py); // ry = -s*(rx-px) - py228}229230static void point_mul(struct point *d, u8 *a, struct point *b) // a is bignum231{232u32 i;233u8 mask;234235point_zero(d);236237for (i = 0; i < 21; i++)238for (mask = 0x80; mask != 0; mask >>= 1) {239point_double(d, d);240if ((a[i] & mask) != 0)241point_add(d, d, b);242}243}244// Modified from original to support kirk engine use - July 2011245// Added call to Kirk Random number generator rather than /dev/random246247static void generate_ecdsa(u8 *outR, u8 *outS, u8 *k, u8 *hash)248{249u8 e[21];250u8 kk[21];251u8 m[21];252u8 R[21];253u8 S[21];254u8 minv[21];255struct point mG;256257e[0] = 0;R[0] = 0;S[0] = 0;258memcpy(e + 1, hash, 20);259bn_reduce(e, ec_N, 21);260261// Original removed for portability262//try_again:263//fp = fopen("/dev/random", "rb");264//if (fread(m, sizeof m, 1, fp) != 1)265//fail("reading random");266//fclose(fp);267//m[0] = 0;268//if (bn_compare(m, ec_N, 21) >= 0)269//goto try_again;270271// R = (mG).x272273// Added call back to kirk PRNG - July 2011274kirk_CMD14(m+1, 20);275m[0] = 0;276277point_mul(&mG, m, &ec_G);278point_from_mon(&mG);279R[0] = 0;280elt_copy(R+1, mG.x);281282// S = m**-1*(e + Rk) (mod N)283284bn_copy(kk, k, 21);285bn_reduce(kk, ec_N, 21);286bn_to_mon(m, ec_N, 21);287bn_to_mon(e, ec_N, 21);288bn_to_mon(R, ec_N, 21);289bn_to_mon(kk, ec_N, 21);290291bn_mon_mul(S, R, kk, ec_N, 21);292bn_add(kk, S, e, ec_N, 21);293bn_mon_inv(minv, m, ec_N, 21);294bn_mon_mul(S, minv, kk, ec_N, 21);295296bn_from_mon(R, ec_N, 21);297bn_from_mon(S, ec_N, 21);298memcpy(outR,R+1,20);299memcpy(outS,S+1,20);300}301302// Signing =303// r = k *G;304// s = x*r+m / k305306// Verify =307// r/s * P = m/s * G308309// Slightly modified to support kirk compatible signature input - July 2011310static int check_ecdsa(struct point *Q, u8 *inR, u8 *inS, u8 *hash)311{312u8 Sinv[21];313u8 e[21], R[21], S[21];314u8 w1[21], w2[21];315struct point r1, r2;316u8 rr[21];317318e[0] = 0;319memcpy(e + 1, hash, 20);320bn_reduce(e, ec_N, 21);321R[0] = 0;322memcpy(R + 1, inR, 20);323bn_reduce(R, ec_N, 21);324S[0] = 0;325memcpy(S + 1, inS, 20);326bn_reduce(S, ec_N, 21);327328bn_to_mon(R, ec_N, 21);329bn_to_mon(S, ec_N, 21);330bn_to_mon(e, ec_N, 21);331// make Sinv = 1/S332bn_mon_inv(Sinv, S, ec_N, 21);333// w1 = m * Sinv334bn_mon_mul(w1, e, Sinv, ec_N, 21);335// w2 = r * Sinv336bn_mon_mul(w2, R, Sinv, ec_N, 21);337338// mod N both339bn_from_mon(w1, ec_N, 21);340bn_from_mon(w2, ec_N, 21);341342// r1 = m/s * G343point_mul(&r1, w1, &ec_G);344// r2 = r/s * P345point_mul(&r2, w2, Q);346347//r1 = r1 + r2348point_add(&r1, &r1, &r2);349350point_from_mon(&r1);351352rr[0] = 0;353memcpy(rr + 1, r1.x, 20);354bn_reduce(rr, ec_N, 21);355356bn_from_mon(R, ec_N, 21);357bn_from_mon(S, ec_N, 21);358359return (bn_compare(rr, R, 21) == 0);360}361362363// Modified from original to support kirk engine use - July 2011364void ec_priv_to_pub(u8 *k, u8 *Q)365{366struct point ec_temp;367bn_to_mon(k, ec_N, 21);368point_mul(&ec_temp, k, &ec_G);369point_from_mon(&ec_temp);370//bn_from_mon(k, ec_N, 21);371memcpy(Q,ec_temp.x,20);372memcpy(Q+20,ec_temp.y,20);373}374375// Modified from original to support kirk engine use - July 2011376void ec_pub_mult(u8 *k, u8 *Q)377{378struct point ec_temp;379//bn_to_mon(k, ec_N, 21);380point_mul(&ec_temp, k, &ec_Q);381point_from_mon(&ec_temp);382//bn_from_mon(k, ec_N, 21);383memcpy(Q,ec_temp.x,20);384memcpy(Q+20,ec_temp.y,20);385}386387388// Simplified for use by Kirk Engine - NO LONGER COMPATIABLE WITH ORIGINAL VERSION - July 2011389int ecdsa_set_curve(u8* p,u8* a,u8* b,u8* N,u8* Gx,u8* Gy)390{391memcpy(ec_p,p,20);392memcpy(ec_a,a,20);393memcpy(ec_b,b,20);394memcpy(ec_N,N,21);395396bn_to_mon(ec_a, ec_p, 20);397bn_to_mon(ec_b, ec_p, 20);398399memcpy(ec_G.x, Gx, 20);400memcpy(ec_G.y, Gy, 20);401point_to_mon(&ec_G);402403return 0;404}405406void ecdsa_set_pub(u8 *Q)407{408memcpy(ec_Q.x, Q, 20);409memcpy(ec_Q.y, Q+20, 20);410point_to_mon(&ec_Q);411}412413void ecdsa_set_priv(u8 *ink)414{415u8 k[21];416k[0]=0;417memcpy(k+1,ink,20);418bn_reduce(k, ec_N, 21);419420memcpy(ec_k, k, sizeof ec_k);421}422423int ecdsa_verify(u8 *hash, u8 *R, u8 *S)424{425return check_ecdsa(&ec_Q, R, S, hash);426}427428void ecdsa_sign(u8 *hash, u8 *R, u8 *S)429{430generate_ecdsa(R, S, ec_k, hash);431}432433int point_is_on_curve(u8 *p)434{435u8 s[20], t[20];436u8 *x, *y;437438x = p;439y = p + 20;440441elt_square(t, x);442elt_mul(s, t, x);// s = x^3443444elt_mul(t, x, ec_a);445elt_add(s, s, t); //s = x^3 + a *x446447elt_add(s, s, ec_b);//s = x^3 + a *x + b448449elt_square(t, y); //t = y^2450elt_sub(s, s, t); // is s - t = 0?451hex_dump("S", s, 20);452hex_dump("T", t,20);453return elt_is_zero(s);454}455456void dump_ecc(void) {457hex_dump("P", ec_p, 20);458hex_dump("a", ec_a, 20);459hex_dump("b", ec_b, 20);460hex_dump("N", ec_N, 21);461hex_dump("Gx", ec_G.x, 20);462hex_dump("Gy", ec_G.y, 20);463}464465466