git.distorted.org.uk Git - u/mdw/catacomb/blob - ec-prime.c

   1 /* -*-c-*-
   2  *
   3  * $Id: ec-prime.c,v 1.3.4.1 2003/06/10 13:43:53 mdw Exp $
   4  *
   5  * Elliptic curves over prime fields
   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-prime.c,v $
  33  * Revision 1.3.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.3  2003/05/15 23:25:59  mdw
  37  * Make elliptic curve stuff build.
  38  *
  39  * Revision 1.2  2002/01/13 13:48:44  mdw
  40  * Further progress.
  41  *
  42  * Revision 1.1  2001/04/29 18:12:33  mdw
  43  * Prototype version.
  44  *
  45  */
  46
  47 /*----- Header files ------------------------------------------------------*/
  48
  49 #include <mLib/sub.h>
  50
  51 #include "ec.h"
  52
  53 /*----- Data structures ---------------------------------------------------*/
  54
  55 typedef struct ecctx {
  56   ec_curve c;
  57   mp *a, *b;
  58 } ecctx;
  59
  60 /*----- Simple prime curves -----------------------------------------------*/
  61
  62 static const ec_ops ec_primeops;
  63
  64 static ec *ecneg(ec_curve *c, ec *d, const ec *p)
  65 {
  66   EC_COPY(d, p);
  67   d->y = F_NEG(c->f, d->y, d->y);
  68   return (d);
  69 }
  70
  71 static ec *ecdbl(ec_curve *c, ec *d, const ec *a)
  72 {
  73   if (EC_ATINF(a))
  74     EC_SETINF(d);
  75   else if (!MP_LEN(a->y))
  76     EC_COPY(d, a);
  77   else {
  78     field *f = c->f;
  79     ecctx *cc = (ecctx *)c;
  80     mp *lambda;
  81     mp *dy, *dx;
  82
  83     dx = F_SQR(f, MP_NEW, a->x);
  84     dy = F_DBL(f, MP_NEW, a->y);
  85     dx = F_TPL(f, dx, dx);
  86     dx = F_ADD(f, dx, dx, cc->a);
  87     dy = F_INV(f, dy, dy);
  88     lambda = F_MUL(f, MP_NEW, dx, dy);
  89
  90     dx = F_SQR(f, dx, lambda);
  91     dy = F_DBL(f, dy, a->x);
  92     dx = F_SUB(f, dx, dx, dy);
  93     dy = F_SUB(f, dy, a->x, dx);
  94     dy = F_MUL(f, dy, lambda, dy);
  95     dy = F_SUB(f, dy, dy, a->y);
  96
  97     EC_DESTROY(d);
  98     d->x = dx;
  99     d->y = dy;
 100     d->z = 0;
 101     MP_DROP(lambda);
 102   }
 103   return (d);
 104 }
 105
 106 static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b)
 107 {
 108   if (a == b)
 109     ecdbl(c, d, a);
 110   else if (EC_ATINF(a))
 111     EC_COPY(d, b);
 112   else if (EC_ATINF(b))
 113     EC_COPY(d, a);
 114   else {
 115     field *f = c->f;
 116     mp *lambda;
 117     mp *dy, *dx;
 118
 119     if (!MP_EQ(a->x, b->x)) {
 120       dy = F_SUB(f, MP_NEW, a->y, b->y);
 121       dx = F_SUB(f, MP_NEW, a->x, b->x);
 122       dx = F_INV(f, dx, dx);
 123       lambda = F_MUL(f, MP_NEW, dy, dx);
 124     } else if (!MP_LEN(a->y) || !MP_EQ(a->y, b->y)) {
 125       EC_SETINF(d);
 126       return (d);
 127     } else {
 128       ecctx *cc = (ecctx *)c;
 129       dx = F_SQR(f, MP_NEW, a->x);
 130       dx = F_TPL(f, dx, dx);
 131       dx = F_ADD(f, dx, dx, cc->a);
 132       dy = F_DBL(f, MP_NEW, a->y);
 133       dy = F_INV(f, dy, dy);
 134       lambda = F_MUL(f, MP_NEW, dx, dy);
 135     }
 136
 137     dx = F_SQR(f, dx, lambda);
 138     dx = F_SUB(f, dx, dx, a->x);
 139     dx = F_SUB(f, dx, dx, b->x);
 140     dy = F_SUB(f, dy, b->x, dx);
 141     dy = F_MUL(f, dy, lambda, dy);
 142     dy = F_SUB(f, dy, dy, b->y);
 143
 144     EC_DESTROY(d);
 145     d->x = dx;
 146     d->y = dy;
 147     d->z = 0;
 148     MP_DROP(lambda);
 149   }
 150   return (d);
 151 }
 152
 153 static void ecdestroy(ec_curve *c)
 154 {
 155   ecctx *cc = (ecctx *)c;
 156   MP_DROP(cc->a);
 157   MP_DROP(cc->b);
 158   DESTROY(cc);
 159 }
 160
 161 /* --- @ec_prime@, @ec_primeproj@ --- *
 162  *
 163  * Arguments:   @field *f@ = the underlying field for this elliptic curve
 164  *              @mp *a, *b@ = the coefficients for this curve
 165  *
 166  * Returns:     A pointer to the curve.
 167  *
 168  * Use:         Creates a curve structure for an elliptic curve defined over
 169  *              a prime field.  The @primeproj@ variant uses projective
 170  *              coordinates, which can be a win.
 171  */
 172
 173 extern ec_curve *ec_prime(field *f, mp *a, mp *b)
 174 {
 175   ecctx *cc = CREATE(ecctx);
 176   cc->c.ops = &ec_primeops;
 177   cc->c.f = f;
 178   cc->a = F_IN(f, MP_NEW, a);
 179   cc->b = F_IN(f, MP_NEW, b);
 180   return (&cc->c);
 181 }
 182
 183 static const ec_ops ec_primeops = {
 184   ecdestroy, ec_idin, ec_idout, 0, ecneg, ecadd, ec_stdsub, ecdbl
 185 };
 186
 187 /*----- Test rig ----------------------------------------------------------*/
 188
 189 #ifdef TEST_RIG
 190
 191 #define MP(x) mp_readstring(MP_NEW, #x, 0, 0)
 192
 193 int main(void)
 194 {
 195   field *f;
 196   ec_curve *c;
 197   ec g = EC_INIT, d = EC_INIT;
 198   mp *p, *a, *b, *r;
 199
 200   printf("ec-prime: ");
 201   fflush(stdout);
 202   a = MP(-3);
 203   b = MP(0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1);
 204   p = MP(6277101735386680763835789423207666416083908700390324961279);
 205   r = MP(6277101735386680763835789423176059013767194773182842284080);
 206
 207   f = field_prime(p);
 208   c = ec_prime(f, a, b);
 209
 210   g.x = MP(0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012);
 211   g.y = MP(0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811);
 212
 213   ec_mul(c, &d, &g, r);
 214   if (EC_ATINF(&d)) {
 215     fprintf(stderr, "zero too early\n");
 216     return (1);
 217   }
 218   ec_add(c, &d, &d, &g);
 219   if (!EC_ATINF(&d)) {
 220     fprintf(stderr, "didn't reach zero\n");
 221     MP_EPRINT("d.x", d.x);
 222     MP_EPRINT("d.y", d.y);
 223     return (1);
 224   }
 225
 226   ec_destroy(&d);
 227   ec_destroy(&g);
 228   ec_destroycurve(c);
 229   F_DESTROY(f);
 230   MP_DROP(p); MP_DROP(a); MP_DROP(b); MP_DROP(r);
 231   assert(!mparena_count(&mparena_global));
 232   printf("ok\n");
 233   return (0);
 234 }
 235
 236 #endif
 237
 238 /*----- That's all, folks -------------------------------------------------*/