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

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