X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/432c4e184d44704511a5991b80224a87cb1d4613..5278d9afdf1aff9fd6f64073ea42395d756ee58c:/ec-bin.c diff --git a/ec-bin.c b/ec-bin.c index 0efb72f..8ba7354 100644 --- a/ec-bin.c +++ b/ec-bin.c @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: ec-bin.c,v 1.5 2004/03/27 17:54:11 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,52 +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.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 ---------------------------------------------------------*/ @@ -89,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 { @@ -152,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$% */ @@ -179,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); } @@ -211,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); @@ -225,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$% */ @@ -322,6 +291,7 @@ static int eccheck(ec_curve *c, const ec *p) int rc; mp *u, *v; + if (EC_ATINF(p)) return (0); v = F_SQR(f, MP_NEW, p->x); u = F_MUL(f, MP_NEW, v, p->x); v = F_MUL(f, v, v, c->a); @@ -341,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); @@ -350,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); @@ -362,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 @@ -371,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); @@ -382,23 +352,41 @@ 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, 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 = { - ecdestroy, ec_idin, ec_idout, ec_idfix, + "bin", + ecdestroy, ec_stdsamep, ec_idin, ec_idout, ec_idfix, ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck }; static const ec_ops ec_binprojops = { - ecdestroy, ec_projin, ec_projout, ec_projfix, + "binproj", + ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix, ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck }; @@ -413,24 +401,23 @@ int main(int argc, char *argv[]) field *f; ec_curve *c; ec g = EC_INIT, d = EC_INIT; - mp *p, *a, *b, *r; + mp *p, *a, *b, *r, *beta; int i, n = argc == 1 ? 1 : atoi(argv[1]); printf("ec-bin: "); fflush(stdout); - a = MP(1); - b = MP(0x021a5c2c8ee9feb5c4b9a753b7b476b7fd6422ef1f3dd674761fa99d6ac27c8a9a197b272822f6cd57a55aa4f50ae317b13545f); - p = MP(0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001); - r = - MP(661055968790248598951915308032771039828404682964281219284648798304157774827374805208143723762179110965979867288366567526770); + a = MP(0x7ffffffffffffffffffffffffffffffffffffffff); + b = MP(0x6645f3cacf1638e139c6cd13ef61734fbc9e3d9fb); + p = MP(0x800000000000000000000000000000000000000c9); + beta = MP(0x715169c109c612e390d347c748342bcd3b02a0bef); + r = MP(0x040000000000000000000292fe77e70c12a4234c32); - f = field_binpoly(p); + f = field_binnorm(p, beta); c = ec_binproj(f, a, b); - - g.x = MP(0x15d4860d088ddb3496b0c6064756260441cde4af1771d4db01ffe5b34e59703dc255a868a1180515603aeab60794e54bb7996a7); - g.y = MP(0x061b1cfab6be5f32bbfa78324ed106a7636b9c5a7bd198d0158aa4f5488d08f38514f1fdf4b4f40d2181b3681c364ba0273c706); + 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"); @@ -449,7 +436,7 @@ int main(int argc, char *argv[]) ec_destroy(&g); ec_destroycurve(c); F_DESTROY(f); - MP_DROP(p); MP_DROP(a); MP_DROP(b); MP_DROP(r); + MP_DROP(p); MP_DROP(a); MP_DROP(b); MP_DROP(r); MP_DROP(beta); assert(!mparena_count(&mparena_global)); printf("ok\n"); return (0);