X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/4edc47b89bc56cd4041fdb0f4e8e892acd589ed8..6a7dce9165a4a707382e49877334353618fcad9a:/ec-bin.c diff --git a/ec-bin.c b/ec-bin.c index db1bebf..8ba7354 100644 --- a/ec-bin.c +++ b/ec-bin.c @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: ec-bin.c,v 1.7 2004/04/01 21:28:41 mdw Exp $ + * $Id$ * * Arithmetic for elliptic curves over binary fields * * (c) 2004 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of Catacomb. * @@ -15,64 +15,24 @@ * it under the terms of the GNU Library General Public License as * published by the Free Software Foundation; either version 2 of the * License, or (at your option) any later version. - * + * * Catacomb is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Library General Public License for more details. - * + * * You should have received a copy of the GNU Library General Public * License along with Catacomb; if not, write to the Free * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, * MA 02111-1307, USA. */ -/*----- Revision history --------------------------------------------------* - * - * $Log: ec-bin.c,v $ - * Revision 1.7 2004/04/01 21:28:41 mdw - * Normal basis support (translates to poly basis internally). Rewrite - * EC and prime group table generators in awk, so that they can reuse data - * for repeated constants. - * - * Revision 1.6 2004/04/01 12:50:09 mdw - * Add cyclic group abstraction, with test code. Separate off exponentation - * functions for better static linking. Fix a buttload of bugs on the way. - * Generally ensure that negative exponents do inversion correctly. Add - * table of standard prime-field subgroups. (Binary field subgroups are - * currently unimplemented but easy to add if anyone ever finds a good one.) - * - * Revision 1.5 2004/03/27 17:54:11 mdw - * Standard curves and curve checking. - * - * Revision 1.4 2004/03/23 15:19:32 mdw - * Test elliptic curves more thoroughly. - * - * Revision 1.3 2004/03/22 02:19:09 mdw - * Rationalise the sliding-window threshold. Drop guarantee that right - * arguments to EC @add@ are canonical, and fix up projective implementations - * to cope. - * - * Revision 1.2 2004/03/21 22:52:06 mdw - * Merge and close elliptic curve branch. - * - * Revision 1.1.2.1 2004/03/21 22:39:46 mdw - * Elliptic curves on binary fields work. - * - */ - /*----- Header files ------------------------------------------------------*/ #include #include "ec.h" - -/*----- Data structures ---------------------------------------------------*/ - -typedef struct ecctx { - ec_curve c; - mp *bb; -} ecctx; +#include "ec-guts.h" /*----- Main code ---------------------------------------------------------*/ @@ -101,7 +61,7 @@ static ec *ecfind(ec_curve *c, ec *d, mp *x) { field *f = c->f; mp *y, *u, *v; - + if (F_ZEROP(f, x)) y = F_SQRT(f, MP_NEW, c->b); else { @@ -164,7 +124,7 @@ static ec *ecprojdbl(ec_curve *c, ec *d, const ec *a) EC_SETINF(d); else { field *f = c->f; - ecctx *cc = (ecctx *)c; + ecctx_bin *cc = (ecctx_bin *)c; mp *dx, *dy, *dz, *u, *v; dy = F_SQR(f, MP_NEW, a->z); /* %$z^2$% */ @@ -191,9 +151,6 @@ static ec *ecprojdbl(ec_curve *c, ec *d, const ec *a) d->z = dz; MP_DROP(u); MP_DROP(v); - assert(!(d->x->f & MP_DESTROYED)); - assert(!(d->y->f & MP_DESTROYED)); - assert(!(d->z->f & MP_DESTROYED)); } return (d); } @@ -223,7 +180,7 @@ static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b) dx = F_ADD(f, dx, dx, c->a); /* %$a + \lambda^2 + \lambda$% */ dx = F_ADD(f, dx, dx, a->x); /* %$a + \lambda^2 + \lambda + x_0$% */ dx = F_ADD(f, dx, dx, b->x); - /* %$x' = a + \lambda^2 + \lambda + x_0 + x_1$% */ + /* %$x' = a + \lambda^2 + \lambda + x_0 + x_1$% */ } else if (!MP_EQ(a->y, b->y) || F_ZEROP(f, a->x)) { EC_SETINF(d); return (d); @@ -237,7 +194,7 @@ static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b) dx = F_ADD(f, dx, dx, c->a); /* %$x' = a + \lambda^2 + \lambda$% */ dy = MP_NEW; } - + dy = F_ADD(f, dy, a->x, dx); /* %$ x + x' $% */ dy = F_MUL(f, dy, dy, lambda); /* %$ (x + x') \lambda$% */ dy = F_ADD(f, dy, dy, a->y); /* %$ (x + x') \lambda + y$% */ @@ -354,7 +311,7 @@ static int ecprojcheck(ec_curve *c, const ec *p) { ec t = EC_INIT; int rc; - + c->ops->fix(c, &t, p); rc = eccheck(c, &t); EC_DESTROY(&t); @@ -363,7 +320,7 @@ static int ecprojcheck(ec_curve *c, const ec *p) static void ecdestroy(ec_curve *c) { - ecctx *cc = (ecctx *)c; + ecctx_bin *cc = (ecctx_bin *)c; MP_DROP(cc->c.a); MP_DROP(cc->c.b); if (cc->bb) MP_DROP(cc->bb); @@ -375,7 +332,7 @@ static void ecdestroy(ec_curve *c) * Arguments: @field *f@ = the underlying field for this elliptic curve * @mp *a, *b@ = the coefficients for this curve * - * Returns: A pointer to the curve. + * Returns: A pointer to the curve, or null. * * Use: Creates a curve structure for an elliptic curve defined over * a binary field. The @binproj@ variant uses projective @@ -384,7 +341,7 @@ static void ecdestroy(ec_curve *c) ec_curve *ec_bin(field *f, mp *a, mp *b) { - ecctx *cc = CREATE(ecctx); + ecctx_bin *cc = CREATE(ecctx_bin); cc->c.ops = &ec_binops; cc->c.f = f; cc->c.a = F_IN(f, MP_NEW, a); @@ -395,22 +352,40 @@ ec_curve *ec_bin(field *f, mp *a, mp *b) ec_curve *ec_binproj(field *f, mp *a, mp *b) { - ecctx *cc = CREATE(ecctx); + ecctx_bin *cc = CREATE(ecctx_bin); + int i; + mp *c, *d; + cc->c.ops = &ec_binprojops; cc->c.f = f; cc->c.a = F_IN(f, MP_NEW, a); cc->c.b = F_IN(f, MP_NEW, b); - cc->bb = F_SQRT(f, MP_NEW, cc->c.b); - cc->bb = F_SQRT(f, cc->bb, cc->bb); + + c = MP_COPY(cc->c.b); + for (i = 0; i < f->nbits - 2; i++) + c = F_SQR(f, c, c); + d = F_SQR(f, MP_NEW, c); d = F_SQR(f, d, d); + if (!MP_EQ(d, cc->c.b)) { + MP_DROP(c); + MP_DROP(d); + MP_DROP(cc->c.a); + MP_DROP(cc->c.b); + DESTROY(cc); + return (0); + } + cc->bb = c; + MP_DROP(d); return (&cc->c); } static const ec_ops ec_binops = { + "bin", ecdestroy, ec_stdsamep, ec_idin, ec_idout, ec_idfix, ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck }; static const ec_ops ec_binprojops = { + "binproj", ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix, ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck }; @@ -442,7 +417,7 @@ int main(int argc, char *argv[]) g.x = MP(0x0311103c17167564ace77ccb09c681f886ba54ee8); g.y = MP(0x333ac13c6447f2e67613bf7009daf98c87bb50c7f); - for (i = 0; i < n; i++) { + for (i = 0; i < n; i++) { ec_mul(c, &d, &g, r); if (EC_ATINF(&d)) { fprintf(stderr, "zero too early\n");