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

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