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

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