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

   1 /* -*-c-*-
   2  *
   3  * $Id: ec.h,v 1.8 2004/03/27 17:54:11 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.8  2004/03/27 17:54:11  mdw
  34  * Standard curves and curve checking.
  35  *
  36  * Revision 1.7  2004/03/23 15:19:32  mdw
  37  * Test elliptic curves more thoroughly.
  38  *
  39  * Revision 1.6  2004/03/22 02:19:10  mdw
  40  * Rationalise the sliding-window threshold.  Drop guarantee that right
  41  * arguments to EC @add@ are canonical, and fix up projective implementations
  42  * to cope.
  43  *
  44  * Revision 1.5  2004/03/21 22:52:06  mdw
  45  * Merge and close elliptic curve branch.
  46  *
  47  * Revision 1.4.4.3  2004/03/21 22:39:46  mdw
  48  * Elliptic curves on binary fields work.
  49  *
  50  * Revision 1.4.4.2  2004/03/20 00:13:31  mdw
  51  * Projective coordinates for prime curves
  52  *
  53  * Revision 1.4.4.1  2003/06/10 13:43:53  mdw
  54  * Simple (non-projective) curves over prime fields now seem to work.
  55  *
  56  * Revision 1.4  2003/05/15 23:25:59  mdw
  57  * Make elliptic curve stuff build.
  58  *
  59  * Revision 1.3  2002/01/13 13:48:44  mdw
  60  * Further progress.
  61  *
  62  * Revision 1.2  2001/05/07 17:29:44  mdw
  63  * Treat projective coordinates as an internal representation.  Various
  64  * minor interface changes.
  65  *
  66  * Revision 1.1  2001/04/29 18:12:33  mdw
  67  * Prototype version.
  68  *
  69  */
  70
  71 #ifndef CATACOMB_EC_H
  72 #define CATACOMB_EC_H
  73
  74 #ifdef __cplusplus
  75   extern "C" {
  76 #endif
  77
  78 /*----- Header files ------------------------------------------------------*/
  79
  80 #ifndef CATACOMB_FIELD_H
  81 #  include "field.h"
  82 #endif
  83
  84 #ifndef CATACOMB_MP_H
  85 #  include "mp.h"
  86 #endif
  87
  88 #ifndef CATACOMB_QDPARSE_H
  89 #  include "qdparse.h"
  90 #endif
  91
  92 /*----- Data structures ---------------------------------------------------*/
  93
  94 /* --- An elliptic curve representation --- */
  95
  96 typedef struct ec_curve {
  97   const struct ec_ops *ops;             /* Curve operations */
  98   field *f;                             /* Underlying field structure */
  99   mp *a, *b;                            /* Standard params (internal form) */
 100 } ec_curve;
 101
 102 /* --- An elliptic curve point --- */
 103
 104 typedef struct ec {
 105   mp *x, *y;                            /* Point coordinates */
 106   mp *z;                                /* Common denominator (or null) */
 107 } ec;
 108
 109 /* --- A factor for simultaneous multiplication --- */
 110
 111 typedef struct ec_mulfactor {
 112   ec base;                              /* The point */
 113   mp *exp;                              /* The exponent */
 114 } ec_mulfactor;
 115
 116 /* --- Elliptic curve operations --- *
 117  *
 118  * All operations (apart from @destroy@ and @in@) are guaranteed to be
 119  * performed on internal representations of points.
 120  *
 121  * (Historical note.  We used to guarantee that the second to @add@ and @mul@
 122  * was the output of @in@ or @fix@, but this canonification turned out to
 123  * make the precomputation in @ec_exp@ too slow.  Projective implementations
 124  * must therefore cope with a pair of arbitrary points.)
 125  */
 126
 127 typedef struct ec_ops {
 128   void (*destroy)(ec_curve */*c*/);
 129   ec *(*in)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 130   ec *(*out)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 131   ec *(*fix)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 132   ec *(*find)(ec_curve */*c*/, ec */*d*/, mp */*x*/);
 133   ec *(*neg)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 134   ec *(*add)(ec_curve */*c*/, ec */*d*/, const ec */*p*/, const ec */*q*/);
 135   ec *(*sub)(ec_curve */*c*/, ec */*d*/, const ec */*p*/, const ec */*q*/);
 136   ec *(*dbl)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 137   int (*check)(ec_curve */*c*/, const ec */*p*/);
 138 } ec_ops;
 139
 140 #define EC_IN(c, d, p)          (c)->ops->in((c), (d), (p))
 141 #define EC_OUT(c, d, p)         (c)->ops->out((c), (d), (p))
 142 #define EC_FIX(c, d, p)         (c)->ops->fix((c), (d), (p))
 143
 144 #define EC_FIND(c, d, x)        (c)->ops->find((c), (d), (x))
 145 #define EC_NEG(c, d, x)         (c)->ops->neg((c), (d), (x))
 146 #define EC_ADD(c, d, p, q)      (c)->ops->add((c), (d), (p), (q))
 147 #define EC_SUB(c, d, p, q)      (c)->ops->sub((c), (d), (p), (q))
 148 #define EC_DBL(c, d, p)         (c)->ops->dbl((c), (d), (p))
 149 #define EC_CHECK(c, p)          (c)->ops->check((c), (p))
 150
 151 /* --- Elliptic curve parameters --- */
 152
 153 typedef struct ec_info {
 154   ec_curve *c;                          /* The actual curve */
 155   ec g;                                 /* The common point */
 156   mp *r;                                /* Order of %$g$% */
 157   mp *h;                                /* Cofactor %$h = \#E/r$% */
 158 } ec_info;
 159
 160 /*----- Simple memory management things -----------------------------------*/
 161
 162 /* --- @ec_create@ --- *
 163  *
 164  * Arguments:   @ec *p@ = pointer to an elliptic-curve point
 165  *
 166  * Returns:     The argument @p@.
 167  *
 168  * Use:         Initializes a new point.  The initial value is the additive
 169  *              identity (which is universal for all curves).
 170  */
 171
 172 #define EC_INIT { MP_NEW, MP_NEW, MP_NEW }
 173
 174 #define EC_CREATE(p) do {                                               \
 175   ec *_p = (p);                                                         \
 176   _p->x = _p->y = _p->z = MP_NEW;                                       \
 177 } while (0)
 178
 179 extern ec *ec_create(ec */*p*/);
 180
 181 /* --- @ec_destroy@ --- *
 182  *
 183  * Arguments:   @ec *p@ = pointer to an elliptic-curve point
 184  *
 185  * Returns:     ---
 186  *
 187  * Use:         Destroys a point, making it invalid.
 188  */
 189
 190 #define EC_DESTROY(p) do {                                              \
 191   ec *_p = (p);                                                         \
 192   if (!EC_ATINF(_p)) {                                                  \
 193     MP_DROP(_p->x);                                                     \
 194     MP_DROP(_p->y);                                                     \
 195     if (_p->z) MP_DROP(_p->z);                                          \
 196   }                                                                     \
 197 } while (0)
 198
 199 extern void ec_destroy(ec */*p*/);
 200
 201 /* --- @ec_atinf@ --- *
 202  *
 203  * Arguments:   @const ec *p@ = pointer to a point
 204  *
 205  * Returns:     Nonzero if %$p = O$% is the point at infinity, zero
 206  *              otherwise.
 207  */
 208
 209 #define EC_ATINF(p) ((p)->x == MP_NEW || (p)->x == MP_NEWSEC)
 210
 211 extern int ec_atinf(const ec */*p*/);
 212
 213 /* --- @ec_setinf@ --- *
 214  *
 215  * Arguments:   @ec *p@ = pointer to a point
 216  *
 217  * Returns:     The argument @p@.
 218  *
 219  * Use:         Sets the given point to be the point %$O$% at infinity.
 220  */
 221
 222 #define EC_SETINF(p) do {                                               \
 223   ec *_p = (p);                                                         \
 224   if (!EC_ATINF(_p)) {                                                  \
 225     MP_DROP(_p->x);                                                     \
 226     MP_DROP(_p->y);                                                     \
 227     if (_p->z) MP_DROP(_p->z);                                          \
 228     _p->x = _p->y = _p->z = MP_NEW;                                     \
 229     _p->y = MP_NEW;                                                     \
 230     _p->z = MP_NEW;                                                     \
 231   }                                                                     \
 232 } while (0)
 233
 234 extern ec *ec_setinf(ec */*p*/);
 235
 236 /* --- @ec_copy@ --- *
 237  *
 238  * Arguments:   @ec *d@ = pointer to destination point
 239  *              @const ec *p@ = pointer to source point
 240  *
 241  * Returns:     The destination @d@.
 242  *
 243  * Use:         Creates a copy of an elliptic curve point.
 244  */
 245
 246 #define EC_COPY(d, p) do {                                              \
 247   ec *_d = (d);                                                         \
 248   const ec *_p = (p);                                                   \
 249   if (d != p) {                                                         \
 250     EC_DESTROY(d);                                                      \
 251     if (EC_ATINF(p))                                                    \
 252       _d->x = _d->y = _d->z = MP_NEW;                                   \
 253     else {                                                              \
 254       _d->x = MP_COPY(_p->x);                                           \
 255       _d->y = MP_COPY(_p->y);                                           \
 256       _d->z = _p->z ? MP_COPY(_p->z) : MP_NEW;                          \
 257     }                                                                   \
 258   }                                                                     \
 259 } while (0)
 260
 261 extern ec *ec_copy(ec */*d*/, const ec */*p*/);
 262
 263 /* --- @ec_eq@ --- *
 264  *
 265  * Arguments:   @const ec *p, *q@ = two points
 266  *
 267  * Returns:     Nonzero if the points are equal.  Compares external-format
 268  *              points.
 269  */
 270
 271 #define EC_EQ(p, q)                                                     \
 272     ((EC_ATINF(p) && EC_ATINF(q)) ||                                    \
 273      (!EC_ATINF(p) && !EC_ATINF(q) &&                                   \
 274       MP_EQ((p)->x, (q)->x) &&                                          \
 275       MP_EQ((p)->y, (q)->y)))
 276
 277 extern int ec_eq(const ec *p, const ec *q);
 278
 279 /*----- Interesting arithmetic --------------------------------------------*/
 280
 281 /* --- @ec_find@ --- *
 282  *
 283  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 284  *              @ec *d@ = pointer to the destination point
 285  *              @mp *x@ = a possible x-coordinate
 286  *
 287  * Returns:     The destination if OK, or null if no point was found.
 288  *
 289  * Use:         Finds a point on an elliptic curve with a given
 290  *              x-coordinate.  If there is no point with the given
 291  *              %$x$%-coordinate, a null pointer is returned and the
 292  *              destination is left invalid.
 293  */
 294
 295 extern ec *ec_find(ec_curve */*c*/, ec */*d*/, mp */*x*/);
 296
 297 /* --- @ec_rand@ --- *
 298  *
 299  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 300  *              @ec *d@ = pointer to the destination point
 301  *              @grand *r@ = random number source
 302  *
 303  * Returns:     The destination @d@.
 304  *
 305  * Use:         Finds a random point on the given curve.
 306  */
 307
 308 extern ec *ec_rand(ec_curve */*c*/, ec */*d*/, grand */*r*/);
 309
 310 /* --- @ec_neg@ --- *
 311  *
 312  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 313  *              @ec *d@ = pointer to the destination point
 314  *              @const ec *p@ = pointer to the operand point
 315  *
 316  * Returns:     The destination point.
 317  *
 318  * Use:         Computes the negation of the given point.
 319  */
 320
 321 extern ec *ec_neg(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 322
 323 /* --- @ec_add@ --- *
 324  *
 325  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 326  *              @ec *d@ = pointer to the destination point
 327  *              @const ec *p, *q@ = pointers to the operand points
 328  *
 329  * Returns:     The destination @d@.
 330  *
 331  * Use:         Adds two points on an elliptic curve.
 332  */
 333
 334 extern ec *ec_add(ec_curve */*c*/, ec */*d*/,
 335                   const ec */*p*/, const ec */*q*/);
 336
 337 /* --- @ec_sub@ --- *
 338  *
 339  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 340  *              @ec *d@ = pointer to the destination point
 341  *              @const ec *p, *q@ = pointers to the operand points
 342  *
 343  * Returns:     The destination @d@.
 344  *
 345  * Use:         Subtracts one point from another on an elliptic curve.
 346  */
 347
 348 extern ec *ec_sub(ec_curve */*c*/, ec */*d*/,
 349                   const ec */*p*/, const ec */*q*/);
 350
 351 /* --- @ec_dbl@ --- *
 352  *
 353  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 354  *              @ec *d@ = pointer to the destination point
 355  *              @const ec *p@ = pointer to the operand point
 356  *
 357  * Returns:     The destination @d@.
 358  *
 359  * Use:         Doubles a point on an elliptic curve.
 360  */
 361
 362 extern ec *ec_dbl(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 363
 364 /* --- @ec_check@ --- *
 365  *
 366  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 367  *              @const ec *p@ = pointer to the point
 368  *
 369  * Returns:     Zero if OK, nonzero if this is an invalid point.
 370  *
 371  * Use:         Checks that a point is actually on an elliptic curve.
 372  */
 373
 374 extern int ec_check(ec_curve */*c*/, const ec */*p*/);
 375
 376 /* --- @ec_mul@, @ec_imul@ --- *
 377  *
 378  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 379  *              @ec *d@ = pointer to the destination point
 380  *              @const ec *p@ = pointer to the generator point
 381  *              @mp *n@ = integer multiplier
 382  *
 383  * Returns:     The destination @d@.
 384  *
 385  * Use:         Multiplies a point by a scalar, returning %$n p$%.  The
 386  *              @imul@ variant uses internal representations for argument
 387  *              and result.
 388  */
 389
 390 extern ec *ec_mul(ec_curve */*c*/, ec */*d*/, const ec */*p*/, mp */*n*/);
 391 extern ec *ec_imul(ec_curve */*c*/, ec */*d*/, const ec */*p*/, mp */*n*/);
 392
 393 /* --- @ec_mmul@, @ec_immul@ --- *
 394  *
 395  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 396  *              @ec *d@ = pointer to the destination point
 397  *              @const ec_mulfactor *f@ = pointer to vector of factors
 398  *              @size_t n@ = number of factors
 399  *
 400  * Returns:     The destination @d@.
 401  *
 402  * Use:         Does simultaneous point multiplication.  The @immul@ variant
 403  *              uses internal representations for arguments and result.
 404  */
 405
 406 extern ec *ec_mmul(ec_curve */*c*/, ec */*d*/,
 407                    const ec_mulfactor */*f*/, size_t /*n*/);
 408 extern ec *ec_immul(ec_curve */*c*/, ec */*d*/,
 409                     const ec_mulfactor */*f*/, size_t /*n*/);
 410
 411 /*----- Standard curve operations -----------------------------------------*/
 412
 413 /* --- @ec_idin@, @ec_idout@, @ec_idfix@ --- *
 414  *
 415  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 416  *              @ec *d@ = pointer to the destination
 417  *              @const ec *p@ = pointer to a source point
 418  *
 419  * Returns:     The destination @d@.
 420  *
 421  * Use:         An identity operation if your curve has no internal
 422  *              representation.  (The field internal representation is still
 423  *              used.)
 424  */
 425
 426 extern ec *ec_idin(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 427 extern ec *ec_idout(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 428 extern ec *ec_idfix(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 429
 430 /* --- @ec_projin@, @ec_projout@, @ec_projfix@ --- *
 431  *
 432  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 433  *              @ec *d@ = pointer to the destination
 434  *              @const ec *p@ = pointer to a source point
 435  *
 436  * Returns:     The destination @d@.
 437  *
 438  * Use:         Conversion functions if your curve operations use a
 439  *              projective representation.
 440  */
 441
 442 extern ec *ec_projin(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 443 extern ec *ec_projout(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 444 extern ec *ec_projfix(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 445
 446 /* --- @ec_stdsub@ --- *
 447  *
 448  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 449  *              @ec *d@ = pointer to the destination
 450  *              @const ec *p, *q@ = the operand points
 451  *
 452  * Returns:     The destination @d@.
 453  *
 454  * Use:         Standard point subtraction operation, in terms of negation
 455  *              and addition.  This isn't as efficient as a ready-made
 456  *              subtraction operator.
 457  */
 458
 459 extern ec *ec_stdsub(ec_curve */*c*/, ec */*d*/,
 460                      const ec */*p*/, const ec */*q*/);
 461
 462 /*----- Creating curves ---------------------------------------------------*/
 463
 464 /* --- @ec_destroycurve@ --- *
 465  *
 466  * Arguments:   @ec_curve *c@ = pointer to an ellptic curve
 467  *
 468  * Returns:     ---
 469  *
 470  * Use:         Destroys a description of an elliptic curve.
 471  */
 472
 473 extern void ec_destroycurve(ec_curve */*c*/);
 474
 475 /* --- @ec_prime@, @ec_primeproj@ --- *
 476  *
 477  * Arguments:   @field *f@ = the underlying field for this elliptic curve
 478  *              @mp *a, *b@ = the coefficients for this curve
 479  *
 480  * Returns:     A pointer to the curve.
 481  *
 482  * Use:         Creates a curve structure for an elliptic curve defined over
 483  *              a prime field.  The @primeproj@ variant uses projective
 484  *              coordinates, which can be a win.
 485  */
 486
 487 extern ec_curve *ec_prime(field */*f*/, mp */*a*/, mp */*b*/);
 488 extern ec_curve *ec_primeproj(field */*f*/, mp */*a*/, mp */*b*/);
 489
 490 /* --- @ec_bin@, @ec_binproj@ --- *
 491  *
 492  * Arguments:   @field *f@ = the underlying field for this elliptic curve
 493  *              @mp *a, *b@ = the coefficients for this curve
 494  *
 495  * Returns:     A pointer to the curve.
 496  *
 497  * Use:         Creates a curve structure for an elliptic curve defined over
 498  *              a binary field.  The @binproj@ variant uses projective
 499  *              coordinates, which can be a win.
 500  */
 501
 502 extern ec_curve *ec_bin(field */*f*/, mp */*a*/, mp */*b*/);
 503 extern ec_curve *ec_binproj(field */*f*/, mp */*a*/, mp */*b*/);
 504
 505 /*----- Curve parameter sets ----------------------------------------------*/
 506
 507 /* --- @ec_curveparse@ --- *
 508  *
 509  * Arguments:   @qd_parse *qd@ = parser context
 510  *
 511  * Returns:     Elliptic curve pointer if OK, or null.
 512  *
 513  * Use:         Parses an elliptic curve description, which has the form
 514  *
 515  *                * a field description
 516  *                * an optional `/'
 517  *                * `prime', `primeproj', `bin', or `binproj'
 518  *                * an optional `:'
 519  *                * the %$a$% parameter
 520  *                * an optional `,'
 521  *                * the %$b$% parameter
 522  */
 523
 524 extern ec_curve *ec_curveparse(qd_parse */*qd*/);
 525
 526 /* --- @ec_ptparse@ --- *
 527  *
 528  * Arguments:   @qd_parse *qd@ = parser context
 529  *              @ec *p@ = where to put the point
 530  *
 531  * Returns:     The point address, or null.
 532  *
 533  * Use:         Parses an elliptic curve point.  This has the form
 534  *
 535  *                * %$x$%-coordinate
 536  *                * optional `,'
 537  *                * %$y$%-coordinate
 538  */
 539
 540 extern ec *ec_ptparse(qd_parse */*qd*/, ec */*p*/);
 541
 542 /* --- @ec_infoparse@ --- *
 543  *
 544  * Arguments:   @qd_parse *qd@ = parser context
 545  *              @ec_info *ei@ = curve information block, currently
 546  *                      uninitialized
 547  *
 548  * Returns:     Zero on success, nonzero on failure.
 549  *
 550  * Use:         Parses an elliptic curve information string, and stores the
 551  *              information in @ei@.  This has the form
 552  *
 553  *                * elliptic curve description
 554  *                * optional `/'
 555  *                * common point
 556  *                * optional `:'
 557  *                * group order
 558  *                * optional `*'
 559  *                * cofactor
 560  */
 561
 562 extern int ec_infoparse(qd_parse */*qd*/, ec_info */*ei*/);
 563
 564 /* --- @ec_getinfo@ --- *
 565  *
 566  * Arguments:   @ec_info *ei@ = where to write the information
 567  *              @const char *p@ = string describing a curve
 568  *
 569  * Returns:     Null on success, or a pointer to an error message.
 570  *
 571  * Use:         Parses out information about a curve.  The string is either a
 572  *              standard curve name, or a curve info string.
 573  */
 574
 575 extern const char *ec_getinfo(ec_info */*ei*/, const char */*p*/);
 576
 577 /* --- @ec_freeinfo@ --- *
 578  *
 579  * Arguments:   @ec_info *ei@ = elliptic curve information block to free
 580  *
 581  * Returns:     ---
 582  *
 583  * Use:         Frees the information block.
 584  */
 585
 586 extern void ec_freeinfo(ec_info */*ei*/);
 587
 588 /* --- @ec_checkinfo@ --- *
 589  *
 590  * Arguments:   @const ec_info *ei@ = elliptic curve information block
 591  *
 592  * Returns:     Null if OK, or pointer to error message.
 593  *
 594  * Use:         Checks an elliptic curve according to the rules in SEC1.
 595  */
 596
 597 extern const char *ec_checkinfo(const ec_info */*ei*/, grand */*gr*/);
 598
 599 /*----- That's all, folks -------------------------------------------------*/
 600
 601 #ifdef __cplusplus
 602   }
 603 #endif
 604
 605 #endif