Add cyclic group abstraction, with test code. Separate off exponentation

[u/mdw/catacomb] / ec.h

/* -*-c-*-
 *
 * $Id: ec.h,v 1.9 2004/04/01 12:50:09 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.h,v $
 * Revision 1.9  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.8  2004/03/27 17:54:11  mdw
 * Standard curves and curve checking.
 *
 * Revision 1.7  2004/03/23 15:19:32  mdw
 * Test elliptic curves more thoroughly.
 *
 * Revision 1.6  2004/03/22 02:19:10  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.5  2004/03/21 22:52:06  mdw
 * Merge and close elliptic curve branch.
 *
 * Revision 1.4.4.3  2004/03/21 22:39:46  mdw
 * Elliptic curves on binary fields work.
 *
 * 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.
 *
 */

#ifndef CATACOMB_EC_H
#define CATACOMB_EC_H

#ifdef __cplusplus
  extern "C" {
#endif

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

#ifndef CATACOMB_FIELD_H
#  include "field.h"
#endif

#ifndef CATACOMB_MP_H
#  include "mp.h"
#endif

#ifndef CATACOMB_QDPARSE_H
#  include "qdparse.h"
#endif

/*----- Data structures ---------------------------------------------------*/

/* --- An elliptic curve representation --- */

typedef struct ec_curve {
  const struct ec_ops *ops;             /* Curve operations */
  field *f;                             /* Underlying field structure */
  mp *a, *b;                            /* Standard params (internal form) */
} ec_curve;

/* --- An elliptic curve point --- */

typedef struct ec {
  mp *x, *y;                            /* Point coordinates */
  mp *z;                                /* Common denominator (or null) */
} ec;

/* --- A factor for simultaneous multiplication --- */

typedef struct ec_mulfactor {
  ec base;                              /* The point */
  mp *exp;                              /* The exponent */
} ec_mulfactor;

/* --- Elliptic curve operations --- *
 *
 * All operations (apart from @destroy@ and @in@) are guaranteed to be
 * performed on internal representations of points.
 *
 * (Historical note.  We used to guarantee that the second to @add@ and @mul@
 * was the output of @in@ or @fix@, but this canonification turned out to
 * make the precomputation in @ec_exp@ too slow.  Projective implementations
 * must therefore cope with a pair of arbitrary points.)
 */

typedef struct ec_ops {
  void (*destroy)(ec_curve */*c*/);
  int (*samep)(ec_curve */*c*/, ec_curve */*d*/);
  ec *(*in)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
  ec *(*out)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
  ec *(*fix)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
  ec *(*find)(ec_curve */*c*/, ec */*d*/, mp */*x*/);
  ec *(*neg)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
  ec *(*add)(ec_curve */*c*/, ec */*d*/, const ec */*p*/, const ec */*q*/);
  ec *(*sub)(ec_curve */*c*/, ec */*d*/, const ec */*p*/, const ec */*q*/);
  ec *(*dbl)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
  int (*check)(ec_curve */*c*/, const ec */*p*/);
} ec_ops;

#define EC_SAMEP(c, d)          (c)->ops->samep((c), (d))
#define EC_IN(c, d, p)          (c)->ops->in((c), (d), (p))
#define EC_OUT(c, d, p)         (c)->ops->out((c), (d), (p))
#define EC_FIX(c, d, p)         (c)->ops->fix((c), (d), (p))

#define EC_FIND(c, d, x)        (c)->ops->find((c), (d), (x))
#define EC_NEG(c, d, x)         (c)->ops->neg((c), (d), (x))
#define EC_ADD(c, d, p, q)      (c)->ops->add((c), (d), (p), (q))
#define EC_SUB(c, d, p, q)      (c)->ops->sub((c), (d), (p), (q))
#define EC_DBL(c, d, p)         (c)->ops->dbl((c), (d), (p))
#define EC_CHECK(c, p)          (c)->ops->check((c), (p))

/* --- Elliptic curve parameters --- */

typedef struct ec_info {
  ec_curve *c;                          /* The actual curve */
  ec g;                                 /* The common point */
  mp *r;                                /* Order of %$g$% */
  mp *h;                                /* Cofactor %$h = \#E/r$% */
} ec_info;

/*----- Simple memory management things -----------------------------------*/

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

#define EC_INIT { MP_NEW, MP_NEW, MP_NEW }

#define EC_CREATE(p) do {                                               \
  ec *_p = (p);                                                         \
  _p->x = _p->y = _p->z = MP_NEW;                                       \
} while (0)

extern ec *ec_create(ec */*p*/);

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

#define EC_DESTROY(p) do {                                              \
  ec *_p = (p);                                                         \
  if (!EC_ATINF(_p)) {                                                  \
    MP_DROP(_p->x);                                                     \
    MP_DROP(_p->y);                                                     \
    if (_p->z) MP_DROP(_p->z);                                          \
  }                                                                     \
} while (0)

extern void ec_destroy(ec */*p*/);

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

#define EC_ATINF(p) ((p)->x == MP_NEW || (p)->x == MP_NEWSEC)

extern int ec_atinf(const ec */*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.
 */

#define EC_SETINF(p) do {                                               \
  ec *_p = (p);                                                         \
  if (!EC_ATINF(_p)) {                                                  \
    MP_DROP(_p->x);                                                     \
    MP_DROP(_p->y);                                                     \
    if (_p->z) MP_DROP(_p->z);                                          \
    _p->x = _p->y = _p->z = MP_NEW;                                     \
    _p->y = MP_NEW;                                                     \
    _p->z = MP_NEW;                                                     \
  }                                                                     \
} while (0)

extern ec *ec_setinf(ec */*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.
 */

#define EC_COPY(d, p) do {                                              \
  ec *_d = (d);                                                         \
  const ec *_p = (p);                                                   \
  if (d != p) {                                                         \
    EC_DESTROY(d);                                                      \
    if (EC_ATINF(p))                                                    \
      _d->x = _d->y = _d->z = MP_NEW;                                   \
    else {                                                              \
      _d->x = MP_COPY(_p->x);                                           \
      _d->y = MP_COPY(_p->y);                                           \
      _d->z = _p->z ? MP_COPY(_p->z) : MP_NEW;                          \
    }                                                                   \
  }                                                                     \
} while (0)

extern ec *ec_copy(ec */*d*/, const ec */*p*/);

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

#define EC_EQ(p, q)                                                     \
    ((EC_ATINF(p) && EC_ATINF(q)) ||                                    \
     (!EC_ATINF(p) && !EC_ATINF(q) &&                                   \
      MP_EQ((p)->x, (q)->x) &&                                          \
      MP_EQ((p)->y, (q)->y)))

extern int ec_eq(const ec *p, const ec *q);

/*----- Interesting arithmetic --------------------------------------------*/

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

extern int ec_samep(ec_curve */*c*/, ec_curve */*d*/);

/* --- @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:     The destination if OK, or null if no point was found.
 *
 * Use:         Finds a point on an elliptic curve with a given
 *              x-coordinate.  If there is no point with the given
 *              %$x$%-coordinate, a null pointer is returned and the
 *              destination is left invalid.
 */

extern ec *ec_find(ec_curve */*c*/, ec */*d*/, mp */*x*/);

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

extern ec *ec_rand(ec_curve */*c*/, ec */*d*/, grand */*r*/);

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

extern ec *ec_neg(ec_curve */*c*/, ec */*d*/, const ec */*p*/);

/* --- @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:     The destination @d@.
 *
 * Use:         Adds two points on an elliptic curve.
 */

extern ec *ec_add(ec_curve */*c*/, ec */*d*/,
                  const ec */*p*/, const ec */*q*/);

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

extern ec *ec_sub(ec_curve */*c*/, ec */*d*/,
                  const ec */*p*/, const ec */*q*/);

/* --- @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:     The destination @d@.
 *
 * Use:         Doubles a point on an elliptic curve.
 */

extern ec *ec_dbl(ec_curve */*c*/, ec */*d*/, const ec */*p*/);

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

extern int ec_check(ec_curve */*c*/, const ec */*p*/);

/* --- @ec_mul@, @ec_imul@ --- *
 *
 * 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:     The destination @d@.
 *
 * Use:         Multiplies a point by a scalar, returning %$n p$%.  The
 *              @imul@ variant uses internal representations for argument
 *              and result.
 */

extern ec *ec_mul(ec_curve */*c*/, ec */*d*/, const ec */*p*/, mp */*n*/);
extern ec *ec_imul(ec_curve */*c*/, ec */*d*/, const ec */*p*/, mp */*n*/);

/* --- @ec_mmul@, @ec_immul@ --- *
 *
 * Arguments:   @ec_curve *c@ = pointer to an elliptic curve
 *              @ec *d@ = pointer to the destination point
 *              @const ec_mulfactor *f@ = pointer to vector of factors
 *              @size_t n@ = number of factors
 *
 * Returns:     The destination @d@.
 *
 * Use:         Does simultaneous point multiplication.  The @immul@ variant
 *              uses internal representations for arguments and result.
 */

extern ec *ec_mmul(ec_curve */*c*/, ec */*d*/,
                   const ec_mulfactor */*f*/, size_t /*n*/);
extern ec *ec_immul(ec_curve */*c*/, ec */*d*/,
                    const ec_mulfactor */*f*/, size_t /*n*/);

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

extern int ec_stdsamep(ec_curve */*c*/, ec_curve */*d*/);

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

extern ec *ec_idin(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
extern ec *ec_idout(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
extern ec *ec_idfix(ec_curve */*c*/, ec */*d*/, const ec */*p*/);

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

extern ec *ec_projin(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
extern ec *ec_projout(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
extern ec *ec_projfix(ec_curve */*c*/, ec */*d*/, const ec */*p*/);

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

extern ec *ec_stdsub(ec_curve */*c*/, ec */*d*/,
                     const ec */*p*/, const ec */*q*/);

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

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

extern void ec_destroycurve(ec_curve */*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.
 *
 * 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*/);
extern ec_curve *ec_primeproj(field */*f*/, mp */*a*/, mp */*b*/);

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

extern ec_curve *ec_bin(field */*f*/, mp */*a*/, mp */*b*/);
extern ec_curve *ec_binproj(field */*f*/, mp */*a*/, mp */*b*/);

/*----- Curve parameter sets ----------------------------------------------*/

/* --- @ec_curveparse@ --- *
 *
 * Arguments:   @qd_parse *qd@ = parser context
 *
 * Returns:     Elliptic curve pointer if OK, or null.
 *
 * Use:         Parses an elliptic curve description, which has the form
 *
 *                * a field description
 *                * an optional `/'
 *                * `prime', `primeproj', `bin', or `binproj'
 *                * an optional `:'
 *                * the %$a$% parameter
 *                * an optional `,'
 *                * the %$b$% parameter
 */

extern ec_curve *ec_curveparse(qd_parse */*qd*/);

/* --- @ec_ptparse@ --- *
 *
 * Arguments:   @qd_parse *qd@ = parser context
 *              @ec *p@ = where to put the point
 *
 * Returns:     The point address, or null.
 *
 * Use:         Parses an elliptic curve point.  This has the form
 *
 *                * %$x$%-coordinate
 *                * optional `,'
 *                * %$y$%-coordinate
 */

extern ec *ec_ptparse(qd_parse */*qd*/, ec */*p*/);

/* --- @ec_infoparse@ --- *
 *
 * Arguments:   @qd_parse *qd@ = parser context
 *              @ec_info *ei@ = curve information block, currently
 *                      uninitialized
 *
 * Returns:     Zero on success, nonzero on failure.
 *
 * Use:         Parses an elliptic curve information string, and stores the
 *              information in @ei@.  This has the form
 *
 *                * elliptic curve description
 *                * optional `/'
 *                * common point
 *                * optional `:'
 *                * group order
 *                * optional `*'
 *                * cofactor
 */

extern int ec_infoparse(qd_parse */*qd*/, ec_info */*ei*/);

/* --- @ec_getinfo@ --- *
 *
 * Arguments:   @ec_info *ei@ = where to write the information
 *              @const char *p@ = string describing a curve
 *
 * Returns:     Null on success, or a pointer to an error message.
 *
 * Use:         Parses out information about a curve.  The string is either a
 *              standard curve name, or a curve info string.
 */

extern const char *ec_getinfo(ec_info */*ei*/, const char */*p*/);

/* --- @ec_sameinfop@ --- *
 *
 * Arguments:   @ec_info *ei, *ej@ = two elliptic curve parameter sets
 *
 * Returns:     Nonzero if the curves are identical (not just isomorphic).
 *
 * Use:         Checks for sameness of curve parameters.
 */

extern int ec_sameinfop(ec_info */*ei*/, ec_info */*ej*/);

/* --- @ec_freeinfo@ --- *
 *
 * Arguments:   @ec_info *ei@ = elliptic curve information block to free
 *
 * Returns:     ---
 *
 * Use:         Frees the information block.
 */

extern void ec_freeinfo(ec_info */*ei*/);

/* --- @ec_checkinfo@ --- *
 *
 * Arguments:   @const ec_info *ei@ = elliptic curve information block
 *
 * Returns:     Null if OK, or pointer to error message.
 *
 * Use:         Checks an elliptic curve according to the rules in SEC1.
 */

extern const char *ec_checkinfo(const ec_info */*ei*/, grand */*gr*/);

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

#ifdef __cplusplus
  }
#endif

#endif