chiark - git - mdw - catacomb/blob - math/ec-bin.c

   1 /* -*-c-*-
   2  *
   3  * Arithmetic for elliptic curves over binary fields
   4  *
   5  * (c) 2004 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include <mLib/sub.h>
  31
  32 #include "ec.h"
  33 #include "ec-guts.h"
  34
  35 /*----- Main code ---------------------------------------------------------*/
  36
  37 static const ec_ops ec_binops, ec_binprojops;
  38
  39 static ec *ecneg(ec_curve *c, ec *d, const ec *p)
  40 {
  41   EC_COPY(d, p);
  42   if (d->x)
  43     d->y = F_ADD(c->f, d->y, d->y, d->x);
  44   return (d);
  45 }
  46
  47 static ec *ecprojneg(ec_curve *c, ec *d, const ec *p)
  48 {
  49   EC_COPY(d, p);
  50   if (d->x) {
  51     mp *t = F_MUL(c->f, MP_NEW, d->x, d->z);
  52     d->y = F_ADD(c->f, d->y, d->y, t);
  53     MP_DROP(t);
  54   }
  55   return (d);
  56 }
  57
  58 static ec *ecfind(ec_curve *c, ec *d, mp *x)
  59 {
  60   field *f = c->f;
  61   mp *y, *u, *v;
  62
  63   if (F_ZEROP(f, x))
  64     y = F_SQRT(f, MP_NEW, c->b);
  65   else {
  66     u = F_SQR(f, MP_NEW, x);            /* %$x^2$% */
  67     y = F_MUL(f, MP_NEW, u, c->a);      /* %$a x^2$% */
  68     y = F_ADD(f, y, y, c->b);           /* %$a x^2 + b$% */
  69     v = F_MUL(f, MP_NEW, u, x);         /* %$x^3$% */
  70     y = F_ADD(f, y, y, v);              /* %$A = x^3 + a x^2 + b$% */
  71     if (!F_ZEROP(f, y)) {
  72       u = F_INV(f, u, u);               /* %$x^{-2}$% */
  73       v = F_MUL(f, v, u, y);        /* %$B = A x^{-2} = x + a + b x^{-2}$% */
  74       y = F_QUADSOLVE(f, y, v);         /* %$z^2 + z = B$% */
  75       if (y) y = F_MUL(f, y, y, x);     /* %$y = z x$% */
  76       /* Hence %$y^2 + x y = (z^2 + z) x^2 = A$% */
  77     }
  78     MP_DROP(u);
  79     MP_DROP(v);
  80   }
  81   if (!y) return (0);
  82   EC_DESTROY(d);
  83   d->x = MP_COPY(x);
  84   d->y = y;
  85   d->z = MP_COPY(f->one);
  86   return (d);
  87 }
  88
  89 static ec *ecdbl(ec_curve *c, ec *d, const ec *a)
  90 {
  91   if (EC_ATINF(a) || F_ZEROP(c->f, a->x))
  92     EC_SETINF(d);
  93   else {
  94     field *f = c->f;
  95     mp *lambda;
  96     mp *dx, *dy;
  97
  98     dx = F_INV(f, MP_NEW, a->x);        /* %$x^{-1}$% */
  99     dy = F_MUL(f, MP_NEW, dx, a->y);    /* %$y/x$% */
 100     lambda = F_ADD(f, dy, dy, a->x);    /* %$\lambda = x + y/x$% */
 101
 102     dx = F_SQR(f, dx, lambda);          /* %$\lambda^2$% */
 103     dx = F_ADD(f, dx, dx, lambda);      /* %$\lambda^2 + \lambda$% */
 104     dx = F_ADD(f, dx, dx, c->a);       /* %$x' = a + \lambda^2 + \lambda$% */
 105
 106     dy = F_ADD(f, MP_NEW, a->x, dx);    /* %$ x + x' $% */
 107     dy = F_MUL(f, dy, dy, lambda);      /* %$ (x + x') \lambda$% */
 108     dy = F_ADD(f, dy, dy, a->y);        /* %$ (x + x') \lambda + y$% */
 109     dy = F_ADD(f, dy, dy, dx);      /* %$ y' = (x + x') \lambda + y + x'$% */
 110
 111     EC_DESTROY(d);
 112     d->x = dx;
 113     d->y = dy;
 114     d->z = 0;
 115     MP_DROP(lambda);
 116   }
 117   return (d);
 118 }
 119
 120 static ec *ecprojdbl(ec_curve *c, ec *d, const ec *a)
 121 {
 122   if (EC_ATINF(a) || F_ZEROP(c->f, a->x))
 123     EC_SETINF(d);
 124   else {
 125     field *f = c->f;
 126     ecctx_bin *cc = (ecctx_bin *)c;
 127     mp *dx, *dy, *dz, *u, *v;
 128
 129     dy = F_SQR(f, MP_NEW, a->z);        /* %$z^2$% */
 130     dx = F_MUL(f, MP_NEW, dy, cc->bb);  /* %$c z^2$% */
 131     dx = F_ADD(f, dx, dx, a->x);        /* %$x + c z^2$% */
 132     dz = F_SQR(f, MP_NEW, dx);          /* %$(x + c z^2)^2$% */
 133     dx = F_SQR(f, dx, dz);              /* %$x' = (x + c z^2)^4$% */
 134
 135     dz = F_MUL(f, dz, dy, a->x);        /* %$z' = x z^2$% */
 136
 137     dy = F_SQR(f, dy, a->x);            /* %$x^2$% */
 138     u = F_MUL(f, MP_NEW, a->y, a->z);   /* %$y z$% */
 139     u = F_ADD(f, u, u, dz);             /* %$z' + y z$% */
 140     u = F_ADD(f, u, u, dy);             /* %$u = z' + x^2 + y z$% */
 141
 142     v = F_SQR(f, MP_NEW, dy);           /* %$x^4$% */
 143     dy = F_MUL(f, dy, v, dz);           /* %$x^4 z'$% */
 144     v = F_MUL(f, v, u, dx);             /* %$u x'$% */
 145     dy = F_ADD(f, dy, dy, v);           /* %$y' = x^4 z' + u x'$% */
 146
 147     EC_DESTROY(d);
 148     d->x = dx;
 149     d->y = dy;
 150     d->z = dz;
 151     MP_DROP(u);
 152     MP_DROP(v);
 153   }
 154   return (d);
 155 }
 156
 157 static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b)
 158 {
 159   if (a == b)
 160     ecdbl(c, d, a);
 161   else if (EC_ATINF(a))
 162     EC_COPY(d, b);
 163   else if (EC_ATINF(b))
 164     EC_COPY(d, a);
 165   else {
 166     field *f = c->f;
 167     mp *lambda;
 168     mp *dx, *dy;
 169
 170     if (!MP_EQ(a->x, b->x)) {
 171       dx = F_ADD(f, MP_NEW, a->x, b->x); /* %$x_0 + x_1$% */
 172       dy = F_INV(f, MP_NEW, dx);        /* %$(x_0 + x_1)^{-1}$% */
 173       dx = F_ADD(f, dx, a->y, b->y);    /* %$y_0 + y_1$% */
 174       lambda = F_MUL(f, MP_NEW, dy, dx);
 175                                   /* %$\lambda = (y_0 + y_1)/(x_0 + x_1)$% */
 176
 177       dx = F_SQR(f, dx, lambda);        /* %$\lambda^2$% */
 178       dx = F_ADD(f, dx, dx, lambda);    /* %$\lambda^2 + \lambda$% */
 179       dx = F_ADD(f, dx, dx, c->a);      /* %$a + \lambda^2 + \lambda$% */
 180       dx = F_ADD(f, dx, dx, a->x);    /* %$a + \lambda^2 + \lambda + x_0$% */
 181       dx = F_ADD(f, dx, dx, b->x);
 182                            /* %$x' = a + \lambda^2 + \lambda + x_0 + x_1$% */
 183     } else if (!MP_EQ(a->y, b->y) || F_ZEROP(f, a->x)) {
 184       EC_SETINF(d);
 185       return (d);
 186     } else {
 187       dx = F_INV(f, MP_NEW, a->x);      /* %$x^{-1}$% */
 188       dy = F_MUL(f, MP_NEW, dx, a->y);  /* %$y/x$% */
 189       lambda = F_ADD(f, dy, dy, a->x);  /* %$\lambda = x + y/x$% */
 190
 191       dx = F_SQR(f, dx, lambda);        /* %$\lambda^2$% */
 192       dx = F_ADD(f, dx, dx, lambda);    /* %$\lambda^2 + \lambda$% */
 193       dx = F_ADD(f, dx, dx, c->a);    /* %$x' = a + \lambda^2 + \lambda$% */
 194       dy = MP_NEW;
 195     }
 196
 197     dy = F_ADD(f, dy, a->x, dx);        /* %$ x + x' $% */
 198     dy = F_MUL(f, dy, dy, lambda);      /* %$ (x + x') \lambda$% */
 199     dy = F_ADD(f, dy, dy, a->y);        /* %$ (x + x') \lambda + y$% */
 200     dy = F_ADD(f, dy, dy, dx);      /* %$ y' = (x + x') \lambda + y + x'$% */
 201
 202     EC_DESTROY(d);
 203     d->x = dx;
 204     d->y = dy;
 205     d->z = 0;
 206     MP_DROP(lambda);
 207   }
 208   return (d);
 209 }
 210
 211 static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b)
 212 {
 213   if (a == b)
 214     c->ops->dbl(c, d, a);
 215   else if (EC_ATINF(a))
 216     EC_COPY(d, b);
 217   else if (EC_ATINF(b))
 218     EC_COPY(d, a);
 219   else {
 220     field *f = c->f;
 221     mp *dx, *dy, *dz, *u, *uu, *v, *t, *s, *ss, *r, *w, *l;
 222
 223     dz = F_SQR(f, MP_NEW, b->z);        /* %$z_1^2$% */
 224     u = F_MUL(f, MP_NEW, dz, a->x);     /* %$u_0 = x_0 z_1^2$% */
 225     t = F_MUL(f, MP_NEW, dz, b->z);     /* %$z_1^3$% */
 226     s = F_MUL(f, MP_NEW, t, a->y);      /* %$s_0 = y_0 z_1^3$% */
 227
 228     dz = F_SQR(f, dz, a->z);            /* %$z_0^2$% */
 229     uu = F_MUL(f, MP_NEW, dz, b->x);    /* %$u_1 = x_1 z_0^2$% */
 230     t = F_MUL(f, t, dz, a->z);          /* %$z_0^3$% */
 231     ss = F_MUL(f, MP_NEW, t, b->y);     /* %$s_1 = y_1 z_0^3$% */
 232
 233     w = F_ADD(f, u, u, uu);             /* %$r = u_0 + u_1$% */
 234     r = F_ADD(f, s, s, ss);             /* %$w = s_0 + s_1$% */
 235     if (F_ZEROP(f, w)) {
 236       MP_DROP(w);
 237       MP_DROP(uu);
 238       MP_DROP(ss);
 239       MP_DROP(t);
 240       MP_DROP(dz);
 241       if (F_ZEROP(f, r)) {
 242         MP_DROP(r);
 243         return (c->ops->dbl(c, d, a));
 244       } else {
 245         MP_DROP(r);
 246         EC_SETINF(d);
 247         return (d);
 248       }
 249     }
 250
 251     l = F_MUL(f, t, a->z, w);           /* %$l = z_0 w$% */
 252
 253     dz = F_MUL(f, dz, l, b->z);         /* %$z' = l z_1$% */
 254
 255     ss = F_MUL(f, ss, r, b->x);         /* %$r x_1$% */
 256     t = F_MUL(f, uu, l, b->y);          /* %$l y_1$% */
 257     v = F_ADD(f, ss, ss, t);            /* %$v = r x_1 + l y_1$% */
 258
 259     t = F_ADD(f, t, r, dz);             /* %$t = r + z'$% */
 260
 261     uu = F_SQR(f, MP_NEW, dz);          /* %$z'^2$% */
 262     dx = F_MUL(f, MP_NEW, uu, c->a);    /* %$a z'^2$% */
 263     uu = F_MUL(f, uu, t, r);            /* %$t r$% */
 264     dx = F_ADD(f, dx, dx, uu);          /* %$a z'^2 + t r$% */
 265     r = F_SQR(f, r, w);                 /* %$w^2$% */
 266     uu = F_MUL(f, uu, r, w);            /* %$w^3$% */
 267     dx = F_ADD(f, dx, dx, uu);          /* %$x' = a z'^2 + t r + w^3$% */
 268
 269     r = F_SQR(f, r, l);                 /* %$l^2$% */
 270     dy = F_MUL(f, uu, v, r);            /* %$v l^2$% */
 271     l = F_MUL(f, l, t, dx);             /* %$t x'$% */
 272     dy = F_ADD(f, dy, dy, l);           /* %$y' = t x' + v l^2$% */
 273
 274     EC_DESTROY(d);
 275     d->x = dx;
 276     d->y = dy;
 277     d->z = dz;
 278     MP_DROP(l);
 279     MP_DROP(r);
 280     MP_DROP(w);
 281     MP_DROP(t);
 282     MP_DROP(v);
 283   }
 284   return (d);
 285 }
 286
 287 static int eccheck(ec_curve *c, const ec *p)
 288 {
 289   field *f = c->f;
 290   int rc;
 291   mp *u, *v;
 292
 293   if (EC_ATINF(p)) return (0);
 294   v = F_SQR(f, MP_NEW, p->x);
 295   u = F_MUL(f, MP_NEW, v, p->x);
 296   v = F_MUL(f, v, v, c->a);
 297   u = F_ADD(f, u, u, v);
 298   u = F_ADD(f, u, u, c->b);
 299   v = F_MUL(f, v, p->x, p->y);
 300   u = F_ADD(f, u, u, v);
 301   v = F_SQR(f, v, p->y);
 302   u = F_ADD(f, u, u, v);
 303   rc = F_ZEROP(f, u) ? 0 : -1;
 304   mp_drop(u);
 305   mp_drop(v);
 306   return (rc);
 307 }
 308
 309 static int ecprojcheck(ec_curve *c, const ec *p)
 310 {
 311   ec t = EC_INIT;
 312   int rc;
 313
 314   c->ops->fix(c, &t, p);
 315   rc = eccheck(c, &t);
 316   EC_DESTROY(&t);
 317   return (rc);
 318 }
 319
 320 static int eccompr(ec_curve *c, const ec *p)
 321 {
 322   /* --- Take the LSB of %$y/x$%, or zero if %$x = 0$% ---
 323    *
 324    * The negative of a point has %$y' = y + x$%.  Therefore either %$y/x$% or
 325    * $%(y + x)/x = y/x + 1$% is odd, and this disambiguates, unless %$x =
 326    * 0$%; but in that case we must have %$y^2 = b$% which has exactly one
 327    * solution (because squaring is linear in a binary field).
 328    */
 329
 330   int ybit;
 331   field *f = c->f;
 332   mp *y, *t;
 333   if (MP_ZEROP(p->x)) ybit = 0;
 334   else {
 335     t = F_IN(f, MP_NEW, p->x);
 336     y = F_IN(f, MP_NEW, p->y);
 337     t = F_INV(f, t, t);
 338     t = F_MUL(f, t, y, t);
 339     t = F_OUT(f, t, t);
 340     ybit = MP_ODDP(t);
 341     MP_DROP(y); MP_DROP(t);
 342   }
 343   return (ybit);
 344 }
 345
 346 static void ecdestroy(ec_curve *c)
 347 {
 348   ecctx_bin *cc = (ecctx_bin *)c;
 349   MP_DROP(cc->c.a);
 350   MP_DROP(cc->c.b);
 351   if (cc->bb) MP_DROP(cc->bb);
 352   DESTROY(cc);
 353 }
 354
 355 /* --- @ec_bin@, @ec_binproj@ --- *
 356  *
 357  * Arguments:   @field *f@ = the underlying field for this elliptic curve
 358  *              @mp *a, *b@ = the coefficients for this curve
 359  *
 360  * Returns:     A pointer to the curve, or null.
 361  *
 362  * Use:         Creates a curve structure for an elliptic curve defined over
 363  *              a binary field.  The @binproj@ variant uses projective
 364  *              coordinates, which can be a win.
 365  */
 366
 367 ec_curve *ec_bin(field *f, mp *a, mp *b)
 368 {
 369   ecctx_bin *cc = CREATE(ecctx_bin);
 370   cc->c.ops = &ec_binops;
 371   cc->c.f = f;
 372   cc->c.a = F_IN(f, MP_NEW, a);
 373   cc->c.b = F_IN(f, MP_NEW, b);
 374   cc->bb = 0;
 375   return (&cc->c);
 376 }
 377
 378 ec_curve *ec_binproj(field *f, mp *a, mp *b)
 379 {
 380   ecctx_bin *cc = CREATE(ecctx_bin);
 381   int i;
 382   mp *c, *d;
 383
 384   cc->c.ops = &ec_binprojops;
 385   cc->c.f = f;
 386   cc->c.a = F_IN(f, MP_NEW, a);
 387   cc->c.b = F_IN(f, MP_NEW, b);
 388
 389   c = MP_COPY(cc->c.b);
 390   for (i = 0; i < f->nbits - 2; i++)
 391     c = F_SQR(f, c, c);
 392   d = F_SQR(f, MP_NEW, c); d = F_SQR(f, d, d);
 393   if (!MP_EQ(d, cc->c.b)) {
 394     MP_DROP(c);
 395     MP_DROP(d);
 396     MP_DROP(cc->c.a);
 397     MP_DROP(cc->c.b);
 398     DESTROY(cc);
 399     return (0);
 400   }
 401   cc->bb = c;
 402   MP_DROP(d);
 403   return (&cc->c);
 404 }
 405
 406 static const ec_ops ec_binops = {
 407   "bin",
 408   ecdestroy, ec_stdsamep, ec_idin, ec_idout, ec_idfix,
 409   ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck, eccompr
 410 };
 411
 412 static const ec_ops ec_binprojops = {
 413   "binproj",
 414   ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
 415   ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck, eccompr
 416 };
 417
 418 /*----- Test rig ----------------------------------------------------------*/
 419
 420 #ifdef TEST_RIG
 421
 422 #define MP(x) mp_readstring(MP_NEW, #x, 0, 0)
 423
 424 int main(int argc, char *argv[])
 425 {
 426   field *f;
 427   ec_curve *c;
 428   ec g = EC_INIT, d = EC_INIT;
 429   mp *p, *a, *b, *r, *beta;
 430   int i, n = argc == 1 ? 1 : atoi(argv[1]);
 431
 432   printf("ec-bin: ");
 433   fflush(stdout);
 434   a = MP(0x7ffffffffffffffffffffffffffffffffffffffff);
 435   b = MP(0x6645f3cacf1638e139c6cd13ef61734fbc9e3d9fb);
 436   p = MP(0x800000000000000000000000000000000000000c9);
 437   beta = MP(0x715169c109c612e390d347c748342bcd3b02a0bef);
 438   r = MP(0x040000000000000000000292fe77e70c12a4234c32);
 439
 440   f = field_binnorm(p, beta);
 441   c = ec_binproj(f, a, b);
 442   g.x = MP(0x0311103c17167564ace77ccb09c681f886ba54ee8);
 443   g.y = MP(0x333ac13c6447f2e67613bf7009daf98c87bb50c7f);
 444
 445   for (i = 0; i < n; i++) {
 446     ec_mul(c, &d, &g, r);
 447     if (EC_ATINF(&d)) {
 448       fprintf(stderr, "zero too early\n");
 449       return (1);
 450     }
 451     ec_add(c, &d, &d, &g);
 452     if (!EC_ATINF(&d)) {
 453       fprintf(stderr, "didn't reach zero\n");
 454       MP_EPRINTX("d.x", d.x);
 455       MP_EPRINTX("d.y", d.y);
 456       return (1);
 457     }
 458     ec_destroy(&d);
 459   }
 460
 461   ec_destroy(&g);
 462   ec_destroycurve(c);
 463   F_DESTROY(f);
 464   MP_DROP(p); MP_DROP(a); MP_DROP(b); MP_DROP(r); MP_DROP(beta);
 465   assert(!mparena_count(&mparena_global));
 466   printf("ok\n");
 467   return (0);
 468 }
 469
 470 #endif
 471
 472 /*----- That's all, folks -------------------------------------------------*/