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

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