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

   1 /* -*-c-*-
   2  *
   3  * $Id: ec.c,v 1.7 2004/03/27 17:54:11 mdw Exp $
   4  *
   5  * Elliptic curve definitions
   6  *
   7  * (c) 2001 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.c,v $
  33  * Revision 1.7  2004/03/27 17:54:11  mdw
  34  * Standard curves and curve checking.
  35  *
  36  * Revision 1.6  2004/03/23 15:19:32  mdw
  37  * Test elliptic curves more thoroughly.
  38  *
  39  * Revision 1.5  2004/03/21 22:52:06  mdw
  40  * Merge and close elliptic curve branch.
  41  *
  42  * Revision 1.4.4.2  2004/03/20 00:13:31  mdw
  43  * Projective coordinates for prime curves
  44  *
  45  * Revision 1.4.4.1  2003/06/10 13:43:53  mdw
  46  * Simple (non-projective) curves over prime fields now seem to work.
  47  *
  48  * Revision 1.4  2003/05/15 23:25:59  mdw
  49  * Make elliptic curve stuff build.
  50  *
  51  * Revision 1.3  2002/01/13 13:48:44  mdw
  52  * Further progress.
  53  *
  54  * Revision 1.2  2001/05/07 17:29:44  mdw
  55  * Treat projective coordinates as an internal representation.  Various
  56  * minor interface changes.
  57  *
  58  * Revision 1.1  2001/04/29 18:12:33  mdw
  59  * Prototype version.
  60  *
  61  */
  62
  63 /*----- Header files ------------------------------------------------------*/
  64
  65 #include "ec.h"
  66 #include "ec-exp.h"
  67
  68 /*----- Trivial wrappers --------------------------------------------------*/
  69
  70 /* --- @ec_create@ --- *
  71  *
  72  * Arguments:   @ec *p@ = pointer to an elliptic-curve point
  73  *
  74  * Returns:     The argument @p@.
  75  *
  76  * Use:         Initializes a new point.  The initial value is the additive
  77  *              identity (which is universal for all curves).
  78  */
  79
  80 ec *ec_create(ec *p) { EC_CREATE(p); return (p); }
  81
  82 /* --- @ec_destroy@ --- *
  83  *
  84  * Arguments:   @ec *p@ = pointer to an elliptic-curve point
  85  *
  86  * Returns:     ---
  87  *
  88  * Use:         Destroys a point, making it invalid.
  89  */
  90
  91 void ec_destroy(ec *p) { EC_DESTROY(p); }
  92
  93 /* --- @ec_atinf@ --- *
  94  *
  95  * Arguments:   @const ec *p@ = pointer to a point
  96  *
  97  * Returns:     Nonzero if %$p = O$% is the point at infinity, zero
  98  *              otherwise.
  99  */
 100
 101 int ec_atinf(const ec *p) { return (EC_ATINF(p)); }
 102
 103 /* --- @ec_setinf@ --- *
 104  *
 105  * Arguments:   @ec *p@ = pointer to a point
 106  *
 107  * Returns:     The argument @p@.
 108  *
 109  * Use:         Sets the given point to be the point %$O$% at infinity.
 110  */
 111
 112 ec *ec_setinf(ec *p) { EC_SETINF(p); return (p); }
 113
 114 /* --- @ec_copy@ --- *
 115  *
 116  * Arguments:   @ec *d@ = pointer to destination point
 117  *              @const ec *p@ = pointer to source point
 118  *
 119  * Returns:     The destination @d@.
 120  *
 121  * Use:         Creates a copy of an elliptic curve point.
 122  */
 123
 124 ec *ec_copy(ec *d, const ec *p) { EC_COPY(d, p); return (d); }
 125
 126 /* --- @ec_eq@ --- *
 127  *
 128  * Arguments:   @const ec *p, *q@ = two points
 129  *
 130  * Returns:     Nonzero if the points are equal.  Compares external-format
 131  *              points.
 132  */
 133
 134 int ec_eq(const ec *p, const ec *q) { return (EC_EQ(p, q)); }
 135
 136 /*----- Standard curve operations -----------------------------------------*/
 137
 138 /* --- @ec_idin@, @ec_idout@, @ec_idfix@ --- *
 139  *
 140  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 141  *              @ec *d@ = pointer to the destination
 142  *              @const ec *p@ = pointer to a source point
 143  *
 144  * Returns:     The destination @d@.
 145  *
 146  * Use:         An identity operation if your curve has no internal
 147  *              representation.  (The field internal representation is still
 148  *              used.)
 149  */
 150
 151 ec *ec_idin(ec_curve *c, ec *d, const ec *p)
 152 {
 153   if (EC_ATINF(p))
 154     EC_SETINF(d);
 155   else {
 156     field *f = c->f;
 157     d->x = F_IN(f, d->x, p->x);
 158     d->y = F_IN(f, d->y, p->y);
 159     mp_drop(d->z); d->z = 0;
 160   }
 161   return (d);
 162 }
 163
 164 ec *ec_idout(ec_curve *c, ec *d, const ec *p)
 165 {
 166   if (EC_ATINF(p))
 167     EC_SETINF(d);
 168   else {
 169     field *f = c->f;
 170     d->x = F_OUT(f, d->x, p->x);
 171     d->y = F_OUT(f, d->y, p->y);
 172     mp_drop(d->z); d->z = 0;
 173   }
 174   return (d);
 175 }
 176
 177 ec *ec_idfix(ec_curve *c, ec *d, const ec *p)
 178 {
 179   EC_COPY(d, p);
 180   return (d);
 181 }
 182
 183 /* --- @ec_projin@, @ec_projout@ --- *
 184  *
 185  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 186  *              @ec *d@ = pointer to the destination
 187  *              @const ec *p@ = pointer to a source point
 188  *
 189  * Returns:     The destination @d@.
 190  *
 191  * Use:         Conversion functions if your curve operations use a
 192  *              projective representation.
 193  */
 194
 195 ec *ec_projin(ec_curve *c, ec *d, const ec *p)
 196 {
 197   if (EC_ATINF(p))
 198     EC_SETINF(d);
 199   else {
 200     field *f = c->f;
 201     d->x = F_IN(f, d->x, p->x);
 202     d->y = F_IN(f, d->y, p->y);
 203     mp_drop(d->z); d->z = MP_COPY(f->one);
 204   }
 205   return (d);
 206 }
 207
 208 ec *ec_projout(ec_curve *c, ec *d, const ec *p)
 209 {
 210   if (EC_ATINF(p))
 211     EC_SETINF(d);
 212   else {
 213     mp *x, *y, *z, *zz;
 214     field *f = c->f;
 215     z = F_INV(f, MP_NEW, p->z);
 216     zz = F_SQR(f, MP_NEW, z);
 217     z = F_MUL(f, z, zz, z);
 218     x = F_MUL(f, d->x, p->x, zz);
 219     y = F_MUL(f, d->y, p->y, z);
 220     mp_drop(z);
 221     mp_drop(zz);
 222     mp_drop(d->z);
 223     d->x = F_OUT(f, x, x);
 224     d->y = F_OUT(f, y, y);
 225     d->z = 0;
 226   }
 227   return (d);
 228 }
 229
 230 ec *ec_projfix(ec_curve *c, ec *d, const ec *p)
 231 {
 232   if (EC_ATINF(p))
 233     EC_SETINF(d);
 234   else if (d->z == c->f->one)
 235     EC_COPY(d, p);
 236   else {
 237     mp *z, *zz;
 238     field *f = c->f;
 239     z = F_INV(f, MP_NEW, p->z);
 240     zz = F_SQR(f, MP_NEW, z);
 241     z = F_MUL(f, z, zz, z);
 242     d->x = F_MUL(f, d->x, p->x, zz);
 243     d->y = F_MUL(f, d->y, p->y, z);
 244     mp_drop(z);
 245     mp_drop(zz);
 246     mp_drop(d->z);
 247     d->z = MP_COPY(f->one);
 248   }
 249   return (d);
 250 }
 251
 252 /* --- @ec_stdsub@ --- *
 253  *
 254  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 255  *              @ec *d@ = pointer to the destination
 256  *              @const ec *p, *q@ = the operand points
 257  *
 258  * Returns:     The destination @d@.
 259  *
 260  * Use:         Standard point subtraction operation, in terms of negation
 261  *              and addition.  This isn't as efficient as a ready-made
 262  *              subtraction operator.
 263  */
 264
 265 ec *ec_stdsub(ec_curve *c, ec *d, const ec *p, const ec *q)
 266 {
 267   ec t = EC_INIT;
 268   EC_NEG(c, &t, q);
 269   EC_FIX(c, &t, &t);
 270   EC_ADD(c, d, p, &t);
 271   EC_DESTROY(&t);
 272   return (d);
 273 }
 274
 275 /*----- Creating curves ---------------------------------------------------*/
 276
 277 /* --- @ec_destroycurve@ --- *
 278  *
 279  * Arguments:   @ec_curve *c@ = pointer to an ellptic curve
 280  *
 281  * Returns:     ---
 282  *
 283  * Use:         Destroys a description of an elliptic curve.
 284  */
 285
 286 void ec_destroycurve(ec_curve *c) { c->ops->destroy(c); }
 287
 288 /*----- Real arithmetic ---------------------------------------------------*/
 289
 290 /* --- @ec_find@ --- *
 291  *
 292  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 293  *              @ec *d@ = pointer to the destination point
 294  *              @mp *x@ = a possible x-coordinate
 295  *
 296  * Returns:     Zero if OK, nonzero if there isn't a point there.
 297  *
 298  * Use:         Finds a point on an elliptic curve with a given x-coordinate.
 299  */
 300
 301 ec *ec_find(ec_curve *c, ec *d, mp *x)
 302 {
 303   x = F_IN(c->f, MP_NEW, x);
 304   if ((d = EC_FIND(c, d, x)) != 0)
 305     EC_OUT(c, d, d);
 306   MP_DROP(x);
 307   return (d);
 308 }
 309
 310 /* --- @ec_neg@ --- *
 311  *
 312  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 313  *              @ec *d@ = pointer to the destination point
 314  *              @const ec *p@ = pointer to the operand point
 315  *
 316  * Returns:     The destination point.
 317  *
 318  * Use:         Computes the negation of the given point.
 319  */
 320
 321 ec *ec_neg(ec_curve *c, ec *d, const ec *p)
 322 {
 323   EC_IN(c, d, p);
 324   EC_NEG(c, d, d);
 325   return (EC_OUT(c, d, d));
 326 }
 327
 328 /* --- @ec_add@ --- *
 329  *
 330  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 331  *              @ec *d@ = pointer to the destination point
 332  *              @const ec *p, *q@ = pointers to the operand points
 333  *
 334  * Returns:     ---
 335  *
 336  * Use:         Adds two points on an elliptic curve.
 337  */
 338
 339 ec *ec_add(ec_curve *c, ec *d, const ec *p, const ec *q)
 340 {
 341   ec pp = EC_INIT, qq = EC_INIT;
 342   EC_IN(c, &pp, p);
 343   EC_IN(c, &qq, q);
 344   EC_ADD(c, d, &pp, &qq);
 345   EC_OUT(c, d, d);
 346   EC_DESTROY(&pp);
 347   EC_DESTROY(&qq);
 348   return (d);
 349 }
 350
 351 /* --- @ec_sub@ --- *
 352  *
 353  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 354  *              @ec *d@ = pointer to the destination point
 355  *              @const ec *p, *q@ = pointers to the operand points
 356  *
 357  * Returns:     The destination @d@.
 358  *
 359  * Use:         Subtracts one point from another on an elliptic curve.
 360  */
 361
 362 ec *ec_sub(ec_curve *c, ec *d, const ec *p, const ec *q)
 363 {
 364   ec pp = EC_INIT, qq = EC_INIT;
 365   EC_IN(c, &pp, p);
 366   EC_IN(c, &qq, q);
 367   EC_SUB(c, d, &pp, &qq);
 368   EC_OUT(c, d, d);
 369   EC_DESTROY(&pp);
 370   EC_DESTROY(&qq);
 371   return (d);
 372 }
 373
 374 /* --- @ec_dbl@ --- *
 375  *
 376  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 377  *              @ec *d@ = pointer to the destination point
 378  *              @const ec *p@ = pointer to the operand point
 379  *
 380  * Returns:     ---
 381  *
 382  * Use:         Doubles a point on an elliptic curve.
 383  */
 384
 385 ec *ec_dbl(ec_curve *c, ec *d, const ec *p)
 386 {
 387   EC_IN(c, d, p);
 388   EC_DBL(c, d, d);
 389   return (EC_OUT(c, d, d));
 390 }
 391
 392 /* --- @ec_check@ --- *
 393  *
 394  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 395  *              @const ec *p@ = pointer to the point
 396  *
 397  * Returns:     Zero if OK, nonzero if this is an invalid point.
 398  *
 399  * Use:         Checks that a point is actually on an elliptic curve.
 400  */
 401
 402 int ec_check(ec_curve *c, const ec *p)
 403 {
 404   ec t = EC_INIT;
 405   int rc;
 406
 407   if (EC_ATINF(p))
 408     return (0);
 409   EC_IN(c, &t, p);
 410   rc = EC_CHECK(c, &t);
 411   EC_DESTROY(&t);
 412   return (rc);
 413 }
 414
 415 /* --- @ec_rand@ --- *
 416  *
 417  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 418  *              @ec *d@ = pointer to the destination point
 419  *              @grand *r@ = random number source
 420  *
 421  * Returns:     The destination @d@.
 422  *
 423  * Use:         Finds a random point on the given curve.
 424  */
 425
 426 ec *ec_rand(ec_curve *c, ec *d, grand *r)
 427 {
 428   mp *x = MP_NEW;
 429   do x = F_RAND(c->f, x, r); while (!EC_FIND(c, d, x));
 430   mp_drop(x);
 431   if (grand_range(r, 2)) EC_NEG(c, d, d);
 432   return (EC_OUT(c, d, d));
 433 }
 434
 435 /* --- @ec_imul@, @ec_mul@ --- *
 436  *
 437  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 438  *              @ec *d@ = pointer to the destination point
 439  *              @const ec *p@ = pointer to the generator point
 440  *              @mp *n@ = integer multiplier
 441  *
 442  * Returns:     The destination @d@.
 443  *
 444  * Use:         Multiplies a point by a scalar, returning %$n p$%.  The
 445  *              @imul@ variant uses internal representations for argument
 446  *              and result.
 447  */
 448
 449 ec *ec_imul(ec_curve *c, ec *d, const ec *p, mp *n)
 450 {
 451   ec t = EC_INIT;
 452
 453   EC_COPY(&t, p);
 454   if (t.x && (n->f & MP_BURN))
 455     t.x->f |= MP_BURN;
 456   MP_SHRINK(n);
 457   EC_SETINF(d);
 458   if (MP_LEN(n) == 0)
 459     ;
 460   else {
 461     if (n->f & MP_NEG)
 462       EC_NEG(c, &t, &t);
 463     if (MP_LEN(n) < EXP_THRESH)
 464       EXP_SIMPLE(*d, t, n);
 465     else
 466       EXP_WINDOW(*d, t, n);
 467   }
 468   EC_DESTROY(&t);
 469   return (d);
 470 }
 471
 472 ec *ec_mul(ec_curve *c, ec *d, const ec *p, mp *n)
 473 {
 474   EC_IN(c, d, p);
 475   ec_imul(c, d, d, n);
 476   return (EC_OUT(c, d, d));
 477 }
 478
 479 /*----- That's all, folks -------------------------------------------------*/