sys/src/libsec/port/ecc.c

   1 #include "os.h"
   2 #include <mp.h>
   3 #include <libsec.h>
   4 #include <ctype.h>
   5
   6 void
   7 ecassign(ECdomain *, ECpoint *a, ECpoint *b)
   8 {
   9         b->inf = a->inf;
  10         mpassign(a->x, b->x);
  11         mpassign(a->y, b->y);
  12 }
  13
  14 void
  15 ecadd(ECdomain *dom, ECpoint *a, ECpoint *b, ECpoint *s)
  16 {
  17         mpint *l, *k, *sx, *sy;
  18
  19         if(a->inf && b->inf){
  20                 s->inf = 1;
  21                 return;
  22         }
  23         if(a->inf){
  24                 ecassign(dom, b, s);
  25                 return;
  26         }
  27         if(b->inf){
  28                 ecassign(dom, a, s);
  29                 return;
  30         }
  31         if(mpcmp(a->x, b->x) == 0 && (mpcmp(a->y, mpzero) == 0 || mpcmp(a->y, b->y) != 0)){
  32                 s->inf = 1;
  33                 return;
  34         }
  35         l = mpnew(0);
  36         k = mpnew(0);
  37         sx = mpnew(0);
  38         sy = mpnew(0);
  39         if(mpcmp(a->x, b->x) == 0 && mpcmp(a->y, b->y) == 0){
  40                 mpadd(mpone, mptwo, k);
  41                 mpmul(a->x, a->x, l);
  42                 mpmul(l, k, l);
  43                 mpadd(l, dom->a, l);
  44                 mpleft(a->y, 1, k);
  45                 mpmod(k, dom->p, k);
  46                 mpinvert(k, dom->p, k);
  47                 mpmul(k, l, l);
  48                 mpmod(l, dom->p, l);
  49
  50                 mpleft(a->x, 1, k);
  51                 mpmul(l, l, sx);
  52                 mpsub(sx, k, sx);
  53                 mpmod(sx, dom->p, sx);
  54
  55                 mpsub(a->x, sx, sy);
  56                 mpmul(l, sy, sy);
  57                 mpsub(sy, a->y, sy);
  58                 mpmod(sy, dom->p, sy);
  59                 mpassign(sx, s->x);
  60                 mpassign(sy, s->y);
  61                 mpfree(sx);
  62                 mpfree(sy);
  63                 mpfree(l);
  64                 mpfree(k);
  65                 return;
  66         }
  67         mpsub(b->y, a->y, l);
  68         mpmod(l, dom->p, l);
  69         mpsub(b->x, a->x, k);
  70         mpmod(k, dom->p, k);
  71         mpinvert(k, dom->p, k);
  72         mpmul(k, l, l);
  73         mpmod(l, dom->p, l);
  74
  75         mpmul(l, l, sx);
  76         mpsub(sx, a->x, sx);
  77         mpsub(sx, b->x, sx);
  78         mpmod(sx, dom->p, sx);
  79
  80         mpsub(a->x, sx, sy);
  81         mpmul(sy, l, sy);
  82         mpsub(sy, a->y, sy);
  83         mpmod(sy, dom->p, sy);
  84
  85         mpassign(sx, s->x);
  86         mpassign(sy, s->y);
  87         mpfree(sx);
  88         mpfree(sy);
  89         mpfree(l);
  90         mpfree(k);
  91 }
  92
  93 void
  94 ecmul(ECdomain *dom, ECpoint *a, mpint *k, ECpoint *s)
  95 {
  96         ECpoint ns, na;
  97         mpint *l;
  98
  99         if(a->inf || mpcmp(k, mpzero) == 0){
 100                 s->inf = 1;
 101                 return;
 102         }
 103         ns.inf = 1;
 104         ns.x = mpnew(0);
 105         ns.y = mpnew(0);
 106         na.x = mpnew(0);
 107         na.y = mpnew(0);
 108         ecassign(dom, a, &na);
 109         l = mpcopy(k);
 110         l->sign = 1;
 111         while(mpcmp(l, mpzero) != 0){
 112                 if(l->p[0] & 1)
 113                         ecadd(dom, &na, &ns, &ns);
 114                 ecadd(dom, &na, &na, &na);
 115                 mpright(l, 1, l);
 116         }
 117         if(k->sign < 0){
 118                 ns.y->sign = -1;
 119                 mpmod(ns.y, dom->p, ns.y);
 120         }
 121         ecassign(dom, &ns, s);
 122         mpfree(ns.x);
 123         mpfree(ns.y);
 124         mpfree(na.x);
 125         mpfree(na.y);
 126 }
 127
 128 int
 129 ecverify(ECdomain *dom, ECpoint *a)
 130 {
 131         mpint *p, *q;
 132         int r;
 133
 134         if(a->inf)
 135                 return 1;
 136
 137         p = mpnew(0);
 138         q = mpnew(0);
 139         mpmul(a->y, a->y, p);
 140         mpmod(p, dom->p, p);
 141         mpmul(a->x, a->x, q);
 142         mpadd(q, dom->a, q);
 143         mpmul(a->x, q, q);
 144         mpadd(q, dom->b, q);
 145         mpmod(q, dom->p, q);
 146         r = mpcmp(p, q);
 147         mpfree(p);
 148         mpfree(q);
 149         return r == 0;
 150 }
 151
 152 int
 153 ecpubverify(ECdomain *dom, ECpub *a)
 154 {
 155         ECpoint p;
 156         int r;
 157
 158         if(a->inf)
 159                 return 0;
 160         if(!ecverify(dom, a))
 161                 return 0;
 162         p.x = mpnew(0);
 163         p.y = mpnew(0);
 164         ecmul(dom, a, dom->n, &p);
 165         r = p.inf;
 166         mpfree(p.x);
 167         mpfree(p.y);
 168         return r;
 169 }
 170
 171 static void
 172 fixnibble(uchar *a)
 173 {
 174         if(*a >= 'a')
 175                 *a -= 'a'-10;
 176         else if(*a >= 'A')
 177                 *a -= 'A'-10;
 178         else
 179                 *a -= '0';
 180 }
 181
 182 static int
 183 octet(char **s)
 184 {
 185         uchar c, d;
 186
 187         c = *(*s)++;
 188         if(!isxdigit(c))
 189                 return -1;
 190         d = *(*s)++;
 191         if(!isxdigit(d))
 192                 return -1;
 193         fixnibble(&c);
 194         fixnibble(&d);
 195         return (c << 4) | d;
 196 }
 197
 198 static mpint*
 199 halfpt(ECdomain *dom, char *s, char **rptr, mpint *out)
 200 {
 201         char *buf, *r;
 202         int n;
 203         mpint *ret;
 204
 205         n = ((mpsignif(dom->p)+7)/8)*2;
 206         if(strlen(s) < n)
 207                 return 0;
 208         buf = malloc(n+1);
 209         buf[n] = 0;
 210         memcpy(buf, s, n);
 211         ret = strtomp(buf, &r, 16, out);
 212         *rptr = s + (r - buf);
 213         free(buf);
 214         return ret;
 215 }
 216
 217 static int
 218 mpleg(mpint *a, mpint *b)
 219 {
 220         int r, k;
 221         mpint *m, *n, *t;
 222
 223         r = 1;
 224         m = mpcopy(a);
 225         n = mpcopy(b);
 226         for(;;){
 227                 if(mpcmp(m, n) > 0)
 228                         mpmod(m, n, m);
 229                 if(mpcmp(m, mpzero) == 0){
 230                         r = 0;
 231                         break;
 232                 }
 233                 if(mpcmp(m, mpone) == 0)
 234                         break;
 235                 k = mplowbits0(m);
 236                 if(k > 0){
 237                         if(k & 1)
 238                                 switch(n->p[0] & 15){
 239                                 case 3: case 5: case 11: case 13:
 240                                         r = -r;
 241                                 }
 242                         mpright(m, k, m);
 243                 }
 244                 if((n->p[0] & 3) == 3 && (m->p[0] & 3) == 3)
 245                         r = -r;
 246                 t = m;
 247                 m = n;
 248                 n = t;
 249         }
 250         mpfree(m);
 251         mpfree(n);
 252         return r;
 253 }
 254
 255 static int
 256 mpsqrt(mpint *n, mpint *p, mpint *r)
 257 {
 258         mpint *a, *t, *s, *xp, *xq, *yp, *yq, *zp, *zq, *N;
 259
 260         if(mpleg(n, p) == -1)
 261                 return 0;
 262         a = mpnew(0);
 263         t = mpnew(0);
 264         s = mpnew(0);
 265         N = mpnew(0);
 266         xp = mpnew(0);
 267         xq = mpnew(0);
 268         yp = mpnew(0);
 269         yq = mpnew(0);
 270         zp = mpnew(0);
 271         zq = mpnew(0);
 272         for(;;){
 273                 for(;;){
 274                         mprand(mpsignif(p), genrandom, a);
 275                         if(mpcmp(a, mpzero) > 0 && mpcmp(a, p) < 0)
 276                                 break;
 277                 }
 278                 mpmul(a, a, t);
 279                 mpsub(t, n, t);
 280                 mpmod(t, p, t);
 281                 if(mpleg(t, p) == -1)
 282                         break;
 283         }
 284         mpadd(p, mpone, N);
 285         mpright(N, 1, N);
 286         mpmul(a, a, t);
 287         mpsub(t, n, t);
 288         mpassign(a, xp);
 289         uitomp(1, xq);
 290         uitomp(1, yp);
 291         uitomp(0, yq);
 292         while(mpcmp(N, mpzero) != 0){
 293                 if(N->p[0] & 1){
 294                         mpmul(xp, yp, zp);
 295                         mpmul(xq, yq, zq);
 296                         mpmul(zq, t, zq);
 297                         mpadd(zp, zq, zp);
 298                         mpmod(zp, p, zp);
 299                         mpmul(xp, yq, zq);
 300                         mpmul(xq, yp, s);
 301                         mpadd(zq, s, zq);
 302                         mpmod(zq, p, yq);
 303                         mpassign(zp, yp);
 304                 }
 305                 mpmul(xp, xp, zp);
 306                 mpmul(xq, xq, zq);
 307                 mpmul(zq, t, zq);
 308                 mpadd(zp, zq, zp);
 309                 mpmod(zp, p, zp);
 310                 mpmul(xp, xq, zq);
 311                 mpadd(zq, zq, zq);
 312                 mpmod(zq, p, xq);
 313                 mpassign(zp, xp);
 314                 mpright(N, 1, N);
 315         }
 316         if(mpcmp(yq, mpzero) != 0)
 317                 abort();
 318         mpassign(yp, r);
 319         mpfree(a);
 320         mpfree(t);
 321         mpfree(s);
 322         mpfree(N);
 323         mpfree(xp);
 324         mpfree(xq);
 325         mpfree(yp);
 326         mpfree(yq);
 327         mpfree(zp);
 328         mpfree(zq);
 329         return 1;
 330 }
 331
 332 ECpoint*
 333 strtoec(ECdomain *dom, char *s, char **rptr, ECpoint *ret)
 334 {
 335         int allocd, o;
 336         mpint *r;
 337
 338         allocd = 0;
 339         if(ret == nil){
 340                 allocd = 1;
 341                 ret = mallocz(sizeof(*ret), 1);
 342                 if(ret == nil)
 343                         return nil;
 344                 ret->x = mpnew(0);
 345                 ret->y = mpnew(0);
 346         }
 347         o = 0;
 348         switch(octet(&s)){
 349         case 0:
 350                 ret->inf = 1;
 351                 return ret;
 352         case 3:
 353                 o = 1;
 354         case 2:
 355                 if(halfpt(dom, s, &s, ret->x) == nil)
 356                         goto err;
 357                 r = mpnew(0);
 358                 mpmul(ret->x, ret->x, r);
 359                 mpadd(r, dom->a, r);
 360                 mpmul(r, ret->x, r);
 361                 mpadd(r, dom->b, r);
 362                 if(!mpsqrt(r, dom->p, r)){
 363                         mpfree(r);
 364                         goto err;
 365                 }
 366                 if((r->p[0] & 1) != o)
 367                         mpsub(dom->p, r, r);
 368                 mpassign(r, ret->y);
 369                 mpfree(r);
 370                 if(!ecverify(dom, ret))
 371                         goto err;
 372                 return ret;
 373         case 4:
 374                 if(halfpt(dom, s, &s, ret->x) == nil)
 375                         goto err;
 376                 if(halfpt(dom, s, &s, ret->y) == nil)
 377                         goto err;
 378                 if(!ecverify(dom, ret))
 379                         goto err;
 380                 return ret;
 381         }
 382 err:
 383         if(rptr)
 384                 *rptr = s;
 385         if(allocd){
 386                 mpfree(ret->x);
 387                 mpfree(ret->y);
 388                 free(ret);
 389         }
 390         return nil;
 391 }
 392
 393 ECpriv*
 394 ecgen(ECdomain *dom, ECpriv *p)
 395 {
 396         if(p == nil){
 397                 p = mallocz(sizeof(*p), 1);
 398                 if(p == nil)
 399                         return nil;
 400                 p->x = mpnew(0);
 401                 p->y = mpnew(0);
 402                 p->d = mpnew(0);
 403         }
 404         for(;;){
 405                 mprand(mpsignif(dom->n), genrandom, p->d);
 406                 if(mpcmp(p->d, mpzero) > 0 && mpcmp(p->d, dom->n) < 0)
 407                         break;
 408         }
 409         ecmul(dom, dom->G, p->d, p);
 410         return p;
 411 }
 412
 413 void
 414 ecdsasign(ECdomain *dom, ECpriv *priv, uchar *dig, int len, mpint *r, mpint *s)
 415 {
 416         ECpriv tmp;
 417         mpint *E, *t;
 418
 419         tmp.x = mpnew(0);
 420         tmp.y = mpnew(0);
 421         tmp.d = mpnew(0);
 422         E = betomp(dig, len, nil);
 423         t = mpnew(0);
 424         if(mpsignif(dom->n) < 8*len)
 425                 mpright(E, 8*len - mpsignif(dom->n), E);
 426         for(;;){
 427                 ecgen(dom, &tmp);
 428                 mpmod(tmp.x, dom->n, r);
 429                 if(mpcmp(r, mpzero) == 0)
 430                         continue;
 431                 mpmul(r, priv->d, s);
 432                 mpadd(E, s, s);
 433                 mpinvert(tmp.d, dom->n, t);
 434                 mpmul(s, t, s);
 435                 mpmod(s, dom->n, s);
 436                 if(mpcmp(s, mpzero) != 0)
 437                         break;
 438         }
 439         mpfree(t);
 440         mpfree(E);
 441         mpfree(tmp.x);
 442         mpfree(tmp.y);
 443         mpfree(tmp.d);
 444 }
 445
 446 int
 447 ecdsaverify(ECdomain *dom, ECpub *pub, uchar *dig, int len, mpint *r, mpint *s)
 448 {
 449         mpint *E, *t, *u1, *u2;
 450         ECpoint R, S;
 451         int ret;
 452
 453         if(mpcmp(r, mpone) < 0 || mpcmp(s, mpone) < 0 || mpcmp(r, dom->n) >= 0 || mpcmp(r, dom->n) >= 0)
 454                 return 0;
 455         E = betomp(dig, len, nil);
 456         if(mpsignif(dom->n) < 8*len)
 457                 mpright(E, 8*len - mpsignif(dom->n), E);
 458         t = mpnew(0);
 459         u1 = mpnew(0);
 460         u2 = mpnew(0);
 461         R.x = mpnew(0);
 462         R.y = mpnew(0);
 463         S.x = mpnew(0);
 464         S.y = mpnew(0);
 465         mpinvert(s, dom->n, t);
 466         mpmul(E, t, u1);
 467         mpmod(u1, dom->n, u1);
 468         mpmul(r, t, u2);
 469         mpmod(u2, dom->n, u2);
 470         ecmul(dom, dom->G, u1, &R);
 471         ecmul(dom, pub, u2, &S);
 472         ecadd(dom, &R, &S, &R);
 473         ret = 0;
 474         if(!R.inf){
 475                 mpmod(R.x, dom->n, t);
 476                 ret = mpcmp(r, t) == 0;
 477         }
 478         mpfree(t);
 479         mpfree(u1);
 480         mpfree(u2);
 481         mpfree(R.x);
 482         mpfree(R.y);
 483         mpfree(S.x);
 484         mpfree(S.y);
 485         return ret;
 486 }
 487
 488 static char *code = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
 489
 490 void
 491 base58enc(uchar *src, char *dst, int len)
 492 {
 493         mpint *n, *r, *b;
 494         char *sdst, t;
 495
 496         sdst = dst;
 497         n = betomp(src, len, nil);
 498         b = uitomp(58, nil);
 499         r = mpnew(0);
 500         while(mpcmp(n, mpzero) != 0){
 501                 mpdiv(n, b, n, r);
 502                 *dst++ = code[mptoui(r)];
 503         }
 504         for(; *src == 0; src++)
 505                 *dst++ = code[0];
 506         dst--;
 507         while(dst > sdst){
 508                 t = *sdst;
 509                 *sdst++ = *dst;
 510                 *dst-- = t;
 511         }
 512 }
 513
 514 int
 515 base58dec(char *src, uchar *dst, int len)
 516 {
 517         mpint *n, *b, *r;
 518         char *t;
 519         int l;
 520
 521         n = mpnew(0);
 522         r = mpnew(0);
 523         b = uitomp(58, nil);
 524         for(; *src; src++){
 525                 t = strchr(code, *src);
 526                 if(t == nil){
 527                         mpfree(n);
 528                         mpfree(r);
 529                         mpfree(b);
 530                         werrstr("invalid base58 char");
 531                         return -1;
 532                 }
 533                 uitomp(t - code, r);
 534                 mpmul(n, b, n);
 535                 mpadd(n, r, n);
 536         }
 537         memset(dst, 0, len);
 538         l = (mpsignif(n) + 7) / 8;
 539         mptobe(n, dst + (len - l), l, nil);
 540         mpfree(n);
 541         mpfree(r);
 542         mpfree(b);
 543         return 0;
 544 }