Prototype version.

[u/mdw/catacomb] / ec.c

/* -*-c-*-
 *
 * $Id: ec.c,v 1.1 2001/04/29 18:12:33 mdw Exp $
 *
 * Elliptic curve definitions
 *
 * (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.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: ec.c,v $
 * Revision 1.1  2001/04/29 18:12:33  mdw
 * Prototype version.
 *
 */

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

#include "ec.h"

/*----- Trivial wrappers --------------------------------------------------*/

/* --- @ec_create@ --- *
 *
 * Arguments:	@ec *p@ = pointer to an elliptic-curve point
 *
 * Returns:	---
 *
 * Use:		Initializes a new point.  The initial value is the additive
 *		identity (which is universal for all curves).
 */

void ec_create(ec *p) { EC_CREATE(p); }

/* --- @ec_destroy@ --- *
 *
 * Arguments:	@ec *p@ = pointer to an elliptic-curve point
 *
 * Returns:	---
 *
 * Use:		Destroys a point, making it invalid.
 */

void ec_destroy(ec *p) { EC_DESTROY(p); }

/* --- @ec_atinf@ --- *
 *
 * Arguments:	@const ec *p@ = pointer to a point
 *
 * Returns:	Nonzero if %$p = O$% is the point at infinity, zero
 *		otherwise.
 */

int ec_atinf(const ec *p) { return (EC_ATINF(p)); }

/* --- @ec_setinf@ --- *
 *
 * Arguments:	@ec *p@ = pointer to a point
 *
 * Returns:	---
 *
 * Use:		Sets the given point to be the point %$O$% at infinity.
 */

void ec_setinf(ec *p) { EC_SETINF(p); }

/* --- @ec_copy@ --- *
 *
 * Arguments:	@ec *d@ = pointer to destination point
 *		@const ec *p@ = pointer to source point
 *
 * Returns:	---
 *
 * Use:		Creates a copy of an elliptic curve point.
 */

void ec_copy(ec *d, const ec *p) { EC_COPY(d, p); }

/*----- Real arithmetic ---------------------------------------------------*/

/* --- @ec_denorm@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@ec *d@ = pointer to the destination point
 *		@const ec *p@ = pointer to the source point
 *
 * Returns:	---
 *
 * Use:		Denormalizes the given point, converting to internal
 *		representations and setting the denominator to 1.
 */

void ec_denorm(ec_curve *c, ec *d, const ec *p)
{
  if (EC_ATINF(p))
    EC_SETINF(d);
  else {
    field *f = c->f;
    d->x = F_IN(f, d->x, p->x);
    d->y = F_IN(f, d->y, p->y);
    mp_drop(d->z);
    d->z = MP_COPY(f->one);
  }
}

/* --- @ec_norm@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@ec *d@ = pointer to the destination point
 *		@const ec *p@ = pointer to the source point
 *
 * Returns:	---
 *
 * Use:		Normalizes the given point, by dividing through by the
 *		denominator and returning to external representation.
 */

void ec_norm(ec_curve *c, ec *d, const ec *p)
{
  if (EC_ATINF(p))
    EC_SETINF(d);
  else {
    mp *x, *y, *z;
    field *f = c->f;
    z = F_INV(f, MP_NEW, p->z);
    x = F_MUL(f, d->x, p->x, z);
    y = F_MUL(f, d->y, p->y, z);
    mp_drop(z);
    mp_drop(d->z);
    d->x = F_OUT(f, x, x);
    d->y = F_OUT(f, y, y);
    d->z = 0;
  }
}

/* --- @ec_find@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@ec *d@ = pointer to the destination point
 *		@mp *x@ = a possible x-coordinate
 *
 * Returns:	Zero if OK, nonzero if there isn't a point there.
 *
 * Use:		Finds a point on an elliptic curve with a given x-coordinate.
 */

void ec_find(ec_curve *c, ec *d, mp *x)
{
  int rc;
  x = F_IN(c->f, MP_NEW, x);
  if ((rc = EC_FIND(c, d, x)) == 0)
    ec_norm(c, d, d);
  mp_drop(x);
  return (rc);
}

/* --- @ec_add@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@ec *d@ = pointer to the destination point
 *		@const ec *p, *q@ = pointers to the operand points
 *
 * Returns:	---
 *
 * Use:		Adds two points on an elliptic curve.
 */

void ec_add(ec_curve *c, ec *d, const ec *p, const ec *q)
{
  ec pp = EC_INIT, qq = EC_INIT;
  ec_denorm(c, &pp, p);
  ec_denorm(c, &qq, q);
  EC_ADD(c, d, &pp, &qq);
  ec_norm(c, d, d);
  EC_DESTROY(&pp);
  EC_DESTROY(&qq);
}

/* --- @ec_dbl@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@ec *d@ = pointer to the destination point
 *		@const ec *p@ = pointer to the operand point
 *
 * Returns:	---
 *
 * Use:		Doubles a point on an elliptic curve.
 */

void ec_dbl(ec_curve *c, ec *d, const ec *p)
{
  ec_denorm(c, d, p);
  EC_DBL(c, d, d);
  ec_norm(c, d, d);
}

/* --- @ec_mul@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@ec *d@ = pointer to the destination point
 *		@const ec *p@ = pointer to the generator point
 *		@mp *n@ = integer multiplier
 *
 * Returns:	---
 *
 * Use:		Multiplies a point by a scalar, returning %$n p$%.
 */

void ec_mul(ec_curve *c, ec *d, const ec *p, mp *n)
{
  mpscan sc;
  ec g = EC_INIT;
  unsigned sq = 0;

  EC_SETINF(d);
  if (EC_ATINF(p))
    return;

  mp_rscan(&sc, n);
  if (!MP_RSTEP(&sc))
    goto exit;
  while (!MP_RBIT(&sc))
    MP_RSTEP(&sc);

  ec_denorm(c, &g, p);
  if ((n->f & MP_BURN) && !(g.x->f & MP_BURN))
    MP_DEST(g.x, 0, MP_BURN);
  if ((n->f & MP_BURN) && !(g.y->f & MP_BURN))
    MP_DEST(g.y, 0, MP_BURN);

  for (;;) {
    EC_ADD(c, d, d, &g);
    sq = 0;
    for (;;) {
      if (!MP_RSTEP(&sc))
	goto done;
      if (MP_RBIT(&sc))
	break;
      sq++;
    }
    sq++;
    while (sq) {
      EC_DBL(c, d, d);
      sq--;
    }
  }

done:
  while (sq) {
    EC_DBL(c, d, d);
    sq--;
  }

  EC_DESTROY(&g);
exit:
  ec_norm(c, d, d);
}

/*----- That's all, folks -------------------------------------------------*/