X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/5233862aa438102e71474baa9eec7f6e3d6a2c36..b0ab12e6a6cb035df2b6312df7ad1736af0a6128:/ec.h?ds=sidebyside diff --git a/ec.h b/ec.h new file mode 100644 index 0000000..db5adfc --- /dev/null +++ b/ec.h @@ -0,0 +1,296 @@ +/* -*-c-*- + * + * $Id: ec.h,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.h,v $ + * 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 ------------------------------------------------------*/ + +#include "field.h" +#include "mp.h" + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct ec_curve { + const struct ec_ops *ops; /* Curve operations */ + field *f; /* Underlying field structure */ +} ec_curve; + +typedef struct ec { + mp *x, *y; /* Point coordinates */ + mp *z; /* Common denominator (or null) */ +} ec; + +typedef struct ec_ops { + void (*destroy)(ec_curve */*c*/); + int (*find)(ec_curve */*c*/, ec */*d*/, mp */*x*/); + void (*add)(ec_curve */*c*/, ec */*d*/, ec */*p*/, ec */*q*/); + void (*dbl)(ec_curve */*c*/, ec */*d*/, ec */*p*/); +} ec_ops; + +#define EC_DESTROY(c) (c)->ops->destroy((c)) + +#define EC_FIND(c, d, x) (c)->ops->find((c), (d), (x)) +#define EC_ADD(c, d, p, q) (c)->ops->add((c), (d), (p), (q)) +#define EC_DBL(c, d, p) (c)->ops->dbl((c), (d), (p)) + +/*----- Simple memory management things -----------------------------------*/ + +/* --- @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). + */ + +#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 void 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: --- + * + * 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 void ec_setinf(ec */*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. + */ + +#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 = _p->x; \ + _d->y = _p->y; \ + _d->z = _p->z; \ + } \ + } \ +} while (0) + +extern void ec_copy(ec */*d*/, const ec */*p*/); + +/*----- Interesting 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. + */ + +extern void ec_denorm(ec_curve */*c*/, ec */*d*/, const ec */*p*/); + +/* --- @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. + */ + +extern void ec_norm(ec_curve */*c*/, ec */*d*/, const ec */*p*/); + +/* --- @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. + */ + +extern void ec_find(ec_curve */*c*/, ec */*d*/, mp */*x*/); + +/* --- @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. + */ + +extern void ec_add(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: --- + * + * Use: Doubles a point on an elliptic curve. + */ + +extern void ec_dbl(ec_curve */*c*/, ec */*d*/, const ec */*p*/); + +/* --- @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$%. + */ + +extern void ec_mul(ec_curve */*c*/, ec */*d*/, const ec */*p*/, mp */*n*/); + +/*----- Creating curves ---------------------------------------------------*/ + +/* --- @ec_prime@ --- * + * + * Arguments: @field *f@ = the underyling 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. + */ + +extern ec_curve *ec_prime(field */*f*/, mp */*a*/, mp */*b*/); + +/* --- @ec_bin@ --- * + * + * 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 a non-supersingular elliptic + * curve defined over a binary field. + */ + +extern ec_curve *ec_bin(field */*f*/, mp */*a*/, mp */*b*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif