## -*-m4-*-
##
-## $Id: Makefile.m4,v 1.70 2004/03/27 00:04:46 mdw Exp $
+## $Id: Makefile.m4,v 1.71 2004/03/27 17:54:11 mdw Exp $
##
## Makefile for Catacomb
##
##----- Revision history ----------------------------------------------------
##
## $Log: Makefile.m4,v $
+## Revision 1.71 2004/03/27 17:54:11 mdw
+## Standard curves and curve checking.
+##
## Revision 1.70 2004/03/27 00:04:46 mdw
## Implement efficient reduction for pleasant-looking primes.
##
./mptypes >mptypes.h.new
mv mptypes.h.new mptypes.h
+ectab.c: ectab.in ec-gentab.sh mpdump
+ $(srcdir)/ec-gentab.sh <$(srcdir)/ectab.in >ectab.c.new
+ mv ectab.c.new ectab.c
+
BUILT_SOURCES = \
getdate.c modes-stamp \
addsuffix(join(`ciphers', `-', `cipher_modes'), `.c') \
## difference between the first and last numbers is major version.
pkginclude_HEADERS = \
- arena.h paranoia.h buf.h \
+ arena.h paranoia.h buf.h qdparse.h \
blkc.h hash.h gcipher.h ghash.h gmac.h grand.h ghash-def.h \
lcrand.h fibrand.h rc4.h seal.h rand.h noise.h fipstest.h maurer.h \
key.h key-data.h passphrase.h pixie.h lmem.h \
gfreduce.c gfreduce-exp.h ')
define(`EC_SOURCES',
- `field.c f-prime.c f-niceprime.c f-binpoly.c \
- ec.c ec-prime.c ec-bin.c ec-test.c')
+ `field.c field-parse.c f-prime.c f-niceprime.c f-binpoly.c \
+ ec.c ec-prime.c ec-bin.c ec-test.c ec-info.c ectab.c')
define(`PGEN_SOURCES',
`pfilt.c rabin.c \
libcatacomb_la_SOURCES = \
grand.c keysz.c \
lcrand.c fibrand.c rc4.c seal.c rand.c noise.c fipstest.c maurer.c \
- arena.c \
+ arena.c qdparse.c \
passphrase.c pixie-client.c pixie-common.c lmem.c \
oaep.c pkcs1.c pss.c tlsprf.c sslprf.c \
gfshare.c \
bin_PROGRAMS = dsig key pixie rspit factorial hashsum mkphrase
bin_SCRIPTS = catacomb-config xpixie
noinst_PROGRAMS = \
- genprimes mptypes serpent-check bittest \
+ genprimes mptypes serpent-check bittest mpdump \
addsuffix(`gen_tables', `-mktab')
LDADD = libcatacomb.la
mptypes_SOURCES = mptypes.c
mptypes_LDADD =
+mpdump_SOURCES = \
+ mpdump.c \
+ mpx.c mpx-kmul.c mpx-ksqr.c mpscan.c mparena.c \
+ mp-misc.c mp-mem.c mp-const.c mp-arith.c mp-io.c \
+ mptext.c mptext-string.c
+mpdump_LDADD =
+
## --- Install the pixie setuid-root if we can ---
##
## Bodge around a bug in Automake: it doesn't call `install-exec-hook' from
/* -*-c-*-
*
- * $Id: ec-bin.c,v 1.4 2004/03/23 15:19:32 mdw Exp $
+ * $Id: ec-bin.c,v 1.5 2004/03/27 17:54:11 mdw Exp $
*
* Arithmetic for elliptic curves over binary fields
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec-bin.c,v $
+ * Revision 1.5 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
* Revision 1.4 2004/03/23 15:19:32 mdw
* Test elliptic curves more thoroughly.
*
typedef struct ecctx {
ec_curve c;
- mp *a, *b;
mp *bb;
} ecctx;
static ec *ecfind(ec_curve *c, ec *d, mp *x)
{
field *f = c->f;
- ecctx *cc = (ecctx *)c;
mp *y, *u, *v;
if (F_ZEROP(f, x))
- y = F_SQRT(f, MP_NEW, cc->b);
+ y = F_SQRT(f, MP_NEW, c->b);
else {
u = F_SQR(f, MP_NEW, x); /* %$x^2$% */
- y = F_MUL(f, MP_NEW, u, cc->a); /* %$a x^2$% */
- y = F_ADD(f, y, y, cc->b); /* %$a x^2 + b$% */
+ y = F_MUL(f, MP_NEW, u, c->a); /* %$a x^2$% */
+ y = F_ADD(f, y, y, c->b); /* %$a x^2 + b$% */
v = F_MUL(f, MP_NEW, u, x); /* %$x^3$% */
y = F_ADD(f, y, y, v); /* %$A = x^3 + a x^2 + b$% */
if (!F_ZEROP(f, y)) {
EC_SETINF(d);
else {
field *f = c->f;
- ecctx *cc = (ecctx *)c;
mp *lambda;
mp *dx, *dy;
dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */
dx = F_ADD(f, dx, dx, lambda); /* %$\lambda^2 + \lambda$% */
- dx = F_ADD(f, dx, dx, cc->a); /* %$x' = a + \lambda^2 + \lambda$% */
+ dx = F_ADD(f, dx, dx, c->a); /* %$x' = a + \lambda^2 + \lambda$% */
dy = F_ADD(f, MP_NEW, a->x, dx); /* %$ x + x' $% */
dy = F_MUL(f, dy, dy, lambda); /* %$ (x + x') \lambda$% */
EC_COPY(d, a);
else {
field *f = c->f;
- ecctx *cc = (ecctx *)c;
mp *lambda;
mp *dx, *dy;
dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */
dx = F_ADD(f, dx, dx, lambda); /* %$\lambda^2 + \lambda$% */
- dx = F_ADD(f, dx, dx, cc->a); /* %$a + \lambda^2 + \lambda$% */
+ dx = F_ADD(f, dx, dx, c->a); /* %$a + \lambda^2 + \lambda$% */
dx = F_ADD(f, dx, dx, a->x); /* %$a + \lambda^2 + \lambda + x_0$% */
dx = F_ADD(f, dx, dx, b->x);
/* %$x' = a + \lambda^2 + \lambda + x_0 + x_1$% */
dx = F_SQR(f, dx, lambda); /* %$\lambda^2$% */
dx = F_ADD(f, dx, dx, lambda); /* %$\lambda^2 + \lambda$% */
- dx = F_ADD(f, dx, dx, cc->a); /* %$x' = a + \lambda^2 + \lambda$% */
+ dx = F_ADD(f, dx, dx, c->a); /* %$x' = a + \lambda^2 + \lambda$% */
dy = MP_NEW;
}
EC_COPY(d, a);
else {
field *f = c->f;
- ecctx *cc = (ecctx *)c;
mp *dx, *dy, *dz, *u, *uu, *v, *t, *s, *ss, *r, *w, *l;
dz = F_SQR(f, MP_NEW, b->z); /* %$z_1^2$% */
t = F_ADD(f, t, r, dz); /* %$t = r + z'$% */
uu = F_SQR(f, MP_NEW, dz); /* %$z'^2$% */
- dx = F_MUL(f, MP_NEW, uu, cc->a); /* %$a z'^2$% */
+ dx = F_MUL(f, MP_NEW, uu, c->a); /* %$a z'^2$% */
uu = F_MUL(f, uu, t, r); /* %$t r$% */
dx = F_ADD(f, dx, dx, uu); /* %$a z'^2 + t r$% */
r = F_SQR(f, r, w); /* %$w^2$% */
static int eccheck(ec_curve *c, const ec *p)
{
- ecctx *cc = (ecctx *)c;
field *f = c->f;
int rc;
mp *u, *v;
v = F_SQR(f, MP_NEW, p->x);
u = F_MUL(f, MP_NEW, v, p->x);
- v = F_MUL(f, v, v, cc->a);
+ v = F_MUL(f, v, v, c->a);
u = F_ADD(f, u, u, v);
- u = F_ADD(f, u, u, cc->b);
+ u = F_ADD(f, u, u, c->b);
v = F_MUL(f, v, p->x, p->y);
u = F_ADD(f, u, u, v);
v = F_SQR(f, v, p->y);
static void ecdestroy(ec_curve *c)
{
ecctx *cc = (ecctx *)c;
- MP_DROP(cc->a);
- MP_DROP(cc->b);
+ MP_DROP(cc->c.a);
+ MP_DROP(cc->c.b);
if (cc->bb) MP_DROP(cc->bb);
DESTROY(cc);
}
ecctx *cc = CREATE(ecctx);
cc->c.ops = &ec_binops;
cc->c.f = f;
- cc->a = F_IN(f, MP_NEW, a);
- cc->b = F_IN(f, MP_NEW, b);
+ cc->c.a = F_IN(f, MP_NEW, a);
+ cc->c.b = F_IN(f, MP_NEW, b);
cc->bb = 0;
return (&cc->c);
}
ecctx *cc = CREATE(ecctx);
cc->c.ops = &ec_binprojops;
cc->c.f = f;
- cc->a = F_IN(f, MP_NEW, a);
- cc->b = F_IN(f, MP_NEW, b);
+ cc->c.a = F_IN(f, MP_NEW, a);
+ cc->c.b = F_IN(f, MP_NEW, b);
cc->bb = F_SQRT(f, MP_NEW, b);
cc->bb = F_SQRT(f, cc->bb, cc->bb);
return (&cc->c);
--- /dev/null
+#! /bin/sh
+
+set -e
+
+cat <<EOF
+/* -*-c-*-
+ *
+ * Table of standard elliptic curves [generated]
+ */
+
+#include "ectab.h"
+
+#define N(x) (sizeof(x)/sizeof(*x))
+
+/*----- Curve data --------------------------------------------------------*/
+
+EOF
+
+names=""
+while read t n f; do
+
+ case $t in
+ curve) ;;
+ alias) names="$names $n=$f" continue;;
+ \#* | "") continue;;
+ *) echo >&2 "$0: unknown keyword $t"; exit 1;;
+ esac
+
+ names="$names $n=$n"
+ cat <<EOF
+/* --- Curve $n --- */
+
+EOF
+
+ n=`echo $n | sed 's/[^a-zA-Z0-9_][^a-zA-Z0-9_]*/_/g'`
+ case $f in
+ prime | niceprime | binpoly)
+ read t p;
+ if [ $t != p ]; then echo >&2 "$0: wanted p; found $t"; exit 1; fi
+ read t a
+ if [ $t != a ]; then echo >&2 "$0: wanted a; found $t"; exit 1; fi
+ read t b
+ if [ $t != b ]; then echo >&2 "$0: wanted b; found $t"; exit 1; fi
+
+ cat <<EOF
+static const mpw c_${n}_p[] = {
+EOF
+ ./mpdump $p
+ cat <<EOF
+};
+
+static const mpw c_${n}_a[] = {
+EOF
+ ./mpdump $a
+ cat <<EOF
+};
+
+static const mpw c_${n}_b[] = {
+EOF
+ ./mpdump $b
+ cat <<EOF
+};
+
+EOF
+ ;;
+ *) echo >&2 "$0: unknown field type $f"; exit 1;;
+ esac
+
+ read t r
+ if [ $t != r ]; then echo >&2 "$0: wanted r; found $t"; exit 1; fi
+ read t h
+ if [ $t != h ]; then echo >&2 "$0: wanted h; found $t"; exit 1; fi
+ read t gx
+ if [ $t != gx ]; then echo >&2 "$0: wanted gx; found $t"; exit 1; fi
+ read t gy
+ if [ $t != gy ]; then echo >&2 "$0: wanted gy; found $t"; exit 1; fi
+
+ cat <<EOF
+static const mpw c_${n}_r[] = {
+EOF
+ ./mpdump $r
+ cat <<EOF
+};
+
+static const mpw c_${n}_h[] = {
+EOF
+ ./mpdump $h
+ cat <<EOF
+};
+
+static const mpw c_${n}_gx[] = {
+EOF
+ ./mpdump $gx
+ cat <<EOF
+};
+
+static const mpw c_${n}_gy[] = {
+EOF
+ ./mpdump $gy
+ cat <<EOF
+};
+
+EOF
+
+ case $f in
+ prime) ftag=FTAG_PRIME;;
+ niceprime) ftag=FTAG_NICEPRIME;;
+ binpoly) ftag=FTAG_BINPOLY;;
+ esac
+ cat <<EOF
+static const ecdata c_$n = {
+ $ftag,
+ c_${n}_p, N(c_${n}_p),
+ c_${n}_a, N(c_${n}_a),
+ c_${n}_b, N(c_${n}_b),
+ c_${n}_r, N(c_${n}_r),
+ c_${n}_h, N(c_${n}_h),
+ c_${n}_gx, N(c_${n}_gx),
+ c_${n}_gy, N(c_${n}_gy)
+};
+
+EOF
+
+done
+
+cat <<EOF
+/*----- Main table --------------------------------------------------------*/
+
+const ecentry ectab[] = {
+EOF
+for i in $names; do
+ a=`echo $i | sed 's/=.*$//'`
+ n=`echo $i | sed 's/^.*=//; s/[^a-zA-Z0-9_][^a-zA-Z0-9_]*/_/g'`
+ cat <<EOF
+ { "$a", &c_$n },
+EOF
+done
+cat <<EOF
+ { 0, 0 }
+};
+
+/*----- That's all, folks -------------------------------------------------*/
+EOF
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: ec-info.c,v 1.1 2004/03/27 17:54:11 mdw Exp $
+ *
+ * Elliptic curve information management
+ *
+ * (c) 2004 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-info.c,v $
+ * Revision 1.1 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "ec.h"
+#include "ectab.h"
+#include "gf.h"
+#include "pgen.h"
+#include "mprand.h"
+#include "rabin.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @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
+ */
+
+ec_curve *ec_curveparse(qd_parse *qd)
+{
+ mp *a = MP_NEW, *b = MP_NEW;
+ ec_curve *c;
+ field *f;
+
+ if ((f = field_parse(qd)) == 0) goto fail;
+ qd_delim(qd, '/');
+ switch (qd_enum(qd, "prime,primeproj,bin,binproj")) {
+ case 0:
+ if (F_TYPE(f) != FTY_PRIME) {
+ qd->e = "field not prime";
+ goto fail;
+ }
+ qd_delim(qd, ':');
+ if ((a = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, ',');
+ if ((b = qd_getmp(qd)) == 0) goto fail;
+ c = ec_prime(f, a, b);
+ break;
+ case 1:
+ if (F_TYPE(f) != FTY_PRIME) {
+ qd->e = "field not prime";
+ goto fail;
+ }
+ qd_delim(qd, ':');
+ if ((a = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, ',');
+ if ((b = qd_getmp(qd)) == 0) goto fail;
+ c = ec_primeproj(f, a, b);
+ break;
+ case 2:
+ if (F_TYPE(f) != FTY_BINARY) {
+ qd->e = "field not binary";
+ goto fail;
+ }
+ qd_delim(qd, ':');
+ if ((a = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, ',');
+ if ((b = qd_getmp(qd)) == 0) goto fail;
+ c = ec_bin(f, a, b);
+ break;
+ case 3:
+ if (F_TYPE(f) != FTY_BINARY) {
+ qd->e = "field not binary";
+ goto fail;
+ }
+ qd_delim(qd, ':');
+ if ((a = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, ',');
+ if ((b = qd_getmp(qd)) == 0) goto fail;
+ c = ec_binproj(f, a, b);
+ break;
+ default:
+ goto fail;
+ }
+ if (a) MP_DROP(a);
+ if (b) MP_DROP(b);
+ return (c);
+
+fail:
+ if (f) F_DESTROY(f);
+ if (a) MP_DROP(a);
+ if (b) MP_DROP(b);
+ return (0);
+}
+
+/* --- @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
+ */
+
+ec *ec_ptparse(qd_parse *qd, ec *p)
+{
+ mp *x = MP_NEW, *y = MP_NEW;
+
+ if (qd_enum(qd, "inf") >= 0) {
+ EC_SETINF(p);
+ return (p);
+ }
+ if ((x = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, ',');
+ if ((y = qd_getmp(qd)) == 0) goto fail;
+ EC_DESTROY(p);
+ p->x = x;
+ p->y = y;
+ p->z = 0;
+ return (p);
+
+fail:
+ if (x) MP_DROP(x);
+ if (y) MP_DROP(y);
+ return (0);
+}
+
+/* --- @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
+ */
+
+int ec_infoparse(qd_parse *qd, ec_info *ei)
+{
+ ec_curve *c = 0;
+ field *f;
+ ec g = EC_INIT;
+ mp *r = MP_NEW, *h = MP_NEW;
+
+ if ((c = ec_curveparse(qd)) == 0) goto fail;
+ qd_delim(qd, '/'); if (!ec_ptparse(qd, &g)) goto fail;
+ qd_delim(qd, ':'); if ((r = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, '*'); if ((h = qd_getmp(qd)) == 0) goto fail;
+
+ ei->c = c; ei->g = g; ei->r = r; ei->h = h;
+ return (0);
+
+fail:
+ EC_DESTROY(&g);
+ if (r) MP_DROP(r);
+ if (h) MP_DROP(h);
+ if (c) { f = c->f; ec_destroycurve(c); F_DESTROY(f); }
+ return (-1);
+}
+
+/* --- @getinfo@ --- *
+ *
+ * Arguments: @ec_info *ei@ = where to write the information
+ * @const ecdata *ed@ = raw data
+ *
+ * Returns: ---
+ *
+ * Use: Loads elliptic curve information about one of the standard
+ * curves.
+ */
+
+static mp *getmp(const mpw *v, size_t n)
+{
+ mp *x = mp_new(n, 0);
+ memcpy(x->v, v, MPWS(n));
+ return (x);
+}
+
+static void getinfo(ec_info *ei, const ecdata *ed)
+{
+ field *f;
+ mp *p = 0, *a = 0, *b = 0;
+
+ switch (ed->ftag) {
+ case FTAG_PRIME:
+ p = getmp(ed->p, ed->psz);
+ f = field_prime(p);
+ a = getmp(ed->a, ed->asz); b = getmp(ed->b, ed->bsz);
+ ei->c = ec_primeproj(f, a, b);
+ break;
+ case FTAG_NICEPRIME:
+ p = getmp(ed->p, ed->psz);
+ f = field_niceprime(p);
+ a = getmp(ed->a, ed->asz); b = getmp(ed->b, ed->bsz);
+ ei->c = ec_primeproj(f, a, b);
+ break;
+ case FTAG_BINPOLY:
+ p = getmp(ed->p, ed->psz);
+ f = field_binpoly(p);
+ a = getmp(ed->a, ed->asz); b = getmp(ed->b, ed->bsz);
+ ei->c = ec_binproj(f, a, b);
+ break;
+ default:
+ abort();
+ }
+
+ EC_CREATE(&ei->g);
+ ei->g.x = getmp(ed->gx, ed->gxsz);
+ ei->g.y = getmp(ed->gy, ed->gysz);
+ ei->g.z = 0;
+ ei->r = getmp(ed->r, ed->rsz);
+ ei->h = getmp(ed->h, ed->hsz);
+
+ MP_DROP(p);
+ MP_DROP(a);
+ MP_DROP(b);
+}
+
+/* --- @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.
+ */
+
+const char *ec_getinfo(ec_info *ei, const char *p)
+{
+ qd_parse qd;
+ const ecentry *ee;
+
+ qd.p = p;
+ qd.e = 0;
+ for (ee = ectab; ee->name; ee++) {
+ if (qd_enum(&qd, ee->name) >= 0) {
+ getinfo(ei, ee->data);
+ goto found;
+ }
+ }
+ if (ec_infoparse(&qd, ei))
+ return (qd.e);
+found:
+ if (!qd_eofp(&qd)) {
+ ec_freeinfo(ei);
+ return ("junk found at end of string");
+ }
+ return (0);
+}
+
+/* --- @ec_freeinfo@ --- *
+ *
+ * Arguments: @ec_info *ei@ = elliptic curve information block to free
+ *
+ * Returns: ---
+ *
+ * Use: Frees the information block.
+ */
+
+void ec_freeinfo(ec_info *ei)
+{
+ field *f;
+
+ EC_DESTROY(&ei->g);
+ MP_DROP(ei->r);
+ MP_DROP(ei->h);
+ f = ei->c->f; ec_destroycurve(ei->c); F_DESTROY(f);
+}
+
+/* --- @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.
+ */
+
+static int primep(mp *p, grand *gr)
+{
+ int i = rabin_iters(mp_bits(p));
+ rabin r;
+ mp *x = MP_NEW;
+
+ switch (pfilt_smallfactor(p)) {
+ case PGEN_DONE: return (1);
+ case PGEN_FAIL: return (0);
+ }
+ rabin_create(&r, p);
+ while (i) {
+ x = mprand_range(x, p, gr, 0);
+ if (rabin_rtest(&r, x) == PGEN_FAIL)
+ break;
+ i--;
+ }
+ MP_DROP(x);
+ rabin_destroy(&r);
+ return (!i);
+}
+
+static int primeeltp(mp *x, field *f)
+{
+ return (!MP_ISNEG(x) && MP_CMP(x, <, f->m));
+}
+
+static const char *primecheck(const ec_info *ei, grand *gr)
+{
+ ec_curve *c = ei->c;
+ field *f = c->f;
+ int i;
+ mp *x, *y;
+ ec p;
+ int rc;
+
+ /* --- Check %$p$% is an odd prime --- */
+
+ if (!primep(f->m, gr)) return ("p not prime");
+
+ /* --- Check %$a$%, %$b$%, %$G_x$% and %$G_y$% are in %$[0, p)$% --- */
+
+ if (!primeeltp(c->a, f)) return ("a out of range");
+ if (!primeeltp(c->b, f)) return ("b out of range");
+ if (!primeeltp(ei->g.x, f)) return ("G_x out of range");
+ if (!primeeltp(ei->g.x, f)) return ("G_y out of range");
+
+ /* --- Check %$4 a^3 + 27 b^2 \not\equiv 0 \pmod{p}$% --- */
+
+ x = F_SQR(f, MP_NEW, c->a);
+ x = F_MUL(f, x, x, c->a);
+ x = F_QDL(f, x, x);
+ y = F_SQR(f, MP_NEW, c->b);
+ y = F_TPL(f, y, y);
+ y = F_TPL(f, y, y);
+ y = F_TPL(f, y, y);
+ x = F_ADD(f, x, x, y);
+ rc = F_ZEROP(f, x);
+ MP_DROP(x);
+ MP_DROP(y);
+ if (rc) return ("not an elliptic curve");
+
+ /* --- Check %$G \in E$% --- */
+
+ if (EC_ATINF(&ei->g)) return ("generator at infinity");
+ if (ec_check(c, &ei->g)) return ("generator not on curve");
+
+ /* --- Check %$r$% is prime --- */
+
+ if (!primep(ei->r, gr)) return ("generator order not prime");
+
+ /* --- Check %$0 < h \le 4$% --- */
+
+ if (MP_CMP(ei->h, <, MP_ONE) || MP_CMP(ei->h, >, MP_FOUR))
+ return ("cofactor out of range");
+
+ /* --- Check %$h = \lfloor (\sqrt{p} + 1)^2/r \rlfoor$% --- *
+ *
+ * This seems to work with the approximate-sqrt in the library, but might
+ * not be so good in some cases. Throw in some extra significate figures
+ * for good measure.
+ */
+
+ x = mp_lsl(MP_NEW, f->m, 128);
+ x = mp_sqrt(x, x);
+ y = mp_lsl(MP_NEW, MP_ONE, 64);
+ x = mp_add(x, x, y);
+ x = mp_sqr(x, x);
+ mp_div(&x, 0, x, ei->r);
+ x = mp_lsr(x, x, 128);
+ rc = MP_EQ(x, ei->h);
+ MP_DROP(x);
+ MP_DROP(y);
+ if (!rc) return ("incorrect cofactor");
+
+ /* --- Check %$n G = O$% --- */
+
+ EC_CREATE(&p);
+ ec_mul(c, &p, &ei->g, ei->r);
+ rc = EC_ATINF(&p);
+ EC_DESTROY(&p);
+ if (!rc) return ("incorrect group order");
+
+ /* --- Check that %$p^B \not\equiv 1 \pmod{r}$% for %$1 \le B < 20$% --- *
+ *
+ * The spec says %$q$%, not %$p$%, but I think that's a misprint.
+ */
+
+ x = MP_NEW;
+ mp_div(0, &x, f->m, ei->r);
+ i = 20;
+ while (i) {
+ if (MP_EQ(x, MP_ONE)) break;
+ x = mp_mul(x, x, f->m);
+ mp_div(0, &x, x, ei->r);
+ i--;
+ }
+ MP_DROP(x);
+ if (i) return ("curve is weak");
+
+ /* --- Done --- */
+
+ return (0);
+}
+
+static const char *bincheck(const ec_info *ei, grand *gr)
+{
+ ec_curve *c = ei->c;
+ field *f = c->f;
+ int i;
+ mp *x, *y;
+ ec p;
+ int rc;
+
+ /* --- Check that %$p$% is irreducible --- */
+
+ if (!gf_irreduciblep(f->m)) return ("p not irreducible");
+
+ /* --- Check that %$a, b, G_x, G_y$% have degree less than %$p$% --- */
+
+ if (mp_bits(c->a) > f->nbits) return ("a out of range");
+ if (mp_bits(c->b) > f->nbits) return ("a out of range");
+ if (mp_bits(ei->g.x) > f->nbits) return ("G_x out of range");
+ if (mp_bits(ei->g.y) > f->nbits) return ("G_y out of range");
+
+ /* --- Check that %$b \ne 0$% --- */
+
+ if (F_ZEROP(f, c->b)) return ("b is zero");
+
+ /* --- Check that %$G \in E$% --- */
+
+ if (EC_ATINF(&ei->g)) return ("generator at infinity");
+ if (ec_check(c, &ei->g)) return ("generator not on curve");
+
+ /* --- Check %$r$% is prime --- */
+
+ if (!primep(ei->r, gr)) return ("generator order not prime");
+
+ /* --- Check %$0 < h \le 4$% --- */
+
+ if (MP_CMP(ei->h, <, MP_ONE) || MP_CMP(ei->h, >, MP_FOUR))
+ return ("cofactor out of range");
+
+ /* --- Check %$h = \lfloor (\sqrt{2^m} + 1)^2/r \rlfoor$% --- *
+ *
+ * This seems to work with the approximate-sqrt in the library, but might
+ * not be so good in some cases. Throw in some extra significate figures
+ * for good measure.
+ */
+
+ x = mp_lsl(MP_NEW, MP_ONE, f->nbits + 128);
+ x = mp_sqrt(x, x);
+ y = mp_lsl(MP_NEW, MP_ONE, 64);
+ x = mp_add(x, x, y);
+ x = mp_sqr(x, x);
+ mp_div(&x, 0, x, ei->r);
+ x = mp_lsr(x, x, 128);
+ rc = MP_EQ(x, ei->h);
+ MP_DROP(x);
+ MP_DROP(y);
+ if (!rc) return ("incorrect cofactor");
+
+ /* --- Check %$n G = O$% --- */
+
+ EC_CREATE(&p);
+ ec_mul(c, &p, &ei->g, ei->r);
+ rc = EC_ATINF(&p);
+ EC_DESTROY(&p);
+ if (!rc) return ("incorrect group order");
+
+ /* --- Check %$2^{m B} \not\equiv 1 \pmod{r}$% for %$1 \le B < 20$% --- */
+
+ x = mp_lsl(MP_NEW, MP_ONE, f->nbits);
+ mp_div(0, &x, x, ei->r);
+ i = 20;
+ while (i) {
+ if (MP_EQ(x, MP_ONE)) break;
+ x = mp_mul(x, x, f->m);
+ mp_div(0, &x, x, ei->r);
+ i--;
+ }
+ MP_DROP(x);
+ if (i) return ("curve is weak");
+
+ /* --- Done --- */
+
+ return (0);
+}
+
+const char *ec_checkinfo(const ec_info *ei, grand *gr)
+{
+ switch (F_TYPE(ei->c->f)) {
+ case FTY_PRIME: return (primecheck(ei, gr)); break;
+ case FTY_BINARY: return (bincheck(ei, gr)); break;
+ }
+ return ("unknown curve type");
+}
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+#include "fibrand.h"
+
+int main(void)
+{
+ const ecentry *ee;
+ const char *e;
+ int ok = 1;
+ grand *gr;
+
+ gr = fibrand_create(0);
+ fputs("checking standard curves: ", stdout);
+ for (ee = ectab; ee->name; ee++) {
+ ec_info ei;
+ getinfo(&ei, ee->data);
+ e = ec_checkinfo(&ei, gr);
+ ec_freeinfo(&ei);
+ if (e) {
+ fprintf(stderr, "\n*** curve %s fails: %s\n", ee->name, e);
+ ok = 0;
+ }
+ putchar('.');
+ fflush(stdout);
+ }
+ gr->ops->destroy(gr);
+ fputs(ok ? " ok\n" : " failed\n", stdout);
+ return (!ok);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: ec-prime.c,v 1.7 2004/03/27 00:04:46 mdw Exp $
+ * $Id: ec-prime.c,v 1.8 2004/03/27 17:54:11 mdw Exp $
*
* Elliptic curves over prime fields
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec-prime.c,v $
+ * Revision 1.8 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
* Revision 1.7 2004/03/27 00:04:46 mdw
* Implement efficient reduction for pleasant-looking primes.
*
#include "ec.h"
-/*----- Data structures ---------------------------------------------------*/
-
-typedef struct ecctx {
- ec_curve c;
- mp *a, *b;
-} ecctx;
-
/*----- Simple prime curves -----------------------------------------------*/
static const ec_ops ec_primeops, ec_primeprojops, ec_primeprojxops;
static ec *ecfind(ec_curve *c, ec *d, mp *x)
{
mp *p, *q;
- ecctx *cc = (ecctx *)c;
field *f = c->f;
q = F_SQR(f, MP_NEW, x);
p = F_MUL(f, MP_NEW, x, q);
- q = F_MUL(f, q, x, cc->a);
+ q = F_MUL(f, q, x, c->a);
p = F_ADD(f, p, p, q);
- p = F_ADD(f, p, p, cc->b);
+ p = F_ADD(f, p, p, c->b);
MP_DROP(q);
p = F_SQRT(f, p, p);
if (!p)
EC_COPY(d, a);
else {
field *f = c->f;
- ecctx *cc = (ecctx *)c;
mp *lambda;
mp *dy, *dx;
dx = F_SQR(f, MP_NEW, a->x); /* %$x^2$% */
dy = F_DBL(f, MP_NEW, a->y); /* %$2 y$% */
dx = F_TPL(f, dx, dx); /* %$3 x^2$% */
- dx = F_ADD(f, dx, dx, cc->a); /* %$3 x^2 + A$% */
+ dx = F_ADD(f, dx, dx, c->a); /* %$3 x^2 + A$% */
dy = F_INV(f, dy, dy); /* %$(2 y)^{-1}$% */
lambda = F_MUL(f, MP_NEW, dx, dy); /* %$\lambda = (3 x^2 + A)/(2 y)$% */
EC_COPY(d, a);
else {
field *f = c->f;
- ecctx *cc = (ecctx *)c;
mp *p, *q, *m, *s, *dx, *dy, *dz;
p = F_SQR(f, MP_NEW, a->z); /* %$z^2$% */
q = F_SQR(f, MP_NEW, p); /* %$z^4$% */
- p = F_MUL(f, p, q, cc->a); /* %$A z^4$% */
+ p = F_MUL(f, p, q, c->a); /* %$A z^4$% */
m = F_SQR(f, MP_NEW, a->x); /* %$x^2$% */
m = F_TPL(f, m, m); /* %$3 x^2$% */
m = F_ADD(f, m, m, p); /* %$m = 3 x^2 + A z^4$% */
EC_SETINF(d);
return (d);
} else {
- ecctx *cc = (ecctx *)c;
dx = F_SQR(f, MP_NEW, a->x); /* %$x_0^2$% */
dx = F_TPL(f, dx, dx); /* %$3 x_0^2$% */
- dx = F_ADD(f, dx, dx, cc->a); /* %$3 x_0^2 + A$% */
+ dx = F_ADD(f, dx, dx, c->a); /* %$3 x_0^2 + A$% */
dy = F_DBL(f, MP_NEW, a->y); /* %$2 y_0$% */
dy = F_INV(f, dy, dy); /* %$(2 y_0)^{-1}$% */
lambda = F_MUL(f, MP_NEW, dx, dy);
static int eccheck(ec_curve *c, const ec *p)
{
- ecctx *cc = (ecctx *)c;
field *f = c->f;
int rc;
mp *l = F_SQR(f, MP_NEW, p->y);
mp *x = F_SQR(f, MP_NEW, p->x);
mp *r = F_MUL(f, MP_NEW, x, p->x);
- x = F_MUL(f, x, cc->a, p->x);
+ x = F_MUL(f, x, c->a, p->x);
r = F_ADD(f, r, r, x);
- r = F_ADD(f, r, r, cc->b);
+ r = F_ADD(f, r, r, c->b);
rc = MP_EQ(l, r) ? 0 : -1;
mp_drop(l);
mp_drop(x);
static void ecdestroy(ec_curve *c)
{
- ecctx *cc = (ecctx *)c;
- MP_DROP(cc->a);
- MP_DROP(cc->b);
- DESTROY(cc);
+ MP_DROP(c->a);
+ MP_DROP(c->b);
+ DESTROY(c);
}
/* --- @ec_prime@, @ec_primeproj@ --- *
extern ec_curve *ec_prime(field *f, mp *a, mp *b)
{
- ecctx *cc = CREATE(ecctx);
- cc->c.ops = &ec_primeops;
- cc->c.f = f;
- cc->a = F_IN(f, MP_NEW, a);
- cc->b = F_IN(f, MP_NEW, b);
- return (&cc->c);
+ ec_curve *c = CREATE(ec_curve);
+ c->ops = &ec_primeops;
+ c->f = f;
+ c->a = F_IN(f, MP_NEW, a);
+ c->b = F_IN(f, MP_NEW, b);
+ return (c);
}
extern ec_curve *ec_primeproj(field *f, mp *a, mp *b)
{
- ecctx *cc = CREATE(ecctx);
+ ec_curve *c = CREATE(ec_curve);
mp *ax;
ax = mp_add(MP_NEW, a, MP_THREE);
ax = F_IN(f, ax, ax);
if (F_ZEROP(f, ax))
- cc->c.ops = &ec_primeprojxops;
+ c->ops = &ec_primeprojxops;
else
- cc->c.ops = &ec_primeprojops;
+ c->ops = &ec_primeprojops;
MP_DROP(ax);
- cc->c.f = f;
- cc->a = F_IN(f, MP_NEW, a);
- cc->b = F_IN(f, MP_NEW, b);
- return (&cc->c);
+ c->f = f;
+ c->a = F_IN(f, MP_NEW, a);
+ c->b = F_IN(f, MP_NEW, b);
+ return (c);
}
static const ec_ops ec_primeops = {
printf("ec-prime: ");
fflush(stdout);
a = MP(-3);
- b = MP(0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1);
- p = MP(6277101735386680763835789423207666416083908700390324961279);
- r = MP(6277101735386680763835789423176059013767194773182842284080);
+ b = MP(0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef);
+ p = MP(39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319);
+ r = MP(39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942642);
f = field_niceprime(p);
c = ec_primeproj(f, a, b);
- g.x = MP(0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012);
- g.y = MP(0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811);
+ g.x = MP(0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7);
+ g.y = MP(0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f);
for (i = 0; i < n; i++) {
ec_mul(c, &d, &g, r);
/* -*-c-*-
*
- * $Id: ec-test.c,v 1.2 2004/03/27 00:04:46 mdw Exp $
+ * $Id: ec-test.c,v 1.3 2004/03/27 17:54:11 mdw Exp $
*
* Code for testing elliptic-curve stuff
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec-test.c,v $
+ * Revision 1.3 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
* Revision 1.2 2004/03/27 00:04:46 mdw
* Implement efficient reduction for pleasant-looking primes.
*
return (c->name);
}
-/*----- Test field types --------------------------------------------------*
- *
- * Really lazy parser. Sorry.
- */
-
-static void skipws(const char **p)
-{
- while (isspace((unsigned char)**p)) (*p)++;
-}
-
-static void ckchar(const char **p, int ch)
-{ skipws(p); if (**p == ch) (*p)++; }
-
-static void ckend(const char **p)
-{
- skipws(p);
- if (**p) {
- fprintf(stderr, "syntax error: junk at end of line\n");
- abort();
- }
-}
-
-static int ckstring(const char **p, const char **s)
-{
- int i;
- size_t n;
-
- skipws(p);
- for (i = 0; s[i]; i++) {
- n = strlen(s[i]);
- if (strncmp(*p, s[i], n) == 0 && !isalnum((unsigned char)(*p)[n])) {
- *p += n;
- return (i);
- }
- }
- fprintf(stderr, "syntax error: couldn't recognize keyword\n");
- abort();
-}
-
-static mp *getmp(const char **p)
-{
- char *q;
- mp *m;
- skipws(p);
- m = mp_readstring(MP_NEW, *p, &q, 0);
- if (!m || isalnum((unsigned char)*q)) {
- fprintf(stderr, "syntax error: bad number\n");
- abort();
- }
- *p = q;
- return (m);
-}
+/*----- Test field types --------------------------------------------------*/
static void ecvcvt(const char *buf, dstr *d)
{
- field *f;
ec_curve *v;
- mp *m, *n;
- const char *p = buf;
- int i;
-
- static const char *fnames[] = {
- "prime", "niceprime", "binpoly", 0
- };
- static const char *ecnames[] = {
- "prime", "primeproj", "bin", "binproj", 0
- };
-
- switch (i = ckstring(&p, fnames), ckchar(&p, ':'), i) {
- case 0: m = getmp(&p); f = field_prime(m); mp_drop(m); break;
- case 1: m = getmp(&p); f = field_niceprime(m); mp_drop(m); break;
- case 2: m = getmp(&p); f = field_binpoly(m); mp_drop(m); break;
- default: abort();
- }
- ckchar(&p, '/');
-
- switch (i = ckstring(&p, ecnames), ckchar(&p, ':'), i) {
- case 0: m = getmp(&p); ckchar(&p, ','); n = getmp(&p);
- v = ec_prime(f, m, n); mp_drop(m); mp_drop(n); break;
- case 1: m = getmp(&p); ckchar(&p, ','); n = getmp(&p);
- v = ec_primeproj(f, m, n); mp_drop(m); mp_drop(n); break;
- case 2: m = getmp(&p); ckchar(&p, ','); n = getmp(&p);
- v = ec_bin(f, m, n); mp_drop(m); mp_drop(n); break;
- case 3: m = getmp(&p); ckchar(&p, ','); n = getmp(&p);
- v = ec_binproj(f, m, n); mp_drop(m); mp_drop(n); break;
- default: abort();
+ qd_parse qd;
+
+ qd.p = buf;
+ qd.e = 0;
+ if ((v = ec_curveparse(&qd)) == 0) {
+ fprintf(stderr, "bad curve `%.*s|%s': %s\n",
+ qd.p - buf, buf, qd.p, qd.e);
+ exit(1);
}
- ckend(&p);
-
dstr_ensure(d, sizeof(v));
*(ec_curve **)d->buf = ec_cutout(v, buf);
d->len += sizeof(v);
static void eccvt(const char *p, dstr *d)
{
ec *a;
+ qd_parse qd;
+ qd.p = p;
+ qd.e = 0;
dstr_ensure(d, sizeof(ec));
a = (ec *)d->buf;
d->len += sizeof(ec);
ec_create(a);
- skipws(&p);
- if (strcmp(p, "inf") == 0)
- EC_SETINF(a);
- else
- { a->x = getmp(&p); ckchar(&p, ','); a->y = getmp(&p); ckend(&p); }
+ if (!ec_ptparse(&qd, a)) {
+ fprintf(stderr, "bad point `%.*s|%s': %s\n", qd.p - p, p, qd.p, qd.e);
+ exit(1);
+ }
}
static void ecdodump(ec *a, FILE *fp)
/* -*-c-*-
*
- * $Id: ec.c,v 1.6 2004/03/23 15:19:32 mdw Exp $
+ * $Id: ec.c,v 1.7 2004/03/27 17:54:11 mdw Exp $
*
* Elliptic curve definitions
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec.c,v $
+ * 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.
*
ec *ec_sub(ec_curve *c, ec *d, const ec *p, const ec *q)
{
- ec pp, qq;
+ ec pp = EC_INIT, qq = EC_INIT;
EC_IN(c, &pp, p);
EC_IN(c, &qq, q);
EC_SUB(c, d, &pp, &qq);
/* -*-c-*-
*
- * $Id: ec.h,v 1.7 2004/03/23 15:19:32 mdw Exp $
+ * $Id: ec.h,v 1.8 2004/03/27 17:54:11 mdw Exp $
*
* Elliptic curve definitions
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec.h,v $
+ * 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.
*
/*----- Header files ------------------------------------------------------*/
-#include "field.h"
-#include "mp.h"
+#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 ---------------------------------------------------*/
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 --- */
#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@ --- *
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_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
--- /dev/null
+#! /usr/bin/perl
+
+while (<>) {
+ print, next if /^\s*(\#|$)/;
+ @F = split;
+ $k = shift @F;
+ print, next if $k eq "curve";
+ $n = lc(join("", @F));
+ if ($n =~ m"^/") {
+ $p = join(" + ", map("2^$_", split(m"/", substr($n, 1))));
+ $n = `calc 'printf("%x", $p)'`;
+ } elsif ($n =~ /../ && $n !~ /^0x/) {
+ $n = "0x$n";
+ }
+ print " $k $n\n";
+}
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: ectab.h,v 1.1 2004/03/27 17:54:11 mdw Exp $
+ *
+ * Table of standard elliptic curves (internal)
+ *
+ * (c) 2004 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: ectab.h,v $
+ * Revision 1.1 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
+ */
+
+#ifndef CATACOMB_ECTAB_H
+#define CATACOMB_ECTAB_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "ec.h"
+
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct ecdata {
+ unsigned ftag; /* The kind of curve this is */
+ const mpw *p; size_t psz; /* Modulus */
+ const mpw *a; size_t asz; /* Elliptic curve parameters */
+ const mpw *b; size_t bsz;
+ const mpw *r; size_t rsz; /* Order of common point %$g$% */
+ const mpw *h; size_t hsz; /* Cofactor %$h = \#E/r$% */
+ const mpw *gx; size_t gxsz; /* Common point */
+ const mpw *gy; size_t gysz;
+} ecdata;
+
+enum {
+ FTAG_PRIME, /* Prime but not nice */
+ FTAG_NICEPRIME, /* Nice prime field */
+ FTAG_BINPOLY /* Any old binary field */
+};
+
+typedef struct ecentry {
+ const char *name;
+ const ecdata *data;
+} ecentry;
+
+/*----- Global variables --------------------------------------------------*/
+
+extern const ecentry ectab[];
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+# $Id: ectab.in,v 1.1 2004/03/27 17:54:11 mdw Exp $
+#
+# Standard ellipic curves
+
+#----- Curves from SEC2 -----------------------------------------------------
+
+curve secp112r1 prime
+ p 0xdb7c2abf62e35e668076bead208b
+ a 0xdb7c2abf62e35e668076bead2088
+ b 0x659ef8ba043916eede8911702b22
+ r 0xdb7c2abf62e35e7628dfac6561c5
+ h 1
+ gx 0x09487239995a5ee76b55f9c2f098
+ gy 0xa89ce5af8724c0a23e0e0ff77500
+
+curve secp112r2 prime
+ p 0xdb7c2abf62e35e668076bead208b
+ a 0x6127c24c05f38a0aaaf65c0ef02c
+ b 0x51def1815db5ed74fcc34c85d709
+ r 0x36df0aafd8b8d7597ca10520d04b
+ h 4
+ gx 0x4ba30ab5e892b4e1649dd0928643
+ gy 0xadcd46f5882e3747def36e956e97
+
+curve secp128r1 niceprime
+ p 0xfffffffdffffffffffffffffffffffff
+ a 0xfffffffdfffffffffffffffffffffffc
+ b 0xe87579c11079f43dd824993c2cee5ed3
+ r 0xfffffffe0000000075a30d1b9038a115
+ h 1
+ gx 0x161ff7528b899b2d0c28607ca52c5b86
+ gy 0xcf5ac8395bafeb13c02da292dded7a83
+
+curve secp128r2 niceprime
+ p 0xfffffffdffffffffffffffffffffffff
+ a 0xd6031998d1b3bbfebf59cc9bbff9aee1
+ b 0x5eeefca380d02919dc2c6558bb6d8a5d
+ r 0x3fffffff7fffffffbe0024720613b5a3
+ h 4
+ gx 0x7b6aa5d85e572983e6fb32a7cdebc140
+ gy 0x27b6916a894d3aee7106fe805fc34b44
+
+curve secp160k1 niceprime
+ p 0xfffffffffffffffffffffffffffffffeffffac73
+ a 0
+ b 7
+ r 0x0100000000000000000001b8fa16dfab9aca16b6b3
+ h 1
+ gx 0x3b4c382ce37aa192a4019e763036f4f5dd4d7ebb
+ gy 0x938cf935318fdced6bc28286531733c3f03c4fee
+
+curve secp160r1 niceprime
+ p 0xffffffffffffffffffffffffffffffff7fffffff
+ a 0xffffffffffffffffffffffffffffffff7ffffffc
+ b 0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45
+ r 0x0100000000000000000001f4c8f927aed3ca752257
+ h 1
+ gx 0x4a96b5688ef573284664698968c38bb913cbfc82
+ gy 0x23a628553168947d59dcc912042351377ac5fb32
+
+curve secp160r2 niceprime
+ p 0xfffffffffffffffffffffffffffffffeffffac73
+ a 0xfffffffffffffffffffffffffffffffeffffac70
+ b 0xb4e134d3fb59eb8bab57274904664d5af50388ba
+ r 0x0100000000000000000000351ee786a818f3a1a16b
+ h 1
+ gx 0x52dcb034293a117e1f4ff11b30f7199d3144ce6d
+ gy 0xfeaffef2e331f296e071fa0df9982cfea7d43f2e
+
+curve secp192k1 niceprime
+ p 0xfffffffffffffffffffffffffffffffffffffffeffffee37
+ a 0
+ b 3
+ r 0xfffffffffffffffffffffffe26f2fc170f69466a74defd8d
+ h 1
+ gx 0xdb4ff10ec057e9ae26b07d0280b7f4341da5d1b1eae06c7d
+ gy 0x9b2f2f6d9c5628a7844163d015be86344082aa88d95e2f9d
+
+curve secp192r1 niceprime
+ p 0xfffffffffffffffffffffffffffffffeffffffffffffffff
+ a 0xfffffffffffffffffffffffffffffffefffffffffffffffc
+ b 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1
+ r 0xffffffffffffffffffffffff99def836146bc9b1b4d22831
+ h 1
+ gx 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012
+ gy 0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811
+
+curve secp224k1 niceprime
+ p 0xfffffffffffffffffffffffffffffffffffffffffffffffeffffe56d
+ a 0
+ b 5
+ r 0x010000000000000000000000000001dce8d2ec6184caf0a971769fb1f7
+ h 1
+ gx 0xa1455b334df099df30fc28a169a467e9e47075a90f7e650eb6b7a45c
+ gy 0x7e089fed7fba344282cafbd6f7e319f7c0b0bd59e2ca4bdb556d61a5
+
+curve secp224r1 niceprime
+ p 0xffffffffffffffffffffffffffffffff000000000000000000000001
+ a 0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe
+ b 0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4
+ r 0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d
+ h 1
+ gx 0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21
+ gy 0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34
+
+curve secp256k1 niceprime
+ p 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
+ a 0
+ b 7
+ r 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
+ h 1
+ gx 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
+ gy 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
+
+curve secp256r1 niceprime
+ p 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
+ a 0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc
+ b 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
+ r 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
+ h 1
+ gx 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
+ gy 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
+
+curve secp384r1 niceprime
+ p 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000ffffffff
+ a 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeffffffff0000000000000000fffffffc
+ b 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef
+ r 0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf581a0db248b0a77aecec196accc52973
+ h 1
+ gx 0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7
+ gy 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f
+
+curve secp521r1 niceprime
+ p 0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
+ a 0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc
+ b 0x0051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00
+ r 0x01fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409
+ h 1
+ gx 0x00c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66
+ gy 0x011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650
+
+curve sect113r1 binpoly
+ p 0x20000000000000000000000000201
+ a 0x003088250ca6e7c7fe649ce85820f7
+ b 0x00e8bee4d3e2260744188be0e9c723
+ r 0x0100000000000000d9ccec8a39e56f
+ h 2
+ gx 0x009d73616f35f4ab1407d73562c10f
+ gy 0x00a52830277958ee84d1315ed31886
+
+curve sect113r2 binpoly
+ p 0x20000000000000000000000000201
+ a 0x00689918dbec7e5a0dd6dfc0aa55c7
+ b 0x0095e9a9ec9b297bd4bf36e059184f
+ r 0x010000000000000108789b2496af93
+ h 2
+ gx 0x01a57a6a7b26ca5ef52fcdb8164797
+ gy 0x00b3adc94ed1fe674c06e695baba1d
+
+curve sect131r1 binpoly
+ p 0x80000000000000000000000000000010d
+ a 0x07a11b09a76b562144418ff3ff8c2570b8
+ b 0x0217c05610884b63b9c6c7291678f9d341
+ r 0x0400000000000000023123953a9464b54d
+ h 2
+ gx 0x0081baf91fdf9833c40f9c181343638399
+ gy 0x078c6e7ea38c001f73c8134b1b4ef9e150
+
+curve sect131r2 binpoly
+ p 0x80000000000000000000000000000010d
+ a 0x03e5a88919d7cafcbf415f07c2176573b2
+ b 0x04b8266a46c55657ac734ce38f018f2192
+ r 0x0400000000000000016954a233049ba98f
+ h 2
+ gx 0x0356dcd8f2f95031ad652d23951bb366a8
+ gy 0x0648f06d867940a5366d9e265de9eb240f
+
+curve sect163k1 binpoly
+ p 0x800000000000000000000000000000000000000c9
+ a 1
+ b 1
+ r 0x04000000000000000000020108a2e0cc0d99f8a5ef
+ h 2
+ gx 0x02fe13c0537bbc11acaa07d793de4e6d5e5c94eee8
+ gy 0x0289070fb05d38ff58321f2e800536d538ccdaa3d9
+
+curve sect163r1 binpoly
+ p 0x800000000000000000000000000000000000000c9
+ a 0x07b6882caaefa84f9554ff8428bd88e246d2782ae2
+ b 0x0713612dcddcb40aab946bda29ca91f73af958afd9
+ r 0x03ffffffffffffffffffff48aab689c29ca710279b
+ h 2
+ gx 0x0369979697ab43897789566789567f787a7876a654
+ gy 0x00435edb42efafb2989d51fefce3c80988f41ff883
+
+curve sect163r2 binpoly
+ p 0x800000000000000000000000000000000000000c9
+ a 1
+ b 0x020a601907b8c953ca1481eb10512f78744a3205fd
+ r 0x040000000000000000000292fe77e70c12a4234c33
+ h 2
+ gx 0x03f0eba16286a2d57ea0991168d4994637e8343e36
+ gy 0x00d51fbc6c71a0094fa2cdd545b11c5c0c797324f1
+
+curve sect193r1 binpoly
+ p 0x2000000000000000000000000000000000000000000008001
+ a 0x0017858feb7a98975169e171f77b4087de098ac8a911df7b01
+ b 0x00fdfb49bfe6c3a89facadaa7a1e5bbc7cc1c2e5d831478814
+ r 0x01000000000000000000000000c7f34a778f443acc920eba49
+ h 2
+ gx 0x01f481bc5f0ff84a74ad6cdf6fdef4bf6179625372d8c0c5e1
+ gy 0x0025e399f2903712ccf3ea9e3a1ad17fb0b3201b6af7ce1b05
+
+curve sect193r2 binpoly
+ p 0x2000000000000000000000000000000000000000000008001
+ a 0x0163f35a5137c2ce3ea6ed8667190b0bc43ecd69977702709b
+ b 0x00c9bb9e8927d4d64c377e2ab2856a5b16e3efb7f61d4316ae
+ r 0x010000000000000000000000015aab561b005413ccd4ee99d5
+ h 2
+ gx 0x00d9b67d192e0367c803f39e1a7e82ca14a651350aae617e8f
+ gy 0x01ce94335607c304ac29e7defbd9ca01f596f927224cdecf6c
+
+curve sect233k1 binpoly
+ p 0x20000000000000000000000000000000000000004000000000000000001
+ a 0
+ b 1
+ r 0x8000000000000000000000000000069d5bb915bcd46efb1ad5f173abdf
+ h 4
+ gx 0x017232ba853a7e731af129f22ff4149563a419c26bf50a4c9d6eefad6126
+ gy 0x01db537dece819b7f70f555a67c427a8cd9bf18aeb9b56e0c11056fae6a3
+
+curve sect233r1 binpoly
+ p 0x20000000000000000000000000000000000000004000000000000000001
+ a 1
+ b 0x0066647ede6c332c7f8c0923bb58213b333b20e9ce4281fe115f7d8f90ad
+ r 0x01000000000000000000000000000013e974e72f8a6922031d2603cfe0d7
+ h 2
+ gx 0x00fac9dfcbac8313bb2139f1bb755fef65bc391f8b36f8f8eb7371fd558b
+ gy 0x01006a08a41903350678e58528bebf8a0beff867a7ca36716f7e01f81052
+
+curve sect239k1 binpoly
+ p 0x800000000000000000004000000000000000000000000000000000000001
+ a 0
+ b 1
+ r 0x2000000000000000000000000000005a79fec67cb6e91f1c1da800e478a5
+ h 4
+ gx 0x29a0b6a887a983e9730988a68727a8b2d126c44cc2cc7b2a6555193035dc
+ gy 0x76310804f12e549bdb011c103089e73510acb275fc312a5dc6b76553f0ca
+
+curve sect283k1 binpoly
+ p 0x800000000000000000000000000000000000000000000000000000000000000000010a1
+ a 0
+ b 1
+ r 0x01ffffffffffffffffffffffffffffffffffe9ae2ed07577265dff7f94451e061e163c61
+ h 4
+ gx 0x0503213f78ca44883f1a3b8162f188e553cd265f23c1567a16876913b0c2ac2458492836
+ gy 0x01ccda380f1c9e318d90f95d07e5426fe87e45c0e8184698e45962364e34116177dd2259
+
+curve sect283r1 binpoly
+ p 0x800000000000000000000000000000000000000000000000000000000000000000010a1
+ a 1
+ b 0x027b680ac8b8596da5a4af8a19a0303fca97fd7645309fa2a581485af6263e313b79a2f5
+ r 0x03ffffffffffffffffffffffffffffffffffef90399660fc938a90165b042a7cefadb307
+ h 2
+ gx 0x05f939258db7dd90e1934f8c70b0dfec2eed25b8557eac9c80e2e198f8cdbecd86b12053
+ gy 0x03676854fe24141cb98fe6d4b20d02b4516ff702350eddb0826779c813f0df45be8112f4
+
+curve sect409k1 binpoly
+ p 0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001
+ a 0
+ b 1
+ r 0x7ffffffffffffffffffffffffffffffffffffffffffffffffffe5f83b2d4ea20400ec4557d5ed3e3e7ca5b4b5c83b8e01e5fcf
+ h 4
+ gx 0x0060f05f658f49c1ad3ab1890f7184210efd0987e307c84c27accfb8f9f67cc2c460189eb5aaaa62ee222eb1b35540cfe9023746
+ gy 0x01e369050b7c4e42acba1dacbf04299c3460782f918ea427e6325165e9ea10e3da5f6c42e9c55215aa9ca27a5863ec48d8e0286b
+
+curve sect409r1 binpoly
+ p 0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001
+ a 1
+ b 0x0021a5c2c8ee9feb5c4b9a753b7b476b7fd6422ef1f3dd674761fa99d6ac27c8a9a197b272822f6cd57a55aa4f50ae317b13545f
+ r 0x010000000000000000000000000000000000000000000000000001e2aad6a612f33307be5fa47c3c9e052f838164cd37d9a21173
+ h 2
+ gx 0x015d4860d088ddb3496b0c6064756260441cde4af1771d4db01ffe5b34e59703dc255a868a1180515603aeab60794e54bb7996a7
+ gy 0x0061b1cfab6be5f32bbfa78324ed106a7636b9c5a7bd198d0158aa4f5488d08f38514f1fdf4b4f40d2181b3681c364ba0273c706
+
+curve sect571k1 binpoly
+ p 0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000425
+ a 0
+ b 1
+ r 0x020000000000000000000000000000000000000000000000000000000000000000000000131850e1f19a63e4b391a8db917f4138b630d84be5d639381e91deb45cfe778f637c1001
+ h 4
+ gx 0x026eb7a859923fbc82189631f8103fe4ac9ca2970012d5d46024804801841ca44370958493b205e647da304db4ceb08cbbd1ba39494776fb988b47174dca88c7e2945283a01c8972
+ gy 0x0349dc807f4fbf374f4aeade3bca95314dd58cec9f307a54ffc61efc006d8a2c9d4979c0ac44aea74fbebbb9f772aedcb620b01a7ba7af1b320430c8591984f601cd4c143ef1c7a3
+
+curve sect571r1 binpoly
+ p 0x80000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000425
+ a 1
+ b 0x02f40e7e2221f295de297117b7f3d62f5c6a97ffcb8ceff1cd6ba8ce4a9a18ad84ffabbd8efa59332be7ad6756a66e294afd185a78ff12aa520e4de739baca0c7ffeff7f2955727a
+ r 0x03ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe661ce18ff55987308059b186823851ec7dd9ca1161de93d5174d66e8382e9bb2fe84e47
+ h 2
+ gx 0x0303001d34b856296c16c0d40d3cd7750a93d1d2955fa80aa5f40fc8db7b2abdbde53950f4c0d293cdd711a35b67fb1499ae60038614f1394abfa3b4c850d927e1e7769c8eec2d19
+ gy 0x037bf27342da639b6dccfffeb73d69d78c6c27a6009cbbca1980f8533921e8a684423e43bab08a576291af8f461bb2a8b3531d2f0485c19b16e2f1516e23dd3c1a4827af1b8ac15b
+
+#----- Curves from RFC2414 (Oakley) -----------------------------------------
+#
+# oakley155 has too large a cofactor
+# oakley185's group has composite order; we double the generator to
+# produce a group of composite order
+
+curve oakley185 binpoly
+ p 0x020000000000000000000000000000200000000000000001
+ a 0
+ b 0x1ee9
+ r 0x007ffffffffffffffffffffff6fcbe226dcf92105d7e53af
+ h 4
+ gx 0x1bd555555555555555555555555554e8000000000000158
+ gy 0x14e999999999999999999999999998d7000000000001fe6
+
+#----- NIST curves from FIPS186-2 -------------------------------------------
+#
+# Most of these are duplicates of SEC2 curves.
+
+alias nist-p192 secp192r1
+alias nist-p224 secp224r1
+alias nist-p256 secp256r1
+alias nist-p384 secp384r1
+alias nist-p521 secp521r1
+
+alias nist-k163 sect163k1
+alias nist-k233 sect233k1
+alias nist-k283 sect283k1
+alias nist-k409 sect409k1
+alias nist-k571 sect571k1
+
+alias nist-b163 sect163r2
+alias nist-b233 sect233r1
+alias nist-b283 sect283r1
+alias nist-b409 sect409r1
+alias nist-b571 sect571r1
+
+#----- That's all, folks ----------------------------------------------------
/* -*-c-*-
*
- * $Id: f-binpoly.c,v 1.4 2004/03/23 15:19:32 mdw Exp $
+ * $Id: f-binpoly.c,v 1.5 2004/03/27 17:54:11 mdw Exp $
*
* Binary fields with polynomial basis representation
*
/*----- Revision history --------------------------------------------------*
*
* $Log: f-binpoly.c,v $
+ * Revision 1.5 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
* Revision 1.4 2004/03/23 15:19:32 mdw
* Test elliptic curves more thoroughly.
*
DESTROY(f);
}
-static mp *frand(field *ff, mp *d, grand *r)
+static mp *frand(field *f, mp *d, grand *r)
{
- fctx *f = (fctx *)ff;
- return (mprand(d, mp_octets(f->r.p) - 1, r, 0));
+ return (mprand(d, f->nbits, r, 0));
}
static int fzerop(field *ff, mp *x)
f->f.ops = &fops;
f->f.zero = MP_ZERO;
f->f.one = MP_ONE;
+ f->f.nbits = mp_bits(p) - 1;
+ f->f.noctets = (f->f.nbits + 7) >> 3;
gfreduce_create(&f->r, p);
+ f->f.m = f->r.p;
return (&f->f);
}
/* -*-c-*-
*
- * $Id: f-niceprime.c,v 1.1 2004/03/27 00:04:46 mdw Exp $
+ * $Id: f-niceprime.c,v 1.2 2004/03/27 17:54:11 mdw Exp $
*
* Prime fields with efficient reduction for special-form primes
*
/*----- Revision history --------------------------------------------------*
*
* $Log: f-niceprime.c,v $
+ * Revision 1.2 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
* Revision 1.1 2004/03/27 00:04:46 mdw
* Implement efficient reduction for pleasant-looking primes.
*
f->f.ops = &fops;
f->f.zero = MP_ZERO;
f->f.one = MP_ONE;
+ f->f.nbits = mp_bits(p);
+ f->f.noctets = (f->f.nbits + 7) >> 3;
mpreduce_create(&f->r, p);
+ f->f.m = f->r.p;
return (&f->f);
}
/* -*-c-*-
*
- * $Id: f-prime.c,v 1.6 2004/03/23 15:19:32 mdw Exp $
+ * $Id: f-prime.c,v 1.7 2004/03/27 17:54:11 mdw Exp $
*
* Prime fields with Montgomery arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: f-prime.c,v $
+ * 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.
*
mpmont_create(&f->mm, p);
f->f.zero = MP_ZERO;
f->f.one = f->mm.r;
+ f->f.m = f->mm.m;
+ f->f.nbits = mp_bits(p);
+ f->f.noctets = (f->f.nbits + 7) >> 3;
return (&f->f);
}
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: field-parse.c,v 1.1 2004/03/27 17:54:11 mdw Exp $
+ *
+ * Parse field descriptions
+ *
+ * (c) 2004 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-parse.c,v $
+ * Revision 1.1 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "field.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @field_parse@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = parser context
+ *
+ * Returns: Field pointer if OK, or null.
+ *
+ * Use: Parses a field description, which has the form
+ *
+ * * `prime', `niceprime' or `binpoly'
+ * * an optional `:'
+ * * the field modulus
+ */
+
+field *field_parse(qd_parse *qd)
+{
+ field *f;
+ mp *m = MP_NEW;
+
+ switch (qd_enum(qd, "prime,niceprime,binpoly")) {
+ case 0:
+ qd_delim(qd, ':');
+ if ((m = qd_getmp(qd)) == 0) return (0);
+ f = field_prime(m);
+ break;
+ case 1:
+ qd_delim(qd, ':');
+ if ((m = qd_getmp(qd)) == 0) return (0);
+ f = field_niceprime(m);
+ break;
+ case 2:
+ qd_delim(qd, ':');
+ if ((m = qd_getmp(qd)) == 0) return (0);
+ f = field_binpoly(m);
+ break;
+ default:
+ f = 0;
+ break;
+ }
+ mp_drop(m);
+ return (f);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: field.h,v 1.7 2004/03/27 00:04:46 mdw Exp $
+ * $Id: field.h,v 1.8 2004/03/27 17:54:11 mdw Exp $
*
* Definitions for field arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: field.h,v $
+ * Revision 1.8 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
* Revision 1.7 2004/03/27 00:04:46 mdw
* Implement efficient reduction for pleasant-looking primes.
*
# include "mp.h"
#endif
+#ifndef CATACOMB_QDPARSE_H
+# include "qdparse.h"
+#endif
+
/*----- Data structures ---------------------------------------------------*/
typedef struct field {
const struct field_ops *ops; /* Field operations */
mp *zero, *one; /* Identities in the field */
+ mp *m; /* Modulus (prime and binary) */
+ unsigned long nbits; /* Length of field element in bits */
+ size_t noctets; /* Length of element in octets */
} field;
enum {
extern field *field_binpoly(mp */*p*/);
+/* --- @field_parse@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = parser context
+ *
+ * Returns: Field pointer if OK, or null.
+ *
+ * Use: Parses a field description, which has the form
+ *
+ * * `prime', `niceprime' or `binpoly'
+ * * an optional `:'
+ * * the field modulus
+ */
+
+extern field *field_parse(qd_parse */*qd*/);
+
/*----- That's all, folks -------------------------------------------------*/
#ifdef __cplusplus
/* -*-c-*-
*
- * $Id: gf-arith.c,v 1.2 2004/03/21 22:52:06 mdw Exp $
+ * $Id: gf-arith.c,v 1.3 2004/03/27 17:54:11 mdw Exp $
*
* Basic arithmetic on binary polynomials
*
/*----- Revision history --------------------------------------------------*
*
* $Log: gf-arith.c,v $
+ * Revision 1.3 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
* Revision 1.2 2004/03/21 22:52:06 mdw
* Merge and close elliptic curve branch.
*
size_t m = MAX(MP_LEN(a), MP_LEN(b));
mpw *s;
MP_DEST(d, 2 * m, a->f | b->f | MP_UNDEF);
- s = mpalloc(d->a, 2 * m);
- gfx_kmul(d->v, d->vl, a->v, a->vl, b->v, b->vl, s, s + 2 * m);
+ s = mpalloc(d->a, 3 * m);
+ gfx_kmul(d->v, d->vl, a->v, a->vl, b->v, b->vl, s, s + 3 * m);
mpfree(d->a, s);
}
}
}
+/* --- @gf_irreduciblep@ --- *
+ *
+ * Arguments: @mp *f@ = a polynomial
+ *
+ * Returns: Nonzero if the polynomial is irreducible; otherwise zero.
+ */
+
+int gf_irreduciblep(mp *f)
+{
+ unsigned long m = mp_bits(f) - 1;
+ mp *u = MP_TWO;
+ mp *v = MP_NEW;
+
+ m /= 2;
+ while (m) {
+ u = gf_sqr(u, u);
+ gf_div(0, &u, u, f);
+ v = gf_add(v, u, MP_TWO);
+ gf_gcd(&v, 0, 0, v, f);
+ if (!MP_EQ(v, MP_ONE)) break;
+ m--;
+ }
+ MP_DROP(u);
+ MP_DROP(v);
+ return (!m);
+}
+
/*----- Test rig ----------------------------------------------------------*/
#ifdef TEST_RIG
return (ok);
}
+static int tirred(dstr *v)
+{
+ mp *a = *(mp **)v[0].buf;
+ int r = *(int *)v[1].buf;
+ int c = gf_irreduciblep(a);
+ int ok = 1;
+ if (r != c) {
+ ok = 0;
+ fprintf(stderr, "\n*** irred failed");
+ fputs("\n*** a = ", stderr); mp_writefile(a, stderr, 16);
+ fprintf(stderr, "\n*** r = %d\n", r);
+ fprintf(stderr, "*** c = %d\n", c);
+ }
+ mp_drop(a);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
static test_chunk tests[] = {
{ "add", tadd, { &type_mp, &type_mp, &type_mp, 0 } },
{ "mul", tmul, { &type_mp, &type_mp, &type_mp, 0 } },
{ "sqr", tsqr, { &type_mp, &type_mp, 0 } },
{ "div", tdiv, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
+ { "irred", tirred, { &type_mp, &type_int, 0 } },
{ 0, 0, { 0 } },
};
/* -*-c-*-
*
- * $Id: gf.h,v 1.2 2004/03/21 22:52:06 mdw Exp $
+ * $Id: gf.h,v 1.3 2004/03/27 17:54:11 mdw Exp $
*
* Arithmetic on binary polynomials
*
/*----- Revision history --------------------------------------------------*
*
* $Log: gf.h,v $
+ * Revision 1.3 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
* Revision 1.2 2004/03/21 22:52:06 mdw
* Merge and close elliptic curve branch.
*
extern void gf_div(mp **/*qq*/, mp **/*rr*/, mp */*a*/, mp */*b*/);
+/* --- @gf_irreduciblep@ --- *
+ *
+ * Arguments: @mp *f@ = a polynomial
+ *
+ * Returns: Nonzero if the polynomial is irreducible; otherwise zero.
+ */
+
+extern int gf_irreduciblep(mp */*f*/);
+
/* --- @gf_gcd@ --- *
*
* Arguments: @mp **gcd, **xx, **yy@ = where to write the results
/* -*-c-*-
*
- * $Id: gfx-kmul.c,v 1.2 2002/10/09 00:36:03 mdw Exp $
+ * $Id: gfx-kmul.c,v 1.3 2004/03/27 17:54:11 mdw Exp $
*
* Karatsuba's multiplication algorithm on binary polynomials
*
/*----- Revision history --------------------------------------------------*
*
* $Log: gfx-kmul.c,v $
+ * Revision 1.3 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
* Revision 1.2 2002/10/09 00:36:03 mdw
* Fix bounds on workspace for Karatsuba operations.
*
mpw *bsv = sv + m, *ssv = bsv + m;
mpw *rdv = dv + m, *rdvl = rdv + 2 * m;
- assert(rdvl < dvl);
- assert(ssv < svl);
+ assert(rdvl <= dvl);
+ assert(ssv <= svl);
UXOR2(sv, bsv, av, avm, avm, avl);
UXOR2(bsv, ssv, bv, bvm, bvm, bvl);
if (m > GFK_THRESH)
/* -*-c-*-
*
- * $Id: mp-sqrt.c,v 1.3 2001/02/03 12:00:29 mdw Exp $
+ * $Id: mp-sqrt.c,v 1.4 2004/03/27 17:54:11 mdw Exp $
*
* Compute integer square roots
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mp-sqrt.c,v $
+ * Revision 1.4 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
* Revision 1.3 2001/02/03 12:00:29 mdw
* Now @mp_drop@ checks its argument is non-NULL before attempting to free
* it. Note that the macro version @MP_DROP@ doesn't do this.
z >>= 1;
mp_copy(a);
d = mp_lsr(d, a, z);
- mp_drop(a);
/* --- Main approximation --- *
*
/* --- Finished, at last --- */
+ mp_drop(a);
mp_drop(q);
mp_drop(r);
return (d);
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: mpdump.c,v 1.1 2004/03/27 17:54:11 mdw Exp $
+ *
+ * Dump a multiprecision integer as C data
+ *
+ * (c) 2004 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: mpdump.c,v $
+ * Revision 1.1 2004/03/27 17:54:11 mdw
+ * Standard curves and curve checking.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <errno.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "mp.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+int main(int argc, char *argv[])
+{
+ mp *x;
+ int i;
+ int w, n;
+
+ if (argc != 2) {
+ fprintf(stderr, "%s: missing argument\n", argv[0]);
+ return (1);
+ }
+ if ((x = mp_readstring(0, argv[1], 0, 0)) == 0) {
+ fprintf(stderr, "%s: bad integer `%s'", argv[0], argv[1]);
+ return (1);
+ }
+ fputs(" ", stdout);
+ w = (MPW_BITS + 3)/4;
+ n = 1;
+ while (2 + 2 * n * (4 + w) < 72) n <<= 1;
+ i = 0;
+ for (;;) {
+ printf("0x%0*x", w, x->v[i]);
+ i++;
+ if (i >= MP_LEN(x)) break;
+ fputs(",", stdout);
+ if (i % n) fputs(" ", stdout); else fputs("\n ", stdout);
+ }
+ if (fflush(stdout) || ferror(stdout)) {
+ fprintf(stderr, "%s: error writing data: %s", argv[0], strerror(errno));
+ return (1);
+ }
+ fputs("\n", stdout);
+ return (0);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: mpx-kmul.c,v 1.8 2002/10/09 00:36:03 mdw Exp $
+ * $Id: mpx-kmul.c,v 1.9 2004/03/27 17:54:12 mdw Exp $
*
* Karatsuba's multiplication algorithm
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpx-kmul.c,v $
+ * Revision 1.9 2004/03/27 17:54:12 mdw
+ * Standard curves and curve checking.
+ *
* Revision 1.8 2002/10/09 00:36:03 mdw
* Fix bounds on workspace for Karatsuba operations.
*
mpw *bsv = sv + m + 1, *ssv = bsv + m + 1;
mpw *rdv = dv + m, *rdvl = rdv + 2 * (m + 2);
- assert(rdvl < dvl);
- assert(ssv < svl);
+ assert(rdvl <= dvl);
+ assert(ssv <= svl);
UADD2(sv, bsv, av, avm, avm, avl);
UADD2(bsv, ssv, bv, bvm, bvm, bvl);
if (m > MPK_THRESH)
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: qdparse.c,v 1.1 2004/03/27 17:54:12 mdw Exp $
+ *
+ * Quick-and-dirty parser
+ *
+ * (c) 2004 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: qdparse.c,v $
+ * Revision 1.1 2004/03/27 17:54:12 mdw
+ * Standard curves and curve checking.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <ctype.h>
+#include <string.h>
+
+#include "qdparse.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @qd_skipspc@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = context
+ *
+ * Returns: ---
+ *
+ * Use: Skips spaces in the string. No errors.
+ */
+
+void qd_skipspc(qd_parse *qd)
+{
+ while (isspace((unsigned char)*qd->p))
+ qd->p++;
+}
+
+/* --- @qd_delim@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = context
+ * @int ch@ = character to compare with
+ *
+ * Returns: Nonzero if it was, zero if it wasn't.
+ *
+ * Use: Checks the next (non-whitespace) character is what we
+ * expect. If it is, the character is eaten; otherwise it's no
+ * big deal.
+ */
+
+int qd_delim(qd_parse *qd, int ch)
+{
+ qd_skipspc(qd);
+ if (*qd->p != ch)
+ return (0);
+ qd->p++;
+ return (1);
+}
+
+/* --- @qd_enum@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = context
+ * @const char *e@ = list of enum strings, space separated
+ *
+ * Returns: Index of the string matched, or @-1@.
+ *
+ * Use: Matches a keyword.
+ */
+
+int qd_enum(qd_parse *qd, const char *e)
+{
+ size_t n;
+ int i = 0;
+
+ qd_skipspc(qd);
+ for (;;) {
+ e += strspn(e, ", ");
+ if (!*e) break;
+ n = strcspn(e, ", ");
+ if (strncmp(qd->p, e, n) == 0 && !isalnum((unsigned char)qd->p[n])) {
+ qd->p += n;
+ return (i);
+ }
+ i++; e += n;
+ }
+ qd->e = "unrecognized keyword";
+ return (-1);
+}
+
+/* --- @qd_getmp@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = context
+ *
+ * Returns: The integer extracted, or null.
+ *
+ * Use: Parses a multiprecision integer from a string.
+ */
+
+mp *qd_getmp(qd_parse *qd)
+{
+ char *q;
+ mp *m;
+
+ qd_skipspc(qd);
+ m = mp_readstring(MP_NEW, qd->p, &q, 0);
+ if (m && !isalnum((unsigned char)*q))
+ qd->p = q;
+ else {
+ mp_drop(m);
+ qd->e = "bad number";
+ }
+ return (m);
+}
+
+/* --- @qd_eofp@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = context
+ *
+ * Returns: Nonzero if at EOF, zero otherwise.
+ */
+
+int qd_eofp(qd_parse *qd)
+{
+ qd_skipspc(qd);
+ return (!*qd->p);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: qdparse.h,v 1.1 2004/03/27 17:54:12 mdw Exp $
+ *
+ * Quick-and-dirty parser
+ *
+ * (c) 2004 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: qdparse.h,v $
+ * Revision 1.1 2004/03/27 17:54:12 mdw
+ * Standard curves and curve checking.
+ *
+ */
+
+#ifndef CATACOMB_QDPARSE_H
+#define CATACOMB_QDPARSE_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#ifndef CATACOMB_MP_H
+# include "mp.h"
+#endif
+
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct qd_parse {
+ const char *p; /* Where we are right now */
+ const char *e; /* Error string (output) */
+} qd_parse;
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @qd_skipspc@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = context
+ *
+ * Returns: ---
+ *
+ * Use: Skips spaces in the string. No errors.
+ */
+
+extern void qd_skipspc(qd_parse */*qd*/);
+
+/* --- @qd_delim@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = context
+ * @int ch@ = character to compare with
+ *
+ * Returns: Nonzero if it was, zero if it wasn't.
+ *
+ * Use: Checks the next (non-whitespace) character is what we
+ * expect. If it is, the character is eaten; otherwise it's no
+ * big deal.
+ */
+
+extern int qd_delim(qd_parse */*qd*/, int /*ch*/);
+
+/* --- @qd_enum@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = context
+ * @const char *e@ = list of enum strings, space separated
+ *
+ * Returns: Index of the string matched, or @-1@.
+ *
+ * Use: Matches a keyword.
+ */
+
+extern int qd_enum(qd_parse */*qd*/, const char */*e*/);
+
+/* --- @qd_getmp@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = context
+ *
+ * Returns: The integer extracted, or null.
+ *
+ * Use: Parses a multiprecision integer from a string.
+ */
+
+extern mp *qd_getmp(qd_parse */*qd*/);
+
+/* --- @qd_eofp@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = context
+ *
+ * Returns: Nonzero if at EOF, zero otherwise.
+ */
+
+extern int qd_eofp(qd_parse */*qd*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
-# $Id: ec,v 1.2 2004/03/27 00:04:46 mdw Exp $
+# $Id: ec,v 1.3 2004/03/27 17:54:12 mdw Exp $
#
# Elliptic curve tests
0x325f41d0ef702dc310254c42d65851a3b91471ac7"
"0x1aeb33fed9c49e0200a0c561ea66d5ab85bd4c2d4,
0x49ed3be7f510e30e2462c517ad39038e493fc573c";
+
+ "binpoly: 0x020000000000000000000000000000200000000000000001
+ bin: 0, 0x1ee9"
+ "0x18, 0xd"
+ "0x1bd555555555555555555555555554e8000000000000158,
+ 0x14e999999999999999999999999998d7000000000001fe6";
}
add {
-# $Id: gf,v 1.2 2004/03/21 22:52:06 mdw Exp $
+# $Id: gf,v 1.3 2004/03/27 17:54:12 mdw Exp $
#
# Test cases for higher-level binary poly arithmetic.
0x398c4111da6d06cdf3d83704ee403101;
}
+irred {
+ 0xc1a7bd3b4e853fc92d4e1588719986aa 0;
+ 0x800000000000000000000000000000000000000c9 1;
+ 0x2000000000000000000000000000000000000000000000000000000000000000000000000000000008000000000000000000001 1;
+}
+
gcd {
0xc1a7bd3b4e853fc92d4e1588719986aa
0xbe1f8593ee2c6f8f9497cc7335d97111
0x35a8e33503b3695be00528f8b82db931
0x283ed59f1226dcefa7ff0ef87ceff5d5;
0x800000000000000000000000000000000000000c9
+ 4
+ 1
+ 1
+ 0x20000000000000000000000000000000000000032;
+ 0x800000000000000000000000000000000000000c9
0x3f0eba16286a2d57ea0991168d4994637e8343e36
1
0xa17e704470d80cb5a78f295db0ce543dda16a169
-# $Id: gfreduce,v 1.3 2004/03/23 15:19:32 mdw Exp $
+# $Id: gfreduce,v 1.4 2004/03/27 17:54:12 mdw Exp $
#
# Test efficient polynomial reduction
sqrt {
0x20000000000000000000000000000000000000000000000000000000000001001
0x1f081e69f45d3254530766ab98d55fa612c7bb27ea31bc2621d894be9c0b196b3
- 0x7fb838a8a0a95046b9d9d9fb4440f7bbc1a7bd3b4e853fc92d4e1588719986aa;
+ 0x7fb838a8a0a95046b9d9d9fb4440f7bbc1a7bd3b4e853fc92d4e1588719986aa;
0x10000000000000000000000000000000000000000003
- 0x4594094509835690805698083560980459903450984
- 0x820291881a244a02840a2f8ece3f23f88f38bf0b3a;
+ 0x4594094509835690805698083560980459903450984
+ 0x820291881a244a02840a2f8ece3f23f88f38bf0b3a;
}
halftrace {