[u/mdw/catacomb] / math / ec-prime.c

/* -*-c-*-
 *
 * Elliptic curves over prime fields
 *
 * (c) 2001 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * 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.
 */

/*----- Header files ------------------------------------------------------*/

#include <mLib/sub.h>

#include "ec.h"

/*----- Simple prime curves -----------------------------------------------*/

static const ec_ops ec_primeops, ec_primeprojops, ec_primeprojxops;

static ec *ecneg(ec_curve *c, ec *d, const ec *p)
{
  EC_COPY(d, p);
  if (d->y)
    d->y = F_NEG(c->f, d->y, d->y);
  return (d);
}

static ec *ecfind(ec_curve *c, ec *d, mp *x)
{
  mp *p, *q;
  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, c->a);
  p = F_ADD(f, p, p, q);
  p = F_ADD(f, p, p, c->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) || F_ZEROP(c->f, a->y))
    EC_SETINF(d);
  else {
    field *f = c->f;
    mp *lambda;
    mp *dy, *dx;

    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, c->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);		/* %$\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;
    d->y = dy;
    d->z = 0;
    MP_DROP(lambda);
  }
  return (d);
}

static ec *ecprojdbl(ec_curve *c, ec *d, const ec *a)
{
  if (EC_ATINF(a) || F_ZEROP(c->f, a->y))
    EC_SETINF(d);
  else {
    field *f = c->f;
    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, c->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) || F_ZEROP(c->f, a->y))
    EC_SETINF(d);
  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)
    ecdbl(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 *lambda;
    mp *dy, *dx;

    if (!MP_EQ(a->x, b->x)) {
      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);
				   /* %$\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 {
      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, c->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);		/* %$\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;
    d->y = dy;
    d->z = 0;
    MP_DROP(lambda);
  }
  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, *uu, *s, *ss, *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$% */

    q = F_SQR(f, MP_NEW, b->z);		/* %$z_1^2$% */
    uu = F_MUL(f, MP_NEW, q, a->x);	/* %$uu = x_0 z_1^2$%*/
    p = F_MUL(f, p, q, a->y);		/* %$y_0 z_1^2$% */
    ss = F_MUL(f, q, p, b->z);		/* %$ss = y_0 z_1^3$% */

    w = F_SUB(f, p, uu, u);		/* %$w = uu - u$% */
    r = F_SUB(f, MP_NEW, ss, s);	/* %$r = ss - s$% */
    if (F_ZEROP(f, w)) {
      MP_DROP(w);
      MP_DROP(u);
      MP_DROP(s);
      MP_DROP(uu);
      MP_DROP(ss);
      if (F_ZEROP(f, r)) {
	MP_DROP(r);
	return (c->ops->dbl(c, d, a));
      } else {
	MP_DROP(r);
	EC_SETINF(d);
	return (d);
      }
    }
    u = F_ADD(f, u, u, uu);		/* %$t = uu + u$% */
    s = F_ADD(f, s, s, ss);		/* %$m = ss + s$% */

    uu = F_MUL(f, uu, a->z, w);		/* %$z_0 w$% */
    dz = F_MUL(f, ss, uu, b->z);	/* %$z' = z_0 z_1 w$% */

    p = F_SQR(f, uu, 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)
{
  field *f = c->f;
  mp *l, *x, *r;
  int rc;
  if (EC_ATINF(p)) return (0);
  l = F_SQR(f, MP_NEW, p->y);
  x = F_SQR(f, MP_NEW, p->x);
  r = F_MUL(f, MP_NEW, x, p->x);
  x = F_MUL(f, x, c->a, p->x);
  r = F_ADD(f, r, r, x);
  r = F_ADD(f, r, r, c->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)
{
  MP_DROP(c->a);
  MP_DROP(c->b);
  DESTROY(c);
}

/* --- @ec_prime@, @ec_primeproj@ --- *
 *
 * Arguments:	@field *f@ = the underlying field for this elliptic curve
 *		@mp *a, *b@ = the coefficients for this curve
 *
 * Returns:	A pointer to the curve, or null.
 *
 * Use:		Creates a curve structure for an elliptic curve defined over
 *		a prime field.  The @primeproj@ variant uses projective
 *		coordinates, which can be a win.
 */

extern ec_curve *ec_prime(field *f, mp *a, mp *b)
{
  ec_curve *c = CREATE(ec_curve);
  c->ops = &ec_primeops;
  c->f = f;
  c->a = F_IN(f, MP_NEW, a);
  c->b = F_IN(f, MP_NEW, b);
  return (c);
}

extern ec_curve *ec_primeproj(field *f, mp *a, mp *b)
{
  ec_curve *c = CREATE(ec_curve);
  mp *ax;

  ax = mp_add(MP_NEW, a, MP_THREE);
  ax = F_IN(f, ax, ax);
  if (F_ZEROP(f, ax))
    c->ops = &ec_primeprojxops;
  else
    c->ops = &ec_primeprojops;
  MP_DROP(ax);
  c->f = f;
  c->a = F_IN(f, MP_NEW, a);
  c->b = F_IN(f, MP_NEW, b);
  return (c);
}

static const ec_ops ec_primeops = {
  "prime",
  ecdestroy, ec_stdsamep, ec_idin, ec_idout, ec_idfix,
  ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
};

static const ec_ops ec_primeprojops = {
  "primeproj",
  ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
  ecfind, ecneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
};

static const ec_ops ec_primeprojxops = {
  "primeproj",
  ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
  ecfind, ecneg, ecprojadd, ec_stdsub, ecprojxdbl, ecprojcheck
};

/*----- Test rig ----------------------------------------------------------*/

#ifdef TEST_RIG

#define MP(x) mp_readstring(MP_NEW, #x, 0, 0)

int main(int argc, char *argv[])
{
  field *f;
  ec_curve *c;
  ec g = EC_INIT, d = EC_INIT;
  mp *p, *a, *b, *r;
  int i, n = argc == 1 ? 1 : atoi(argv[1]);

  printf("ec-prime: ");
  fflush(stdout);
  a = MP(-3);
  b = MP(0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef);
  p = MP(39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319);
  r = MP(39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942642);

  f = field_niceprime(p);
  c = ec_primeproj(f, a, b);

  g.x = MP(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7);
  g.y = MP(0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f);

  for (i = 0; i < n; i++) {
    ec_mul(c, &d, &g, r);
    if (EC_ATINF(&d)) {
      fprintf(stderr, "zero too early\n");
      return (1);
    }
    ec_add(c, &d, &d, &g);
    if (!EC_ATINF(&d)) {
      fprintf(stderr, "didn't reach zero\n");
      MP_EPRINT("d.x", d.x);
      MP_EPRINT("d.y", d.y);
      return (1);
    }
    ec_destroy(&d);
  }
  ec_destroy(&g);
  ec_destroycurve(c);
  F_DESTROY(f);
  MP_DROP(p); MP_DROP(a); MP_DROP(b); MP_DROP(r);
  assert(!mparena_count(&mparena_global));
  printf("ok\n");
  return (0);
}

#endif

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
b0ab12e6	1	/* --c--
b0ab12e6	2	*
b0ab12e6	3	* Elliptic curves over prime fields
	4	*
	5	* (c) 2001 Straylight/Edgeware
	6	*/
	7
45c0fd36	8	/----- Licensing notice --------------------------------------------------
b0ab12e6	9	*
	10	* This file is part of Catacomb.
	11	*
	12	* Catacomb is free software; you can redistribute it and/or modify
	13	* it under the terms of the GNU Library General Public License as
	14	* published by the Free Software Foundation; either version 2 of the
	15	* License, or (at your option) any later version.
45c0fd36	16	*
b0ab12e6	17	* Catacomb is distributed in the hope that it will be useful,
	18	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	19	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	20	* GNU Library General Public License for more details.
45c0fd36	21	*
b0ab12e6	22	* You should have received a copy of the GNU Library General Public
	23	* License along with Catacomb; if not, write to the Free
	24	* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
	25	* MA 02111-1307, USA.
	26	*/
	27
b0ab12e6	28	/----- Header files ------------------------------------------------------/
b0ab12e6	29
41cb1beb	30	#include <mLib/sub.h>
41cb1beb	31
b0ab12e6	32	#include "ec.h"
b0ab12e6	33
dbfee00a	34	/----- Simple prime curves -----------------------------------------------/
b0ab12e6	35
8823192f	36	static const ec_ops ec_primeops, ec_primeprojops, ec_primeprojxops;
41cb1beb	37
41cb1beb	38	static ec ecneg(ec_curve c, ec d, const ec p)
b085fd91	39	{
b085fd91	40	EC_COPY(d, p);
ceb3f0c0	41	if (d->y)
ceb3f0c0	42	d->y = F_NEG(c->f, d->y, d->y);
b085fd91	43	return (d);
	44	}
	45
8823192f	46	static ec ecfind(ec_curve c, ec d, mp x)
	47	{
	48	mp p, q;
8823192f	49	field *f = c->f;
	50
	51	q = F_SQR(f, MP_NEW, x);
	52	p = F_MUL(f, MP_NEW, x, q);
432c4e18	53	q = F_MUL(f, q, x, c->a);
8823192f	54	p = F_ADD(f, p, p, q);
432c4e18	55	p = F_ADD(f, p, p, c->b);
8823192f	56	MP_DROP(q);
	57	p = F_SQRT(f, p, p);
	58	if (!p)
	59	return (0);
	60	EC_DESTROY(d);
	61	d->x = MP_COPY(x);
	62	d->y = p;
	63	d->z = MP_COPY(f->one);
b085fd91	64	return (d);
	65	}
	66
	67	static ec ecdbl(ec_curve c, ec d, const ec a)
b0ab12e6	68	{
1ccdb13a	69	if (EC_ATINF(a) \|\| F_ZEROP(c->f, a->y))
b085fd91	70	EC_SETINF(d);
b085fd91	71	else {
b085fd91	72	field *f = c->f;
b085fd91	73	mp *lambda;
	74	mp dy, dx;
	75
8823192f	76	dx = F_SQR(f, MP_NEW, a->x); /* %$x^2$% */
	77	dy = F_DBL(f, MP_NEW, a->y); /* %$2 y$% */
	78	dx = F_TPL(f, dx, dx); /* %$3 x^2$% */
432c4e18	79	dx = F_ADD(f, dx, dx, c->a); /* %$3 x^2 + A$% */
8823192f	80	dy = F_INV(f, dy, dy); /* %$(2 y)^{-1}$% */
8823192f	81	lambda = F_MUL(f, MP_NEW, dx, dy); /* %$\lambda = (3 x^2 + A)/(2 y)$% */
b085fd91	82
8823192f	83	dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */
	84	dy = F_DBL(f, dy, a->x); /* %$2 x$% */
	85	dx = F_SUB(f, dx, dx, dy); /* %$x' = \lambda^2 - 2 x */
	86	dy = F_SUB(f, dy, a->x, dx); /* %$x - x'$% */
	87	dy = F_MUL(f, dy, lambda, dy); /* %$\lambda (x - x')$% */
	88	dy = F_SUB(f, dy, dy, a->y); /* %$y' = \lambda (x - x') - y$% */
b0ab12e6	89
b085fd91	90	EC_DESTROY(d);
	91	d->x = dx;
	92	d->y = dy;
	93	d->z = 0;
	94	MP_DROP(lambda);
	95	}
	96	return (d);
	97	}
	98
8823192f	99	static ec ecprojdbl(ec_curve c, ec d, const ec a)
8823192f	100	{
1ccdb13a	101	if (EC_ATINF(a) \|\| F_ZEROP(c->f, a->y))
8823192f	102	EC_SETINF(d);
8823192f	103	else {
8823192f	104	field *f = c->f;
8823192f	105	mp p, q, m, s, dx, dy, *dz;
	106
	107	p = F_SQR(f, MP_NEW, a->z); /* %$z^2$% */
	108	q = F_SQR(f, MP_NEW, p); /* %$z^4$% */
432c4e18	109	p = F_MUL(f, p, q, c->a); /* %$A z^4$% */
8823192f	110	m = F_SQR(f, MP_NEW, a->x); /* %$x^2$% */
	111	m = F_TPL(f, m, m); /* %$3 x^2$% */
	112	m = F_ADD(f, m, m, p); /* %$m = 3 x^2 + A z^4$% */
	113
	114	q = F_DBL(f, q, a->y); /* %$2 y$% */
	115	dz = F_MUL(f, MP_NEW, q, a->z); /* %$z' = 2 y z$% */
	116
	117	p = F_SQR(f, p, q); /* %$4 y^2$% */
	118	s = F_MUL(f, MP_NEW, p, a->x); /* %$s = 4 x y^2$% */
	119	q = F_SQR(f, q, p); /* %$16 y^4$% */
	120	q = F_HLV(f, q, q); /* %$t = 8 y^4$% */
	121
	122	p = F_DBL(f, p, s); /* %$2 s$% */
	123	dx = F_SQR(f, MP_NEW, m); /* %$m^2$% */
	124	dx = F_SUB(f, dx, dx, p); /* %$x' = m^2 - 2 s$% */
	125
	126	s = F_SUB(f, s, s, dx); /* %$s - x'$% */
	127	dy = F_MUL(f, p, m, s); /* %$m (s - x')$% */
	128	dy = F_SUB(f, dy, dy, q); /* %$y' = m (s - x') - t$% */
	129
	130	EC_DESTROY(d);
	131	d->x = dx;
	132	d->y = dy;
	133	d->z = dz;
	134	MP_DROP(m);
	135	MP_DROP(q);
	136	MP_DROP(s);
	137	}
	138	return (d);
	139	}
	140
	141	static ec ecprojxdbl(ec_curve c, ec d, const ec a)
	142	{
1ccdb13a	143	if (EC_ATINF(a) \|\| F_ZEROP(c->f, a->y))
8823192f	144	EC_SETINF(d);
8823192f	145	else {
	146	field *f = c->f;
	147	mp p, q, m, s, dx, dy, *dz;
	148
	149	m = F_SQR(f, MP_NEW, a->z); /* %$z^2$% */
	150	p = F_SUB(f, MP_NEW, a->x, m); /* %$x - z^2$% */
	151	q = F_ADD(f, MP_NEW, a->x, m); /* %$x + z^2$% */
	152	m = F_MUL(f, m, p, q); /* %$x^2 - z^4$% */
	153	m = F_TPL(f, m, m); /* %$m = 3 x^2 - 3 z^4$% */
	154
	155	q = F_DBL(f, q, a->y); /* %$2 y$% */
	156	dz = F_MUL(f, MP_NEW, q, a->z); /* %$z' = 2 y z$% */
	157
	158	p = F_SQR(f, p, q); /* %$4 y^2$% */
	159	s = F_MUL(f, MP_NEW, p, a->x); /* %$s = 4 x y^2$% */
	160	q = F_SQR(f, q, p); /* %$16 y^4$% */
	161	q = F_HLV(f, q, q); /* %$t = 8 y^4$% */
	162
	163	p = F_DBL(f, p, s); /* %$2 s$% */
	164	dx = F_SQR(f, MP_NEW, m); /* %$m^2$% */
	165	dx = F_SUB(f, dx, dx, p); /* %$x' = m^2 - 2 s$% */
	166
	167	s = F_SUB(f, s, s, dx); /* %$s - x'$% */
	168	dy = F_MUL(f, p, m, s); /* %$m (s - x')$% */
	169	dy = F_SUB(f, dy, dy, q); /* %$y' = m (s - x') - t$% */
	170
	171	EC_DESTROY(d);
	172	d->x = dx;
	173	d->y = dy;
	174	d->z = dz;
	175	MP_DROP(m);
	176	MP_DROP(q);
	177	MP_DROP(s);
	178	}
	179	return (d);
	180	}
	181
b085fd91	182	static ec ecadd(ec_curve c, ec d, const ec a, const ec *b)
b085fd91	183	{
b0ab12e6	184	if (a == b)
	185	ecdbl(c, d, a);
	186	else if (EC_ATINF(a))
	187	EC_COPY(d, b);
	188	else if (EC_ATINF(b))
	189	EC_COPY(d, a);
b085fd91	190	else {
	191	field *f = c->f;
	192	mp *lambda;
	193	mp dy, dx;
	194
	195	if (!MP_EQ(a->x, b->x)) {
8823192f	196	dy = F_SUB(f, MP_NEW, a->y, b->y); /* %$y_0 - y_1$% */
	197	dx = F_SUB(f, MP_NEW, a->x, b->x); /* %$x_0 - x_1$% */
	198	dx = F_INV(f, dx, dx); /* %$(x_0 - x_1)^{-1}$% */
b085fd91	199	lambda = F_MUL(f, MP_NEW, dy, dx);
8823192f	200	/* %$\lambda = (y_0 - y1)/(x_0 - x_1)$% */
8823192f	201	} else if (F_ZEROP(c->f, a->y) \|\| !MP_EQ(a->y, b->y)) {
b0ab12e6	202	EC_SETINF(d);
b085fd91	203	return (d);
b085fd91	204	} else {
8823192f	205	dx = F_SQR(f, MP_NEW, a->x); /* %$x_0^2$% */
8823192f	206	dx = F_TPL(f, dx, dx); /* %$3 x_0^2$% */
432c4e18	207	dx = F_ADD(f, dx, dx, c->a); /* %$3 x_0^2 + A$% */
8823192f	208	dy = F_DBL(f, MP_NEW, a->y); /* %$2 y_0$% */
8823192f	209	dy = F_INV(f, dy, dy); /* %$(2 y_0)^{-1}$% */
41cb1beb	210	lambda = F_MUL(f, MP_NEW, dx, dy);
8823192f	211	/* %$\lambda = (3 x_0^2 + A)/(2 y_0)$% */
b085fd91	212	}
b085fd91	213
8823192f	214	dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */
	215	dx = F_SUB(f, dx, dx, a->x); /* %$\lambda^2 - x_0$% */
	216	dx = F_SUB(f, dx, dx, b->x); /* %$x' = \lambda^2 - x_0 - x_1$% */
	217	dy = F_SUB(f, dy, b->x, dx); /* %$x_1 - x'$% */
	218	dy = F_MUL(f, dy, lambda, dy); /* %$\lambda (x_1 - x')$% */
ceb3f0c0	219	dy = F_SUB(f, dy, dy, b->y); /* %$y' = \lambda (x_1 - x') - y_1$% */
b0ab12e6	220
b085fd91	221	EC_DESTROY(d);
	222	d->x = dx;
	223	d->y = dy;
	224	d->z = 0;
	225	MP_DROP(lambda);
b0ab12e6	226	}
b085fd91	227	return (d);
b0ab12e6	228	}
b0ab12e6	229
8823192f	230	static ec ecprojadd(ec_curve c, ec d, const ec a, const ec *b)
	231	{
	232	if (a == b)
	233	c->ops->dbl(c, d, a);
	234	else if (EC_ATINF(a))
	235	EC_COPY(d, b);
	236	else if (EC_ATINF(b))
	237	EC_COPY(d, a);
	238	else {
	239	field *f = c->f;
391faf42	240	mp p, q, r, w, u, uu, s, ss, dx, dy, *dz;
8823192f	241
	242	q = F_SQR(f, MP_NEW, a->z); /* %$z_0^2$% */
	243	u = F_MUL(f, MP_NEW, q, b->x); /* %$u = x_1 z_0^2$% */
	244	p = F_MUL(f, MP_NEW, q, b->y); /* %$y_1 z_0^2$% */
	245	s = F_MUL(f, q, p, a->z); /* %$s = y_1 z_0^3$% */
	246
391faf42	247	q = F_SQR(f, MP_NEW, b->z); /* %$z_1^2$% */
	248	uu = F_MUL(f, MP_NEW, q, a->x); /* %$uu = x_0 z_1^2$%*/
	249	p = F_MUL(f, p, q, a->y); /* %$y_0 z_1^2$% */
	250	ss = F_MUL(f, q, p, b->z); /* %$ss = y_0 z_1^3$% */
	251
	252	w = F_SUB(f, p, uu, u); /* %$w = uu - u$% */
	253	r = F_SUB(f, MP_NEW, ss, s); /* %$r = ss - s$% */
8823192f	254	if (F_ZEROP(f, w)) {
ceb3f0c0	255	MP_DROP(w);
	256	MP_DROP(u);
	257	MP_DROP(s);
391faf42	258	MP_DROP(uu);
391faf42	259	MP_DROP(ss);
8823192f	260	if (F_ZEROP(f, r)) {
8823192f	261	MP_DROP(r);
8823192f	262	return (c->ops->dbl(c, d, a));
8823192f	263	} else {
8823192f	264	MP_DROP(r);
8823192f	265	EC_SETINF(d);
	266	return (d);
	267	}
	268	}
391faf42	269	u = F_ADD(f, u, u, uu); /* %$t = uu + u$% */
3f19a2c1	270	s = F_ADD(f, s, s, ss); /* %$m = ss + s$% */
8823192f	271
391faf42	272	uu = F_MUL(f, uu, a->z, w); /* %$z_0 w$% */
391faf42	273	dz = F_MUL(f, ss, uu, b->z); /* %$z' = z_0 z_1 w$% */
8823192f	274
391faf42	275	p = F_SQR(f, uu, w); /* %$w^2$% */
8823192f	276	q = F_MUL(f, MP_NEW, p, u); /* %$t w^2$% */
	277	u = F_MUL(f, u, p, w); /* %$w^3$% */
	278	p = F_MUL(f, p, u, s); /* %$m w^3$% */
45c0fd36	279
8823192f	280	dx = F_SQR(f, u, r); /* %$r^2$% */
	281	dx = F_SUB(f, dx, dx, q); /* %$x' = r^2 - t w^2$% */
	282
	283	s = F_DBL(f, s, dx); /* %$2 x'$% */
	284	q = F_SUB(f, q, q, s); /* %$v = t w^2 - 2 x'$% */
	285	dy = F_MUL(f, s, q, r); /* %$v r$% */
	286	dy = F_SUB(f, dy, dy, p); /* %$v r - m w^3$% */
	287	dy = F_HLV(f, dy, dy); /* %$y' = (v r - m w^3)/2$% */
	288
	289	EC_DESTROY(d);
	290	d->x = dx;
	291	d->y = dy;
	292	d->z = dz;
	293	MP_DROP(p);
	294	MP_DROP(q);
	295	MP_DROP(r);
	296	MP_DROP(w);
	297	}
	298	return (d);
	299	}
	300
	301	static int eccheck(ec_curve c, const ec p)
	302	{
8823192f	303	field *f = c->f;
34e4f738	304	mp l, x, *r;
8823192f	305	int rc;
34e4f738	306	if (EC_ATINF(p)) return (0);
	307	l = F_SQR(f, MP_NEW, p->y);
	308	x = F_SQR(f, MP_NEW, p->x);
	309	r = F_MUL(f, MP_NEW, x, p->x);
432c4e18	310	x = F_MUL(f, x, c->a, p->x);
8823192f	311	r = F_ADD(f, r, r, x);
432c4e18	312	r = F_ADD(f, r, r, c->b);
8823192f	313	rc = MP_EQ(l, r) ? 0 : -1;
	314	mp_drop(l);
	315	mp_drop(x);
	316	mp_drop(r);
	317	return (rc);
	318	}
	319
	320	static int ecprojcheck(ec_curve c, const ec p)
	321	{
	322	ec t = EC_INIT;
	323	int rc;
45c0fd36	324
8823192f	325	c->ops->fix(c, &t, p);
	326	rc = eccheck(c, &t);
	327	EC_DESTROY(&t);
	328	return (rc);
	329	}
	330
41cb1beb	331	static void ecdestroy(ec_curve *c)
41cb1beb	332	{
432c4e18	333	MP_DROP(c->a);
	334	MP_DROP(c->b);
	335	DESTROY(c);
41cb1beb	336	}
	337
	338	/* --- @ec_prime@, @ec_primeproj@ --- *
	339	*
dbfee00a	340	* Arguments: @field *f@ = the underlying field for this elliptic curve
41cb1beb	341	* @mp a, b@ = the coefficients for this curve
41cb1beb	342	*
02d7884d	343	* Returns: A pointer to the curve, or null.
41cb1beb	344	*
	345	* Use: Creates a curve structure for an elliptic curve defined over
	346	* a prime field. The @primeproj@ variant uses projective
	347	* coordinates, which can be a win.
	348	*/
	349
	350	extern ec_curve ec_prime(field f, mp a, mp b)
	351	{
432c4e18	352	ec_curve *c = CREATE(ec_curve);
	353	c->ops = &ec_primeops;
	354	c->f = f;
	355	c->a = F_IN(f, MP_NEW, a);
	356	c->b = F_IN(f, MP_NEW, b);
	357	return (c);
41cb1beb	358	}
41cb1beb	359
8823192f	360	extern ec_curve ec_primeproj(field f, mp a, mp b)
8823192f	361	{
432c4e18	362	ec_curve *c = CREATE(ec_curve);
8823192f	363	mp *ax;
	364
	365	ax = mp_add(MP_NEW, a, MP_THREE);
	366	ax = F_IN(f, ax, ax);
	367	if (F_ZEROP(f, ax))
432c4e18	368	c->ops = &ec_primeprojxops;
8823192f	369	else
432c4e18	370	c->ops = &ec_primeprojops;
8823192f	371	MP_DROP(ax);
432c4e18	372	c->f = f;
	373	c->a = F_IN(f, MP_NEW, a);
	374	c->b = F_IN(f, MP_NEW, b);
	375	return (c);
41cb1beb	376	}
	377
	378	static const ec_ops ec_primeops = {
f94b972d	379	"prime",
34e4f738	380	ecdestroy, ec_stdsamep, ec_idin, ec_idout, ec_idfix,
bc985cef	381	ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
8823192f	382	};
	383
	384	static const ec_ops ec_primeprojops = {
f94b972d	385	"primeproj",
34e4f738	386	ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
bc985cef	387	ecfind, ecneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
8823192f	388	};
	389
	390	static const ec_ops ec_primeprojxops = {
f94b972d	391	"primeproj",
34e4f738	392	ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
bc985cef	393	ecfind, ecneg, ecprojadd, ec_stdsub, ecprojxdbl, ecprojcheck
41cb1beb	394	};
	395
	396	/----- Test rig ----------------------------------------------------------/
	397
	398	#ifdef TEST_RIG
	399
	400	#define MP(x) mp_readstring(MP_NEW, #x, 0, 0)
	401
ceb3f0c0	402	int main(int argc, char *argv[])
41cb1beb	403	{
	404	field *f;
	405	ec_curve *c;
	406	ec g = EC_INIT, d = EC_INIT;
	407	mp p, a, b, r;
ceb3f0c0	408	int i, n = argc == 1 ? 1 : atoi(argv[1]);
41cb1beb	409
dbfee00a	410	printf("ec-prime: ");
dbfee00a	411	fflush(stdout);
41cb1beb	412	a = MP(-3);
432c4e18	413	b = MP(0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef);
	414	p = MP(39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319);
	415	r = MP(39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942642);
41cb1beb	416
f46efa79	417	f = field_niceprime(p);
ceb3f0c0	418	c = ec_primeproj(f, a, b);
45c0fd36	419
432c4e18	420	g.x = MP(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7);
432c4e18	421	g.y = MP(0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f);
41cb1beb	422
45c0fd36	423	for (i = 0; i < n; i++) {
ceb3f0c0	424	ec_mul(c, &d, &g, r);
	425	if (EC_ATINF(&d)) {
	426	fprintf(stderr, "zero too early\n");
	427	return (1);
	428	}
	429	ec_add(c, &d, &d, &g);
	430	if (!EC_ATINF(&d)) {
	431	fprintf(stderr, "didn't reach zero\n");
	432	MP_EPRINT("d.x", d.x);
	433	MP_EPRINT("d.y", d.y);
	434	return (1);
	435	}
	436	ec_destroy(&d);
dbfee00a	437	}
41cb1beb	438	ec_destroy(&g);
	439	ec_destroycurve(c);
	440	F_DESTROY(f);
dbfee00a	441	MP_DROP(p); MP_DROP(a); MP_DROP(b); MP_DROP(r);
	442	assert(!mparena_count(&mparena_global));
	443	printf("ok\n");
41cb1beb	444	return (0);
	445	}
	446
	447	#endif
	448
b0ab12e6	449	/----- That's all, folks -------------------------------------------------/