/* -*-c-*-
*
- * $Id: ec-bin.c,v 1.2 2004/03/21 22:52:06 mdw Exp $
+ * $Id: ec-bin.c,v 1.4 2004/03/23 15:19:32 mdw Exp $
*
* Arithmetic for elliptic curves over binary fields
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec-bin.c,v $
+ * 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.
*
static ec *ecfind(ec_curve *c, ec *d, mp *x)
{
- /* write me */
- return (0);
+ 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);
+ 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$% */
+ 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)) {
+ u = F_INV(f, u, u); /* %$x^{-2}$% */
+ v = F_MUL(f, v, u, y); /* %$B = A x^{-2} = x + a + b x^{-2}$% */
+ y = F_QUADSOLVE(f, y, v); /* %$z^2 + z = B$% */
+ if (y) y = F_MUL(f, y, y, x); /* %$y = z x$% */
+ }
+ MP_DROP(u);
+ MP_DROP(v);
+ }
+ if (!y) return (0);
+ EC_DESTROY(d);
+ d->x = MP_COPY(x);
+ d->y = y;
+ d->z = MP_COPY(f->one);
+ return (d);
}
static ec *ecdbl(ec_curve *c, ec *d, const ec *a)
u = F_ADD(f, u, u, v);
v = F_SQR(f, v, p->y);
u = F_ADD(f, u, u, v);
- rc = F_ZEROP(f, u);
+ rc = F_ZEROP(f, u) ? 0 : -1;
mp_drop(u);
mp_drop(v);
return (rc);
static const ec_ops ec_binops = {
ecdestroy, ec_idin, ec_idout, ec_idfix,
- 0, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
+ ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
};
static const ec_ops ec_binprojops = {
ecdestroy, ec_projin, ec_projout, ec_projfix,
- 0, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
+ ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
};
/*----- Test rig ----------------------------------------------------------*/
printf("ec-bin: ");
fflush(stdout);
a = MP(1);
- b = MP(0x066647ede6c332c7f8c0923bb58213b333b20e9ce4281fe115f7d8f90ad);
- p = MP(0x20000000000000000000000000000000000000004000000000000000001);
+ b = MP(0x021a5c2c8ee9feb5c4b9a753b7b476b7fd6422ef1f3dd674761fa99d6ac27c8a9a197b272822f6cd57a55aa4f50ae317b13545f);
+ p = MP(0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001);
r =
- MP(6901746346790563787434755862277025555839812737345013555379383634485462);
+ MP(661055968790248598951915308032771039828404682964281219284648798304157774827374805208143723762179110965979867288366567526770);
f = field_binpoly(p);
c = ec_binproj(f, a, b);
- g.x = MP(0x0fac9dfcbac8313bb2139f1bb755fef65bc391f8b36f8f8eb7371fd558b);
- g.y = MP(0x1006a08a41903350678e58528bebf8a0beff867a7ca36716f7e01f81052);
+ g.x = MP(0x15d4860d088ddb3496b0c6064756260441cde4af1771d4db01ffe5b34e59703dc255a868a1180515603aeab60794e54bb7996a7);
+ g.y = MP(0x061b1cfab6be5f32bbfa78324ed106a7636b9c5a7bd198d0158aa4f5488d08f38514f1fdf4b4f40d2181b3681c364ba0273c706);
for (i = 0; i < n; i++) {
ec_mul(c, &d, &g, r);
fprintf(stderr, "didn't reach zero\n");
MP_EPRINTX("d.x", d.x);
MP_EPRINTX("d.y", d.y);
- MP_EPRINTX("d.z", d.y);
return (1);
}
ec_destroy(&d);