/* -*-c-*-
*
- * $Id: ec-bin.c,v 1.4 2004/03/23 15:19:32 mdw Exp $
+ * $Id: ec-bin.c,v 1.6 2004/04/01 12:50:09 mdw Exp $
*
* Arithmetic for elliptic curves over binary fields
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec-bin.c,v $
+ * 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->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);
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
};