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

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