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

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