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

   1 /* -*-c-*-
   2  *
   3  * $Id: ec.c,v 1.3 2002/01/13 13:48: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.c,v $
  33  * Revision 1.3  2002/01/13 13:48:44  mdw
  34  * Further progress.
  35  *
  36  * Revision 1.2  2001/05/07 17:29:44  mdw
  37  * Treat projective coordinates as an internal representation.  Various
  38  * minor interface changes.
  39  *
  40  * Revision 1.1  2001/04/29 18:12:33  mdw
  41  * Prototype version.
  42  *
  43  */
  44
  45 /*----- Header files ------------------------------------------------------*/
  46
  47 #include "ec.h"
  48 #include "ec-exp.h"
  49
  50 /*----- Trivial wrappers --------------------------------------------------*/
  51
  52 /* --- @ec_create@ --- *
  53  *
  54  * Arguments:   @ec *p@ = pointer to an elliptic-curve point
  55  *
  56  * Returns:     ---
  57  *
  58  * Use:         Initializes a new point.  The initial value is the additive
  59  *              identity (which is universal for all curves).
  60  */
  61
  62 void ec_create(ec *p) { EC_CREATE(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:     ---
  90  *
  91  * Use:         Sets the given point to be the point %$O$% at infinity.
  92  */
  93
  94 void ec_setinf(ec *p) { EC_SETINF(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:     ---
 102  *
 103  * Use:         Creates a copy of an elliptic curve point.
 104  */
 105
 106 void ec_copy(ec *d, const ec *p) { EC_COPY(d, p); }
 107
 108 /*----- Standard curve operations -----------------------------------------*/
 109
 110 /* --- @ec_idin@, @ec_idout@ --- *
 111  *
 112  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 113  *              @ec *d@ = pointer to the destination
 114  *              @const ec *p@ = pointer to a source point
 115  *
 116  * Returns:     The destination @d@.
 117  *
 118  * Use:         An identity operation if your curve has no internal
 119  *              representation.  (The field internal representation is still
 120  *              used.)
 121  */
 122
 123 ec *ec_idin(ec_curve *c, ec *d, const ec *p)
 124 {
 125   if (EC_ATINF(p))
 126     EC_SETINF(d);
 127   else {
 128     field *f = c->f;
 129     d->x = F_IN(f, d->x, p->x);
 130     d->y = F_IN(f, d->y, p->y);
 131     mp_drop(d->z); d->z = 0;
 132   }
 133   return (d);
 134 }
 135
 136 ec *ec_idout(ec_curve *c, ec *d, const ec *p)
 137 {
 138   if (EC_ATINF(p))
 139     EC_SETINF(d);
 140   else {
 141     field *f = c->f;
 142     d->x = F_OUT(f, d->x, p->x);
 143     d->y = F_OUT(f, d->y, p->y);
 144     mp_drop(d->z); d->z = 0;
 145   }
 146   return (d);
 147 }
 148
 149 /* --- @ec_projin@, @ec_projout@ --- *
 150  *
 151  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 152  *              @ec *d@ = pointer to the destination
 153  *              @const ec *p@ = pointer to a source point
 154  *
 155  * Returns:     The destination @d@.
 156  *
 157  * Use:         Conversion functions if your curve operations use a
 158  *              projective representation.
 159  */
 160
 161 ec *ec_projin(ec_curve *c, ec *d, const ec *p)
 162 {
 163   if (EC_ATINF(p))
 164     EC_SETINF(d);
 165   else {
 166     field *f = c->f;
 167     d->x = F_IN(f, d->x, p->x);
 168     d->y = F_IN(f, d->y, p->y);
 169     mp_drop(d->z); d->z = MP_COPY(f->one);
 170   }
 171   return (d);
 172 }
 173
 174 ec *ec_projout(ec_curve *c, ec *d, const ec *p)
 175 {
 176   if (EC_ATINF(p))
 177     EC_SETINF(d);
 178   else {
 179     mp *x, *y, *z;
 180     field *f = c->f;
 181     z = F_INV(f, MP_NEW, p->z);
 182     x = F_MUL(f, d->x, p->x, z);
 183     y = F_MUL(f, d->y, p->y, z);
 184     mp_drop(z);
 185     mp_drop(d->z);
 186     d->x = F_OUT(f, x, x);
 187     d->y = F_OUT(f, y, y);
 188     d->z = 0;
 189   }
 190   return (d);
 191 }
 192
 193 /* --- @ec_stdsub@ --- *
 194  *
 195  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 196  *              @ec *d@ = pointer to the destination
 197  *              @const ec *a, *b@ = the operand points
 198  *
 199  * Returns:     The destination @d@.
 200  *
 201  * Use:         Standard point subtraction operation, in terms of negation
 202  *              and addition.  This isn't as efficient as a ready-made
 203  *              subtraction operator.
 204  */
 205
 206 ec *ec_stdsub(ec_curve *c, ec *d, const ec *a, const ec *b)
 207 {
 208   ec t = EC_INIT;
 209   EC_NEG(c, &t, b);
 210   EC_SUB(c, d, a, &t);
 211   EC_DESTROY(&t);
 212   return (d);
 213 }
 214
 215 /*----- Real arithmetic ---------------------------------------------------*/
 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 ec *ec_find(ec_curve *c, ec *d, mp *x)
 229 {
 230   x = F_IN(c->f, MP_NEW, x);
 231   if ((d = EC_FIND(c, d, x)) != 0)
 232     EC_OUT(c, d, d);
 233   mp_drop(x);
 234   return (d);
 235 }
 236
 237 /* --- @ec_add@ --- *
 238  *
 239  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 240  *              @ec *d@ = pointer to the destination point
 241  *              @const ec *p, *q@ = pointers to the operand points
 242  *
 243  * Returns:     ---
 244  *
 245  * Use:         Adds two points on an elliptic curve.
 246  */
 247
 248 ec *ec_add(ec_curve *c, ec *d, const ec *p, const ec *q)
 249 {
 250   ec pp = EC_INIT, qq = EC_INIT;
 251   EC_IN(c, &pp, p);
 252   EC_IN(c, &qq, q);
 253   EC_ADD(c, d, &pp, &qq);
 254   EC_OUT(c, d, d);
 255   EC_DESTROY(&pp);
 256   EC_DESTROY(&qq);
 257   return (d);
 258 }
 259
 260 /* --- @ec_dbl@ --- *
 261  *
 262  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 263  *              @ec *d@ = pointer to the destination point
 264  *              @const ec *p@ = pointer to the operand point
 265  *
 266  * Returns:     ---
 267  *
 268  * Use:         Doubles a point on an elliptic curve.
 269  */
 270
 271 ec *ec_dbl(ec_curve *c, ec *d, const ec *p)
 272 {
 273   EC_IN(c, d, p);
 274   EC_DBL(c, d, d);
 275   return (EC_OUT(c, d, d));
 276 }
 277
 278 /* --- @ec_imul@, @ec_mul@ --- *
 279  *
 280  * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 281  *              @ec *d@ = pointer to the destination point
 282  *              @const ec *p@ = pointer to the generator point
 283  *              @mp *n@ = integer multiplier
 284  *
 285  * Returns:     The destination @d@.
 286  *
 287  * Use:         Multiplies a point by a scalar, returning %$n p$%.  The
 288  *              @imul@ variant uses internal representations for argument
 289  *              and result.
 290  */
 291
 292 ec *ec_imul(ec_curve *c, ec *d, const ec *p, mp *n)
 293 {
 294   ec t = EC_INIT;
 295
 296   EC_COPY(&t, p);
 297   if (t.x && (n->f & MP_BURN))
 298     t.x->f |= MP_BURN;
 299   MP_SHRINK(n);
 300   EC_SETINF(d);
 301   if (MP_LEN(n) == 0)
 302     ;
 303   else if (MP_LEN(n) < EXP_THRESH)
 304     EXP_SIMPLE(&d, t, n);
 305   else
 306     EXP_WINDOW(&d, t, n);
 307   return (d);
 308 }
 309
 310 ec *ec_mul(ec_curve *c, ec *d, const ec *p, mp *n)
 311 {
 312   EC_IN(c, d, p);
 313   ec_imul(c, d, d, n);
 314   return (EC_OUT(c, d, d));
 315 }
 316
 317 /*----- That's all, folks -------------------------------------------------*/