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

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