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

   1 /* -*-c-*-
   2  *
   3  * $Id: ec.h,v 1.2 2001/05/07 17:29:44 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.2  2001/05/07 17:29:44  mdw
  34  * Treat projective coordinates as an internal representation.  Various
  35  * minor interface changes.
  36  *
  37  * Revision 1.1  2001/04/29 18:12:33  mdw
  38  * Prototype version.
  39  *
  40  */
  41
  42 #ifndef CATACOMB_EC_H
  43 #define CATACOMB_EC_H
  44
  45 #ifdef __cplusplus
  46   extern "C" {
  47 #endif
  48
  49 /*----- Header files ------------------------------------------------------*/
  50
  51 #include "field.h"
  52 #include "mp.h"
  53
  54 /*----- Data structures ---------------------------------------------------*/
  55
  56 typedef struct ec_curve {
  57   const struct ec_ops *ops;             /* Curve operations */
  58   field *f;                             /* Underlying field structure */
  59 } ec_curve;
  60
  61 typedef struct ec {
  62   mp *x, *y;                            /* Point coordinates */
  63   mp *z;                                /* Common denominator (or null) */
  64 } ec;
  65
  66 typedef struct ec_ops {
  67   void (*destroy)(ec_curve */*c*/);
  68   ec *(*in)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
  69   ec *(*out)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
  70   ec *(*find)(ec_curve */*c*/, ec */*d*/, mp */*x*/);
  71   ec *(*add)(ec_curve */*c*/, ec */*d*/, const ec */*p*/, const ec */*q*/);
  72   ec *(*dbl)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
  73 } ec_ops;
  74
  75 #define EC_DESTROY(c)           (c)->ops->destroy((c))
  76
  77 #define EC_IN(c, d, p)          (c)->ops->in((c), (d), (p))
  78 #define EC_OUT(c, d, p)         (c)->ops->in((c), (d), (p))
  79
  80 #define EC_FIND(c, d, x)        (c)->ops->find((c), (d), (x))
  81 #define EC_ADD(c, d, p, q)      (c)->ops->add((c), (d), (p), (q))
  82 #define EC_DBL(c, d, p)         (c)->ops->dbl((c), (d), (p))
  83
  84 /*----- Simple memory management things -----------------------------------*/
  85
  86 /* --- @ec_create@ --- *
  87  *
  88  * Arguments:   @ec *p@ = pointer to an elliptic-curve point
  89  *
  90  * Returns:     The argument @p@.
  91  *
  92  * Use:         Initializes a new point.  The initial value is the additive
  93  *              identity (which is universal for all curves).
  94  */
  95
  96 #define EC_INIT { MP_NEW, MP_NEW, MP_NEW }
  97
  98 #define EC_CREATE(p) do {                                               \
  99   ec *_p = (p);                                                         \
 100   _p->x = _p->y = _p->z = MP_NEW;                                       \
 101 } while (0)
 102
 103 extern ec *ec_create(ec */*p*/);
 104
 105 /* --- @ec_destroy@ --- *
 106  *
 107  * Arguments:   @ec *p@ = pointer to an elliptic-curve point
 108  *
 109  * Returns:     ---
 110  *
 111  * Use:         Destroys a point, making it invalid.
 112  */
 113
 114 #define EC_DESTROY(p) do {                                              \
 115   ec *_p = (p);                                                         \
 116   if (!EC_ATINF(_p)) {                                                  \
 117     MP_DROP(_p->x);                                                     \
 118     MP_DROP(_p->y);                                                     \
 119     if (_p->z) MP_DROP(_p->z);                                          \
 120   }                                                                     \
 121 } while (0)
 122
 123 extern void ec_destroy(ec */*p*/);
 124
 125 /* --- @ec_atinf@ --- *
 126  *
 127  * Arguments:   @const ec *p@ = pointer to a point
 128  *
 129  * Returns:     Nonzero if %$p = O$% is the point at infinity, zero
 130  *              otherwise.
 131  */
 132
 133 #define EC_ATINF(p) ((p)->x == MP_NEW || (p)->x == MP_NEWSEC)
 134
 135 extern int ec_atinf(const ec */*p*/);
 136
 137 /* --- @ec_setinf@ --- *
 138  *
 139  * Arguments:   @ec *p@ = pointer to a point
 140  *
 141  * Returns:     The argument @p@.
 142  *
 143  * Use:         Sets the given point to be the point %$O$% at infinity.
 144  */
 145
 146 #define EC_SETINF(p) do {                                               \
 147   ec *_p = (p);                                                         \
 148   if (!EC_ATINF(_p)) {                                                  \
 149     MP_DROP(_p->x);                                                     \
 150     MP_DROP(_p->y);                                                     \
 151     if (_p->z) MP_DROP(_p->z);                                          \
 152     _p->x = _p->y = _p->z = MP_NEW;                                     \
 153     _p->y = MP_NEW;                                                     \
 154     _p->z = MP_NEW;                                                     \
 155   }                                                                     \
 156 } while (0)
 157
 158 extern ec *ec_setinf(ec */*p*/);
 159
 160 /* --- @ec_copy@ --- *
 161  *
 162  * Arguments:   @ec *d@ = pointer to destination point
 163  *              @const ec *p@ = pointer to source point
 164  *
 165  * Returns:     The destination @d@.
 166  *
 167  * Use:         Creates a copy of an elliptic curve point.
 168  */
 169
 170 #define EC_COPY(d, p) do {                                              \
 171   ec *_d = (d);                                                         \
 172   const ec *_p = (p);                                                   \
 173   if (d != p) {                                                         \
 174     EC_DESTROY(d);                                                      \
 175     if (EC_ATINF(p))                                                    \
 176       _d->x = _d->y = _d->z = MP_NEW;                                   \
 177     else {                                                              \
 178       _d->x = _p->x;                                                    \
 179       _d->y = _p->y;                                                    \
 180       _d->z = _p->z;                                                    \
 181     }                                                                   \
 182   }                                                                     \
 183 } while (0)
 184
 185 extern ec *ec_copy(ec */*d*/, const ec */*p*/);
 186
 187 /*----- Interesting arithmetic --------------------------------------------*/
 188
 189 /* --- @ec_denorm@ --- *
 190  *
 191  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 192  *              @ec *d@ = pointer to the destination point
 193  *              @const ec *p@ = pointer to the source point
 194  *
 195  * Returns:     ---
 196  *
 197  * Use:         Denormalizes the given point, converting to internal
 198  *              representations and setting the denominator to 1.
 199  */
 200
 201 extern void ec_denorm(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 202
 203 /* --- @ec_norm@ --- *
 204  *
 205  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 206  *              @ec *d@ = pointer to the destination point
 207  *              @const ec *p@ = pointer to the source point
 208  *
 209  * Returns:     ---
 210  *
 211  * Use:         Normalizes the given point, by dividing through by the
 212  *              denominator and returning to external representation.
 213  */
 214
 215 extern void ec_norm(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 216
 217 /* --- @ec_find@ --- *
 218  *
 219  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 220  *              @ec *d@ = pointer to the destination point
 221  *              @mp *x@ = a possible x-coordinate
 222  *
 223  * Returns:     Zero if OK, nonzero if there isn't a point there.
 224  *
 225  * Use:         Finds a point on an elliptic curve with a given x-coordinate.
 226  */
 227
 228 extern void ec_find(ec_curve */*c*/, ec */*d*/, mp */*x*/);
 229
 230 /* --- @ec_add@ --- *
 231  *
 232  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 233  *              @ec *d@ = pointer to the destination point
 234  *              @const ec *p, *q@ = pointers to the operand points
 235  *
 236  * Returns:     The destination @d@.
 237  *
 238  * Use:         Adds two points on an elliptic curve.
 239  */
 240
 241 extern ec *ec_add(ec_curve */*c*/, ec */*d*/,
 242                   const ec */*p*/, const ec */*q*/);
 243
 244 /* --- @ec_dbl@ --- *
 245  *
 246  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 247  *              @ec *d@ = pointer to the destination point
 248  *              @const ec *p@ = pointer to the operand point
 249  *
 250  * Returns:     The destination @d@.
 251  *
 252  * Use:         Doubles a point on an elliptic curve.
 253  */
 254
 255 extern ec *ec_dbl(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 256
 257 /* --- @ec_mul@ --- *
 258  *
 259  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 260  *              @ec *d@ = pointer to the destination point
 261  *              @const ec *p@ = pointer to the generator point
 262  *              @mp *n@ = integer multiplier
 263  *
 264  * Returns:     The destination @d@.
 265  *
 266  * Use:         Multiplies a point by a scalar, returning %$n p$%.
 267  */
 268
 269 extern ec *ec_mul(ec_curve */*c*/, ec */*d*/, const ec */*p*/, mp */*n*/);
 270
 271 /*----- Standard curve operations -----------------------------------------*/
 272
 273 /* --- @ec_idin@, @ec_idout@ --- *
 274  *
 275  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 276  *              @ec *d@ = pointer to the destination
 277  *              @const ec *p@ = pointer to a source point
 278  *
 279  * Returns:     The destination @d@.
 280  *
 281  * Use:         An identity operation if your curve has no internal
 282  *              representation.  (The field internal representation is still
 283  *              used.)
 284  */
 285
 286 extern ec *ec_idin(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 287 extern ec *ec_idout(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 288
 289 /* --- @ec_projin@, @ec_projout@ --- *
 290  *
 291  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 292  *              @ec *d@ = pointer to the destination
 293  *              @const ec *p@ = pointer to a source point
 294  *
 295  * Returns:     The destination @d@.
 296  *
 297  * Use:         Conversion functions if your curve operations use a
 298  *              projective representation.
 299  */
 300
 301 extern ec *ec_projin(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 302 extern ec *ec_projout(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
 303
 304 /*----- Creating curves ---------------------------------------------------*/
 305
 306 /* --- @ec_prime@ --- *
 307  *
 308  * Arguments:   @field *f@ = the underyling field for this elliptic curve
 309  *              @mp *a, *b@ = the coefficients for this curve
 310  *
 311  * Returns:     A pointer to the curve.
 312  *
 313  * Use:         Creates a curve structure for an elliptic curve defined over
 314  *              a prime field.
 315  */
 316
 317 extern ec_curve *ec_prime(field */*f*/, mp */*a*/, mp */*b*/);
 318
 319 /* --- @ec_bin@ --- *
 320  *
 321  * Arguments:   @field *f@ = the underlying field for this elliptic curve
 322  *              @mp *a, *b@ = the coefficients for this curve
 323  *
 324  * Returns:     A pointer to the curve.
 325  *
 326  * Use:         Creates a curve structure for a non-supersingular elliptic
 327  *              curve defined over a binary field.
 328  */
 329
 330 extern ec_curve *ec_bin(field */*f*/, mp */*a*/, mp */*b*/);
 331
 332 /*----- That's all, folks -------------------------------------------------*/
 333
 334 #ifdef __cplusplus
 335   }
 336 #endif
 337
 338 #endif