Normal basis support (translates to poly basis internally). Rewrite

[u/mdw/catacomb] / ec.c

/* -*-c-*-
 *
 * $Id: ec.c,v 1.9 2004/04/01 21:28:41 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.9  2004/04/01 21:28:41  mdw
 * Normal basis support (translates to poly basis internally).  Rewrite
 * EC and prime group table generators in awk, so that they can reuse data
 * for repeated constants.
 *
 * Revision 1.8  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.7  2004/03/27 17:54:11  mdw
 * Standard curves and curve checking.
 *
 * Revision 1.6  2004/03/23 15:19:32  mdw
 * Test elliptic curves more thoroughly.
 *
 * Revision 1.5  2004/03/21 22:52:06  mdw
 * Merge and close elliptic curve branch.
 *
 * Revision 1.4.4.2  2004/03/20 00:13:31  mdw
 * Projective coordinates for prime curves
 *
 * Revision 1.4.4.1  2003/06/10 13:43:53  mdw
 * Simple (non-projective) curves over prime fields now seem to work.
 *
 * Revision 1.4  2003/05/15 23:25:59  mdw
 * Make elliptic curve stuff build.
 *
 * Revision 1.3  2002/01/13 13:48:44  mdw
 * Further progress.
 *
 * Revision 1.2  2001/05/07 17:29:44  mdw
 * Treat projective coordinates as an internal representation.  Various
 * minor interface changes.
 *
 * Revision 1.1  2001/04/29 18:12:33  mdw
 * Prototype version.
 *
 */

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

#include "ec.h"

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

/* --- @ec_samep@ --- *
 *
 * Arguments:	@ec_curve *c, *d@ = two elliptic curves
 *
 * Returns:	Nonzero if the curves are identical (not just isomorphic).
 *
 * Use:		Checks for sameness of curves.  This function does the full
 *		check, not just the curve-type-specific check done by the
 *		@sampep@ field operation.
 */

int ec_samep(ec_curve *c, ec_curve *d)
{
  return (field_samep(c->f, d->f) && c->ops == d->ops && EC_SAMEP(c, d));
}

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

ec *ec_create(ec *p) { EC_CREATE(p); return (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:	The argument @p@.
 *
 * Use:		Sets the given point to be the point %$O$% at infinity.
 */

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

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

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

/* --- @ec_eq@ --- *
 *
 * Arguments:	@const ec *p, *q@ = two points
 *
 * Returns:	Nonzero if the points are equal.  Compares external-format
 *		points.
 */

int ec_eq(const ec *p, const ec *q) { return (EC_EQ(p, q)); }

/*----- Standard curve operations -----------------------------------------*/

/* --- @ec_stdsamep@ --- *
 *
 * Arguments:	@ec_curve *c, *d@ = two elliptic curves
 *
 * Returns:	Nonzero if the curves are identical (not just isomorphic).
 *
 * Use:		Simple sameness check on @a@ and @b@ curve members.
 */

int ec_stdsamep(ec_curve *c, ec_curve *d)
{
  return (MP_EQ(c->a, d->a) && MP_EQ(c->b, d->b));
}

/* --- @ec_idin@, @ec_idout@, @ec_idfix@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@ec *d@ = pointer to the destination
 *		@const ec *p@ = pointer to a source point
 *
 * Returns:	The destination @d@.
 *
 * Use:		An identity operation if your curve has no internal
 *		representation.  (The field internal representation is still
 *		used.)
 */

ec *ec_idin(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 = 0;
  }
  return (d);
}

ec *ec_idout(ec_curve *c, ec *d, const ec *p)
{
  if (EC_ATINF(p))
    EC_SETINF(d);
  else {
    field *f = c->f;
    d->x = F_OUT(f, d->x, p->x);
    d->y = F_OUT(f, d->y, p->y);
    mp_drop(d->z); d->z = 0;
  }
  return (d);
}

ec *ec_idfix(ec_curve *c, ec *d, const ec *p)
{
  EC_COPY(d, p);
  return (d);
}

/* --- @ec_projin@, @ec_projout@, @ec_projfix@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@ec *d@ = pointer to the destination
 *		@const ec *p@ = pointer to a source point
 *
 * Returns:	The destination @d@.
 *
 * Use:		Conversion functions if your curve operations use a
 *		projective representation.
 */

ec *ec_projin(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);
  }
  return (d);
}

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

ec *ec_projfix(ec_curve *c, ec *d, const ec *p)
{
  if (EC_ATINF(p))
    EC_SETINF(d);
  else if (d->z == c->f->one)
    EC_COPY(d, p);
  else {
    mp *z, *zz;
    field *f = c->f;
    z = F_INV(f, MP_NEW, p->z);
    zz = F_SQR(f, MP_NEW, z);
    z = F_MUL(f, z, zz, z);
    d->x = F_MUL(f, d->x, p->x, zz);
    d->y = F_MUL(f, d->y, p->y, z);
    mp_drop(z);
    mp_drop(zz);
    mp_drop(d->z);
    d->z = MP_COPY(f->one);
  }
  return (d);
}

/* --- @ec_stdsub@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@ec *d@ = pointer to the destination
 *		@const ec *p, *q@ = the operand points
 *
 * Returns:	The destination @d@.
 *
 * Use:		Standard point subtraction operation, in terms of negation
 *		and addition.  This isn't as efficient as a ready-made
 *		subtraction operator.
 */

ec *ec_stdsub(ec_curve *c, ec *d, const ec *p, const ec *q)
{
  ec t = EC_INIT;
  EC_NEG(c, &t, q);
  EC_FIX(c, &t, &t);
  EC_ADD(c, d, p, &t);
  EC_DESTROY(&t);
  return (d);
}

/*----- Creating curves ---------------------------------------------------*/

/* --- @ec_destroycurve@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an ellptic curve
 *
 * Returns:	---
 *
 * Use:		Destroys a description of an elliptic curve.
 */

void ec_destroycurve(ec_curve *c) { c->ops->destroy(c); }

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

/* --- @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.
 */

ec *ec_find(ec_curve *c, ec *d, mp *x)
{
  x = F_IN(c->f, MP_NEW, x);
  if ((d = EC_FIND(c, d, x)) != 0)
    EC_OUT(c, d, d);
  MP_DROP(x);
  return (d);
}

/* --- @ec_neg@ --- *
 *
 * 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:	The destination point.
 *
 * Use:		Computes the negation of the given point.
 */

ec *ec_neg(ec_curve *c, ec *d, const ec *p)
{
  EC_IN(c, d, p);
  EC_NEG(c, d, d);
  return (EC_OUT(c, d, d));
}

/* --- @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.
 */

ec *ec_add(ec_curve *c, ec *d, const ec *p, const ec *q)
{
  ec pp = EC_INIT, qq = EC_INIT;
  EC_IN(c, &pp, p);
  EC_IN(c, &qq, q);
  EC_ADD(c, d, &pp, &qq);
  EC_OUT(c, d, d);
  EC_DESTROY(&pp);
  EC_DESTROY(&qq);
  return (d);
}

/* --- @ec_sub@ --- *
 *
 * 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:	The destination @d@.
 *
 * Use:		Subtracts one point from another on an elliptic curve.
 */

ec *ec_sub(ec_curve *c, ec *d, const ec *p, const ec *q)
{
  ec pp = EC_INIT, qq = EC_INIT;
  EC_IN(c, &pp, p);
  EC_IN(c, &qq, q);
  EC_SUB(c, d, &pp, &qq);
  EC_OUT(c, d, d);
  EC_DESTROY(&pp);
  EC_DESTROY(&qq);
  return (d);
}

/* --- @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.
 */

ec *ec_dbl(ec_curve *c, ec *d, const ec *p)
{
  EC_IN(c, d, p);
  EC_DBL(c, d, d);
  return (EC_OUT(c, d, d));
}

/* --- @ec_check@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@const ec *p@ = pointer to the point
 *
 * Returns:	Zero if OK, nonzero if this is an invalid point.
 *
 * Use:		Checks that a point is actually on an elliptic curve.
 */

int ec_check(ec_curve *c, const ec *p)
{
  ec t = EC_INIT;
  int rc;

  if (EC_ATINF(p))
    return (0);
  EC_IN(c, &t, p);
  rc = EC_CHECK(c, &t);
  EC_DESTROY(&t);
  return (rc);
}

/* --- @ec_rand@ --- *
 *
 * Arguments:	@ec_curve *c@ = pointer to an elliptic curve
 *		@ec *d@ = pointer to the destination point
 *		@grand *r@ = random number source
 *
 * Returns:	The destination @d@.
 *
 * Use:		Finds a random point on the given curve.
 */

ec *ec_rand(ec_curve *c, ec *d, grand *r)
{
  mp *x = MP_NEW;
  do x = F_RAND(c->f, x, r); while (!EC_FIND(c, d, x));
  mp_drop(x);
  if (grand_range(r, 2)) EC_NEG(c, d, d);
  return (EC_OUT(c, d, d));    
}

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