--- /dev/null
+/* -*-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 -------------------------------------------------*/
--- /dev/null
+/* -*-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 -------------------------------------------------*/
--- /dev/null
+/* -*-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
--- /dev/null
+/* -*-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 <mLib/sub.h>
+
+#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 -------------------------------------------------*/
--- /dev/null
+/* -*-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
projects / u / mdw / catacomb / commitdiff