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

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