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

   1 /* -*-c-*-
   2  *
   3  * Elliptic curve definitions
   4  *
   5  * (c) 2001 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Catacomb.
  11  *
  12  * Catacomb is free software; you can redistribute it and/or modify
  13  * it under the terms of the GNU Library General Public License as
  14  * published by the Free Software Foundation; either version 2 of the
  15  * License, or (at your option) any later version.
  16  *
  17  * Catacomb is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  20  * GNU Library General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Library General Public
  23  * License along with Catacomb; if not, write to the Free
  24  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  25  * MA 02111-1307, USA.
  26  */
  27
  28 /*----- Header files ------------------------------------------------------*/
  29
  30 #include "ec.h"
  31
  32 /*----- Trivial wrappers --------------------------------------------------*/
  33
  34 /* --- @ec_samep@ --- *
  35  *
  36  * Arguments:   @ec_curve *c, *d@ = two elliptic curves
  37  *
  38  * Returns:     Nonzero if the curves are identical (not just isomorphic).
  39  *
  40  * Use:         Checks for sameness of curves.  This function does the full
  41  *              check, not just the curve-type-specific check done by the
  42  *              @sampep@ field operation.
  43  */
  44
  45 int ec_samep(ec_curve *c, ec_curve *d)
  46 {
  47   return (c == d || (field_samep(c->f, d->f) &&
  48                      c->ops == d->ops && EC_SAMEP(c, d)));
  49 }
  50
  51 /* --- @ec_create@ --- *
  52  *
  53  * Arguments:   @ec *p@ = pointer to an elliptic-curve point
  54  *
  55  * Returns:     The argument @p@.
  56  *
  57  * Use:         Initializes a new point.  The initial value is the additive
  58  *              identity (which is universal for all curves).
  59  */
  60
  61 ec *ec_create(ec *p) { EC_CREATE(p); return (p); }
  62
  63 /* --- @ec_destroy@ --- *
  64  *
  65  * Arguments:   @ec *p@ = pointer to an elliptic-curve point
  66  *
  67  * Returns:     ---
  68  *
  69  * Use:         Destroys a point, making it invalid.
  70  */
  71
  72 void ec_destroy(ec *p) { EC_DESTROY(p); }
  73
  74 /* --- @ec_atinf@ --- *
  75  *
  76  * Arguments:   @const ec *p@ = pointer to a point
  77  *
  78  * Returns:     Nonzero if %$p = O$% is the point at infinity, zero
  79  *              otherwise.
  80  */
  81
  82 int ec_atinf(const ec *p) { return (EC_ATINF(p)); }
  83
  84 /* --- @ec_setinf@ --- *
  85  *
  86  * Arguments:   @ec *p@ = pointer to a point
  87  *
  88  * Returns:     The argument @p@.
  89  *
  90  * Use:         Sets the given point to be the point %$O$% at infinity.
  91  */
  92
  93 ec *ec_setinf(ec *p) { EC_SETINF(p); return (p); }
  94
  95 /* --- @ec_copy@ --- *
  96  *
  97  * Arguments:   @ec *d@ = pointer to destination point
  98  *              @const ec *p@ = pointer to source point
  99  *
 100  * Returns:     The destination @d@.
 101  *
 102  * Use:         Creates a copy of an elliptic curve point.
 103  */
 104
 105 ec *ec_copy(ec *d, const ec *p) { EC_COPY(d, p); return (d); }
 106
 107 /* --- @ec_eq@ --- *
 108  *
 109  * Arguments:   @const ec *p, *q@ = two points
 110  *
 111  * Returns:     Nonzero if the points are equal.  Compares external-format
 112  *              points.
 113  */
 114
 115 int ec_eq(const ec *p, const ec *q) { return (EC_EQ(p, q)); }
 116
 117 /*----- Standard curve operations -----------------------------------------*/
 118
 119 /* --- @ec_stdsamep@ --- *
 120  *
 121  * Arguments:   @ec_curve *c, *d@ = two elliptic curves
 122  *
 123  * Returns:     Nonzero if the curves are identical (not just isomorphic).
 124  *
 125  * Use:         Simple sameness check on @a@ and @b@ curve members.
 126  */
 127
 128 int ec_stdsamep(ec_curve *c, ec_curve *d)
 129   { return (MP_EQ(c->a, d->a) && MP_EQ(c->b, d->b)); }
 130
 131 /* --- @ec_idin@, @ec_idout@, @ec_idfix@ --- *
 132  *
 133  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 134  *              @ec *d@ = pointer to the destination
 135  *              @const ec *p@ = pointer to a source point
 136  *
 137  * Returns:     The destination @d@.
 138  *
 139  * Use:         An identity operation if your curve has no internal
 140  *              representation.  (The field internal representation is still
 141  *              used.)
 142  */
 143
 144 ec *ec_idin(ec_curve *c, ec *d, const ec *p)
 145 {
 146   if (EC_ATINF(p))
 147     EC_SETINF(d);
 148   else {
 149     field *f = c->f;
 150     d->x = F_IN(f, d->x, p->x);
 151     d->y = F_IN(f, d->y, p->y);
 152     mp_drop(d->z); d->z = 0;
 153   }
 154   return (d);
 155 }
 156
 157 ec *ec_idout(ec_curve *c, ec *d, const ec *p)
 158 {
 159   if (EC_ATINF(p))
 160     EC_SETINF(d);
 161   else {
 162     field *f = c->f;
 163     d->x = F_OUT(f, d->x, p->x);
 164     d->y = F_OUT(f, d->y, p->y);
 165     mp_drop(d->z); d->z = 0;
 166   }
 167   return (d);
 168 }
 169
 170 ec *ec_idfix(ec_curve *c, ec *d, const ec *p)
 171   { EC_COPY(d, p); return (d); }
 172
 173 /* --- @ec_projin@, @ec_projout@, @ec_projfix@ --- *
 174  *
 175  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 176  *              @ec *d@ = pointer to the destination
 177  *              @const ec *p@ = pointer to a source point
 178  *
 179  * Returns:     The destination @d@.
 180  *
 181  * Use:         Conversion functions if your curve operations use a
 182  *              projective representation.
 183  */
 184
 185 ec *ec_projin(ec_curve *c, ec *d, const ec *p)
 186 {
 187   if (EC_ATINF(p))
 188     EC_SETINF(d);
 189   else {
 190     field *f = c->f;
 191     d->x = F_IN(f, d->x, p->x);
 192     d->y = F_IN(f, d->y, p->y);
 193     mp_drop(d->z); d->z = MP_COPY(f->one);
 194   }
 195   return (d);
 196 }
 197
 198 ec *ec_projout(ec_curve *c, ec *d, const ec *p)
 199 {
 200   if (EC_ATINF(p))
 201     EC_SETINF(d);
 202   else {
 203     mp *x, *y, *z, *zz;
 204     field *f = c->f;
 205     if (p->z == f->one) {
 206       d->x = F_OUT(f, d->x, p->x);
 207       d->y = F_OUT(f, d->y, p->y);
 208     } else {
 209       z = F_INV(f, MP_NEW, p->z);
 210       zz = F_SQR(f, MP_NEW, z);
 211       z = F_MUL(f, z, zz, z);
 212       x = F_MUL(f, d->x, p->x, zz);
 213       y = F_MUL(f, d->y, p->y, z);
 214       mp_drop(z);
 215       mp_drop(zz);
 216       d->x = F_OUT(f, x, x);
 217       d->y = F_OUT(f, y, y);
 218     }
 219     mp_drop(d->z);
 220     d->z = 0;
 221   }
 222   return (d);
 223 }
 224
 225 ec *ec_projfix(ec_curve *c, ec *d, const ec *p)
 226 {
 227   if (EC_ATINF(p))
 228     EC_SETINF(d);
 229   else if (p->z == c->f->one)
 230     EC_COPY(d, p);
 231   else {
 232     mp *z, *zz;
 233     field *f = c->f;
 234     z = F_INV(f, MP_NEW, p->z);
 235     zz = F_SQR(f, MP_NEW, z);
 236     z = F_MUL(f, z, zz, z);
 237     d->x = F_MUL(f, d->x, p->x, zz);
 238     d->y = F_MUL(f, d->y, p->y, z);
 239     mp_drop(z);
 240     mp_drop(zz);
 241     mp_drop(d->z);
 242     d->z = MP_COPY(f->one);
 243   }
 244   return (d);
 245 }
 246
 247 /* --- @ec_stdsub@ --- *
 248  *
 249  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 250  *              @ec *d@ = pointer to the destination
 251  *              @const ec *p, *q@ = the operand points
 252  *
 253  * Returns:     The destination @d@.
 254  *
 255  * Use:         Standard point subtraction operation, in terms of negation
 256  *              and addition.  This isn't as efficient as a ready-made
 257  *              subtraction operator.
 258  */
 259
 260 ec *ec_stdsub(ec_curve *c, ec *d, const ec *p, const ec *q)
 261 {
 262   ec t = EC_INIT;
 263   EC_NEG(c, &t, q);
 264   EC_ADD(c, d, p, &t);
 265   EC_DESTROY(&t);
 266   return (d);
 267 }
 268
 269 /*----- Creating curves ---------------------------------------------------*/
 270
 271 /* --- @ec_destroycurve@ --- *
 272  *
 273  * Arguments:   @ec_curve *c@ = pointer to an ellptic curve
 274  *
 275  * Returns:     ---
 276  *
 277  * Use:         Destroys a description of an elliptic curve.
 278  */
 279
 280 void ec_destroycurve(ec_curve *c) { c->ops->destroy(c); }
 281
 282 /*----- Real arithmetic ---------------------------------------------------*/
 283
 284 /* --- @ec_find@ --- *
 285  *
 286  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 287  *              @ec *d@ = pointer to the destination point
 288  *              @mp *x@ = a possible x-coordinate
 289  *
 290  * Returns:     Zero if OK, nonzero if there isn't a point there.
 291  *
 292  * Use:         Finds a point on an elliptic curve with a given x-coordinate.
 293  */
 294
 295 ec *ec_find(ec_curve *c, ec *d, mp *x)
 296 {
 297   x = F_IN(c->f, MP_NEW, x);
 298   if ((d = EC_FIND(c, d, x)) != 0)
 299     EC_OUT(c, d, d);
 300   MP_DROP(x);
 301   return (d);
 302 }
 303
 304 /* --- @ec_neg@ --- *
 305  *
 306  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 307  *              @ec *d@ = pointer to the destination point
 308  *              @const ec *p@ = pointer to the operand point
 309  *
 310  * Returns:     The destination point.
 311  *
 312  * Use:         Computes the negation of the given point.
 313  */
 314
 315 ec *ec_neg(ec_curve *c, ec *d, const ec *p)
 316   { EC_IN(c, d, p); EC_NEG(c, d, d); return (EC_OUT(c, d, d)); }
 317
 318 /* --- @ec_add@ --- *
 319  *
 320  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 321  *              @ec *d@ = pointer to the destination point
 322  *              @const ec *p, *q@ = pointers to the operand points
 323  *
 324  * Returns:     ---
 325  *
 326  * Use:         Adds two points on an elliptic curve.
 327  */
 328
 329 ec *ec_add(ec_curve *c, ec *d, const ec *p, const ec *q)
 330 {
 331   ec pp = EC_INIT, qq = EC_INIT;
 332   EC_IN(c, &pp, p);
 333   EC_IN(c, &qq, q);
 334   EC_ADD(c, d, &pp, &qq);
 335   EC_OUT(c, d, d);
 336   EC_DESTROY(&pp);
 337   EC_DESTROY(&qq);
 338   return (d);
 339 }
 340
 341 /* --- @ec_sub@ --- *
 342  *
 343  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 344  *              @ec *d@ = pointer to the destination point
 345  *              @const ec *p, *q@ = pointers to the operand points
 346  *
 347  * Returns:     The destination @d@.
 348  *
 349  * Use:         Subtracts one point from another on an elliptic curve.
 350  */
 351
 352 ec *ec_sub(ec_curve *c, ec *d, const ec *p, const ec *q)
 353 {
 354   ec pp = EC_INIT, qq = EC_INIT;
 355   EC_IN(c, &pp, p);
 356   EC_IN(c, &qq, q);
 357   EC_SUB(c, d, &pp, &qq);
 358   EC_OUT(c, d, d);
 359   EC_DESTROY(&pp);
 360   EC_DESTROY(&qq);
 361   return (d);
 362 }
 363
 364 /* --- @ec_dbl@ --- *
 365  *
 366  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 367  *              @ec *d@ = pointer to the destination point
 368  *              @const ec *p@ = pointer to the operand point
 369  *
 370  * Returns:     ---
 371  *
 372  * Use:         Doubles a point on an elliptic curve.
 373  */
 374
 375 ec *ec_dbl(ec_curve *c, ec *d, const ec *p)
 376   { EC_IN(c, d, p); EC_DBL(c, d, d); return (EC_OUT(c, d, d)); }
 377
 378 /* --- @ec_check@ --- *
 379  *
 380  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 381  *              @const ec *p@ = pointer to the point
 382  *
 383  * Returns:     Zero if OK, nonzero if this is an invalid point.
 384  *
 385  * Use:         Checks that a point is actually on an elliptic curve.
 386  */
 387
 388 int ec_check(ec_curve *c, const ec *p)
 389 {
 390   ec t = EC_INIT;
 391   int rc;
 392
 393   if (EC_ATINF(p))
 394     return (0);
 395   EC_IN(c, &t, p);
 396   rc = EC_CHECK(c, &t);
 397   EC_DESTROY(&t);
 398   return (rc);
 399 }
 400
 401 /* --- @ec_rand@ --- *
 402  *
 403  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 404  *              @ec *d@ = pointer to the destination point
 405  *              @grand *r@ = random number source
 406  *
 407  * Returns:     The destination @d@.
 408  *
 409  * Use:         Finds a random point on the given curve.
 410  */
 411
 412 ec *ec_rand(ec_curve *c, ec *d, grand *r)
 413 {
 414   mp *x = MP_NEW;
 415   do x = F_RAND(c->f, x, r); while (!EC_FIND(c, d, x));
 416   mp_drop(x);
 417   if (grand_range(r, 2)) EC_NEG(c, d, d);
 418   return (EC_OUT(c, d, d));
 419 }
 420
 421 /*----- That's all, folks -------------------------------------------------*/