X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/dbfee00a86609283c4633df870692be3db9bc5e4..8823192f6413bed15cfa884ed3a3cbbb97885657:/ec-prime.c diff --git a/ec-prime.c b/ec-prime.c index b2bfd52..14e4c16 100644 --- a/ec-prime.c +++ b/ec-prime.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: ec-prime.c,v 1.3.4.1 2003/06/10 13:43:53 mdw Exp $ + * $Id: ec-prime.c,v 1.3.4.2 2004/03/20 00:13:31 mdw Exp $ * * Elliptic curves over prime fields * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: ec-prime.c,v $ + * Revision 1.3.4.2 2004/03/20 00:13:31 mdw + * Projective coordinates for prime curves + * * Revision 1.3.4.1 2003/06/10 13:43:53 mdw * Simple (non-projective) curves over prime fields now seem to work. * @@ -59,7 +62,7 @@ typedef struct ecctx { /*----- Simple prime curves -----------------------------------------------*/ -static const ec_ops ec_primeops; +static const ec_ops ec_primeops, ec_primeprojops, ec_primeprojxops; static ec *ecneg(ec_curve *c, ec *d, const ec *p) { @@ -68,11 +71,33 @@ static ec *ecneg(ec_curve *c, ec *d, const ec *p) return (d); } +static ec *ecfind(ec_curve *c, ec *d, mp *x) +{ + mp *p, *q; + ecctx *cc = (ecctx *)c; + field *f = c->f; + + q = F_SQR(f, MP_NEW, x); + p = F_MUL(f, MP_NEW, x, q); + q = F_MUL(f, q, x, cc->a); + p = F_ADD(f, p, p, q); + p = F_ADD(f, p, p, cc->b); + MP_DROP(q); + p = F_SQRT(f, p, p); + if (!p) + return (0); + EC_DESTROY(d); + d->x = MP_COPY(x); + d->y = p; + d->z = MP_COPY(f->one); + return (d); +} + static ec *ecdbl(ec_curve *c, ec *d, const ec *a) { if (EC_ATINF(a)) EC_SETINF(d); - else if (!MP_LEN(a->y)) + else if (F_ZEROP(c->f, a->y)) EC_COPY(d, a); else { field *f = c->f; @@ -80,19 +105,19 @@ static ec *ecdbl(ec_curve *c, ec *d, const ec *a) mp *lambda; mp *dy, *dx; - dx = F_SQR(f, MP_NEW, a->x); - dy = F_DBL(f, MP_NEW, a->y); - dx = F_TPL(f, dx, dx); - dx = F_ADD(f, dx, dx, cc->a); - dy = F_INV(f, dy, dy); - lambda = F_MUL(f, MP_NEW, dx, dy); + dx = F_SQR(f, MP_NEW, a->x); /* %$x^2$% */ + dy = F_DBL(f, MP_NEW, a->y); /* %$2 y$% */ + dx = F_TPL(f, dx, dx); /* %$3 x^2$% */ + dx = F_ADD(f, dx, dx, cc->a); /* %$3 x^2 + A$% */ + dy = F_INV(f, dy, dy); /* %$(2 y)^{-1}$% */ + lambda = F_MUL(f, MP_NEW, dx, dy); /* %$\lambda = (3 x^2 + A)/(2 y)$% */ - dx = F_SQR(f, dx, lambda); - dy = F_DBL(f, dy, a->x); - dx = F_SUB(f, dx, dx, dy); - dy = F_SUB(f, dy, a->x, dx); - dy = F_MUL(f, dy, lambda, dy); - dy = F_SUB(f, dy, dy, a->y); + dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */ + dy = F_DBL(f, dy, a->x); /* %$2 x$% */ + dx = F_SUB(f, dx, dx, dy); /* %$x' = \lambda^2 - 2 x */ + dy = F_SUB(f, dy, a->x, dx); /* %$x - x'$% */ + dy = F_MUL(f, dy, lambda, dy); /* %$\lambda (x - x')$% */ + dy = F_SUB(f, dy, dy, a->y); /* %$y' = \lambda (x - x') - y$% */ EC_DESTROY(d); d->x = dx; @@ -103,6 +128,94 @@ static ec *ecdbl(ec_curve *c, ec *d, const ec *a) return (d); } +static ec *ecprojdbl(ec_curve *c, ec *d, const ec *a) +{ + if (EC_ATINF(a)) + EC_SETINF(d); + else if (F_ZEROP(c->f, a->y)) + EC_COPY(d, a); + else { + field *f = c->f; + ecctx *cc = (ecctx *)c; + mp *p, *q, *m, *s, *dx, *dy, *dz; + + p = F_SQR(f, MP_NEW, a->z); /* %$z^2$% */ + q = F_SQR(f, MP_NEW, p); /* %$z^4$% */ + p = F_MUL(f, p, q, cc->a); /* %$A z^4$% */ + m = F_SQR(f, MP_NEW, a->x); /* %$x^2$% */ + m = F_TPL(f, m, m); /* %$3 x^2$% */ + m = F_ADD(f, m, m, p); /* %$m = 3 x^2 + A z^4$% */ + + q = F_DBL(f, q, a->y); /* %$2 y$% */ + dz = F_MUL(f, MP_NEW, q, a->z); /* %$z' = 2 y z$% */ + + p = F_SQR(f, p, q); /* %$4 y^2$% */ + s = F_MUL(f, MP_NEW, p, a->x); /* %$s = 4 x y^2$% */ + q = F_SQR(f, q, p); /* %$16 y^4$% */ + q = F_HLV(f, q, q); /* %$t = 8 y^4$% */ + + p = F_DBL(f, p, s); /* %$2 s$% */ + dx = F_SQR(f, MP_NEW, m); /* %$m^2$% */ + dx = F_SUB(f, dx, dx, p); /* %$x' = m^2 - 2 s$% */ + + s = F_SUB(f, s, s, dx); /* %$s - x'$% */ + dy = F_MUL(f, p, m, s); /* %$m (s - x')$% */ + dy = F_SUB(f, dy, dy, q); /* %$y' = m (s - x') - t$% */ + + EC_DESTROY(d); + d->x = dx; + d->y = dy; + d->z = dz; + MP_DROP(m); + MP_DROP(q); + MP_DROP(s); + } + return (d); +} + +static ec *ecprojxdbl(ec_curve *c, ec *d, const ec *a) +{ + if (EC_ATINF(a)) + EC_SETINF(d); + else if (F_ZEROP(c->f, a->y)) + EC_COPY(d, a); + else { + field *f = c->f; + mp *p, *q, *m, *s, *dx, *dy, *dz; + + m = F_SQR(f, MP_NEW, a->z); /* %$z^2$% */ + p = F_SUB(f, MP_NEW, a->x, m); /* %$x - z^2$% */ + q = F_ADD(f, MP_NEW, a->x, m); /* %$x + z^2$% */ + m = F_MUL(f, m, p, q); /* %$x^2 - z^4$% */ + m = F_TPL(f, m, m); /* %$m = 3 x^2 - 3 z^4$% */ + + q = F_DBL(f, q, a->y); /* %$2 y$% */ + dz = F_MUL(f, MP_NEW, q, a->z); /* %$z' = 2 y z$% */ + + p = F_SQR(f, p, q); /* %$4 y^2$% */ + s = F_MUL(f, MP_NEW, p, a->x); /* %$s = 4 x y^2$% */ + q = F_SQR(f, q, p); /* %$16 y^4$% */ + q = F_HLV(f, q, q); /* %$t = 8 y^4$% */ + + p = F_DBL(f, p, s); /* %$2 s$% */ + dx = F_SQR(f, MP_NEW, m); /* %$m^2$% */ + dx = F_SUB(f, dx, dx, p); /* %$x' = m^2 - 2 s$% */ + + s = F_SUB(f, s, s, dx); /* %$s - x'$% */ + dy = F_MUL(f, p, m, s); /* %$m (s - x')$% */ + dy = F_SUB(f, dy, dy, q); /* %$y' = m (s - x') - t$% */ + + EC_DESTROY(d); + d->x = dx; + d->y = dy; + d->z = dz; + MP_DROP(m); + MP_DROP(q); + MP_DROP(s); + } + return (d); +} + static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b) { if (a == b) @@ -117,29 +230,32 @@ static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b) mp *dy, *dx; if (!MP_EQ(a->x, b->x)) { - dy = F_SUB(f, MP_NEW, a->y, b->y); - dx = F_SUB(f, MP_NEW, a->x, b->x); - dx = F_INV(f, dx, dx); + dy = F_SUB(f, MP_NEW, a->y, b->y); /* %$y_0 - y_1$% */ + dx = F_SUB(f, MP_NEW, a->x, b->x); /* %$x_0 - x_1$% */ + dx = F_INV(f, dx, dx); /* %$(x_0 - x_1)^{-1}$% */ lambda = F_MUL(f, MP_NEW, dy, dx); - } else if (!MP_LEN(a->y) || !MP_EQ(a->y, b->y)) { + /* %$\lambda = (y_0 - y1)/(x_0 - x_1)$% */ + } else if (F_ZEROP(c->f, a->y) || !MP_EQ(a->y, b->y)) { EC_SETINF(d); return (d); } else { ecctx *cc = (ecctx *)c; - dx = F_SQR(f, MP_NEW, a->x); - dx = F_TPL(f, dx, dx); - dx = F_ADD(f, dx, dx, cc->a); - dy = F_DBL(f, MP_NEW, a->y); - dy = F_INV(f, dy, dy); + dx = F_SQR(f, MP_NEW, a->x); /* %$x_0^2$% */ + dx = F_TPL(f, dx, dx); /* %$3 x_0^2$% */ + dx = F_ADD(f, dx, dx, cc->a); /* %$3 x_0^2 + A$% */ + dy = F_DBL(f, MP_NEW, a->y); /* %$2 y_0$% */ + dy = F_INV(f, dy, dy); /* %$(2 y_0)^{-1}$% */ lambda = F_MUL(f, MP_NEW, dx, dy); + /* %$\lambda = (3 x_0^2 + A)/(2 y_0)$% */ } - dx = F_SQR(f, dx, lambda); - dx = F_SUB(f, dx, dx, a->x); - dx = F_SUB(f, dx, dx, b->x); - dy = F_SUB(f, dy, b->x, dx); - dy = F_MUL(f, dy, lambda, dy); + dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */ + dx = F_SUB(f, dx, dx, a->x); /* %$\lambda^2 - x_0$% */ + dx = F_SUB(f, dx, dx, b->x); /* %$x' = \lambda^2 - x_0 - x_1$% */ + dy = F_SUB(f, dy, b->x, dx); /* %$x_1 - x'$% */ + dy = F_MUL(f, dy, lambda, dy); /* %$\lambda (x_1 - x')$% */ dy = F_SUB(f, dy, dy, b->y); + /* %$y' = \lambda (x_1 - x') - y_1$% */ EC_DESTROY(d); d->x = dx; @@ -150,6 +266,101 @@ static ec *ecadd(ec_curve *c, ec *d, const ec *a, const ec *b) return (d); } +static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b) +{ + if (a == b) + c->ops->dbl(c, d, a); + else if (EC_ATINF(a)) + EC_COPY(d, b); + else if (EC_ATINF(b)) + EC_COPY(d, a); + else { + field *f = c->f; + mp *p, *q, *r, *w, *u, *s, *dx, *dy, *dz; + + q = F_SQR(f, MP_NEW, a->z); /* %$z_0^2$% */ + u = F_MUL(f, MP_NEW, q, b->x); /* %$u = x_1 z_0^2$% */ + p = F_MUL(f, MP_NEW, q, b->y); /* %$y_1 z_0^2$% */ + s = F_MUL(f, q, p, a->z); /* %$s = y_1 z_0^3$% */ + + w = F_SUB(f, p, a->x, u); /* %$w = x_0 - u$% */ + r = F_SUB(f, MP_NEW, a->y, s); /* %$r = y_0 - s$% */ + if (F_ZEROP(f, w)) { + if (F_ZEROP(f, r)) { + MP_DROP(w); + MP_DROP(r); + MP_DROP(u); + MP_DROP(s); + return (c->ops->dbl(c, d, a)); + } else { + MP_DROP(w); + MP_DROP(r); + MP_DROP(u); + MP_DROP(s); + EC_SETINF(d); + return (d); + } + } + u = F_ADD(f, u, u, a->x); /* %$t = x_0 + u$% */ + s = F_ADD(f, s, s, a->y); /* %$m = y_0 + r$% */ + + dz = F_MUL(f, MP_NEW, a->z, w); /* %$z' = z_0 w$% */ + + p = F_SQR(f, MP_NEW, w); /* %$w^2$% */ + q = F_MUL(f, MP_NEW, p, u); /* %$t w^2$% */ + u = F_MUL(f, u, p, w); /* %$w^3$% */ + p = F_MUL(f, p, u, s); /* %$m w^3$% */ + + dx = F_SQR(f, u, r); /* %$r^2$% */ + dx = F_SUB(f, dx, dx, q); /* %$x' = r^2 - t w^2$% */ + + s = F_DBL(f, s, dx); /* %$2 x'$% */ + q = F_SUB(f, q, q, s); /* %$v = t w^2 - 2 x'$% */ + dy = F_MUL(f, s, q, r); /* %$v r$% */ + dy = F_SUB(f, dy, dy, p); /* %$v r - m w^3$% */ + dy = F_HLV(f, dy, dy); /* %$y' = (v r - m w^3)/2$% */ + + EC_DESTROY(d); + d->x = dx; + d->y = dy; + d->z = dz; + MP_DROP(p); + MP_DROP(q); + MP_DROP(r); + MP_DROP(w); + } + return (d); +} + +static int eccheck(ec_curve *c, const ec *p) +{ + ecctx *cc = (ecctx *)c; + field *f = c->f; + int rc; + mp *l = F_SQR(f, MP_NEW, p->y); + mp *x = F_SQR(f, MP_NEW, p->x); + mp *r = F_MUL(f, MP_NEW, x, p->x); + x = F_MUL(f, x, cc->a, p->x); + r = F_ADD(f, r, r, x); + r = F_ADD(f, r, r, cc->b); + rc = MP_EQ(l, r) ? 0 : -1; + mp_drop(l); + mp_drop(x); + mp_drop(r); + return (rc); +} + +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); + return (rc); +} + static void ecdestroy(ec_curve *c) { ecctx *cc = (ecctx *)c; @@ -180,8 +391,37 @@ extern ec_curve *ec_prime(field *f, mp *a, mp *b) return (&cc->c); } +extern ec_curve *ec_primeproj(field *f, mp *a, mp *b) +{ + ecctx *cc = CREATE(ecctx); + mp *ax; + + ax = mp_add(MP_NEW, a, MP_THREE); + ax = F_IN(f, ax, ax); + if (F_ZEROP(f, ax)) + cc->c.ops = &ec_primeprojxops; + else + cc->c.ops = &ec_primeprojops; + MP_DROP(ax); + cc->c.f = f; + cc->a = F_IN(f, MP_NEW, a); + cc->b = F_IN(f, MP_NEW, b); + return (&cc->c); +} + static const ec_ops ec_primeops = { - ecdestroy, ec_idin, ec_idout, 0, ecneg, ecadd, ec_stdsub, ecdbl + ecdestroy, ec_idin, ec_idout, ec_idfix, + 0, ecneg, ecadd, ec_stdsub, ecdbl, eccheck +}; + +static const ec_ops ec_primeprojops = { + ecdestroy, ec_projin, ec_projout, ec_projfix, + 0, ecneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck +}; + +static const ec_ops ec_primeprojxops = { + ecdestroy, ec_projin, ec_projout, ec_projfix, + 0, ecneg, ecprojadd, ec_stdsub, ecprojxdbl, ecprojcheck }; /*----- Test rig ----------------------------------------------------------*/