git.distorted.org.uk Git - u/mdw/catacomb/blob - ec.c

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