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

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