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

   1 /* -*-c-*-
   2  *
   3  * $Id: ec-bin.c,v 1.9 2004/04/08 01:36:15 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 /*----- Header files ------------------------------------------------------*/
  31
  32 #include <mLib/sub.h>
  33
  34 #include "ec.h"
  35
  36 /*----- Data structures ---------------------------------------------------*/
  37
  38 typedef struct ecctx {
  39   ec_curve c;
  40   mp *bb;
  41 } ecctx;
  42
  43 /*----- Main code ---------------------------------------------------------*/
  44
  45 static const ec_ops ec_binops, ec_binprojops;
  46
  47 static ec *ecneg(ec_curve *c, ec *d, const ec *p)
  48 {
  49   EC_COPY(d, p);
  50   if (d->x)
  51     d->y = F_ADD(c->f, d->y, d->y, d->x);
  52   return (d);
  53 }
  54
  55 static ec *ecprojneg(ec_curve *c, ec *d, const ec *p)
  56 {
  57   EC_COPY(d, p);
  58   if (d->x) {
  59     mp *t = F_MUL(c->f, MP_NEW, d->x, d->z);
  60     d->y = F_ADD(c->f, d->y, d->y, t);
  61     MP_DROP(t);
  62   }
  63   return (d);
  64 }
  65
  66 static ec *ecfind(ec_curve *c, ec *d, mp *x)
  67 {
  68   field *f = c->f;
  69   mp *y, *u, *v;
  70
  71   if (F_ZEROP(f, x))
  72     y = F_SQRT(f, MP_NEW, c->b);
  73   else {
  74     u = F_SQR(f, MP_NEW, x);            /* %$x^2$% */
  75     y = F_MUL(f, MP_NEW, u, c->a);      /* %$a x^2$% */
  76     y = F_ADD(f, y, y, c->b);           /* %$a x^2 + b$% */
  77     v = F_MUL(f, MP_NEW, u, x);         /* %$x^3$% */
  78     y = F_ADD(f, y, y, v);              /* %$A = x^3 + a x^2 + b$% */
  79     if (!F_ZEROP(f, y)) {
  80       u = F_INV(f, u, u);               /* %$x^{-2}$% */
  81       v = F_MUL(f, v, u, y);        /* %$B = A x^{-2} = x + a + b x^{-2}$% */
  82       y = F_QUADSOLVE(f, y, v);         /* %$z^2 + z = B$% */
  83       if (y) y = F_MUL(f, y, y, x);     /* %$y = z x$% */
  84     }
  85     MP_DROP(u);
  86     MP_DROP(v);
  87   }
  88   if (!y) return (0);
  89   EC_DESTROY(d);
  90   d->x = MP_COPY(x);
  91   d->y = y;
  92   d->z = MP_COPY(f->one);
  93   return (d);
  94 }
  95
  96 static ec *ecdbl(ec_curve *c, ec *d, const ec *a)
  97 {
  98   if (EC_ATINF(a) || F_ZEROP(c->f, a->x))
  99     EC_SETINF(d);
 100   else {
 101     field *f = c->f;
 102     mp *lambda;
 103     mp *dx, *dy;
 104
 105     dx = F_INV(f, MP_NEW, a->x);        /* %$x^{-1}$% */
 106     dy = F_MUL(f, MP_NEW, dx, a->y);    /* %$y/x$% */
 107     lambda = F_ADD(f, dy, dy, a->x);    /* %$\lambda = x + y/x$% */
 108
 109     dx = F_SQR(f, dx, lambda);          /* %$\lambda^2$% */
 110     dx = F_ADD(f, dx, dx, lambda);      /* %$\lambda^2 + \lambda$% */
 111     dx = F_ADD(f, dx, dx, c->a);       /* %$x' = a + \lambda^2 + \lambda$% */
 112
 113     dy = F_ADD(f, MP_NEW, a->x, dx);    /* %$ x + x' $% */
 114     dy = F_MUL(f, dy, dy, lambda);      /* %$ (x + x') \lambda$% */
 115     dy = F_ADD(f, dy, dy, a->y);        /* %$ (x + x') \lambda + y$% */
 116     dy = F_ADD(f, dy, dy, dx);      /* %$ y' = (x + x') \lambda + y + x'$% */
 117
 118     EC_DESTROY(d);
 119     d->x = dx;
 120     d->y = dy;
 121     d->z = 0;
 122     MP_DROP(lambda);
 123   }
 124   return (d);
 125 }
 126
 127 static ec *ecprojdbl(ec_curve *c, ec *d, const ec *a)
 128 {
 129   if (EC_ATINF(a) || F_ZEROP(c->f, a->x))
 130     EC_SETINF(d);
 131   else {
 132     field *f = c->f;
 133     ecctx *cc = (ecctx *)c;
 134     mp *dx, *dy, *dz, *u, *v;
 135
 136     dy = F_SQR(f, MP_NEW, a->z);        /* %$z^2$% */
 137     dx = F_MUL(f, MP_NEW, dy, cc->bb);  /* %$c z^2$% */
 138     dx = F_ADD(f, dx, dx, a->x);        /* %$x + c z^2$% */
 139     dz = F_SQR(f, MP_NEW, dx);          /* %$(x + c z^2)^2$% */
 140     dx = F_SQR(f, dx, dz);              /* %$x' = (x + c z^2)^4$% */
 141
 142     dz = F_MUL(f, dz, dy, a->x);        /* %$z' = x z^2$% */
 143
 144     dy = F_SQR(f, dy, a->x);            /* %$x^2$% */
 145     u = F_MUL(f, MP_NEW, a->y, a->z);   /* %$y z$% */
 146     u = F_ADD(f, u, u, dz);             /* %$z' + y z$% */
 147     u = F_ADD(f, u, u, dy);             /* %$u = z' + x^2 + y z$% */
 148
 149     v = F_SQR(f, MP_NEW, dy);           /* %$x^4$% */
 150     dy = F_MUL(f, dy, v, dz);           /* %$x^4 z'$% */
 151     v = F_MUL(f, v, u, dx);             /* %$u x'$% */
 152     dy = F_ADD(f, dy, dy, v);           /* %$y' = x^4 z' + u x'$% */
 153
 154     EC_DESTROY(d);
 155     d->x = dx;
 156     d->y = dy;
 157     d->z = dz;
 158     MP_DROP(u);
 159     MP_DROP(v);
 160   }
 161   return (d);
 162 }
 163
 164 static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b)
 165 {
 166   if (a == b)
 167     ecdbl(c, d, a);
 168   else if (EC_ATINF(a))
 169     EC_COPY(d, b);
 170   else if (EC_ATINF(b))
 171     EC_COPY(d, a);
 172   else {
 173     field *f = c->f;
 174     mp *lambda;
 175     mp *dx, *dy;
 176
 177     if (!MP_EQ(a->x, b->x)) {
 178       dx = F_ADD(f, MP_NEW, a->x, b->x); /* %$x_0 + x_1$% */
 179       dy = F_INV(f, MP_NEW, dx);        /* %$(x_0 + x_1)^{-1}$% */
 180       dx = F_ADD(f, dx, a->y, b->y);    /* %$y_0 + y_1$% */
 181       lambda = F_MUL(f, MP_NEW, dy, dx);
 182                                   /* %$\lambda = (y_0 + y_1)/(x_0 + x_1)$% */
 183
 184       dx = F_SQR(f, dx, lambda);        /* %$\lambda^2$% */
 185       dx = F_ADD(f, dx, dx, lambda);    /* %$\lambda^2 + \lambda$% */
 186       dx = F_ADD(f, dx, dx, c->a);      /* %$a + \lambda^2 + \lambda$% */
 187       dx = F_ADD(f, dx, dx, a->x);    /* %$a + \lambda^2 + \lambda + x_0$% */
 188       dx = F_ADD(f, dx, dx, b->x);
 189                            /* %$x' = a + \lambda^2 + \lambda + x_0 + x_1$% */
 190     } else if (!MP_EQ(a->y, b->y) || F_ZEROP(f, a->x)) {
 191       EC_SETINF(d);
 192       return (d);
 193     } else {
 194       dx = F_INV(f, MP_NEW, a->x);      /* %$x^{-1}$% */
 195       dy = F_MUL(f, MP_NEW, dx, a->y);  /* %$y/x$% */
 196       lambda = F_ADD(f, dy, dy, a->x);  /* %$\lambda = x + y/x$% */
 197
 198       dx = F_SQR(f, dx, lambda);        /* %$\lambda^2$% */
 199       dx = F_ADD(f, dx, dx, lambda);    /* %$\lambda^2 + \lambda$% */
 200       dx = F_ADD(f, dx, dx, c->a);    /* %$x' = a + \lambda^2 + \lambda$% */
 201       dy = MP_NEW;
 202     }
 203
 204     dy = F_ADD(f, dy, a->x, dx);        /* %$ x + x' $% */
 205     dy = F_MUL(f, dy, dy, lambda);      /* %$ (x + x') \lambda$% */
 206     dy = F_ADD(f, dy, dy, a->y);        /* %$ (x + x') \lambda + y$% */
 207     dy = F_ADD(f, dy, dy, dx);      /* %$ y' = (x + x') \lambda + y + x'$% */
 208
 209     EC_DESTROY(d);
 210     d->x = dx;
 211     d->y = dy;
 212     d->z = 0;
 213     MP_DROP(lambda);
 214   }
 215   return (d);
 216 }
 217
 218 static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b)
 219 {
 220   if (a == b)
 221     c->ops->dbl(c, d, a);
 222   else if (EC_ATINF(a))
 223     EC_COPY(d, b);
 224   else if (EC_ATINF(b))
 225     EC_COPY(d, a);
 226   else {
 227     field *f = c->f;
 228     mp *dx, *dy, *dz, *u, *uu, *v, *t, *s, *ss, *r, *w, *l;
 229
 230     dz = F_SQR(f, MP_NEW, b->z);        /* %$z_1^2$% */
 231     u = F_MUL(f, MP_NEW, dz, a->x);     /* %$u_0 = x_0 z_1^2$% */
 232     t = F_MUL(f, MP_NEW, dz, b->z);     /* %$z_1^3$% */
 233     s = F_MUL(f, MP_NEW, t, a->y);      /* %$s_0 = y_0 z_1^3$% */
 234
 235     dz = F_SQR(f, dz, a->z);            /* %$z_0^2$% */
 236     uu = F_MUL(f, MP_NEW, dz, b->x);    /* %$u_1 = x_1 z_0^2$% */
 237     t = F_MUL(f, t, dz, a->z);          /* %$z_0^3$% */
 238     ss = F_MUL(f, MP_NEW, t, b->y);     /* %$s_1 = y_1 z_0^3$% */
 239
 240     w = F_ADD(f, u, u, uu);             /* %$r = u_0 + u_1$% */
 241     r = F_ADD(f, s, s, ss);             /* %$w = s_0 + s_1$% */
 242     if (F_ZEROP(f, w)) {
 243       MP_DROP(w);
 244       MP_DROP(uu);
 245       MP_DROP(ss);
 246       MP_DROP(t);
 247       MP_DROP(dz);
 248       if (F_ZEROP(f, r)) {
 249         MP_DROP(r);
 250         return (c->ops->dbl(c, d, a));
 251       } else {
 252         MP_DROP(r);
 253         EC_SETINF(d);
 254         return (d);
 255       }
 256     }
 257
 258     l = F_MUL(f, t, a->z, w);           /* %$l = z_0 w$% */
 259
 260     dz = F_MUL(f, dz, l, b->z);         /* %$z' = l z_1$% */
 261
 262     ss = F_MUL(f, ss, r, b->x);         /* %$r x_1$% */
 263     t = F_MUL(f, uu, l, b->y);          /* %$l y_1$% */
 264     v = F_ADD(f, ss, ss, t);            /* %$v = r x_1 + l y_1$% */
 265
 266     t = F_ADD(f, t, r, dz);             /* %$t = r + z'$% */
 267
 268     uu = F_SQR(f, MP_NEW, dz);          /* %$z'^2$% */
 269     dx = F_MUL(f, MP_NEW, uu, c->a);    /* %$a z'^2$% */
 270     uu = F_MUL(f, uu, t, r);            /* %$t r$% */
 271     dx = F_ADD(f, dx, dx, uu);          /* %$a z'^2 + t r$% */
 272     r = F_SQR(f, r, w);                 /* %$w^2$% */
 273     uu = F_MUL(f, uu, r, w);            /* %$w^3$% */
 274     dx = F_ADD(f, dx, dx, uu);          /* %$x' = a z'^2 + t r + w^3$% */
 275
 276     r = F_SQR(f, r, l);                 /* %$l^2$% */
 277     dy = F_MUL(f, uu, v, r);            /* %$v l^2$% */
 278     l = F_MUL(f, l, t, dx);             /* %$t x'$% */
 279     dy = F_ADD(f, dy, dy, l);           /* %$y' = t x' + v l^2$% */
 280
 281     EC_DESTROY(d);
 282     d->x = dx;
 283     d->y = dy;
 284     d->z = dz;
 285     MP_DROP(l);
 286     MP_DROP(r);
 287     MP_DROP(w);
 288     MP_DROP(t);
 289     MP_DROP(v);
 290   }
 291   return (d);
 292 }
 293
 294 static int eccheck(ec_curve *c, const ec *p)
 295 {
 296   field *f = c->f;
 297   int rc;
 298   mp *u, *v;
 299
 300   if (EC_ATINF(p)) return (0);
 301   v = F_SQR(f, MP_NEW, p->x);
 302   u = F_MUL(f, MP_NEW, v, p->x);
 303   v = F_MUL(f, v, v, c->a);
 304   u = F_ADD(f, u, u, v);
 305   u = F_ADD(f, u, u, c->b);
 306   v = F_MUL(f, v, p->x, p->y);
 307   u = F_ADD(f, u, u, v);
 308   v = F_SQR(f, v, p->y);
 309   u = F_ADD(f, u, u, v);
 310   rc = F_ZEROP(f, u) ? 0 : -1;
 311   mp_drop(u);
 312   mp_drop(v);
 313   return (rc);
 314 }
 315
 316 static int ecprojcheck(ec_curve *c, const ec *p)
 317 {
 318   ec t = EC_INIT;
 319   int rc;
 320
 321   c->ops->fix(c, &t, p);
 322   rc = eccheck(c, &t);
 323   EC_DESTROY(&t);
 324   return (rc);
 325 }
 326
 327 static void ecdestroy(ec_curve *c)
 328 {
 329   ecctx *cc = (ecctx *)c;
 330   MP_DROP(cc->c.a);
 331   MP_DROP(cc->c.b);
 332   if (cc->bb) MP_DROP(cc->bb);
 333   DESTROY(cc);
 334 }
 335
 336 /* --- @ec_bin@, @ec_binproj@ --- *
 337  *
 338  * Arguments:   @field *f@ = the underlying field for this elliptic curve
 339  *              @mp *a, *b@ = the coefficients for this curve
 340  *
 341  * Returns:     A pointer to the curve, or null.
 342  *
 343  * Use:         Creates a curve structure for an elliptic curve defined over
 344  *              a binary field.  The @binproj@ variant uses projective
 345  *              coordinates, which can be a win.
 346  */
 347
 348 ec_curve *ec_bin(field *f, mp *a, mp *b)
 349 {
 350   ecctx *cc = CREATE(ecctx);
 351   cc->c.ops = &ec_binops;
 352   cc->c.f = f;
 353   cc->c.a = F_IN(f, MP_NEW, a);
 354   cc->c.b = F_IN(f, MP_NEW, b);
 355   cc->bb = 0;
 356   return (&cc->c);
 357 }
 358
 359 ec_curve *ec_binproj(field *f, mp *a, mp *b)
 360 {
 361   ecctx *cc = CREATE(ecctx);
 362   cc->c.ops = &ec_binprojops;
 363   cc->c.f = f;
 364   cc->c.a = F_IN(f, MP_NEW, a);
 365   cc->c.b = F_IN(f, MP_NEW, b);
 366   cc->bb = F_SQRT(f, MP_NEW, cc->c.b);
 367   if (cc->bb)
 368     cc->bb = F_SQRT(f, cc->bb, cc->bb);
 369   if (!cc->bb) {
 370     MP_DROP(cc->c.a);
 371     MP_DROP(cc->c.b);
 372     DESTROY(cc);
 373     return (0);
 374   }
 375   return (&cc->c);
 376 }
 377
 378 static const ec_ops ec_binops = {
 379   ecdestroy, ec_stdsamep, ec_idin, ec_idout, ec_idfix,
 380   ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
 381 };
 382
 383 static const ec_ops ec_binprojops = {
 384   ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
 385   ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
 386 };
 387
 388 /*----- Test rig ----------------------------------------------------------*/
 389
 390 #ifdef TEST_RIG
 391
 392 #define MP(x) mp_readstring(MP_NEW, #x, 0, 0)
 393
 394 int main(int argc, char *argv[])
 395 {
 396   field *f;
 397   ec_curve *c;
 398   ec g = EC_INIT, d = EC_INIT;
 399   mp *p, *a, *b, *r, *beta;
 400   int i, n = argc == 1 ? 1 : atoi(argv[1]);
 401
 402   printf("ec-bin: ");
 403   fflush(stdout);
 404   a = MP(0x7ffffffffffffffffffffffffffffffffffffffff);
 405   b = MP(0x6645f3cacf1638e139c6cd13ef61734fbc9e3d9fb);
 406   p = MP(0x800000000000000000000000000000000000000c9);
 407   beta = MP(0x715169c109c612e390d347c748342bcd3b02a0bef);
 408   r = MP(0x040000000000000000000292fe77e70c12a4234c32);
 409
 410   f = field_binnorm(p, beta);
 411   c = ec_binproj(f, a, b);
 412   g.x = MP(0x0311103c17167564ace77ccb09c681f886ba54ee8);
 413   g.y = MP(0x333ac13c6447f2e67613bf7009daf98c87bb50c7f);
 414
 415   for (i = 0; i < n; i++) {
 416     ec_mul(c, &d, &g, r);
 417     if (EC_ATINF(&d)) {
 418       fprintf(stderr, "zero too early\n");
 419       return (1);
 420     }
 421     ec_add(c, &d, &d, &g);
 422     if (!EC_ATINF(&d)) {
 423       fprintf(stderr, "didn't reach zero\n");
 424       MP_EPRINTX("d.x", d.x);
 425       MP_EPRINTX("d.y", d.y);
 426       return (1);
 427     }
 428     ec_destroy(&d);
 429   }
 430
 431   ec_destroy(&g);
 432   ec_destroycurve(c);
 433   F_DESTROY(f);
 434   MP_DROP(p); MP_DROP(a); MP_DROP(b); MP_DROP(r); MP_DROP(beta);
 435   assert(!mparena_count(&mparena_global));
 436   printf("ok\n");
 437   return (0);
 438 }
 439
 440 #endif
 441
 442 /*----- That's all, folks -------------------------------------------------*/