/* -*-c-*-
*
- * $Id: ec-bin.c,v 1.4 2004/03/23 15:19:32 mdw Exp $
+ * $Id: ec-bin.c,v 1.7 2004/04/01 21:28:41 mdw Exp $
*
* Arithmetic for elliptic curves over binary fields
*
/*----- 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.
*
typedef struct ecctx {
ec_curve c;
- mp *a, *b;
mp *bb;
} ecctx;
static ec *ecfind(ec_curve *c, ec *d, mp *x)
{
field *f = c->f;
- ecctx *cc = (ecctx *)c;
mp *y, *u, *v;
if (F_ZEROP(f, x))
- y = F_SQRT(f, MP_NEW, cc->b);
+ y = F_SQRT(f, MP_NEW, c->b);
else {
u = F_SQR(f, MP_NEW, x); /* %$x^2$% */
- y = F_MUL(f, MP_NEW, u, cc->a); /* %$a x^2$% */
- y = F_ADD(f, y, y, cc->b); /* %$a x^2 + b$% */
+ y = F_MUL(f, MP_NEW, u, c->a); /* %$a x^2$% */
+ y = F_ADD(f, y, y, c->b); /* %$a x^2 + b$% */
v = F_MUL(f, MP_NEW, u, x); /* %$x^3$% */
y = F_ADD(f, y, y, v); /* %$A = x^3 + a x^2 + b$% */
if (!F_ZEROP(f, y)) {
EC_SETINF(d);
else {
field *f = c->f;
- ecctx *cc = (ecctx *)c;
mp *lambda;
mp *dx, *dy;
dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */
dx = F_ADD(f, dx, dx, lambda); /* %$\lambda^2 + \lambda$% */
- dx = F_ADD(f, dx, dx, cc->a); /* %$x' = a + \lambda^2 + \lambda$% */
+ dx = F_ADD(f, dx, dx, c->a); /* %$x' = a + \lambda^2 + \lambda$% */
dy = F_ADD(f, MP_NEW, a->x, dx); /* %$ x + x' $% */
dy = F_MUL(f, dy, dy, lambda); /* %$ (x + x') \lambda$% */
EC_COPY(d, a);
else {
field *f = c->f;
- ecctx *cc = (ecctx *)c;
mp *lambda;
mp *dx, *dy;
dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */
dx = F_ADD(f, dx, dx, lambda); /* %$\lambda^2 + \lambda$% */
- dx = F_ADD(f, dx, dx, cc->a); /* %$a + \lambda^2 + \lambda$% */
+ 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$% */
dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */
dx = F_ADD(f, dx, dx, lambda); /* %$\lambda^2 + \lambda$% */
- dx = F_ADD(f, dx, dx, cc->a); /* %$x' = a + \lambda^2 + \lambda$% */
+ dx = F_ADD(f, dx, dx, c->a); /* %$x' = a + \lambda^2 + \lambda$% */
dy = MP_NEW;
}
EC_COPY(d, a);
else {
field *f = c->f;
- ecctx *cc = (ecctx *)c;
mp *dx, *dy, *dz, *u, *uu, *v, *t, *s, *ss, *r, *w, *l;
dz = F_SQR(f, MP_NEW, b->z); /* %$z_1^2$% */
t = F_ADD(f, t, r, dz); /* %$t = r + z'$% */
uu = F_SQR(f, MP_NEW, dz); /* %$z'^2$% */
- dx = F_MUL(f, MP_NEW, uu, cc->a); /* %$a z'^2$% */
+ dx = F_MUL(f, MP_NEW, uu, c->a); /* %$a z'^2$% */
uu = F_MUL(f, uu, t, r); /* %$t r$% */
dx = F_ADD(f, dx, dx, uu); /* %$a z'^2 + t r$% */
r = F_SQR(f, r, w); /* %$w^2$% */
static int eccheck(ec_curve *c, const ec *p)
{
- ecctx *cc = (ecctx *)c;
field *f = c->f;
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, cc->a);
+ v = F_MUL(f, v, v, c->a);
u = F_ADD(f, u, u, v);
- u = F_ADD(f, u, u, cc->b);
+ u = F_ADD(f, u, u, c->b);
v = F_MUL(f, v, p->x, p->y);
u = F_ADD(f, u, u, v);
v = F_SQR(f, v, p->y);
static void ecdestroy(ec_curve *c)
{
ecctx *cc = (ecctx *)c;
- MP_DROP(cc->a);
- MP_DROP(cc->b);
+ MP_DROP(cc->c.a);
+ MP_DROP(cc->c.b);
if (cc->bb) MP_DROP(cc->bb);
DESTROY(cc);
}
ecctx *cc = CREATE(ecctx);
cc->c.ops = &ec_binops;
cc->c.f = f;
- cc->a = F_IN(f, MP_NEW, a);
- cc->b = F_IN(f, MP_NEW, b);
+ cc->c.a = F_IN(f, MP_NEW, a);
+ cc->c.b = F_IN(f, MP_NEW, b);
cc->bb = 0;
return (&cc->c);
}
ecctx *cc = CREATE(ecctx);
cc->c.ops = &ec_binprojops;
cc->c.f = f;
- cc->a = F_IN(f, MP_NEW, a);
- cc->b = F_IN(f, MP_NEW, b);
- cc->bb = F_SQRT(f, MP_NEW, b);
+ 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);
return (&cc->c);
}
static const ec_ops ec_binops = {
- ecdestroy, ec_idin, ec_idout, ec_idfix,
+ 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,
+ ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
};
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++) {
ec_mul(c, &d, &g, r);
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);