#include "os.h"
#include <mp.h>
#include <libsec.h>
#include <ctype.h>

extern void jacobian_affine(mpint *p,
       mpint *X, mpint *Y, mpint *Z);
extern void jacobian_dbl(mpint *p, mpint *a,
       mpint *X1, mpint *Y1, mpint *Z1,
       mpint *X3, mpint *Y3, mpint *Z3);
extern void jacobian_add(mpint *p, mpint *a,
       mpint *X1, mpint *Y1, mpint *Z1,
       mpint *X2, mpint *Y2, mpint *Z2,
       mpint *X3, mpint *Y3, mpint *Z3);

void
ecassign(ECdomain *dom, ECpoint *a, ECpoint *b)
{
       if((b->inf = a->inf) != 0)
               return;
       mpassign(a->x, b->x);
       mpassign(a->y, b->y);
       if(b->z != nil){
               mpassign(a->z != nil ? a->z : mpone, b->z);
               return;
       }
       if(a->z != nil){
               b->z = mpcopy(a->z);
               jacobian_affine(dom->p, b->x, b->y, b->z);
               mpfree(b->z);
               b->z = nil;
       }
}

void
ecadd(ECdomain *dom, ECpoint *a, ECpoint *b, ECpoint *s)
{
       if(a->inf && b->inf){
               s->inf = 1;
               return;
       }
       if(a->inf){
               ecassign(dom, b, s);
               return;
       }
       if(b->inf){
               ecassign(dom, a, s);
               return;
       }

       if(s->z == nil){
               s->z = mpcopy(mpone);
               ecadd(dom, a, b, s);
               if(!s->inf)
                       jacobian_affine(dom->p, s->x, s->y, s->z);
               mpfree(s->z);
               s->z = nil;
               return;
       }

       if(a == b)
               jacobian_dbl(dom->p, dom->a,
                       a->x, a->y, a->z != nil ? a->z : mpone,
                       s->x, s->y, s->z);
       else
               jacobian_add(dom->p, dom->a,
                       a->x, a->y, a->z != nil ? a->z : mpone,
                       b->x, b->y, b->z != nil ? b->z : mpone,
                       s->x, s->y, s->z);
       s->inf = mpcmp(s->z, mpzero) == 0;
}

void
ecmul(ECdomain *dom, ECpoint *a, mpint *k, ECpoint *s)
{
       ECpoint ns, na;
       mpint *l;

       if(a->inf || mpcmp(k, mpzero) == 0){
               s->inf = 1;
               return;
       }
       ns.inf = 1;
       ns.x = mpnew(0);
       ns.y = mpnew(0);
       ns.z = mpnew(0);
       na.x = mpnew(0);
       na.y = mpnew(0);
       na.z = mpnew(0);
       ecassign(dom, a, &na);
       l = mpcopy(k);
       l->sign = 1;
       while(mpcmp(l, mpzero) != 0){
               if(l->p[0] & 1)
                       ecadd(dom, &na, &ns, &ns);
               ecadd(dom, &na, &na, &na);
               mpright(l, 1, l);
       }
       if(k->sign < 0 && !ns.inf){
               ns.y->sign = -1;
               mpmod(ns.y, dom->p, ns.y);
       }
       ecassign(dom, &ns, s);
       mpfree(ns.x);
       mpfree(ns.y);
       mpfree(ns.z);
       mpfree(na.x);
       mpfree(na.y);
       mpfree(na.z);
       mpfree(l);
}

int
ecverify(ECdomain *dom, ECpoint *a)
{
       mpint *p, *q;
       int r;

       if(a->inf)
               return 1;

       assert(a->z == nil);    /* need affine coordinates */
       p = mpnew(0);
       q = mpnew(0);
       mpmodmul(a->y, a->y, dom->p, p);
       mpmodmul(a->x, a->x, dom->p, q);
       mpmodadd(q, dom->a, dom->p, q);
       mpmodmul(q, a->x, dom->p, q);
       mpmodadd(q, dom->b, dom->p, q);
       r = mpcmp(p, q);
       mpfree(p);
       mpfree(q);
       return r == 0;
}

int
ecpubverify(ECdomain *dom, ECpub *a)
{
       ECpoint p;
       int r;

       if(a->inf)
               return 0;
       if(!ecverify(dom, a))
               return 0;
       p.x = mpnew(0);
       p.y = mpnew(0);
       p.z = mpnew(0);
       ecmul(dom, a, dom->n, &p);
       r = p.inf;
       mpfree(p.x);
       mpfree(p.y);
       mpfree(p.z);
       return r;
}

static void
fixnibble(uchar *a)
{
       if(*a >= 'a')
               *a -= 'a'-10;
       else if(*a >= 'A')
               *a -= 'A'-10;
       else
               *a -= '0';
}

static int
octet(char **s)
{
       uchar c, d;

       c = *(*s)++;
       if(!isxdigit(c))
               return -1;
       d = *(*s)++;
       if(!isxdigit(d))
               return -1;
       fixnibble(&c);
       fixnibble(&d);
       return (c << 4) | d;
}

static mpint*
halfpt(ECdomain *dom, char *s, char **rptr, mpint *out)
{
       char *buf, *r;
       int n;
       mpint *ret;

       n = ((mpsignif(dom->p)+7)/8)*2;
       if(strlen(s) < n)
               return 0;
       buf = malloc(n+1);
       buf[n] = 0;
       memcpy(buf, s, n);
       ret = strtomp(buf, &r, 16, out);
       *rptr = s + (r - buf);
       free(buf);
       return ret;
}

static int
mpleg(mpint *a, mpint *b)
{
       int r, k;
       mpint *m, *n, *t;

       r = 1;
       m = mpcopy(a);
       n = mpcopy(b);
       for(;;){
               if(mpcmp(m, n) > 0)
                       mpmod(m, n, m);
               if(mpcmp(m, mpzero) == 0){
                       r = 0;
                       break;
               }
               if(mpcmp(m, mpone) == 0)
                       break;
               k = mplowbits0(m);
               if(k > 0){
                       if(k & 1)
                               switch(n->p[0] & 15){
                               case 3: case 5: case 11: case 13:
                                       r = -r;
                               }
                       mpright(m, k, m);
               }
               if((n->p[0] & 3) == 3 && (m->p[0] & 3) == 3)
                       r = -r;
               t = m;
               m = n;
               n = t;
       }
       mpfree(m);
       mpfree(n);
       return r;
}

static int
mpsqrt(mpint *n, mpint *p, mpint *r)
{
       mpint *a, *t, *s, *xp, *xq, *yp, *yq, *zp, *zq, *N;

       if(mpleg(n, p) == -1)
               return 0;
       a = mpnew(0);
       t = mpnew(0);
       s = mpnew(0);
       N = mpnew(0);
       xp = mpnew(0);
       xq = mpnew(0);
       yp = mpnew(0);
       yq = mpnew(0);
       zp = mpnew(0);
       zq = mpnew(0);
       for(;;){
               for(;;){
                       mpnrand(p, genrandom, a);
                       if(mpcmp(a, mpzero) > 0)
                               break;
               }
               mpmul(a, a, t);
               mpsub(t, n, t);
               mpmod(t, p, t);
               if(mpleg(t, p) == -1)
                       break;
       }
       mpadd(p, mpone, N);
       mpright(N, 1, N);
       mpmul(a, a, t);
       mpsub(t, n, t);
       mpassign(a, xp);
       uitomp(1, xq);
       uitomp(1, yp);
       uitomp(0, yq);
       while(mpcmp(N, mpzero) != 0){
               if(N->p[0] & 1){
                       mpmul(xp, yp, zp);
                       mpmul(xq, yq, zq);
                       mpmul(zq, t, zq);
                       mpadd(zp, zq, zp);
                       mpmod(zp, p, zp);
                       mpmul(xp, yq, zq);
                       mpmul(xq, yp, s);
                       mpadd(zq, s, zq);
                       mpmod(zq, p, yq);
                       mpassign(zp, yp);
               }
               mpmul(xp, xp, zp);
               mpmul(xq, xq, zq);
               mpmul(zq, t, zq);
               mpadd(zp, zq, zp);
               mpmod(zp, p, zp);
               mpmul(xp, xq, zq);
               mpadd(zq, zq, zq);
               mpmod(zq, p, xq);
               mpassign(zp, xp);
               mpright(N, 1, N);
       }
       if(mpcmp(yq, mpzero) != 0)
               abort();
       mpassign(yp, r);
       mpfree(a);
       mpfree(t);
       mpfree(s);
       mpfree(N);
       mpfree(xp);
       mpfree(xq);
       mpfree(yp);
       mpfree(yq);
       mpfree(zp);
       mpfree(zq);
       return 1;
}

ECpoint*
strtoec(ECdomain *dom, char *s, char **rptr, ECpoint *ret)
{
       int allocd, o;
       mpint *r;

       allocd = 0;
       if(ret == nil){
               allocd = 1;
               ret = mallocz(sizeof(*ret), 1);
               if(ret == nil)
                       return nil;
               ret->x = mpnew(0);
               ret->y = mpnew(0);
       }
       ret->inf = 0;
       o = 0;
       switch(octet(&s)){
       case 0:
               ret->inf = 1;
               break;
       case 3:
               o = 1;
       case 2:
               if(halfpt(dom, s, &s, ret->x) == nil)
                       goto err;
               r = mpnew(0);
               mpmul(ret->x, ret->x, r);
               mpadd(r, dom->a, r);
               mpmul(r, ret->x, r);
               mpadd(r, dom->b, r);
               if(!mpsqrt(r, dom->p, r)){
                       mpfree(r);
                       goto err;
               }
               if((r->p[0] & 1) != o)
                       mpsub(dom->p, r, r);
               mpassign(r, ret->y);
               mpfree(r);
               if(!ecverify(dom, ret))
                       goto err;
               break;
       case 4:
               if(halfpt(dom, s, &s, ret->x) == nil)
                       goto err;
               if(halfpt(dom, s, &s, ret->y) == nil)
                       goto err;
               if(!ecverify(dom, ret))
                       goto err;
               break;
       }
       if(ret->z != nil && !ret->inf)
               mpassign(mpone, ret->z);
       return ret;

err:
       if(rptr)
               *rptr = s;
       if(allocd){
               mpfree(ret->x);
               mpfree(ret->y);
               free(ret);
       }
       return nil;
}

ECpriv*
ecgen(ECdomain *dom, ECpriv *p)
{
       if(p == nil){
               p = mallocz(sizeof(*p), 1);
               if(p == nil)
                       return nil;
               p->x = mpnew(0);
               p->y = mpnew(0);
               p->d = mpnew(0);
       }
       for(;;){
               mpnrand(dom->n, genrandom, p->d);
               if(mpcmp(p->d, mpzero) > 0)
                       break;
       }
       ecmul(dom, &dom->G, p->d, p);
       return p;
}

void
ecdsasign(ECdomain *dom, ECpriv *priv, uchar *dig, int len, mpint *r, mpint *s)
{
       ECpriv tmp;
       mpint *E, *t;

       tmp.x = mpnew(0);
       tmp.y = mpnew(0);
       tmp.z = nil;
       tmp.d = mpnew(0);
       E = betomp(dig, len, nil);
       t = mpnew(0);
       if(mpsignif(dom->n) < 8*len)
               mpright(E, 8*len - mpsignif(dom->n), E);
       for(;;){
               ecgen(dom, &tmp);
               mpmod(tmp.x, dom->n, r);
               if(mpcmp(r, mpzero) == 0)
                       continue;
               mpmul(r, priv->d, s);
               mpadd(E, s, s);
               mpinvert(tmp.d, dom->n, t);
               mpmodmul(s, t, dom->n, s);
               if(mpcmp(s, mpzero) != 0)
                       break;
       }
       mpfree(t);
       mpfree(E);
       mpfree(tmp.x);
       mpfree(tmp.y);
       mpfree(tmp.d);
}

int
ecdsaverify(ECdomain *dom, ECpub *pub, uchar *dig, int len, mpint *r, mpint *s)
{
       mpint *E, *t, *u1, *u2;
       ECpoint R, S;
       int ret;

       if(mpcmp(r, mpone) < 0 || mpcmp(s, mpone) < 0 || mpcmp(r, dom->n) >= 0 || mpcmp(r, dom->n) >= 0)
               return 0;
       E = betomp(dig, len, nil);
       if(mpsignif(dom->n) < 8*len)
               mpright(E, 8*len - mpsignif(dom->n), E);
       t = mpnew(0);
       u1 = mpnew(0);
       u2 = mpnew(0);
       R.x = mpnew(0);
       R.y = mpnew(0);
       R.z = mpnew(0);
       S.x = mpnew(0);
       S.y = mpnew(0);
       S.z = mpnew(0);
       mpinvert(s, dom->n, t);
       mpmodmul(E, t, dom->n, u1);
       mpmodmul(r, t, dom->n, u2);
       ecmul(dom, &dom->G, u1, &R);
       ecmul(dom, pub, u2, &S);
       ecadd(dom, &R, &S, &R);
       ret = 0;
       if(!R.inf){
               jacobian_affine(dom->p, R.x, R.y, R.z);
               mpmod(R.x, dom->n, t);
               ret = mpcmp(r, t) == 0;
       }
       mpfree(E);
       mpfree(t);
       mpfree(u1);
       mpfree(u2);
       mpfree(R.x);
       mpfree(R.y);
       mpfree(R.z);
       mpfree(S.x);
       mpfree(S.y);
       mpfree(S.z);
       return ret;
}

static char *code = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

void
base58enc(uchar *src, char *dst, int len)
{
       mpint *n, *r, *b;
       char *sdst, t;

       sdst = dst;
       n = betomp(src, len, nil);
       b = uitomp(58, nil);
       r = mpnew(0);
       while(mpcmp(n, mpzero) != 0){
               mpdiv(n, b, n, r);
               *dst++ = code[mptoui(r)];
       }
       for(; *src == 0; src++)
               *dst++ = code[0];
       *dst-- = 0;
       while(dst > sdst){
               t = *sdst;
               *sdst++ = *dst;
               *dst-- = t;
       }
}

int
base58dec(char *src, uchar *dst, int len)
{
       mpint *n, *b, *r;
       char *t;

       n = mpnew(0);
       r = mpnew(0);
       b = uitomp(58, nil);
       for(; *src; src++){
               t = strchr(code, *src);
               if(t == nil){
                       mpfree(n);
                       mpfree(r);
                       mpfree(b);
                       werrstr("invalid base58 char");
                       return -1;
               }
               uitomp(t - code, r);
               mpmul(n, b, n);
               mpadd(n, r, n);
       }
       mptober(n, dst, len);
       mpfree(n);
       mpfree(r);
       mpfree(b);
       return 0;
}

void
ecdominit(ECdomain *dom, void (*init)(mpint *p, mpint *a, mpint *b, mpint *x, mpint *y, mpint *n, mpint *h))
{
       memset(dom, 0, sizeof(*dom));
       dom->p = mpnew(0);
       dom->a = mpnew(0);
       dom->b = mpnew(0);
       dom->G.x = mpnew(0);
       dom->G.y = mpnew(0);
       dom->n = mpnew(0);
       dom->h = mpnew(0);
       if(init){
               (*init)(dom->p, dom->a, dom->b, dom->G.x, dom->G.y, dom->n, dom->h);
               dom->p = mpfield(dom->p);
       }
}

void
ecdomfree(ECdomain *dom)
{
       mpfree(dom->p);
       mpfree(dom->a);
       mpfree(dom->b);
       mpfree(dom->G.x);
       mpfree(dom->G.y);
       mpfree(dom->n);
       mpfree(dom->h);
       memset(dom, 0, sizeof(*dom));
}

int
ecencodepub(ECdomain *dom, ECpub *pub, uchar *data, int len)
{
       int n;

       n = (mpsignif(dom->p)+7)/8;
       if(len < 1 + 2*n)
               return 0;
       len = 1 + 2*n;
       data[0] = 0x04;
       mptober(pub->x, data+1, n);
       mptober(pub->y, data+1+n, n);
       return len;
}

ECpub*
ecdecodepub(ECdomain *dom, uchar *data, int len)
{
       ECpub *pub;
       int n;

       n = (mpsignif(dom->p)+7)/8;
       if(len != 1 + 2*n || data[0] != 0x04)
               return nil;
       pub = mallocz(sizeof(*pub), 1);
       if(pub == nil)
               return nil;
       pub->x = betomp(data+1, n, nil);
       pub->y = betomp(data+1+n, n, nil);
       if(!ecpubverify(dom, pub)){
               ecpubfree(pub);
               pub = nil;
       }
       return pub;
}

void
ecpubfree(ECpub *p)
{
       if(p == nil)
               return;
       mpfree(p->x);
       mpfree(p->y);
       free(p);
}

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.