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_FIX(c, &t, &t);
 265   EC_ADD(c, d, p, &t);
 266   EC_DESTROY(&t);
 267   return (d);
 268 }
 269
 270 /*----- Creating curves ---------------------------------------------------*/
 271
 272 /* --- @ec_destroycurve@ --- *
 273  *
 274  * Arguments:   @ec_curve *c@ = pointer to an ellptic curve
 275  *
 276  * Returns:     ---
 277  *
 278  * Use:         Destroys a description of an elliptic curve.
 279  */
 280
 281 void ec_destroycurve(ec_curve *c) { c->ops->destroy(c); }
 282
 283 /*----- Real arithmetic ---------------------------------------------------*/
 284
 285 /* --- @ec_find@ --- *
 286  *
 287  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 288  *              @ec *d@ = pointer to the destination point
 289  *              @mp *x@ = a possible x-coordinate
 290  *
 291  * Returns:     Zero if OK, nonzero if there isn't a point there.
 292  *
 293  * Use:         Finds a point on an elliptic curve with a given x-coordinate.
 294  */
 295
 296 ec *ec_find(ec_curve *c, ec *d, mp *x)
 297 {
 298   x = F_IN(c->f, MP_NEW, x);
 299   if ((d = EC_FIND(c, d, x)) != 0)
 300     EC_OUT(c, d, d);
 301   MP_DROP(x);
 302   return (d);
 303 }
 304
 305 /* --- @ec_neg@ --- *
 306  *
 307  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 308  *              @ec *d@ = pointer to the destination point
 309  *              @const ec *p@ = pointer to the operand point
 310  *
 311  * Returns:     The destination point.
 312  *
 313  * Use:         Computes the negation of the given point.
 314  */
 315
 316 ec *ec_neg(ec_curve *c, ec *d, const ec *p)
 317   { EC_IN(c, d, p); EC_NEG(c, d, d); return (EC_OUT(c, d, d)); }
 318
 319 /* --- @ec_add@ --- *
 320  *
 321  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 322  *              @ec *d@ = pointer to the destination point
 323  *              @const ec *p, *q@ = pointers to the operand points
 324  *
 325  * Returns:     ---
 326  *
 327  * Use:         Adds two points on an elliptic curve.
 328  */
 329
 330 ec *ec_add(ec_curve *c, ec *d, const ec *p, const ec *q)
 331 {
 332   ec pp = EC_INIT, qq = EC_INIT;
 333   EC_IN(c, &pp, p);
 334   EC_IN(c, &qq, q);
 335   EC_ADD(c, d, &pp, &qq);
 336   EC_OUT(c, d, d);
 337   EC_DESTROY(&pp);
 338   EC_DESTROY(&qq);
 339   return (d);
 340 }
 341
 342 /* --- @ec_sub@ --- *
 343  *
 344  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 345  *              @ec *d@ = pointer to the destination point
 346  *              @const ec *p, *q@ = pointers to the operand points
 347  *
 348  * Returns:     The destination @d@.
 349  *
 350  * Use:         Subtracts one point from another on an elliptic curve.
 351  */
 352
 353 ec *ec_sub(ec_curve *c, ec *d, const ec *p, const ec *q)
 354 {
 355   ec pp = EC_INIT, qq = EC_INIT;
 356   EC_IN(c, &pp, p);
 357   EC_IN(c, &qq, q);
 358   EC_SUB(c, d, &pp, &qq);
 359   EC_OUT(c, d, d);
 360   EC_DESTROY(&pp);
 361   EC_DESTROY(&qq);
 362   return (d);
 363 }
 364
 365 /* --- @ec_dbl@ --- *
 366  *
 367  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 368  *              @ec *d@ = pointer to the destination point
 369  *              @const ec *p@ = pointer to the operand point
 370  *
 371  * Returns:     ---
 372  *
 373  * Use:         Doubles a point on an elliptic curve.
 374  */
 375
 376 ec *ec_dbl(ec_curve *c, ec *d, const ec *p)
 377   { EC_IN(c, d, p); EC_DBL(c, d, d); return (EC_OUT(c, d, d)); }
 378
 379 /* --- @ec_check@ --- *
 380  *
 381  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 382  *              @const ec *p@ = pointer to the point
 383  *
 384  * Returns:     Zero if OK, nonzero if this is an invalid point.
 385  *
 386  * Use:         Checks that a point is actually on an elliptic curve.
 387  */
 388
 389 int ec_check(ec_curve *c, const ec *p)
 390 {
 391   ec t = EC_INIT;
 392   int rc;
 393
 394   if (EC_ATINF(p))
 395     return (0);
 396   EC_IN(c, &t, p);
 397   rc = EC_CHECK(c, &t);
 398   EC_DESTROY(&t);
 399   return (rc);
 400 }
 401
 402 /* --- @ec_rand@ --- *
 403  *
 404  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 405  *              @ec *d@ = pointer to the destination point
 406  *              @grand *r@ = random number source
 407  *
 408  * Returns:     The destination @d@.
 409  *
 410  * Use:         Finds a random point on the given curve.
 411  */
 412
 413 ec *ec_rand(ec_curve *c, ec *d, grand *r)
 414 {
 415   mp *x = MP_NEW;
 416   do x = F_RAND(c->f, x, r); while (!EC_FIND(c, d, x));
 417   mp_drop(x);
 418   if (grand_range(r, 2)) EC_NEG(c, d, d);
 419   return (EC_OUT(c, d, d));
 420 }
 421
 422 /*----- That's all, folks -------------------------------------------------*/