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

   1 /* -*-c-*-
   2  *
   3  * $Id: ec-prime.c,v 1.2 2002/01/13 13:48:44 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.2  2002/01/13 13:48:44  mdw
  34  * Further progress.
  35  *
  36  * Revision 1.1  2001/04/29 18:12:33  mdw
  37  * Prototype version.
  38  *
  39  */
  40
  41 /*----- Header files ------------------------------------------------------*/
  42
  43 #include "ec.h"
  44
  45 /*----- Data structures ---------------------------------------------------*/
  46
  47 typedef struct ecctx {
  48   ec_curve c;
  49   mp *a, *b;
  50 } ecctx;
  51
  52 /*----- Main code ---------------------------------------------------------*/
  53
  54 static ec *ecneg(ec_cuvrve *c, ec *d, const ec *p)
  55 {
  56   EC_COPY(d, p);
  57   d->y = F_NEG(c->f, d->y, d->y);
  58   return (d);
  59 }
  60
  61 static ec *ecdbl(ec_curve *c, ec *d, const ec *a)
  62 {
  63   if (EC_ATINF(a))
  64     EC_SETINF(d);
  65   else if (!MP_LEN(a->y))
  66     EC_COPY(d, a);
  67   else {
  68     field *f = c->f;
  69     ecctx *cc = (ecctx *)c;
  70     mp *lambda;
  71     mp *dy, *dx;
  72
  73     dx = F_SQR(f, MP_NEW, a->x);
  74     dy = F_DBL(f, MP_NEW, a->y);
  75     dx = F_TPL(f, dx, dx);
  76     dx = F_ADD(f, dx, dx, cc->a);
  77     dy = F_INV(f, dy, dy);
  78     lambda = F_MUL(d, MP_NEW, dx, dy);
  79
  80     dx = F_SQR(f, dx, lambda);
  81     dy = F_DBL(d, dy, a->x);
  82     dx = F_SUB(f, dx, dx, dy);
  83     dy = F_SUB(f, dy, a->x, dx);
  84     dy = F_MUL(f, dy, lambda, dy);
  85     dy = F_SUB(f, dy, dy, a->y);
  86
  87     EC_DESTROY(d);
  88     d->x = dx;
  89     d->y = dy;
  90     d->z = 0;
  91     MP_DROP(lambda);
  92   }
  93   return (d);
  94 }
  95
  96 static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b)
  97 {
  98   if (a == b)
  99     ecdbl(c, d, a);
 100   else if (EC_ATINF(a))
 101     EC_COPY(d, b);
 102   else if (EC_ATINF(b))
 103     EC_COPY(d, a);
 104   else {
 105     field *f = c->f;
 106     mp *lambda;
 107     mp *dy, *dx;
 108
 109     if (!MP_EQ(a->x, b->x)) {
 110       dy = F_SUB(f, MP_NEW, a->y, b->y);
 111       dx = F_SUB(f, MP_NEW, a->x, b->x);
 112       dx = F_INV(f, dx, dx);
 113       lambda = F_MUL(f, MP_NEW, dy, dx);
 114     } else if (!MP_LEN(a->y) || !MP_EQ(a->y, b->y)) {
 115       EC_SETINF(d);
 116       return (d);
 117     } else {
 118       ecctx *cc = (ecctx *)c;
 119       dx = F_SQR(f, MP_NEW, a->x);
 120       dx = F_TPL(f, dx, dx);
 121       dx = F_ADD(f, dx, dx, cc->a);
 122       dy = F_DBL(f, MP_NEW, a->y);
 123       dy = F_INV(f, dy, dy);
 124       lambda = F_MUL(d, MP_NEW, dx, dy);
 125     }
 126
 127     dx = F_SQR(f, dx, lambda);
 128     dx = F_SUB(f, dx, dx, a->x);
 129     dx = F_SUB(f, dx, dx, b->x);
 130     dy = F_SUB(f, dy, b->x, dx);
 131     dy = F_MUL(f, dy, lambda, dy);
 132     dy = F_SUB(f, dy, dy, b->y);
 133
 134     EC_DESTROY(d);
 135     d->x = dx;
 136     d->y = dy;
 137     d->z = 0;
 138     MP_DROP(lambda);
 139   }
 140   return (d);
 141 }
 142
 143 /*----- That's all, folks -------------------------------------------------*/