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

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