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

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