From b0ab12e6a6cb035df2b6312df7ad1736af0a6128 Mon Sep 17 00:00:00 2001 From: mdw Date: Sun, 29 Apr 2001 18:12:33 +0000 Subject: [PATCH] Prototype version. --- ec-prime.c | 72 +++++++++++++++ ec.c | 280 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ec.h | 296 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ f-prime.c | 164 ++++++++++++++++++++++++++++++++++ field.h | 143 +++++++++++++++++++++++++++++ 5 files changed, 955 insertions(+) create mode 100644 ec-prime.c create mode 100644 ec.c create mode 100644 ec.h create mode 100644 f-prime.c create mode 100644 field.h diff --git a/ec-prime.c b/ec-prime.c new file mode 100644 index 0000000..5a806da --- /dev/null +++ b/ec-prime.c @@ -0,0 +1,72 @@ +/* -*-c-*- + * + * $Id: ec-prime.c,v 1.1 2001/04/29 18:12:33 mdw Exp $ + * + * 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. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: ec-prime.c,v $ + * Revision 1.1 2001/04/29 18:12:33 mdw + * Prototype version. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "ec.h" + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct ecctx { + ec_curve c; + mp *a, *b; +} ecctx; + +/*----- Main code ---------------------------------------------------------*/ + +static void ecadd(ec_curve *c, ec *d, const ec *a, const ec *b) +{ + /* --- Deal with the simple cases --- */ + + 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 if (MP_EQ(a->x, b->x) && MP_EQ(a->z, b->z)) { + if ((a->y->f ^ b->y->f) & MP_NEG) + EC_SETINF(d); + else + ecdbl(c, d, a); + } else { + + /* --- + } +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/ec.c b/ec.c new file mode 100644 index 0000000..604190b --- /dev/null +++ b/ec.c @@ -0,0 +1,280 @@ +/* -*-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 -------------------------------------------------*/ 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 diff --git a/f-prime.c b/f-prime.c new file mode 100644 index 0000000..1a7b9e8 --- /dev/null +++ b/f-prime.c @@ -0,0 +1,164 @@ +/* -*-c-*- + * + * $Id: f-prime.c,v 1.1 2001/04/29 18:12:33 mdw Exp $ + * + * Prime fields with Montgomery arithmetic + * + * (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: f-prime.c,v $ + * Revision 1.1 2001/04/29 18:12:33 mdw + * Prototype version. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include + +#include "field.h" +#include "mpmont.h" + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct fctx { + field f; + mpmont mm; +} fctx; + +/*----- Main code ---------------------------------------------------------*/ + +/* --- Field operations --- */ + +static void fdestroy(field *ff) +{ + fctx *f = (fctx *)ff; + mpmont_destroy(&f->mm); + DESTROY(f); +} + +static mp *fin(field *ff, mp *d, mp *x) +{ + fctx *f = (fctx *)ff; + return (mpmont_mul(&f->mm, d, x, f->mm.r2)); +} + +static mp *fout(field *ff, mp *d, mp *x) +{ + fctx *f = (fctx *)ff; + return (mpmont_reduce(&f->mm, d, x)); +} + +static mp *fadd(field *ff, mp *d, mp *x, mp *y) +{ + return (mp_add(d, x, y)); +} + +static mp *fsub(field *ff, mp *d, mp *x, mp *y) +{ + return (mp_sub(d, x, y)); +} + +static mp *fmul(field *ff, mp *d, mp *x, mp *y) +{ + fctx *f = (fctx *)ff; + return (mpmont_mul(&f->mm, d, x, y)); +} + +static mp *fsqr(field *ff, mp *d, mp *x) +{ + fctx *f = (fctx *)ff; + d = mp_sqr(d, x); + return (mpmont_reduce(&f->mm, d, d)); +} + +static mp *finv(field *ff, mp *d, mp *x) +{ + fctx *f = (fctx *)ff; + d = mpmont_reduce(&f->mm, x); + mp_gcd(0, 0, &d, f->mm.m, d); + return (mpmont_mul(&f->mm, d, d, f->mm.r2)); +} + +static mp *freduce(field *ff, mp *d, mp *x) +{ + fctx *f = (fctx *)ff; + mp_div(0, &d, x, f->mm.m); + return (d); +} + +static mp *fdbl(field *ff, mp *d, mp *x) +{ + fctx *f = (fctx *)ff; + return (mp_lsl(d, x, 1)); +} + +static mp *ftpl(field *ff, mp *d, mp *x) +{ + fctx *f = (fctx *)ff; + MP_DEST(d, MP_LEN(x) + 1, x->f); + MPX_UMULN(d->v, d->vl, x->v, x->vl, 3); + return (d); +} + +static mp *fsqrt(field *ff, mp *d, mp *x) +{ + fctx *f = (fctx *)ff; + d = mpmont_reduce(&f->mm, x); + d = mp_modsqrt(d, d, f->mm.m); + return (mpmont_mul(&f->mm, d, d, f->mm.r2)); +} + +/* --- Field operations table --- */ + +static field_ops fops = { + fdestroy, + fin, fout, + fadd, fsub, fmul, fsqr, finv, freduce, + fdbl, ftpl, fsqrt +}; + +/* --- @field_prime@ --- * + * + * Arguments: @mp *p@ = the characteristic of the field + * + * Returns: A pointer to the field. + * + * Use: Creates a field structure for a prime field of size %$p$%, + * using Montgomery reduction for arithmetic. + */ + +field *field_prime(mp *p) +{ + ftcx *f = CREATE(fctx); + f->f.ops = &fops; + mpmont_create(&f->mm, p); + f->zero = MP_ZERO; + f->one = &f->mm.r; + return (&f->f); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/field.h b/field.h new file mode 100644 index 0000000..35e9df0 --- /dev/null +++ b/field.h @@ -0,0 +1,143 @@ +/* -*-c-*- + * + * $Id: field.h,v 1.1 2001/04/29 18:12:33 mdw Exp $ + * + * Definitions for field arithmetic + * + * (c) 2000 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: field.h,v $ + * Revision 1.1 2001/04/29 18:12:33 mdw + * Prototype version. + * + */ + +#ifndef CATACOMB_FIELD_H +#define CATACOMB_FIELD_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#ifndef CATACOMB_MP_H +# include "mp.h" +#endif + +/*----- Data structures ---------------------------------------------------*/ + +typedef struct field { + const struct field_ops *ops; /* Field operations */ + mp *zero, *one; /* Identities in the field */ +} field; + +typedef struct field_ops { + + /* --- Universal operations --- */ + + void (*destroy)(field */*f*/); + + mp *(*in)(field */*f*/, mp */*d*/, mp */*x*/); + mp *(*out)(field */*f*/, mp */*d*/, mp */*x*/); + + mp *(*add)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/); + mp *(*sub)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/); + mp *(*mul)(field */*f*/, mp */*d*/, mp */*x*/, mp */*y*/); + mp *(*sqr)(field */*f*/, mp */*d*/, mp */*x*/); + mp *(*inv)(field */*f*/, mp */*d*/, mp */*x*/); + mp *(*reduce)(field */*f*/, mp */*d*/, mp */*x*/); + + /* --- Operations for prime fields only --- */ + + mp *(*dbl)(field */*f*/, mp */*d*/, mp */*x*/); + mp *(*tpl)(field */*f*/, mp */*d*/, mp */*x*/); + mp *(*sqrt)(field */*f*/, mp */*d*/, mp */*x*/); + +} field_ops; + +#define F_DESTROY(f) (f)->ops->destroy((f)) + +#define F_IN(f, d, x) (f)->ops->in((f), (d), (x)) +#define F_OUT(f, d, x) (f)->ops->out((f), (d), (x)) +#define F_ADD(f, d, x, y) (f)->ops->add((f), (d), (x), (y)) +#define F_SUB(f, d, x, y) (f)->ops->sub((f), (d), (x), (y)) +#define F_MUL(f, d, x, y) (f)->ops->mul((f), (d), (x), (y)) +#define F_SQR(f, d, x) (f)->ops->sqr((f), (d), (x)) +#define F_INV(f, d, x) (f)->ops->inv((f), (d), (x)) +#define F_REDUCE(f, d, x) (f)->ops->reduce((f), (d), (x)) + +#define F_DBL(f, d, x) (f)->ops->dbl((f), (d), (x)) +#define F_TPL(f, d, x) (f)->ops->tpl((f), (d), (x)) +#define F_SQRT(f, d, x) (f)->ops->sqrt((f), (d), (x)) + +/*----- Creating fields ---------------------------------------------------*/ + +/* --- @field_prime@ --- * + * + * Arguments: @mp *p@ = the characteristic of the field + * + * Returns: A pointer to the field. + * + * Use: Creates a field structure for a prime field of size %$p$%, + * using Montgomery reduction for arithmetic. + */ + +extern field *field_prime(mp */*p*/); + +/* --- @field_binpoly@ --- * + * + * Arguments: @mp *p@ = an irreducible polynomial over %$\gf{2}$% + * + * Returns: A pointer to the field. + * + * Use: Creates a field structure for a binary field using naive + * arithmetic. + */ + +extern field *field_binpoly(mp */*p*/); + +/* --- @field_binsparsepoly@ --- * + * + * Arguments: @unsigned deg@ = the degree of the field polynomial + * @const unsigned *c@ = degrees of nonzero coefficients + * + * Returns: A pointer to the field. + * + * Use: Creates a field structure for a binary field taking advantage + * of the sparseness of the given polynomial to improve + * reduction performance. + */ + +extern field *field_binsparsepoly(unsigned /*deg*/, const unsigned */*c*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif -- 2.11.0