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

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