functions for better static linking. Fix a buttload of bugs on the way.
Generally ensure that negative exponents do inversion correctly. Add
table of standard prime-field subgroups. (Binary field subgroups are
currently unimplemented but easy to add if anyone ever finds a good one.)
## -*-m4-*-
##
-## $Id: Makefile.m4,v 1.74 2004/03/28 01:58:47 mdw Exp $
+## $Id: Makefile.m4,v 1.75 2004/04/01 12:50:09 mdw Exp $
##
## Makefile for Catacomb
##
##----- Revision history ----------------------------------------------------
##
## $Log: Makefile.m4,v $
+## Revision 1.75 2004/04/01 12:50:09 mdw
+## Add cyclic group abstraction, with test code. Separate off exponentation
+## functions for better static linking. Fix a buttload of bugs on the way.
+## Generally ensure that negative exponents do inversion correctly. Add
+## table of standard prime-field subgroups. (Binary field subgroups are
+## currently unimplemented but easy to add if anyone ever finds a good one.)
+##
## Revision 1.74 2004/03/28 01:58:47 mdw
## Generate, store and retreive elliptic curve keys.
##
primetab.h: primetab.c
primetab.c: genprimes
- ./genprimes -h primetab.h -c primetab.c -n 256 \
+ ./genprimes -h primetab.h -c primetab.c \
+ -s CATACOMB_PRIMETAB_H -n 256 \
-t "unsigned short" -i primetab
archinclude_HEADERS = mptypes.h
mptypes.h: mptypes
$(srcdir)/ec-gentab.sh <$(srcdir)/ectab.in >ectab.c.new
mv ectab.c.new ectab.c
+ptab.c: ptab.in p-gentab.sh mpdump
+ $(srcdir)/p-gentab.sh <$(srcdir)/ptab.in >ptab.c.new
+ mv ptab.c.new ptab.c
+
BUILT_SOURCES = \
getdate.c modes-stamp \
addsuffix(join(`ciphers', `-', `cipher_modes'), `.c') \
gfshare.h share.h \
rho.h \
field.h ec.h ec-exp.h ec-test.h ectab.h ec-keys.h \
+ ptab.h group.h \
allwithsuffix(`ciphers', `cipher_modes', `.h') \
allwithsuffix(`hashes', `hash_modes', `.h') \
addsuffix(`cipher_modes', `-def.h') \
mpint.c mptext.c mptext-file.c mptext-string.c mptext-dstr.c \
mptext-len.c \
exp.c mpcrt.c mpmul.c mprand.c \
- mpbarrett.c mpbarrett-mexp.c mpbarrett-exp.h \
- mpmont.c mpmont-mexp.c mpmont-exp.h \
+ mpbarrett.c mpbarrett-exp.c mpbarrett-mexp.c mpbarrett-exp.h \
+ mpmont.c mpmont-exp.c mpmont-mexp.c mpmont-exp.h \
mpreduce.c mpreduce-exp.h \
- rho.c buf.c \
+ group-stdops.c group-exp.c group-exp.h g-prime.c group-parse.c \
+ group-string.c group-file.c group-dstr.c \
+ rho.c buf.c ptab.c \
GF_SOURCES PGEN_SOURCES EC_SOURCES')
define(`GF_SOURCES',
`gfx.c gfx-kmul.c gfx-sqr.c gf-arith.c gf-gcd.c \
- gfreduce.c gfreduce-exp.h ')
+ gfreduce.c gfreduce-exp.h')
define(`EC_SOURCES',
`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 \
- ec-fetch.c')
+ ec.c ec-exp.c ec-prime.c ec-bin.c ec-test.c ec-info.c ectab.c \
+ ec-fetch.c g-ec.c')
define(`PGEN_SOURCES',
`pfilt.c rabin.c \
keycheck.c keycheck-mp.c keycheck-report.c \
bbs-rand.c bbs-gen.c bbs-jump.c bbs-fetch.c \
rsa-priv.c rsa-pub.c rsa-gen.c rsa-recover.c rsa-fetch.c \
- dh-gen.c dh-limlee.c dh-check.c dh-fetch.c \
+ dh-gen.c dh-limlee.c dh-check.c dh-fetch.c dh-param.c \
dsarand.c dsa-sign.c dsa-verify.c dsa-gen.c dsa-check.c \
key-data.c key-flags.c key-text.c key-binary.c key-pass.c \
key-pack.c key-misc.c key-file.c key-attr.c key-io.c key-moan.c \
tiger.lo: tiger-tab.h
gfshare.lo: gfshare-tab.h
gfx-sqr.lo: gfx-sqr-tab.h
-patsubst(MP_SOURCES, `\.c\>', `.lo') dsig.o keyutil.o rspit.o: mptypes.h
-patsubst(PGEN_SOURCES, `\.c\>', `.lo') dsig.o keyutil.o rspit.o: primetab.h
+patsubst(MP_SOURCES, `\.c\>', `.lo') dsig.o keyutil.o rspit.o: \
+ mptypes.h primetab.h
## --- Utility programs ---
## --- Other handy definitions ---
EXTRA_DIST = \
- Makefile.m4 genmodes $(man_MANS) ectab.in xpixie ec-gentab.sh \
+ Makefile.m4 genmodes $(man_MANS) xpixie group-test.c \
+ ectab.in ec-gentab.sh ptab.in p-gentab.sh \
README.cipher README.hash README.random README.mp \
debian/rules debian/copyright debian/control debian/changelog \
debian/catacomb-bin.postinst debian/catacomb-bin.config \
$1.t)dnl
$1.to: $1.c
$(COMPILE) -c -DTEST_RIG -DSRCDIR=\"$(srcdir)\" $(srcdir)/$1.c -o $1.to
-$1.t: $1.to $1.o libcatacomb.la
+$1.t: $1.to libcatacomb.la
$(CC) $(CFLAGS) $(LDFLAGS) $1.to .libs/libcatacomb.a $(LIBS) -o $1.t')
CTESTRIG(rc4)
CTESTRIG(mptext)
CTESTRIG(mpint)
CTESTRIG(mpbarrett)
+CTESTRIG(mpbarrett-exp)
CTESTRIG(mpbarrett-mexp)
CTESTRIG(mpmont)
+CTESTRIG(mpmont-exp)
CTESTRIG(mpmont-mexp)
CTESTRIG(mpreduce)
CTESTRIG(mpcrt)
CTESTRIG(ec-bin)
CTESTRIG(ec-test)
CTESTRIG(ec-info)
+CTESTRIG(dh-param)
+CTESTRIG(group-test)
CTESTRIG(pgen)
CTESTRIG(dsa-gen)
CTESTRIG(dsa-sign)
/* -*-c-*-
*
- * $Id: buf.c,v 1.2 2003/11/10 22:18:30 mdw Exp $
+ * $Id: buf.c,v 1.3 2004/04/01 12:50:09 mdw Exp $
*
* Buffer handling
*
/*----- Revision history --------------------------------------------------*
*
* $Log: buf.c,v $
+ * Revision 1.3 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.2 2003/11/10 22:18:30 mdw
* Build fixes.
*
#include <string.h>
#include "mp.h"
+#include "ec.h"
#include "buf.h"
/*----- Main code ---------------------------------------------------------*/
mp *buf_getmp(buf *b)
{
uint16 sz;
+ size_t n;
mp *m;
if (buf_getu16(b, &sz) || buf_ensure(b, sz))
return (0);
m = mp_loadb(MP_NEW, BCUR(b), sz);
- if (mp_octets(m) != sz) {
+ n = mp_octets(m);
+ if (n != sz && n != 0 && sz != 1) {
mp_drop(m);
return (0);
}
{
size_t sz = mp_octets(m);
assert(sz < MASK16);
+ if (!sz) sz = 1;
if (buf_putu16(b, sz) || buf_ensure(b, sz))
return (-1);
mp_storeb(m, BCUR(b), sz);
return (0);
}
+/* --- @buf_getec@ --- *
+ *
+ * Arguments: @buf *b@ = pointer to a buffer block
+ * @ec *p@ = where to put the point
+ *
+ * Returns: Zero if it worked, nonzero if it failed.
+ *
+ * Use: Gets a multiprecision integer from a buffer. The point must
+ * be initialized.
+ */
+
+int buf_getec(buf *b, ec *p)
+{
+ mp *x = 0, *y = 0;
+ uint16 n;
+ if (buf_ensure(b, 2)) return (-1);
+ n = LOAD16(BCUR(b)); if (!n) { BSTEP(b, 2); EC_SETINF(p); return (0); }
+ if ((x = buf_getmp(b)) == 0 || (y = buf_getmp(b)) == 0) {
+ mp_drop(x); mp_drop(y); return (-1);
+ }
+ EC_DESTROY(p); p->x = x; p->y = y; p->z = 0;
+ return (0);
+}
+
+/* --- @buf_putec@ --- *
+ *
+ * Arguments: @buf *b@ = pointer to a buffer block
+ * @ec *p@ = an elliptic curve point
+ *
+ * Returns: Zero if it worked, nonzero if there wasn't enough space.
+ *
+ * Use: Puts an elliptic curve point to a buffer.
+ */
+
+int buf_putec(buf *b, ec *p)
+{
+ if (EC_ATINF(p)) return (buf_putu16(b, 0));
+ if (buf_putmp(b, p->x) || buf_putmp(b, p->y)) return (-1);
+ return (0);
+}
+
/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: buf.h,v 1.2 2003/11/10 22:18:30 mdw Exp $
+ * $Id: buf.h,v 1.3 2004/04/01 12:50:09 mdw Exp $
*
* Reading and writing packet buffers
*
/*----- Revision history --------------------------------------------------*
*
* $Log: buf.h,v $
+ * Revision 1.3 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.2 2003/11/10 22:18:30 mdw
* Build fixes.
*
# include "mp.h"
#endif
+#ifndef CATACOMB_EC_H
+# include "ec.h"
+#endif
+
/*----- Data structures ---------------------------------------------------*/
/* --- Buffers --- *
extern int buf_putmp(buf */*b*/, mp */*m*/);
+/* --- @buf_getec@ --- *
+ *
+ * Arguments: @buf *b@ = pointer to a buffer block
+ * @ec *p@ = where to put the point
+ *
+ * Returns: Zero if it worked, nonzero if it failed.
+ *
+ * Use: Gets a multiprecision integer from a buffer. The point must
+ * be initialized.
+ */
+
+extern int buf_getec(buf */*b*/, ec */*p*/);
+
+/* --- @buf_putec@ --- *
+ *
+ * Arguments: @buf *b@ = pointer to a buffer block
+ * @ec *p@ = an elliptic curve point
+ *
+ * Returns: Zero if it worked, nonzero if there wasn't enough space.
+ *
+ * Use: Puts an elliptic curve point to a buffer.
+ */
+
+extern int buf_putec(buf */*b*/, ec */*p*/);
+
/*----- That's all, folks -------------------------------------------------*/
#ifdef __cplusplus
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: dh-param.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Reading Diffie-Hellman parameters
+ *
+ * (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: dh-param.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "dh.h"
+#include "ptab.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @dh_parse@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = parser context
+ * @dh_param *dp@ = parameters to fill in
+ *
+ * Returns: Zero if OK, nonzero on error.
+ *
+ * Use: Parses a prime group string. This is either one of the
+ * standard group strings, or a %$p$%, %$q$%, %$g$% triple
+ * separated by commas.
+ */
+
+static void getinfo(dh_param *dp, pdata *pd)
+ { dp->p = &pd->p; dp->q = &pd->q; dp->g = &pd->g; }
+
+int dh_parse(qd_parse *qd, dh_param *dp)
+{
+ mp *p = MP_NEW, *q = MP_NEW, *g = MP_NEW;
+ const pentry *pe;
+
+ for (pe = ptab; pe->name; pe++) {
+ if (qd_enum(qd, pe->name) >= 0) {
+ getinfo(dp, pe->data);
+ goto found;
+ }
+ }
+ if ((p = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, ','); if ((q = qd_getmp(qd)) == 0) goto fail;
+ qd_delim(qd, ','); if ((g = qd_getmp(qd)) == 0) goto fail;
+ dp->p = p; dp->q = q; dp->g = g;
+found:
+ return (0);
+
+fail:
+ mp_drop(p); mp_drop(q); mp_drop(g);
+ return (-1);
+}
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+#include "fibrand.h"
+
+int main(void)
+{
+ const pentry *pe;
+ const char *e;
+ int ok = 1;
+ grand *gr;
+
+ gr = fibrand_create(0);
+ fputs("checking standard prime fields: ", stdout);
+ for (pe = ptab; pe->name; pe++) {
+ dh_param dp;
+ group *g;
+ getinfo(&dp, pe->data);
+ g = group_prime(&dp);
+ e = G_CHECK(g, gr);
+ G_DESTROYGROUP(g);
+ dh_paramfree(&dp);
+ if (e) {
+ fprintf(stderr, "\n*** group %s fails: %s\n", pe->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: dh.h,v 1.7 2001/02/03 16:08:24 mdw Exp $
+ * $Id: dh.h,v 1.8 2004/04/01 12:50:09 mdw Exp $
*
* Diffie-Hellman and related public-key systems
*
/*----- Revision history --------------------------------------------------*
*
* $Log: dh.h,v $
+ * Revision 1.8 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.7 2001/02/03 16:08:24 mdw
* Add consistency checking for public keys.
*
/*----- Header files ------------------------------------------------------*/
+#ifndef CATACOMB_GROUP_H
+# include "group.h"
+#endif
+
#ifndef CATACOMB_GRAND_H
# include "grand.h"
#endif
# include "pgen.h"
#endif
+#ifndef CATACOMB_QDPARSE_H
+# include "qdparse.h"
+#endif
+
/*----- Data structures ---------------------------------------------------*/
-typedef struct dh_param {
- mp *p, *q; /* Prime numbers %$p$% and %$q$% */
- mp *g; /* Generates order-%$q$% subgroup */
-} dh_param;
+typedef gprime_param dh_param; /* Group parameters */
typedef struct dh_pub {
dh_param dp; /* Shared parameters */
extern int dh_checkparam(keycheck */*kc*/, const dh_param */*dp*/,
mp **/*v*/, size_t /*n*/);
+/* --- @dh_parse@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = parser context
+ * @dh_param *dp@ = parameters to fill in
+ *
+ * Returns: Zero if OK, nonzero on error.
+ *
+ * Use: Parses a prime group string. This is either one of the
+ * standard group strings, or a %$p$%, %$q$%, %$g$% triple
+ * separated by commas.
+ */
+
+extern int dh_parse(qd_parse */*qd*/, dh_param */*dp*/);
+
/*----- That's all, folks -------------------------------------------------*/
#ifdef __cplusplus
/* -*-c-*-
*
- * $Id: ec-bin.c,v 1.5 2004/03/27 17:54:11 mdw Exp $
+ * $Id: ec-bin.c,v 1.6 2004/04/01 12:50:09 mdw Exp $
*
* Arithmetic for elliptic curves over binary fields
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec-bin.c,v $
+ * Revision 1.6 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.5 2004/03/27 17:54:11 mdw
* Standard curves and curve checking.
*
int rc;
mp *u, *v;
+ if (EC_ATINF(p)) return (0);
v = F_SQR(f, MP_NEW, p->x);
u = F_MUL(f, MP_NEW, v, p->x);
v = F_MUL(f, v, v, c->a);
}
static const ec_ops ec_binops = {
- ecdestroy, ec_idin, ec_idout, ec_idfix,
+ ecdestroy, ec_stdsamep, ec_idin, ec_idout, ec_idfix,
ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
};
static const ec_ops ec_binprojops = {
- ecdestroy, ec_projin, ec_projout, ec_projfix,
+ ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
ecfind, ecprojneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
};
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: ec-exp.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Point multiplication for elliptic curves
+ *
+ * (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-exp.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "ec.h"
+#include "ec-exp.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @ec_imul@, @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: The destination @d@.
+ *
+ * Use: Multiplies a point by a scalar, returning %$n p$%. The
+ * @imul@ variant uses internal representations for argument
+ * and result.
+ */
+
+ec *ec_imul(ec_curve *c, ec *d, const ec *p, mp *n)
+{
+ ec t = EC_INIT;
+
+ EC_COPY(&t, p);
+ if (t.x && (n->f & MP_BURN))
+ t.x->f |= MP_BURN;
+ MP_SHRINK(n);
+ EC_SETINF(d);
+ if (MP_LEN(n) == 0)
+ ;
+ else {
+ if (n->f & MP_NEG)
+ EC_NEG(c, &t, &t);
+ if (MP_LEN(n) < EXP_THRESH)
+ EXP_SIMPLE(*d, t, n);
+ else
+ EXP_WINDOW(*d, t, n);
+ }
+ EC_DESTROY(&t);
+ return (d);
+}
+
+ec *ec_mul(ec_curve *c, ec *d, const ec *p, mp *n)
+{
+ EC_IN(c, d, p);
+ ec_imul(c, d, d, n);
+ return (EC_OUT(c, d, d));
+}
+
+/* --- @ec_mmul@, @ec_immul@ --- *
+ *
+ * Arguments: @ec_curve *c@ = pointer to an elliptic curve
+ * @ec *d@ = pointer to the destination point
+ * @const ec_mulfactor *f@ = pointer to vector of factors
+ * @size_t n@ = number of factors
+ *
+ * Returns: The destination @d@.
+ *
+ * Use: Does simultaneous point multiplication. The @immul@ variant
+ * uses internal representations for arguments and result.
+ */
+
+#undef EXP_WINSZ
+#define EXP_WINSZ 3
+
+static ec *immul(ec_curve *c, ec *d, ec_mulfactor *f, size_t n)
+{
+ size_t i;
+
+ for (i = 0; i < n; i++) {
+ MP_SHRINK(f[i].exp);
+ if (f[i].exp->f & MP_NEG)
+ EC_NEG(c, &f[i].base, &f[i].base);
+ if (f[i].base.x && f[i].exp->f & MP_BURN)
+ f[i].base.x->f |= MP_BURN;
+ }
+ EC_SETINF(d);
+ EXP_SIMUL(*d, f, n);
+ for (i = 0; i < n; i++)
+ EC_DESTROY(&f[i].base);
+ xfree(f);
+ return (d);
+}
+
+ec *ec_immul(ec_curve *c, ec *d, const ec_mulfactor *f, size_t n)
+{
+ ec_mulfactor *ff = xmalloc(n * sizeof(ec_mulfactor));
+ size_t i;
+
+ for (i = 0; i < n; i++) {
+ EC_CREATE(&ff[i].base);
+ EC_COPY(&ff[i].base, &f[i].base);
+ ff[i].exp = f[i].exp;
+ }
+ return (immul(c, d, ff, n));
+}
+
+ec *ec_mmul(ec_curve *c, ec *d, const ec_mulfactor *f, size_t n)
+{
+ ec_mulfactor *ff = xmalloc(n * sizeof(ec_mulfactor));
+ size_t i;
+
+ for (i = 0; i < n; i++) {
+ EC_CREATE(&ff[i].base);
+ EC_IN(c, &ff[i].base, &f[i].base);
+ ff[i].exp = f[i].exp;
+ }
+ immul(c, d, ff, n);
+ return (EC_OUT(c, d, d));
+}
+
+/*----- That's all, folks -------------------------------------------------*/
#include "ectab.h"
#define N(x) (sizeof(x)/sizeof(*x))
+#define MP(x) { x, x + N(x), N(x), 0, MP_CONST, 0 }
/*----- Curve data --------------------------------------------------------*/
if [ $t != b ]; then echo >&2 "$0: wanted b; found $t"; exit 1; fi
cat <<EOF
-static const mpw c_${n}_p[] = {
+static mpw c_${n}_p[] = {
EOF
./mpdump $p
cat <<EOF
};
-static const mpw c_${n}_a[] = {
+static mpw c_${n}_a[] = {
EOF
./mpdump $a
cat <<EOF
};
-static const mpw c_${n}_b[] = {
+static mpw c_${n}_b[] = {
EOF
./mpdump $b
cat <<EOF
if [ $t != gy ]; then echo >&2 "$0: wanted gy; found $t"; exit 1; fi
cat <<EOF
-static const mpw c_${n}_r[] = {
+static mpw c_${n}_r[] = {
EOF
./mpdump $r
cat <<EOF
};
-static const mpw c_${n}_h[] = {
+static mpw c_${n}_h[] = {
EOF
./mpdump $h
cat <<EOF
};
-static const mpw c_${n}_gx[] = {
+static mpw c_${n}_gx[] = {
EOF
./mpdump $gx
cat <<EOF
};
-static const mpw c_${n}_gy[] = {
+static mpw c_${n}_gy[] = {
EOF
./mpdump $gy
cat <<EOF
binpoly) ftag=FTAG_BINPOLY;;
esac
cat <<EOF
-static const ecdata c_$n = {
+static 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)
+ MP(c_${n}_p),
+ MP(c_${n}_a),
+ MP(c_${n}_b),
+ MP(c_${n}_r),
+ MP(c_${n}_h),
+ MP(c_${n}_gx),
+ MP(c_${n}_gy)
};
EOF
/* -*-c-*-
*
- * $Id: ec-info.c,v 1.1 2004/03/27 17:54:11 mdw Exp $
+ * $Id: ec-info.c,v 1.2 2004/04/01 12:50:09 mdw Exp $
*
* Elliptic curve information management
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec-info.c,v $
+ * Revision 1.2 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.1 2004/03/27 17:54:11 mdw
* Standard curves and curve checking.
*
return (0);
}
+/* --- @getinfo@ --- *
+ *
+ * Arguments: @ec_info *ei@ = where to write the information
+ * @ecdata *ed@ = raw data
+ *
+ * Returns: ---
+ *
+ * Use: Loads elliptic curve information about one of the standard
+ * curves.
+ */
+
+static void getinfo(ec_info *ei, ecdata *ed)
+{
+ field *f;
+
+ switch (ed->ftag) {
+ case FTAG_PRIME:
+ f = field_prime(&ed->p);
+ ei->c = ec_primeproj(f, &ed->a, &ed->b);
+ break;
+ case FTAG_NICEPRIME:
+ f = field_niceprime(&ed->p);
+ ei->c = ec_primeproj(f, &ed->a, &ed->b);
+ break;
+ case FTAG_BINPOLY:
+ f = field_binpoly(&ed->p);
+ ei->c = ec_binproj(f, &ed->a, &ed->b);
+ break;
+ default:
+ abort();
+ }
+
+ EC_CREATE(&ei->g); ei->g.x = &ed->gx; ei->g.y = &ed->gy; ei->g.z = 0;
+ ei->r = &ed->r; ei->h = &ed->h;
+}
+
/* --- @ec_infoparse@ --- *
*
* Arguments: @qd_parse *qd@ = parser context
* Returns: Zero on success, nonzero on failure.
*
* Use: Parses an elliptic curve information string, and stores the
- * information in @ei@. This has the form
+ * information in @ei@. This is either the name of a standard
+ * curve, or it has the form
*
* * elliptic curve description
* * optional `/'
ec_curve *c = 0;
field *f;
ec g = EC_INIT;
+ const ecentry *ee;
mp *r = MP_NEW, *h = MP_NEW;
+ for (ee = ectab; ee->name; ee++) {
+ if (qd_enum(qd, ee->name) >= 0) {
+ getinfo(ei, ee->data);
+ goto found;
+ }
+ }
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;
+
+found:
return (0);
fail:
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 *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_sameinfop@ --- *
+ *
+ * Arguments: @ec_info *ei, *ej@ = two elliptic curve parameter sets
+ *
+ * Returns: Nonzero if the curves are identical (not just isomorphic).
+ *
+ * Use: Checks for sameness of curve parameters.
+ */
+
+int ec_sameinfop(ec_info *ei, ec_info *ej)
+{
+ return (ec_samep(ei->c, ej->c) &&
+ MP_EQ(ei->r, ej->r) && MP_EQ(ei->h, ej->h) &&
+ EC_EQ(&ei->g, &ej->g));
+}
+
/* --- @ec_freeinfo@ --- *
*
* Arguments: @ec_info *ei@ = elliptic curve information block to free
* 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));
/* --- Check %$p$% is an odd prime --- */
- if (!primep(f->m, gr)) return ("p not prime");
+ if (!pgen_primep(f->m, gr)) return ("p not prime");
/* --- Check %$a$%, %$b$%, %$G_x$% and %$G_y$% are in %$[0, p)$% --- */
/* --- Check %$r$% is prime --- */
- if (!primep(ei->r, gr)) return ("generator order not prime");
+ if (!pgen_primep(ei->r, gr)) return ("generator order not prime");
/* --- Check %$0 < h \le 4$% --- */
/* --- Check %$r$% is prime --- */
- if (!primep(ei->r, gr)) return ("generator order not prime");
+ if (!pgen_primep(ei->r, gr)) return ("generator order not prime");
/* --- Check %$0 < h \le 4$% --- */
/* -*-c-*-
*
- * $Id: ec-keys.h,v 1.1 2004/03/28 01:58:47 mdw Exp $
+ * $Id: ec-keys.h,v 1.2 2004/04/01 12:50:09 mdw Exp $
*
* Elliptic curve key-fetching
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec-keys.h,v $
+ * Revision 1.2 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.1 2004/03/28 01:58:47 mdw
* Generate, store and retreive elliptic curve keys.
*
mp *x; /* Secret exponent */
} ec_priv;
-extern const key_fetchdef ec_paramfetch[], ec_pubfetch[], ec_privfetch[];
+extern const key_fetchdef ec_paramfetch[];
+#define EC_PARAMFETCHSZ 3
+
+extern const key_fetchdef ec_pubfetch[];
+#define EC_PUBFETCHSZ 4
+
+extern const key_fetchdef ec_privfetch[];
+#define EC_PRIVFETCHSZ 7
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @ec_paramfree@, @ec_pubfree@, @ec_privfree@ --- *
+ *
+ * Arguments: @ec_param *ep@, @ec_pub *ep@, @ec_priv *ep@ = pointer to
+ * key block to free
+ *
+ * Returns: ---
+ *
+ * Use: Frees an elliptic curve key block
+ */
+
+extern void ec_paramfree(ec_param */*ep*/);
+extern void ec_pubfree(ec_pub */*ep*/);
+extern void ec_privfree(ec_priv */*ep*/);
/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: ec-prime.c,v 1.8 2004/03/27 17:54:11 mdw Exp $
+ * $Id: ec-prime.c,v 1.9 2004/04/01 12:50:09 mdw Exp $
*
* Elliptic curves over prime fields
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec-prime.c,v $
+ * Revision 1.9 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.8 2004/03/27 17:54:11 mdw
* Standard curves and curve checking.
*
static int eccheck(ec_curve *c, const ec *p)
{
field *f = c->f;
+ mp *l, *x, *r;
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);
+ if (EC_ATINF(p)) return (0);
+ l = F_SQR(f, MP_NEW, p->y);
+ x = F_SQR(f, MP_NEW, p->x);
+ r = F_MUL(f, MP_NEW, x, p->x);
x = F_MUL(f, x, c->a, p->x);
r = F_ADD(f, r, r, x);
r = F_ADD(f, r, r, c->b);
}
static const ec_ops ec_primeops = {
- ecdestroy, ec_idin, ec_idout, ec_idfix,
+ ecdestroy, ec_stdsamep, ec_idin, ec_idout, ec_idfix,
ecfind, ecneg, ecadd, ec_stdsub, ecdbl, eccheck
};
static const ec_ops ec_primeprojops = {
- ecdestroy, ec_projin, ec_projout, ec_projfix,
+ ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
ecfind, ecneg, ecprojadd, ec_stdsub, ecprojdbl, ecprojcheck
};
static const ec_ops ec_primeprojxops = {
- ecdestroy, ec_projin, ec_projout, ec_projfix,
+ ecdestroy, ec_stdsamep, ec_projin, ec_projout, ec_projfix,
ecfind, ecneg, ecprojadd, ec_stdsub, ecprojxdbl, ecprojcheck
};
/* -*-c-*-
*
- * $Id: ec-test.c,v 1.3 2004/03/27 17:54:11 mdw Exp $
+ * $Id: ec-test.c,v 1.4 2004/04/01 12:50:09 mdw Exp $
*
* Code for testing elliptic-curve stuff
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec-test.c,v $
+ * Revision 1.4 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.3 2004/03/27 17:54:11 mdw
* Standard curves and curve checking.
*
return (EC_CHECK(c->real, p));
}
+static int ecSAMEP(ec_curve *cc, ec_curve *dd)
+{
+ ecctx *c = (ecctx *)cc, *d = (ecctx *)dd;
+ return (ec_samep(c->real, d->real));
+}
+
static ec_ops ecops = {
- ecDESTROY, ecIN, ecOUT, ecFIX,
+ ecDESTROY, ecSAMEP, ecIN, ecOUT, ecFIX,
ecFIND, ecNEG, ecADD, ecSUB, ecDBL, ecCHECK
};
ecctx *c = CREATE(ecctx);
c->c.f = real->f;
c->c.ops = &ecops;
+ c->c.a = real->a;
+ c->c.b = real->b;
c->magic = MAGIC;
c->name = xstrdup(name);
c->real = real;
/* -*-c-*-
*
- * $Id: ec.c,v 1.7 2004/03/27 17:54:11 mdw Exp $
+ * $Id: ec.c,v 1.8 2004/04/01 12:50:09 mdw Exp $
*
* Elliptic curve definitions
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec.c,v $
+ * Revision 1.8 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.7 2004/03/27 17:54:11 mdw
* Standard curves and curve checking.
*
/*----- Header files ------------------------------------------------------*/
#include "ec.h"
-#include "ec-exp.h"
/*----- Trivial wrappers --------------------------------------------------*/
+/* --- @ec_samep@ --- *
+ *
+ * Arguments: @ec_curve *c, *d@ = two elliptic curves
+ *
+ * Returns: Nonzero if the curves are identical (not just isomorphic).
+ *
+ * Use: Checks for sameness of curves. This function does the full
+ * check, not just the curve-type-specific check done by the
+ * @sampep@ field operation.
+ */
+
+int ec_samep(ec_curve *c, ec_curve *d)
+{
+ return (field_samep(c->f, d->f) && c->ops == d->ops && EC_SAMEP(c, d));
+}
+
/* --- @ec_create@ --- *
*
* Arguments: @ec *p@ = pointer to an elliptic-curve point
/*----- Standard curve operations -----------------------------------------*/
+/* --- @ec_stdsamep@ --- *
+ *
+ * Arguments: @ec_curve *c, *d@ = two elliptic curves
+ *
+ * Returns: Nonzero if the curves are identical (not just isomorphic).
+ *
+ * Use: Simple sameness check on @a@ and @b@ curve members.
+ */
+
+int ec_stdsamep(ec_curve *c, ec_curve *d)
+{
+ return (MP_EQ(c->a, d->a) && MP_EQ(c->b, d->b));
+}
+
/* --- @ec_idin@, @ec_idout@, @ec_idfix@ --- *
*
* Arguments: @ec_curve *c@ = pointer to an elliptic curve
return (EC_OUT(c, d, d));
}
-/* --- @ec_imul@, @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: The destination @d@.
- *
- * Use: Multiplies a point by a scalar, returning %$n p$%. The
- * @imul@ variant uses internal representations for argument
- * and result.
- */
-
-ec *ec_imul(ec_curve *c, ec *d, const ec *p, mp *n)
-{
- ec t = EC_INIT;
-
- EC_COPY(&t, p);
- if (t.x && (n->f & MP_BURN))
- t.x->f |= MP_BURN;
- MP_SHRINK(n);
- EC_SETINF(d);
- if (MP_LEN(n) == 0)
- ;
- else {
- if (n->f & MP_NEG)
- EC_NEG(c, &t, &t);
- if (MP_LEN(n) < EXP_THRESH)
- EXP_SIMPLE(*d, t, n);
- else
- EXP_WINDOW(*d, t, n);
- }
- EC_DESTROY(&t);
- return (d);
-}
-
-ec *ec_mul(ec_curve *c, ec *d, const ec *p, mp *n)
-{
- EC_IN(c, d, p);
- ec_imul(c, d, d, n);
- return (EC_OUT(c, d, d));
-}
-
/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: ec.h,v 1.8 2004/03/27 17:54:11 mdw Exp $
+ * $Id: ec.h,v 1.9 2004/04/01 12:50:09 mdw Exp $
*
* Elliptic curve definitions
*
/*----- Revision history --------------------------------------------------*
*
* $Log: ec.h,v $
+ * Revision 1.9 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.8 2004/03/27 17:54:11 mdw
* Standard curves and curve checking.
*
typedef struct ec_ops {
void (*destroy)(ec_curve */*c*/);
+ int (*samep)(ec_curve */*c*/, ec_curve */*d*/);
ec *(*in)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
ec *(*out)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
ec *(*fix)(ec_curve */*c*/, ec */*d*/, const ec */*p*/);
int (*check)(ec_curve */*c*/, const ec */*p*/);
} ec_ops;
+#define EC_SAMEP(c, d) (c)->ops->samep((c), (d))
#define EC_IN(c, d, p) (c)->ops->in((c), (d), (p))
#define EC_OUT(c, d, p) (c)->ops->out((c), (d), (p))
#define EC_FIX(c, d, p) (c)->ops->fix((c), (d), (p))
/*----- Interesting arithmetic --------------------------------------------*/
+/* --- @ec_samep@ --- *
+ *
+ * Arguments: @ec_curve *c, *d@ = two elliptic curves
+ *
+ * Returns: Nonzero if the curves are identical (not just isomorphic).
+ *
+ * Use: Checks for sameness of curves. This function does the full
+ * check, not just the curve-type-specific check done by the
+ * @sampep@ field operation.
+ */
+
+extern int ec_samep(ec_curve */*c*/, ec_curve */*d*/);
+
/* --- @ec_find@ --- *
*
* Arguments: @ec_curve *c@ = pointer to an elliptic curve
/*----- Standard curve operations -----------------------------------------*/
+/* --- @ec_stdsamep@ --- *
+ *
+ * Arguments: @ec_curve *c, *d@ = two elliptic curves
+ *
+ * Returns: Nonzero if the curves are identical (not just isomorphic).
+ *
+ * Use: Simple sameness check on @a@ and @b@ curve members.
+ */
+
+extern int ec_stdsamep(ec_curve */*c*/, ec_curve */*d*/);
+
/* --- @ec_idin@, @ec_idout@, @ec_idfix@ --- *
*
* Arguments: @ec_curve *c@ = pointer to an elliptic curve
extern const char *ec_getinfo(ec_info */*ei*/, const char */*p*/);
+/* --- @ec_sameinfop@ --- *
+ *
+ * Arguments: @ec_info *ei, *ej@ = two elliptic curve parameter sets
+ *
+ * Returns: Nonzero if the curves are identical (not just isomorphic).
+ *
+ * Use: Checks for sameness of curve parameters.
+ */
+
+extern int ec_sameinfop(ec_info */*ei*/, ec_info */*ej*/);
+
/* --- @ec_freeinfo@ --- *
*
* Arguments: @ec_info *ei@ = elliptic curve information block to free
/* -*-c-*-
*
- * $Id: ectab.h,v 1.1 2004/03/27 17:54:11 mdw Exp $
+ * $Id: ectab.h,v 1.2 2004/04/01 12:50:09 mdw Exp $
*
- * Table of standard elliptic curves (internal)
+ * Table of standard elliptic curves
*
* (c) 2004 Straylight/Edgeware
*/
/*----- Revision history --------------------------------------------------*
*
* $Log: ectab.h,v $
+ * Revision 1.2 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.1 2004/03/27 17:54:11 mdw
* Standard curves and curve checking.
*
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;
+ mp p; /* Modulus */
+ mp a, b; /* Elliptic curve parameters */
+ mp r; /* Order of common point %$g$% */
+ mp h; /* Cofactor %$h = \#E/r$% */
+ mp gx, gy; /* Common point */
} ecdata;
enum {
typedef struct ecentry {
const char *name;
- const ecdata *data;
+ ecdata *data;
} ecentry;
/*----- Global variables --------------------------------------------------*/
/* -*-c-*-
*
- * $Id: f-binpoly.c,v 1.5 2004/03/27 17:54:11 mdw Exp $
+ * $Id: f-binpoly.c,v 1.6 2004/04/01 12:50:09 mdw Exp $
*
* Binary fields with polynomial basis representation
*
/*----- Revision history --------------------------------------------------*
*
* $Log: f-binpoly.c,v $
+ * Revision 1.6 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.5 2004/03/27 17:54:11 mdw
* Standard curves and curve checking.
*
static field_ops fops = {
FTY_BINARY, "binpoly",
- fdestroy, frand,
+ fdestroy, frand, field_stdsamep,
freduce, field_id,
fzerop, field_id, fadd, fadd, fmul, fsqr, finv, freduce, fsqrt,
fquadsolve,
/* -*-c-*-
*
- * $Id: f-niceprime.c,v 1.2 2004/03/27 17:54:11 mdw Exp $
+ * $Id: f-niceprime.c,v 1.3 2004/04/01 12:50:09 mdw Exp $
*
* Prime fields with efficient reduction for special-form primes
*
/*----- Revision history --------------------------------------------------*
*
* $Log: f-niceprime.c,v $
+ * Revision 1.3 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.2 2004/03/27 17:54:11 mdw
* Standard curves and curve checking.
*
static field_ops fops = {
FTY_PRIME, "niceprime",
- fdestroy, frand,
+ fdestroy, frand, field_stdsamep,
freduce, field_id,
fzerop, fneg, fadd, fsub, fmul, fsqr, finv, freduce, fsqrt,
0,
/* -*-c-*-
*
- * $Id: f-prime.c,v 1.7 2004/03/27 17:54:11 mdw Exp $
+ * $Id: f-prime.c,v 1.8 2004/04/01 12:50:09 mdw Exp $
*
* Prime fields with Montgomery arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: f-prime.c,v $
+ * Revision 1.8 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.7 2004/03/27 17:54:11 mdw
* Standard curves and curve checking.
*
static field_ops fops = {
FTY_PRIME, "prime",
- fdestroy, frand,
+ fdestroy, frand, field_stdsamep,
fin, fout,
fzerop, fneg, fadd, fsub, fmul, fsqr, finv, freduce, fsqrt,
0,
/* -*-c-*-
*
- * $Id: field.c,v 1.2 2004/03/21 22:52:06 mdw Exp $
+ * $Id: field.c,v 1.3 2004/04/01 12:50:09 mdw Exp $
*
* Abstract field operations
*
/*----- Revision history --------------------------------------------------*
*
* $Log: field.c,v $
+ * Revision 1.3 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.2 2004/03/21 22:52:06 mdw
* Merge and close elliptic curve branch.
*
return (x);
}
+/* --- @field_samep@ --- *
+ *
+ * Arguments: @field *f, *g@ = two fields
+ *
+ * Returns: Nonzero if the fields are identical (not just isomorphic).
+ *
+ * Use: Checks for sameness of fields. This function does the full
+ * check, not just the field-type-specific check done by the
+ * @sampep@ field operation.
+ */
+
+int field_samep(field *f, field *g)
+{
+ return (f->ops == g->ops && F_SAMEP(f, g));
+}
+
+/* --- @field_stdsamep@ --- *
+ *
+ * Arguments: @field *f, *g@ = two fields
+ *
+ * Returns: Nonzero if the fields are identical (not just isomorphic).
+ *
+ * Use: Standard sameness check, based on equality of the @m@
+ * member.
+ */
+
+int field_stdsamep(field *f, field *g)
+{
+ return (MP_EQ(f->m, g->m));
+}
+
/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: field.h,v 1.8 2004/03/27 17:54:11 mdw Exp $
+ * $Id: field.h,v 1.9 2004/04/01 12:50:09 mdw Exp $
*
* Definitions for field arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: field.h,v $
+ * Revision 1.9 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.8 2004/03/27 17:54:11 mdw
* Standard curves and curve checking.
*
void (*destroy)(field */*f*/);
mp *(*rand)(field */*f*/, mp */*d*/, grand */*r*/);
+ int (*samep)(field */*f*/, field */*g*/);
mp *(*in)(field */*f*/, mp */*d*/, mp */*x*/);
mp *(*out)(field */*f*/, mp */*d*/, mp */*x*/);
#define F_DESTROY(f) (f)->ops->destroy((f))
#define F_RAND(f, d, r) (f)->ops->rand((f), (d), (r))
+#define F_SAMEP(f, g) (f)->ops->samep((f), (g))
#define F_IN(f, d, x) (f)->ops->in((f), (d), (x))
#define F_OUT(f, d, x) (f)->ops->out((f), (d), (x))
extern mp *field_id(field */*f*/, mp */*d*/, mp */*x*/);
+/* --- @field_samep@ --- *
+ *
+ * Arguments: @field *f, *g@ = two fields
+ *
+ * Returns: Nonzero if the fields are identical (not just isomorphic).
+ *
+ * Use: Checks for sameness of fields. This function does the full
+ * check, not just the field-type-specific check done by the
+ * @sampep@ field operation.
+ */
+
+extern int field_samep(field */*f*/, field */*g*/);
+
+/* --- @field_stdsamep@ --- *
+ *
+ * Arguments: @field *f, *g@ = two fields
+ *
+ * Returns: Nonzero if the fields are identical (not just isomorphic).
+ *
+ * Use: Standard sameness check, based on equality of the @m@
+ * member.
+ */
+
+extern int field_stdsamep(field */*f*/, field */*g*/);
+
/*----- Creating fields ---------------------------------------------------*/
/* --- @field_prime@ --- *
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: g-ec.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Abstraction for elliptic curve groups
+ *
+ * (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: g-ec.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <ctype.h>
+
+#include <mLib/sub.h>
+
+#define ge ec
+#include "group.h"
+
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct gctx {
+ group g;
+ ec id, gen;
+ ec_info ei;
+} gctx;
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- Group operations --- */
+
+static void gdestroygroup(group *gg) {
+ gctx *g = (gctx *)gg;
+ EC_DESTROY(&g->gen);
+ ec_freeinfo(&g->ei);
+ DESTROY(g);
+}
+
+static ec *gcreate(group *gg)
+ { ec *x = CREATE(ec); EC_CREATE(x); return (x); }
+
+static void gcopy(group *gg, ec *d, ec *x) { EC_COPY(d, x); }
+
+static void gburn(group *gg, ec *x) { if (x->x) (x->x)->f |= MP_BURN; }
+
+static void gdestroy(group *gg, ec *x) { EC_DESTROY(x); DESTROY(x); }
+
+static int gsamep(group *gg, group *hh) {
+ gctx *g = (gctx *)gg, *h = (gctx *)hh;
+ return (ec_sameinfop(&g->ei, &h->ei));
+}
+
+static int geq(group *gg, ec *x, ec *y) {
+ gctx *g = (gctx *)gg; EC_FIX(g->ei.c, x, x); EC_FIX(g->ei.c, y, y);
+ return (EC_EQ(x, y));
+}
+
+static int gidentp(group *gg, ec *x) { return (EC_ATINF(x)); }
+
+static const char *gcheck(group *gg, grand *gr)
+ { gctx *g = (gctx *)gg; return (ec_checkinfo(&g->ei, gr)); }
+
+static void gmul(group *gg, ec *d, ec *x, ec *y)
+ { gctx *g = (gctx *)gg; EC_ADD(g->ei.c, d, x, y); }
+
+static void gsqr(group *gg, ec *d, ec *x)
+ { gctx *g = (gctx *)gg; EC_DBL(g->ei.c, d, x); }
+
+static void ginv(group *gg, ec *d, ec *x)
+ { gctx *g = (gctx *)gg; EC_NEG(g->ei.c, d, x); }
+
+static void gdiv(group *gg, ec *d, ec *x, ec *y)
+ { gctx *g = (gctx *)gg; EC_SUB(g->ei.c, d, x, y); }
+
+static void gexp(group *gg, ec *d, ec *x, mp *n)
+ { gctx *g = (gctx *)gg; ec_imul(g->ei.c, d, x, n); }
+
+static void gmexp(group *gg, ec *d, const group_expfactor *f, size_t n) {
+ gctx *g = (gctx *)gg; size_t i;
+ ec_mulfactor *ff = xmalloc(n * sizeof(ec_mulfactor));
+ for (i = 0; i < n; i++) { ff[i].base = *f[i].base; ff[i].exp = f[i].exp; }
+ ec_immul(g->ei.c, d, ff, n); xfree(ff);
+}
+
+static int gread(group *gg, ec *d, const mptext_ops *ops, void *p) {
+ gctx *g = (gctx *)gg;
+ ec t = EC_INIT;
+ int rc = -1;
+ int ch;
+
+ ch = ops->get(p);
+ if (tolower(ch) == 'i') {
+ if (tolower(ops->get(p)) != 'n' || tolower(ops->get(p)) != 'f')
+ return (-1);
+ EC_SETINF(d);
+ return (0);
+ }
+ ops->unget(ch, p);
+ if ((t.x = mp_read(MP_NEW, 0, ops, p)) == 0) goto done;
+ do ch = ops->get(p); while (ch == ',' || isspace(ch)); ops->unget(ch, p);
+ if ((t.y = mp_read(MP_NEW, 0, ops, p)) == 0) goto done;
+ EC_IN(g->ei.c, &t, &t);
+ if (EC_CHECK(g->ei.c, &t)) goto done;
+ EC_COPY(d, &t); rc = 0;
+ EC_DESTROY(&t);
+done:
+ return (rc);
+}
+
+static int gwrite(group *gg, ec *x, const mptext_ops *ops, void *p) {
+ gctx *g = (gctx *)gg; int rc = -1; ec t = EC_INIT; EC_OUT(g->ei.c, &t, x);
+ if (EC_ATINF(&t)) rc = ops->put("inf", 3, p);
+ else if (!ops->put("0x", 2, p) && !mp_write(t.x, 16, ops, p) &&
+ !ops->put(", 0x", 4, p) && !mp_write(t.y, 16, ops, p)) rc = 0;
+ EC_DESTROY(&t); return (rc);
+}
+
+static mp *gtoint(group *gg, mp *d, ec *x) {
+ gctx *g = (gctx *)gg; ec t = EC_INIT; mp *i; if (EC_ATINF(x)) i = 0;
+ else { EC_OUT(g->ei.c, &t, x); i = MP_COPY(t.x); EC_DESTROY(&t); }
+ mp_drop(d); return (i);
+}
+
+static int gfromint(group *gg, ec *d, mp *x) {
+ gctx *g = (gctx *)gg; ec t = EC_INIT;
+ if (!ec_find(g->ei.c, &t, x)) return (-1);
+ EC_IN(g->ei.c, d, &t); EC_DESTROY(&t); return (0);
+}
+
+static int gtoec(group *gg, ec *d, ec *x)
+ { gctx *g = (gctx *)gg; EC_OUT(g->ei.c, d, x); return (0); }
+
+static int gfromec(group *gg, ec *d, ec *x) {
+ gctx *g = (gctx *)gg; ec t = EC_INIT; int rc; EC_IN(g->ei.c, &t, x);
+ rc = EC_CHECK(g->ei.c, &t); if (!rc) EC_COPY(d, &t); EC_DESTROY(&t);
+ return (rc);
+}
+
+static int gtobuf(group *gg, buf *b, ec *x) {
+ gctx *g = (gctx *)gg; ec t = EC_INIT; int rc;
+ EC_OUT(g->ei.c, &t, x); rc = buf_putec(b, &t); EC_DESTROY(&t); return (rc);
+}
+
+static int gfrombuf(group *gg, buf *b, ec *d) {
+ gctx *g = (gctx *)gg; ec t = EC_INIT; int rc;
+ if (buf_getec(b, &t)) return (-1);
+ EC_IN(g->ei.c, &t, &t); rc = EC_CHECK(g->ei.c, &t);
+ if (!rc) EC_COPY(d, &t); EC_DESTROY(&t); return (rc);
+}
+
+/* --- @group_ec@ --- *
+ *
+ * Arguments: @const ec_info *ei@ = elliptic curve parameters
+ *
+ * Returns: A pointer to the group.
+ *
+ * Use: Constructs an abstract group interface for an elliptic curve
+ * group. Group elements are @ec@ structures. The contents of
+ * the @ec_info@ structure becomes the property of the @group@
+ * object; you can (and should) free the structure itself, but
+ * calling @ec_freeinfo@ on it is not allowed.
+ */
+
+static const group_ops gops = {
+ GTY_EC,
+ gdestroygroup, gcreate, gcopy, gburn, gdestroy,
+ gsamep, geq, gidentp,
+ gcheck,
+ gmul, gsqr, ginv, gdiv, gexp, gmexp,
+ gread, gwrite,
+ gtoint, gfromint, gtoec, gfromec, gtobuf, gfrombuf
+};
+
+group *group_ec(const ec_info *ei)
+{
+ gctx *g = CREATE(gctx);
+
+ g->g.ops = &gops;
+ g->g.nbits = ei->c->f->nbits * 2;
+ g->g.noctets = ei->c->f->noctets * 2;
+ g->ei = *ei;
+ EC_CREATE(&g->id);
+ g->g.i = &g->id;
+ EC_CREATE(&g->gen);
+ EC_IN(g->ei.c, &g->gen, &ei->g);
+ g->g.r = ei->r;
+ g->g.h = ei->h;
+ return (&g->g);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: g-prime.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Abstraction for prime groups
+ *
+ * (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: g-prime.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <mLib/sub.h>
+
+#include "mpmont.h"
+#include "pgen.h"
+
+#define ge mp *
+#include "group.h"
+
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct gctx {
+ group g;
+ mp *gen;
+ mpmont mm;
+} gctx;
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- Group operations --- */
+
+static void gdestroygroup(group *gg) {
+ gctx *g = (gctx *)gg;
+ mp_drop(g->gen); mp_drop(g->g.r); mp_drop(g->g.h);
+ mpmont_destroy(&g->mm);
+ DESTROY(g);
+}
+
+static mp **gcreate(group *gg)
+ { mp **x = CREATE(mp *); *x = MP_COPY(*gg->i); return (x); }
+
+static void gcopy(group *gg, mp **d, mp **x)
+ { mp *t = MP_COPY(*x); MP_DROP(*d); *d = t; }
+
+static void gburn(group *gg, mp **x) { (*x)->f |= MP_BURN; }
+
+static void gdestroy(group *gg, mp **x) { MP_DROP(*x); DESTROY(x); }
+
+static int gsamep(group *gg, group *hh)
+ { gctx *g = (gctx *)gg, *h = (gctx *)hh; return (g->mm.m == h->mm.m); }
+
+static int geq(group *gg, mp **x, mp **y) { return (MP_EQ(*x, *y)); }
+
+static const char *gcheck(group *gg, grand *gr) {
+ gctx *g = (gctx *)gg; int rc; mp *t;
+ if (!pgen_primep(g->mm.m, gr)) return ("p is not prime");
+ t = mp_mul(MP_NEW, g->g.r, g->g.h); t = mp_add(t, t, MP_ONE);
+ rc = MP_EQ(t, g->mm.m); MP_DROP(t); if (!rc) return ("not a subgroup");
+ return (group_stdcheck(gg, gr));
+}
+
+static void gmul(group *gg, mp **d, mp **x, mp **y)
+ { gctx *g = (gctx *)gg; *d = mpmont_mul(&g->mm, *d, *x, *y); }
+
+static void gsqr(group *gg, mp **d, mp **x) {
+ gctx *g = (gctx *)gg; mp *r = mp_sqr(*d, *x);
+ *d = mpmont_reduce(&g->mm, r, r);
+}
+
+static void ginv(group *gg, mp **d, mp **x) {
+ gctx *g = (gctx *)gg; mp *r = mpmont_reduce(&g->mm, *d, *x);
+ mp_gcd(0, 0, &r, g->mm.m, r); *d = mpmont_mul(&g->mm, r, r, g->mm.r2);
+}
+
+static void gexp(group *gg, mp **d, mp **x, mp *n)
+ { gctx *g = (gctx *)gg; *d = mpmont_expr(&g->mm, *d, *x, n); }
+
+static void gmexp(group *gg, mp **d, const group_expfactor *f, size_t n) {
+ gctx *g = (gctx *)gg; size_t i;
+ mp_expfactor *ff = xmalloc(n * sizeof(mp_expfactor));
+ for (i = 0; i < n; i++) { ff[i].base = *f[i].base; ff[i].exp = f[i].exp; }
+ *d = mpmont_mexpr(&g->mm, *d, ff, n); xfree(ff);
+}
+
+static int gread(group *gg, mp **d, const mptext_ops *ops, void *p) {
+ gctx *g = (gctx *)gg; mp *t;
+ if ((t = mp_read(MP_NEW, 0, ops, p)) == 0) return (-1);
+ mp_drop(*d); *d = mpmont_mul(&g->mm, t, t, g->mm.r2); return (0);
+}
+
+static int gwrite(group *gg, mp **x, const mptext_ops *ops, void *p) {
+ gctx *g = (gctx *)gg; mp *t = mpmont_reduce(&g->mm, MP_NEW, *x);
+ int rc = mp_write(t, 10, ops, p); MP_DROP(t); return (rc);
+}
+
+static mp *gtoint(group *gg, mp *d, mp **x)
+ { gctx *g = (gctx *)gg; return (mpmont_reduce(&g->mm, d, *x)); }
+
+static int gfromint(group *gg, mp **d, mp *x) {
+ gctx *g = (gctx *)gg; mp_div(0, &x, x, g->mm.m); mp_drop(*d);
+ *d = mpmont_mul(&g->mm, x, x, g->mm.r2); return (0);
+}
+
+static int gtobuf(group *gg, buf *b, mp **x) {
+ gctx *g = (gctx *)gg; mp *t = mpmont_reduce(&g->mm, MP_NEW, *x);
+ int rc = buf_putmp(b, t); MP_DROP(t); return (rc);
+}
+
+static int gfrombuf(group *gg, buf *b, mp **d) {
+ gctx * g = (gctx *)gg; mp *x; if ((x = buf_getmp(b)) == 0) return (-1);
+ mp_div(0, &x, x, g->mm.r2); mp_drop(*d);
+ *d = mpmont_mul(&g->mm, x, x, g->mm.r2); return(0);
+}
+
+/* --- @group_prime@ --- *
+ *
+ * Arguments: @const gprime_param *gp@ = group parameters
+ *
+ * Returns: A pointer to the group.
+ *
+ * Use: Constructs an abstract group interface for a subgroup of a
+ * prime field. Group elements are @mp *@ pointers.
+ */
+
+static const group_ops gops = {
+ GTY_PRIME,
+ gdestroygroup, gcreate, gcopy, gburn, gdestroy,
+ gsamep, geq, group_stdidentp,
+ gcheck,
+ gmul, gsqr, ginv, group_stddiv, gexp, gmexp,
+ gread, gwrite,
+ gtoint, gfromint, group_stdtoec, group_stdfromec, gtobuf, gfrombuf
+};
+
+group *group_prime(const gprime_param *gp)
+{
+ gctx *g = CREATE(gctx);
+
+ g->g.ops = &gops;
+ g->g.nbits = mp_bits(gp->p);
+ g->g.noctets = (g->g.nbits + 7) >> 3;
+ mpmont_create(&g->mm, gp->p);
+ g->g.i = &g->mm.r;
+ g->gen = mpmont_mul(&g->mm, MP_NEW, gp->g, g->mm.r2);
+ g->g.g = &g->gen;
+ g->g.r = MP_COPY(gp->q);
+ g->g.h = MP_NEW; mp_div(&g->g.h, 0, gp->p, gp->q);
+ return (&g->g);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: genprimes.c,v 1.4 2001/03/04 13:08:10 mdw Exp $
+ * $Id: genprimes.c,v 1.5 2004/04/01 12:50:09 mdw Exp $
*
* Generate prime number table
*
/*----- Revision history --------------------------------------------------*
*
* $Log: genprimes.c,v $
+ * Revision 1.5 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.4 2001/03/04 13:08:10 mdw
* Use @DA_LAST@ to determine @MAXPRIME@, now that it exists.
*
char *header = "primetab.h";
char *source = "primetab.c";
char *name = "primetab";
+ char *sym = 0;
intv p = DA_INIT;
int i;
ego(argv[0]);
for (;;) {
- int i = getopt(argc, argv, "h:c:i:n:m:t:");
+ int i = getopt(argc, argv, "h:c:i:n:m:t:s:");
if (i < 0)
break;
switch (i) {
case 't':
type = optarg;
break;
+ case 's':
+ sym = optarg;
+ break;
default:
pquis(stderr, "Usage: $ [-n nprimes] [-m maxprime] [-t type]\n");
exit(EXIT_FAILURE);
char *q;
if (!fp)
die(EXIT_FAILURE, "couldn't write `%s': %s", header, strerror(errno));
- for (q = header; *q; q++) {
- int ch = (unsigned char)*q;
- if (isalnum(ch))
- ch = toupper(ch);
- else
- ch = '_';
- DPUTC(&d, ch);
+ if (!sym) {
+ for (q = header; *q; q++) {
+ int ch = (unsigned char)*q;
+ if (isalnum(ch))
+ ch = toupper(ch);
+ else
+ ch = '_';
+ DPUTC(&d, ch);
+ }
+ DPUTZ(&d);
+ sym = d.buf;
}
- DPUTZ(&d);
fprintf(fp, "\
/* -*-c-*-\n\
*\n\
\n\
#endif\n\
",
- d.buf, d.buf,
+ sym, sym,
(unsigned long)DA_LEN(&p),
DA_LAST(&p),
type, name);
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: group-dstr.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Dynamic string I/O for group elements
+ *
+ * (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: group-dstr.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "group.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @group_readdstr@ --- *
+ *
+ * Arguments: @group *g@ = an abstract group
+ * @ge *d@ = destination group element
+ * @dstr *dd@ = string to read from
+ * @size_t *off@ = offset to start at (updated)
+ *
+ * Returns: Zero on success, nonzero on failure.
+ *
+ * Use: Parses a group element from a dynamic string.
+ */
+
+int group_readdstr(group *g, ge *d, dstr *dd, size_t *off)
+{
+ mptext_dstrctx md;
+
+ md.d = dd;
+ md.i = off ? *off : 0;
+ if (G_READ(g, d, &mptext_dstrops, &md))
+ return (-1);
+ if (off) *off = md.i;
+ return (0);
+}
+
+/* --- @group_writedstr@ --- *
+ *
+ * Arguments: @group *g@ = an abstract group
+ * @ge *x@ = a group element
+ * @dstr *d@ = string to write to
+ * @size_t sz@ = how long the buffer is
+ *
+ * Returns: Zero on success, nonzero on failure.
+ *
+ * Use: Writes a group element to a dstr buffer.
+ */
+
+int group_writedstr(group *g, ge *x, dstr *d)
+{
+ mptext_dstrctx md;
+
+ md.d = d;
+ if (G_WRITE(g, x, &mptext_dstrops, &md))
+ return (-1);
+ DPUTZ(d);
+ return (0);
+}
+
+
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: group-exp.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Exponentiation for abstract groups
+ *
+ * (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: group-exp.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "group.h"
+#include "group-exp.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @group_stdexp@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ge *d@ = destination pointer
+ * @ge *x@ = base element
+ * @mp *n@ = exponent
+ *
+ * Returns: ---
+ *
+ * Use: Computes %$d = x^n$% efficiently.
+ */
+
+void group_stdexp(group *gg, ge *d, ge *x, mp *n)
+{
+ ge *t = G_CREATE(gg);
+
+ G_COPY(gg, t, x);
+ MP_SHRINK(n);
+ G_COPY(gg, d, gg->i);
+ if (n->f & MP_BURN)
+ G_BURN(gg, t);
+ if (MP_LEN(n) == 0)
+ ;
+ else {
+ if (n->f & MP_NEG)
+ G_INV(gg, t, t);
+ if (MP_LEN(n) < EXP_THRESH)
+ EXP_SIMPLE(d, t, n);
+ else
+ EXP_WINDOW(d, t, n);
+ }
+ G_DESTROY(gg, t);
+}
+
+/* --- @group_stdmexp@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ge *d@ = destination pointer
+ * @const group_expfactor *f@ = vector of factors
+ * @size_t n@ = number of factors
+ *
+ * Returns: ---
+ *
+ * Use: Computes %$d = g_0^{x_0} g_1^{x_1} \ldots$% efficiently.
+ */
+
+#undef EXP_WINSZ
+#define EXP_WINSZ 3
+
+void group_stdmexp(group *gg, ge *d, const group_expfactor *f, size_t n)
+{
+ group_expfactor *ff = xmalloc(n * sizeof(group_expfactor));
+ size_t i;
+
+ for (i = 0; i < n; i++) {
+ ff[i].base = G_CREATE(gg);
+ MP_SHRINK(f[i].exp);
+ if (f[i].exp->f & MP_NEG)
+ G_INV(gg, ff[i].base, f[i].base);
+ else
+ G_COPY(gg, ff[i].base, f[i].base);
+ if (f[i].exp->f & MP_BURN)
+ G_BURN(gg, ff[i].base);
+ ff[i].exp = f[i].exp;
+ }
+ G_COPY(gg, d, gg->i);
+ EXP_SIMUL(d, ff, n);
+ for (i = 0; i < n; i++)
+ G_DESTROY(gg, ff[i].base);
+ xfree(ff);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: group-exp.h,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Exponentiation operations for abstract groups
+ *
+ * (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: group-exp.h,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+#ifndef CATACOMB_GROUP_EXP_H
+#define CATACOMB_GROUP_EXP_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Exponentation definitions -----------------------------------------*/
+
+#define EXP_TYPE ge *
+
+#define EXP_COPY(d, p) do { \
+ (d) = G_CREATE(gg); \
+ G_COPY(gg, (d), (p)); \
+} while (0)
+#define EXP_DROP(x) G_DESTROY(gg, (x))
+
+#define EXP_MUL(a, x) G_MUL(gg, (a), (a), (x))
+#define EXP_SQR(a) G_SQR(gg, (a), (a));
+#define EXP_FIX(x)
+
+#define EXP_SETMUL(d, x, y) do { \
+ (d) = G_CREATE(gg); \
+ G_MUL(gg, (d), (x), (y)); \
+} while (0)
+#define EXP_SETSQR(d, x) do { \
+ (d) = G_CREATE(gg); \
+ G_SQR(gg, (d), (x)); \
+} while (0)
+
+#include "exp.h"
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: group-file.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * File I/O for group elements
+ *
+ * (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: group-file.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "group.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @group_readfile@ --- *
+ *
+ * Arguments: @group *g@ = an abstract group
+ * @ge *d@ = destination group element
+ * @FILE *fp@ = the file to read from
+ *
+ * Returns: Zero on success, nonzero on failure.
+ *
+ * Use: Parses a group element from a file.
+ */
+
+int group_readfile(group *g, ge *d, FILE *fp)
+ { return (G_READ(g, d, &mptext_fileops, fp)); }
+
+/* --- @group_writefile@ --- *
+ *
+ * Arguments: @group *g@ = an abstract group
+ * @ge *x@ = a group element
+ * @FILE *fp@ = the file to write on
+ *
+ * Returns: Zero on success, nonzero on failure.
+ *
+ * Use: Writes a group element to a file.
+ */
+
+int group_writefile(group *g, ge *x, FILE *fp)
+ { return (G_WRITE(g, x, &mptext_stringops, fp)); }
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: group-parse.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Parse group description strings
+ *
+ * (c) 2004 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of Trivial IP Encryption (TrIPE).
+ *
+ * TrIPE is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * TrIPE 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with TrIPE; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: group-parse.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "group.h"
+#include "dh.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @group_parse@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = quick-and-dirty parser
+ *
+ * Returns: Group pointer, or null for failure.
+ *
+ * Use: Parses a group description and returns the group. This has
+ * the form `TYPE { SPEC }' where TYPE is `prime' or `ec', and
+ * SPEC is the appropriate kind of group specification of the
+ * given type.
+ */
+
+group *group_parse(qd_parse *qd)
+{
+ group *g = 0;
+
+ switch (qd_enum(qd, "prime,ec")) {
+ case 0: {
+ dh_param dp;
+ qd_delim(qd, '{');
+ if (dh_parse(qd, &dp)) break;
+ qd_delim(qd, '}');
+ g = group_prime(&dp);
+ dh_paramfree(&dp);
+ } break;
+ case 1: {
+ ec_info ei;
+ qd_delim(qd, '{');
+ if (ec_infoparse(qd, &ei)) break;
+ qd_delim(qd, '}');
+ g = group_ec(&ei);
+ } break;
+ }
+ return (g);
+}
+
+/* --- @group_fromstring@ --- *
+ *
+ * Arguments: @const char *p@ = pointer to string to read
+ * @group **gg@ = where to put the group pointer
+ *
+ * Returns: Null if OK, or an error string.
+ *
+ * Use: Parses a group spec from a string, and returns the group.
+ */
+
+const char *group_fromstring(const char *p, group **gg)
+{
+ group *g;
+ qd_parse qd;
+
+ qd.p = p;
+ qd.e = 0;
+ if ((g = group_parse(&qd)) == 0) return (qd.e);
+ if (!qd_eofp(&qd)) { G_DESTROYGROUP(g); return ("junk at end of string"); }
+ *gg = g;
+ return (0);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: group-stdops.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Standard group operations
+ *
+ * (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: group-stdops.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "group.h"
+#include "pgen.h"
+
+/*----- Handy functions ---------------------------------------------------*/
+
+/* --- @group_check@ --- *
+ *
+ * Arguments: @group *g@ = an abstract group
+ * @ge *x@ = a group element
+ *
+ * Returns: Zero on success, nonzero for failure.
+ *
+ * Use: Checks that @x@ is a valid group element. This may take a
+ * while, since it checks that %$x^h \ne 1$% and %$x^r = 1$%.
+ */
+
+int group_check(group *g, ge *x)
+{
+ ge *d = G_CREATE(g);
+ int rc;
+
+ G_EXP(g, d, x, g->h); rc = !G_IDENTP(g, d);
+ if (rc) { G_EXP(g, d, x, g->r); rc = G_IDENTP(g, d); }
+ G_DESTROY(g, d);
+ if (!rc) return (-1);
+ return (0);
+}
+
+/* --- @group_samep@ --- *
+ *
+ * Arguments: @group *g, *h@ = two abstract groups
+ *
+ * Returns: Nonzero if the groups are in fact identical (not just
+ * isomorphic).
+ *
+ * Use: Checks to see whether two groups are actually the same. This
+ * function does the full check: the group operatrion @samep@
+ * just does the group-specific details.
+ */
+
+int group_samep(group *g, group *h)
+{
+ return (g->ops == h->ops &&
+ MP_EQ(g->r, h->r) && MP_EQ(g->h, h->h) &&
+ G_EQ(g, g->i, h->i) && G_EQ(g, g->g, h->g) &&
+ G_SAMEP(g, h));
+}
+
+/*----- Standard implementations ------------------------------------------*/
+
+/* --- @group_stdidentp@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ge *x@ = group element
+ *
+ * Returns: Nonzero if %$x$% is the group identity.
+ */
+
+int group_stdidentp(group *g, ge *x) { return (G_EQ(g, x, g->i)); }
+
+/* --- @group_stdsqr@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ge *d@ = destination pointer
+ * @ge *x@ = group element
+ *
+ * Returns: ---
+ *
+ * Use: Computes %$d = x^2$% as %$d = x x$%.
+ */
+
+void group_stdsqr(group *g, ge *d, ge *x) { G_MUL(g, d, x, x); }
+
+/* --- @group_stddiv@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ge *d@ = destination pointer
+ * @ge *x@ = dividend
+ * @ge *y@ = divisor
+ *
+ * Returns: ---
+ *
+ * Use: Computes %$d = x/y$% as %$d = x y^{-1}$%.
+ */
+
+void group_stddiv(group *g, ge *d, ge *x, ge *y)
+{
+ G_INV(g, d, y);
+ G_MUL(g, d, x, d);
+}
+
+/* --- @group_stdtoec@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ec *d@ = destination point
+ * @ge *x@ = group element
+ *
+ * Returns: @-1@, indicating failure.
+ *
+ * Use: Fails to convert a group element to an elliptic curve point.
+ */
+
+int group_stdtoec(group *g, ec *d, ge *x) { return (-1); }
+
+/* --- @group_stdfromec@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ge *d@ = destination pointer
+ * @ec *p@ = elliptic curve point
+ *
+ * Returns: Zero for success, @-1@ on failure.
+ *
+ * Use: Converts %$p$% to a group element by converting its %$x$%-
+ * coordinate.
+ */
+
+int group_stdfromec(group *g, ge *d, ec *p)
+ { if (EC_ATINF(p)) return (-1); return (G_FROMINT(g, d, p->x)); }
+
+/* --- @group_stdcheck@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @grand *gr@ = random number source.
+ *
+ * Returns: Null on success, or a pointer to an error message.
+ */
+
+const char *group_stdcheck(group *g, grand *gr)
+{
+ ge *t;
+ int rc;
+
+ if (!pgen_primep(g->r, gr)) return ("group order not prime");
+ t = G_CREATE(g); G_EXP(g, t, g->g, g->r);
+ rc = G_IDENTP(g, t); G_DESTROY(g, t);
+ if (!rc) return ("generator not in the group");
+ return (0);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: group-string.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * String I/O for group elements
+ *
+ * (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: group-string.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "group.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @group_readstring@ --- *
+ *
+ * Arguments: @group *g@ = an abstract group
+ * @ge *d@ = destination group element
+ * @const char *p@ = where the string is
+ * @char **end@ = where to put the end pointer
+ *
+ * Returns: Zero on success, nonzero on failure.
+ *
+ * Use: Parses a group element from a string.
+ */
+
+int group_readstring(group *g, ge *d, const char *p, char **end)
+{
+ mptext_stringctx ms;
+
+ ms.buf = (/*unconst*/ char *)p;
+ ms.lim = (/*unconst*/ char *)p + strlen(p);
+ if (G_READ(g, d, &mptext_stringops, &ms))
+ return (-1);
+ if (end) *end = ms.buf;
+ return (0);
+}
+
+/* --- @group_writestring@ --- *
+ *
+ * Arguments: @group *g@ = an abstract group
+ * @ge *x@ = a group element
+ * @char *p@ = where the string should go
+ * @size_t sz@ = how long the buffer is
+ *
+ * Returns: Zero on success, nonzero on failure.
+ *
+ * Use: Writes a group element to a string buffer.
+ */
+
+int group_writestring(group *g, ge *x, char *p, size_t sz)
+{
+ mptext_stringctx ms;
+
+ ms.buf = p;
+ ms.lim = p + sz - 1;
+ if (G_WRITE(g, x, &mptext_stringops, &ms))
+ return (-1);
+ *ms.buf = 0;
+ return (0);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: group-test.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Testing group operations
+ *
+ * (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: group-test.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stdarg.h>
+
+#include <mLib/testrig.h>
+
+#include "group.h"
+#include "fibrand.h"
+#include "ec.h"
+#include "ec-test.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+static group *getgroup(const char *p) {
+ group *g; qd_parse qd;
+ qd.p = p; qd.e = 0; g = group_parse(&qd);
+ if (g && !qd_eofp(&qd)) { G_DESTROYGROUP(g); g = 0; qd.e = "junk at eof"; }
+ if (!g) { fprintf(stderr, "bad group string `%.*s|%s': %s\n", qd.p - p,
+ p, qd.p, qd.e); exit(1); }
+ return (g);
+}
+
+static ge *getge(group *g, const char *p) {
+ ge *x = G_CREATE(g);
+ if (group_readstring(g, x, p, 0)) {
+ fprintf(stderr, "bad group element `%s'\n", p);
+ exit(1);
+ }
+ return (x);
+}
+
+static void show(group *g, const char *p, ge *x) {
+ fprintf(stderr, "*** %s = ", p); group_writefile(g, x, stderr);
+ putc('\n', stderr);
+}
+
+static void showec(const char *p, ec *q) {
+ fprintf(stderr, "*** %s = ", p);
+ if (EC_ATINF(q)) fprintf(stderr, "inf\n");
+ else {
+ mp_writefile(q->x, stderr, 16); fputs(", ", stderr);
+ mp_writefile(q->x, stderr, 16); putchar('\n');
+ }
+}
+
+static void showmp(const char *p, mp *x, int r) {
+ fprintf(stderr, "*** %s = ", p); mp_writefile(x, stderr, r);
+ putc('\n', stderr);
+}
+
+static int check(const char *op, const char *gd, group *g,
+ ge *r, ge *c, ...) {
+ va_list ap;
+
+ if (G_EQ(g, r, c)) return (1);
+ fprintf(stderr, "\n*** %s failed\n", op);
+ fprintf(stderr, "*** group: %s\n", gd);
+ va_start(ap, c);
+ for (;;) {
+ const char *p; ge *x;
+ p = va_arg(ap, const char *); if (!p) break;
+ x = va_arg(ap, ge *); show(g, p, x);
+ }
+ show(g, "expected", r);
+ show(g, "computed", c);
+ return (0);
+}
+
+/*----- Actual tests ------------------------------------------------------*/
+
+static int vcheck(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ grand *gr = fibrand_create(0);
+ const char *e = G_CHECK(g, gr);
+ int ok = 1;
+ gr->ops->destroy(gr);
+ if (!e) e = "ok";
+ G_DESTROYGROUP(g);
+ if (strcmp(e, v[1].buf)) {
+ ok = 0;
+ fprintf(stderr, "*** check failed\n");
+ fprintf(stderr, "*** group: %s\n", v[0].buf);
+ fprintf(stderr, "*** expected: %s\n", v[1].buf);
+ fprintf(stderr, "*** returned: %s\n", e);
+ }
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vcheckelt(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ ge *x = getge(g, v[1].buf);
+ int ir = *(int *)v[2].buf;
+ int ic = group_check(g, x);
+ int ok = 1;
+ if (ir != ic) {
+ ok = 0;
+ fprintf(stderr, "*** check failed\n");
+ fprintf(stderr, "*** group: %s\n", v[0].buf);
+ show(g, "x", x);
+ fprintf(stderr, "*** expected %s\n", ir ? "failure" : "success");
+ }
+ G_DESTROY(g, x);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vmul(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ ge *x = getge(g, v[1].buf);
+ ge *y = getge(g, v[2].buf);
+ ge *r = getge(g, v[3].buf);
+ ge *c = G_CREATE(g);
+ int ok = 1;
+ G_MUL(g, c, x, y);
+ ok &= check("mul", v[0].buf, g, r, c, "x", x, "y", y, (char *)0);
+ G_DESTROY(g, x); G_DESTROY(g, y); G_DESTROY(g, r); G_DESTROY(g, c);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vsqr(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ ge *x = getge(g, v[1].buf);
+ ge *r = getge(g, v[2].buf);
+ ge *c = G_CREATE(g);
+ int ok = 1;
+ G_SQR(g, c, x);
+ ok &= check("sqr", v[0].buf, g, r, c, "x", x, (char *)0);
+ G_DESTROY(g, x); G_DESTROY(g, r); G_DESTROY(g, c);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vinv(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ ge *x = getge(g, v[1].buf);
+ ge *r = getge(g, v[2].buf);
+ ge *c = G_CREATE(g);
+ int ok = 1;
+ G_INV(g, c, x);
+ ok &= check("inv", v[0].buf, g, r, c, "x", x, (char *)0);
+ G_DESTROY(g, x); G_DESTROY(g, r); G_DESTROY(g, c);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vdiv(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ ge *x = getge(g, v[1].buf);
+ ge *y = getge(g, v[2].buf);
+ ge *r = getge(g, v[3].buf);
+ ge *c = G_CREATE(g);
+ int ok = 1;
+ G_DIV(g, c, x, y);
+ ok &= check("div", v[0].buf, g, r, c, "x", x, "y", y, (char *)0);
+ group_stddiv(g, c, x, y);
+ ok &= check("stddiv", v[0].buf, g, r, c, "x", x, "y", y, (char *)0);
+ G_DESTROY(g, x); G_DESTROY(g, y); G_DESTROY(g, r); G_DESTROY(g, c);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vexp(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ ge *x = getge(g, v[1].buf);
+ mp *n = *(mp **)v[2].buf;
+ ge *r = getge(g, v[3].buf);
+ ge *c = G_CREATE(g);
+ int ok = 1;
+ G_EXP(g, c, x, n);
+ if (!G_EQ(g, r, c)) {
+ ok = 0;
+ fprintf(stderr, "\n*** exp failed\n");
+ fprintf(stderr, "*** group: %s\n", v[0].buf);
+ show(g, "x", x); showmp("n", n, 10);
+ show(g, "expected", r); show(g, "computed", c);
+ }
+ group_stdexp(g, c, x, n);
+ if (!G_EQ(g, r, c)) {
+ ok = 0;
+ fprintf(stderr, "\n*** stdexp failed\n");
+ fprintf(stderr, "*** group: %s\n", v[0].buf);
+ show(g, "x", x); showmp("n", n, 10);
+ show(g, "expected", r); show(g, "computed", c);
+ }
+ G_DESTROY(g, x); MP_DROP(n); G_DESTROY(g, r); G_DESTROY(g, c);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vmexp(size_t n, dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ ge *c, *r;
+ group_expfactor *f = xmalloc(n * sizeof(group_expfactor));
+ int ok = 1;
+ size_t i;
+ for (i = 0; i < n; i++) {
+ f[i].base = getge(g, v[1 + 2 * i].buf);
+ f[i].exp = *(mp **)v[2 + 2 * i].buf;
+ }
+ r = getge(g, v[1 + 2 * n].buf);
+ c = G_CREATE(g);
+ G_MEXP(g, c, f, n);
+ if (!G_EQ(g, r, c)) {
+ ok = 0;
+ fprintf(stderr, "\n*** mexp failed\n");
+ fprintf(stderr, "*** group: %s\n", v[0].buf);
+ for (i = 0; i < n; i++) {
+ show(g, "base", f[i].base);
+ showmp("exp", f[i].exp, 10);
+ }
+ show(g, "expected", r); show(g, "computed", c);
+ }
+ group_stdmexp(g, c, f, n);
+ if (!G_EQ(g, r, c)) {
+ ok = 0;
+ fprintf(stderr, "\n*** stdmexp failed\n");
+ fprintf(stderr, "*** group: %s\n", v[0].buf);
+ for (i = 0; i < n; i++) {
+ show(g, "base", f[i].base);
+ showmp("exp", f[i].exp, 10);
+ }
+ show(g, "expected", r); show(g, "computed", c);
+ }
+ for (i = 0; i < n; i++) { G_DESTROY(g, f[i].base); MP_DROP(f[i].exp); }
+ G_DESTROY(g, r); G_DESTROY(g, c);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vmexp1(dstr *v) { return vmexp(1, v); }
+static int vmexp2(dstr *v) { return vmexp(2, v); }
+static int vmexp3(dstr *v) { return vmexp(3, v); }
+static int vmexp4(dstr *v) { return vmexp(4, v); }
+
+static int vtoint(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ ge *x = getge(g, v[1].buf);
+ int ir = *(int *)v[2].buf;
+ mp *r = *(mp **)v[3].buf;
+ mp *c;
+ int ic;
+ int ok = 1;
+ c = G_TOINT(g, MP_NEW, x);
+ ic = c ? 0 : -1;
+ if (ir != ic || (!ic && !MP_EQ(r, c))) {
+ ok = 0;
+ fprintf(stderr, "\n*** toint failed\n");
+ fprintf(stderr, "*** group: %s\n", v[0].buf);
+ if (ir) fprintf(stderr, "*** expected failure\n");
+ else { show(g, "x", x); showmp("expected", r, 16);
+ showmp("computed", c, 16); }
+ }
+ G_DESTROY(g, x); mp_drop(r); mp_drop(c);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vfromint(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ mp *x = *(mp **)v[1].buf;
+ int ir = *(int *)v[2].buf;
+ ge *r = getge(g, v[3].buf);
+ int ic;
+ ge *c = G_CREATE(g);
+ int ok = 1;
+ ic = G_FROMINT(g, c, x);
+ if (ir != ic || (!ic && !G_EQ(g, r, c))) {
+ ok = 0;
+ fprintf(stderr, "\n*** fromint failed\n");
+ fprintf(stderr, "*** group: %s\n", v[0].buf);
+ showmp("x", x, 16); if (ir) fprintf(stderr, "*** should have failed\n");
+ else { show(g, "expected", r); show(g, "computed", c); }
+ }
+ MP_DROP(x); G_DESTROY(g, r); G_DESTROY(g, c);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vtoec(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ ge *x = getge(g, v[1].buf);
+ int ir = *(int *)v[2].buf;
+ ec *r = (ec *)v[3].buf;
+ int ic;
+ ec c = EC_INIT;
+ int ok = 1;
+ ic = G_TOEC(g, &c, x);
+ if (ir != ic || (!ic && !EC_EQ(r, &c))) {
+ ok = 0;
+ fprintf(stderr, "\n*** toec failed\n");
+ fprintf(stderr, "*** group: %s\n", v[0].buf);
+ show(g, "x", x);
+ if (ir) fprintf(stderr, "*** should have failed\n");
+ else { showec("expected", r); showec("computed", &c); }
+ }
+ G_DESTROY(g, x); EC_DESTROY(&c); EC_DESTROY(r);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vfromec(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ ec *p = (ec *)v[1].buf;
+ int ir = *(int *)v[2].buf;
+ ge *r = getge(g, v[3].buf);
+ int ic;
+ ge *c = G_CREATE(g);
+ int ok = 1;
+ ic = G_FROMEC(g, c, p);
+ if (ir != ic || (!ic && !G_EQ(g, r, c))) {
+ ok = 0;
+ fprintf(stderr, "\n*** fromec failed\n");
+ fprintf(stderr, "*** group: %s\n", v[0].buf);
+ showec("p", p); if (ir) fprintf(stderr, "*** should have failed\n");
+ else { show(g, "expected", r); show(g, "computed", c); }
+ }
+ EC_DESTROY(p); G_DESTROY(g, r); G_DESTROY(g, c);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vtobuf(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ ge *x = getge(g, v[1].buf);
+ int ir = *(int *)v[2].buf;
+ dstr c = DSTR_INIT;
+ int ic;
+ buf b;
+ int ok = 1;
+
+ dstr_ensure(&c, v[3].len);
+ buf_init(&b, c.buf, v[3].len);
+ ic = G_TOBUF(g, &b, x);
+ c.len = BLEN(&b);
+ if (ic != ir || (!ic && (c.len != v[3].len ||
+ memcmp(c.buf, v[3].buf, c.len)))) {
+ ok = 0;
+ fprintf(stderr, "*** tobuf failed\n");
+ fprintf(stderr, "*** group: %s\n", v[0].buf);
+ show(g, "x", x);
+ if (ir) fprintf(stderr, "*** expected failure\n");
+ else {
+ fprintf(stderr, "*** expected: "); type_hex.dump(&v[3], stderr);
+ fprintf(stderr, "\n*** computed: "); type_hex.dump(&c, stderr);
+ fputc('\n', stderr);
+ }
+ }
+ G_DESTROY(g, x); dstr_destroy(&c);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static int vfrombuf(dstr *v)
+{
+ group *g = getgroup(v[0].buf);
+ int ir = *(int *)v[2].buf;
+ ge *r = getge(g, v[3].buf);
+ int ic;
+ ge *c = G_CREATE(g);
+ buf b;
+ int ok = 1;
+
+ buf_init(&b, v[1].buf, v[1].len);
+ ic = G_FROMBUF(g, &b, c);
+ if ((ic < 0) != (ir < 0) || (ir >= 0 &&
+ (ir != BLEN(&b) || !G_EQ(g, r, c)))) {
+ ok = 0;
+ fprintf(stderr, "*** frombuf failed\n");
+ fprintf(stderr, "*** group: %s\n", v[0].buf);
+ fprintf(stderr, "*** input string: "); type_hex.dump(&v[1], stderr);
+ fputc('\n', stderr);
+ if (ir < 0) fprintf(stderr, "*** expected failure\n");
+ else {
+ show(g, "expected", r); show(g, "computed", c);
+ fprintf(stderr, "*** expected used = %d\n", ir);
+ fprintf(stderr, "*** computed used = %lu\n", (unsigned long)BLEN(&b));
+ }
+ }
+ G_DESTROY(g, r); G_DESTROY(g, c);
+ G_DESTROYGROUP(g);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return (ok);
+}
+
+static const test_chunk tests[] = {
+ { "check", vcheck, { &type_string, &type_string } },
+ { "checkelt", vcheckelt, { &type_string, &type_string, &type_int } },
+ { "mul", vmul, { &type_string, &type_string,
+ &type_string, &type_string } },
+ { "sqr", vsqr, { &type_string, &type_string,
+ &type_string } },
+ { "inv", vinv, { &type_string, &type_string,
+ &type_string } },
+ { "div", vdiv, { &type_string, &type_string,
+ &type_string, &type_string } },
+ { "exp", vexp, { &type_string, &type_string,
+ &type_mp, &type_string } },
+ { "mexp-1", vmexp1, { &type_string,
+ &type_string, &type_mp,
+ &type_string } },
+ { "mexp-2", vmexp2, { &type_string,
+ &type_string, &type_mp,
+ &type_string, &type_mp,
+ &type_string } },
+ { "mexp-3", vmexp3, { &type_string,
+ &type_string, &type_mp,
+ &type_string, &type_mp,
+ &type_string, &type_mp,
+ &type_string } },
+ { "mexp-4", vmexp4, { &type_string,
+ &type_string, &type_mp,
+ &type_string, &type_mp,
+ &type_string, &type_mp,
+ &type_string, &type_mp,
+ &type_string } },
+ { "toint", vtoint, { &type_string, &type_string,
+ &type_int, &type_mp } },
+ { "fromint", vfromint, { &type_string, &type_mp,
+ &type_int, &type_string } },
+ { "toec", vtoec, { &type_string, &type_string,
+ &type_int, &type_ec } },
+ { "fromec", vfromec, { &type_string, &type_ec,
+ &type_int, &type_string } },
+ { "tobuf", vtobuf, { &type_string, &type_string,
+ &type_int, &type_hex } },
+ { "frombuf", vfrombuf, { &type_string, &type_hex,
+ &type_int, &type_string } },
+ { 0 }
+};
+
+int main(int argc, char *argv[])
+{
+ sub_init();
+ test_run(argc, argv, tests, SRCDIR "/tests/group");
+ return (0);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: group.h,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * General cyclic group abstraction
+ *
+ * (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: group.h,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+#ifndef CATACOMB_GROUP_H
+#define CATACOMB_GROUP_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <mLib/dstr.h>
+
+#ifndef CATACOMB_BUF_H
+# include "buf.h"
+#endif
+
+#ifndef CATACOMB_DH_H
+# include "ec.h"
+#endif
+
+#ifndef CATACOMB_GRAND_H
+# include "grand.h"
+#endif
+
+#ifndef CATACOMB_MP_H
+# include "mp.h"
+#endif
+
+#ifndef CATACOMB_QDPARSE_H
+# include "qdparse.h"
+#endif
+
+/*----- Data structures ---------------------------------------------------*/
+
+#ifndef ge
+ typedef struct ge ge; /* Group element (abstract type) */
+#endif
+
+typedef struct group {
+ const struct group_ops *ops; /* Operations table */
+ size_t nbits; /* Size of an element in bits */
+ size_t noctets; /* Size of an element in octets */
+ ge *i; /* Identity element */
+ ge *g; /* Generator element */
+ mp *r; /* Order of the generator */
+ mp *h; /* Cofactor */
+} group;
+
+typedef struct group_expfactor {
+ ge *base; /* The base */
+ mp *exp; /* The exponent */
+} group_expfactor;
+
+typedef struct group_ops {
+ unsigned ty; /* Type of this group */
+
+ /* --- Memory management --- */
+
+ void (*destroygroup)(group */*g*/);
+ ge *(*create)(group */*g*/);
+ void (*copy)(group */*g*/, ge */*d*/, ge */*x*/);
+ void (*burn)(group */*g*/, ge */*x*/);
+ void (*destroy)(group */*g*/, ge */*e*/);
+
+ /* --- Comparisons --- */
+
+ int (*samep)(group */*g*/, group */*h*/);
+ int (*eq)(group */*g*/, ge */*x*/, ge */*y*/);
+ int (*identp)(group */*g*/, ge */*x*/);
+
+ /* --- Other stuff --- */
+
+ const char *(*check)(group */*g*/, grand */*gr*/);
+
+ /* --- Arithmetic --- */
+
+ void (*mul)(group */*g*/, ge */*d*/, ge */*x*/, ge */*y*/);
+ void (*sqr)(group */*g*/, ge */*d*/, ge */*x*/);
+ void (*inv)(group */*g*/, ge */*d*/, ge */*x*/);
+ void (*div)(group */*g*/, ge */*d*/, ge */*x*/, ge */*y*/);
+ void (*exp)(group */*g*/, ge */*d*/, ge */*x*/, mp */*n*/);
+ void (*mexp)(group */*g*/, ge */*d*/,
+ const group_expfactor */*f*/, size_t /*n*/);
+
+ /* --- Debugging --- */
+
+ int (*read)(group */*g*/, ge */*d*/,
+ const mptext_ops */*ops*/, void */*p*/);
+ int (*write)(group */*g*/, ge */*x*/,
+ const mptext_ops */*ops*/, void */*p*/);
+
+ /* --- Conversions --- */
+
+ mp *(*toint)(group */*g*/, mp */*d*/, ge */*x*/);
+ int (*fromint)(group */*g*/, ge */*d*/, mp */*x*/);
+ int (*toec)(group */*g*/, ec */*d*/, ge */*x*/);
+ int (*fromec)(group */*g*/, ge */*d*/, ec */*p*/);
+ int (*tobuf)(group */*h*/, buf */*b*/, ge */*x*/);
+ int (*frombuf)(group */*h*/, buf */*b*/, ge */*d*/);
+
+} group_ops;
+
+enum {
+ GTY_PRIME, /* Prime field subgroup */
+ GTY_BINARY, /* Binary feld subgroup */
+ GTY_EC /* Elliptic curve group */
+};
+
+#define G_DESTROYGROUP(g) (g)->ops->destroygroup((g))
+#define G_CREATE(g) (g)->ops->create((g))
+#define G_COPY(g, d, x) (g)->ops->copy((g), (d), (x))
+#define G_BURN(g, x) (g)->ops->burn((g), (x))
+#define G_DESTROY(g, x) (g)->ops->destroy((g), (x))
+
+#define G_SAMEP(g, h) (g)->ops->samep((g), (h))
+#define G_EQ(g, x, y) (g)->ops->eq((g), (x), (y))
+#define G_IDENTP(g, x) (g)->ops->identp((g), (x))
+
+#define G_CHECK(g, gr) (g)->ops->check((g), (gr))
+
+#define G_MUL(g, d, x, y) (g)->ops->mul((g), (d), (x), (y))
+#define G_SQR(g, d, x) (g)->ops->sqr((g), (d), (x))
+#define G_INV(g, d, x) (g)->ops->inv((g), (d), (x))
+#define G_DIV(g, d, x, y) (g)->ops->div((g), (d), (x), (y))
+#define G_EXP(g, d, x, n) (g)->ops->exp((g), (d), (x), (n))
+#define G_MEXP(g, d, f, n) (g)->ops->mexp((g), (d), (f), (n))
+
+#define G_READ(g, d, o, p) (g)->ops->read((g), (d), (o), (p))
+#define G_WRITE(g, x, o, p) (g)->ops->write((g), (x), (o), (p))
+
+#define G_TOINT(g, d, x) (g)->ops->toint((g), (d), (x))
+#define G_FROMINT(g, d, x) (g)->ops->fromint((g), (d), (x))
+#define G_TOEC(g, d, x) (g)->ops->toec((g), (d), (x))
+#define G_FROMEC(g, d, p) (g)->ops->fromec((g), (d), (p))
+#define G_TOBUF(g, b, x) (g)->ops->tobuf((g), (b), (x))
+#define G_FROMBUF(g, b, d) (g)->ops->frombuf((g), (b), (d))
+
+/*----- Handy functions ---------------------------------------------------*/
+
+/* --- @group_check@ --- *
+ *
+ * Arguments: @group *g@ = an abstract group
+ * @ge *x@ = a group element
+ *
+ * Returns: Zero on success, nonzero for failure.
+ *
+ * Use: Checks that @x@ is a valid group element. This may take a
+ * while, since it checks that %$x^h \ne 1$%.
+ */
+
+extern int group_check(group */*g*/, ge */*x*/);
+
+/* --- @group_samep@ --- *
+ *
+ * Arguments: @group *g, *h@ = two abstract groups
+ *
+ * Returns: Nonzero if the groups are in fact identical (not just
+ * isomorphic).
+ *
+ * Use: Checks to see whether two groups are actually the same. This
+ * function does the full check: the group operatrion @samep@
+ * just does the group-specific details.
+ */
+
+extern int group_samep(group */*g*/, group */*h*/);
+
+/*----- Textual I/O on group elements -------------------------------------*/
+
+extern int group_readstring(group */*g*/, ge */*d*/,
+ const char */*p*/, char **/*end*/);
+extern int group_writestring(group */*g*/, ge */*d*/,
+ char */*p*/, size_t /*sz*/);
+
+extern int group_readfile(group */*g*/, ge */*d*/, FILE */*fp*/);
+extern int group_writefile(group */*g*/, ge */*x*/, FILE */*fp*/);
+
+extern int group_readdstr(group */*g*/, ge */*d*/,
+ dstr */*dd*/, size_t */*off*/);
+extern int group_writedstr(group */*g*/, ge */*x*/, dstr */*d*/);
+
+/*----- Standard implementations ------------------------------------------*/
+
+/* --- @group_stdidentp@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ge *x@ = group element
+ *
+ * Returns: Nonzero if %$x$% is the group identity.
+ */
+
+extern int group_stdidentp(group */*g*/, ge */*x*/);
+
+/* --- @group_stdcheck@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @grand *gr@ = random number source.
+ *
+ * Returns: Null on success, or a pointer to an error message.
+ */
+
+extern const char *group_stdcheck(group */*g*/, grand */*gr*/);
+
+/* --- @group_stdsqr@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ge *d@ = destination pointer
+ * @ge *x@ = group element
+ *
+ * Returns: ---
+ *
+ * Use: Computes %$d = x^2$% as %$d = x x$%.
+ */
+
+extern void group_stdsqr(group */*g*/, ge */*d*/, ge */*x*/);
+
+/* --- @group_stddiv@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ge *d@ = destination pointer
+ * @ge *x@ = dividend
+ * @ge *y@ = divisor
+ *
+ * Returns: ---
+ *
+ * Use: Computes %$d = x/y$% as %$d = x y^{-1}$%.
+ */
+
+extern void group_stddiv(group */*g*/, ge */*d*/, ge */*x*/, ge */*y*/);
+
+/* --- @group_stdexp@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ge *d@ = destination pointer
+ * @ge *x@ = base element
+ * @mp *n@ = exponent
+ *
+ * Returns: ---
+ *
+ * Use: Computes %$d = x^n$% efficiently.
+ */
+
+extern void group_stdexp(group */*g*/, ge */*d*/, ge */*x*/, mp */*n*/);
+
+/* --- @group_stdmexp@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ge *d@ = destination pointer
+ * @const group_expfactor *f@ = vector of factors
+ * @size_t n@ = number of factors
+ *
+ * Returns: ---
+ *
+ * Use: Computes %$d = g_0^{x_0} g_1^{x_1} \ldots$% efficiently.
+ */
+
+extern void group_stdmexp(group */*g*/, ge */*d*/,
+ const group_expfactor */*f*/, size_t /*n*/);
+
+/* --- @group_stdtoec@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ec *d@ = destination point
+ * @ge *x@ = group element
+ *
+ * Returns: @-1@, indicating failure.
+ *
+ * Use: Fails to convert a group element to an elliptic curve point.
+ */
+
+extern int group_stdtoec(group */*g*/, ec */*d*/, ge */*x*/);
+
+/* --- @group_stdfromec@ --- *
+ *
+ * Arguments: @group *g@ = abstract group
+ * @ge *d@ = destination pointer
+ * @ec *p@ = elliptic curve point
+ *
+ * Returns: Zero for success, @-1@ on failure.
+ *
+ * Use: Converts %$p$% to a group element by converting its %$x$%-
+ * coordinate.
+ */
+
+extern int group_stdfromec(group */*g*/, ge */*d*/, ec */*p*/);
+
+/*----- Prime field subgroups ---------------------------------------------*/
+
+typedef struct gprime_param {
+ mp *p, *q; /* Prime numbers %$p$% and %$q$% */
+ mp *g; /* Generates order-%$q$% subgroup */
+} gprime_param;
+
+/* --- @group_prime@ --- *
+ *
+ * Arguments: @const gprime_param *gp@ = group parameters
+ *
+ * Returns: A pointer to the group.
+ *
+ * Use: Constructs an abstract group interface for a subgroup of a
+ * prime field. Group elements are @mp *@ pointers.
+ */
+
+group *group_prime(const gprime_param */*gp*/);
+
+/*----- Elliptic curve groups ---------------------------------------------*/
+
+/* --- @group_ec@ --- *
+ *
+ * Arguments: @const ec_info *ei@ = elliptic curve parameters
+ *
+ * Returns: A pointer to the group.
+ *
+ * Use: Constructs an abstract group interface for an elliptic curve
+ * group. Group elements are @ec@ structures. The contents of
+ * the @ec_info@ structure becomes the property of the @group@
+ * object; you can (and should) free the structure itself, but
+ * calling @ec_freeinfo@ on it is not allowed.
+ */
+
+group *group_ec(const ec_info */*ei*/);
+
+/*----- General group initialization --------------------------------------*/
+
+/* --- @group_parse@ --- *
+ *
+ * Arguments: @qd_parse *qd@ = quick-and-dirty parser
+ *
+ * Returns: Group pointer, or null for failure.
+ *
+ * Use: Parses a group description and returns the group. This has
+ * the form `TYPE { SPEC }' where TYPE is `prime' or `ec', and
+ * SPEC is the appropriate kind of group specification of the
+ * given type.
+ */
+
+extern group *group_parse(qd_parse */*qd*/);
+
+/* --- @group_fromstring@ --- *
+ *
+ * Arguments: @const char *p@ = pointer to string to read
+ * @group **gg@ = where to put the group pointer
+ *
+ * Returns: Null if OK, or an error string.
+ *
+ * Use: Parses a group spec from a string, and returns the group.
+ */
+
+extern const char *group_fromstring(const char */*p*/, group **/*gg*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
/* -*-c-*-
*
- * $Id: key-binary.c,v 1.4 2004/03/28 01:58:47 mdw Exp $
+ * $Id: key-binary.c,v 1.5 2004/04/01 12:50:09 mdw Exp $
*
* Key binary encoding
*
/*----- Revision history --------------------------------------------------*
*
* $Log: key-binary.c,v $
+ * Revision 1.5 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.4 2004/03/28 01:58:47 mdw
* Generate, store and retreive elliptic curve keys.
*
case KENC_EC: {
size_t xsz, ysz;
+ EC_CREATE(&k->u.e);
+ if (!sz) break;
if (sz < 2) return (-1);
xsz = LOAD16(q + 4);
if (sz < xsz + 4) return (-1);
ysz = LOAD16(q + 6 + xsz);
if (sz < xsz + ysz + 4) return (-1);
- EC_CREATE(&k->u.e);
k->u.e.x = mp_loadb(MP_NEW, q + 6, xsz);
k->u.e.y = mp_loadb(MP_NEW, q + 6 + xsz, ysz);
} break;
case KENC_EC: {
char *p;
- size_t xsz = mp_octets(k->u.e.x), ysz = mp_octets(k->u.e.y);
- size_t sz = xsz + ysz + 4;
+ size_t xsz, ysz;
+ size_t sz;
+ if (EC_ATINF(&k->u.e))
+ sz = 0;
+ else {
+ xsz = mp_octets(k->u.e.x);
+ ysz = mp_octets(k->u.e.y);
+ sz = xsz + ysz + 4;
+ }
DENSURE(d, (sz + 7) & ~3);
p = d->buf + d->len;
STORE16(p, k->e);
STORE16(p + 2, sz);
- STORE16(p + 4, xsz);
- mp_storeb(k->u.e.x, p + 6, xsz);
- STORE16(p + 6 + xsz, ysz);
- mp_storeb(k->u.e.y, p + 8 + xsz, ysz);
+ if (!EC_ATINF(&k->u.e)) {
+ STORE16(p + 4, xsz);
+ mp_storeb(k->u.e.x, p + 6, xsz);
+ STORE16(p + 6 + xsz, ysz);
+ mp_storeb(k->u.e.y, p + 8 + xsz, ysz);
+ }
d->len += sz + 4;
rc = 1;
} break;
/* -*-c-*-
*
- * $Id: keyutil.c,v 1.17 2004/03/28 01:58:47 mdw Exp $
+ * $Id: keyutil.c,v 1.18 2004/04/01 12:50:09 mdw Exp $
*
* Simple key manager program
*
/*----- Revision history --------------------------------------------------*
*
* $Log: keyutil.c,v $
+ * Revision 1.18 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.17 2004/03/28 01:58:47 mdw
* Generate, store and retreive elliptic curve keys.
*
#include "bbs.h"
#include "dh.h"
#include "dsa.h"
+#include "dsarand.h"
#include "ec.h"
#include "ec-keys.h"
#include "ectab.h"
#include "pgen.h"
#include "rsa.h"
+#include "sha-mgf.h"
+#include "sha256-mgf.h"
+#include "sha224-mgf.h"
+#include "sha384-mgf.h"
+#include "sha512-mgf.h"
+#include "tiger-mgf.h"
+#include "rmd128-mgf.h"
+#include "rmd160-mgf.h"
+#include "rmd256-mgf.h"
+#include "rmd320-mgf.h"
+#include "md5-mgf.h"
+#include "dsarand.h"
+
/*----- Handy global state ------------------------------------------------*/
static const char *keyfile = "keyring";
}
}
+/*----- Seeding -----------------------------------------------------------*/
+
+const struct seedalg { const char *p; grand *(*gen)(const void *, size_t); }
+seedtab[] = {
+ { "dsarand", dsarand_create },
+ { "rmd128-mgf", rmd128_mgfrand },
+ { "rmd160-mgf", rmd160_mgfrand },
+ { "rmd256-mgf", rmd256_mgfrand },
+ { "rmd320-mgf", rmd320_mgfrand },
+ { "sha-mgf", sha_mgfrand },
+ { "sha224-mgf", sha224_mgfrand },
+ { "sha256-mgf", sha256_mgfrand },
+ { "sha384-mgf", sha384_mgfrand },
+ { "sha512-mgf", sha512_mgfrand },
+ { "tiger-mgf", tiger_mgfrand },
+ { 0, 0 }
+};
+
+#define SEEDALG_DEFAULT (seedtab + 2)
+
/*----- Key generation ----------------------------------------------------*/
/* --- Key generation parameters --- */
unsigned f; /* Flags for the new key */
unsigned bits, qbits; /* Bit length for the new key */
const char *curve; /* Elliptic curve name/info */
+ grand *r; /* Random number source */
key *p; /* Parameters key-data */
} keyopts;
sz = (k->bits + 7) >> 3;
p = sub_alloc(sz);
m = (1 << (((k->bits - 1) & 7) + 1)) - 1;
- rand_get(RAND_GLOBAL, p, sz);
+ k->r->ops->fill(k->r, p, sz);
*p &= m;
key_binary(&k->k->k, p, sz);
k->k->k.e |= KCAT_SYMM | KF_BURN;
sz = k->bits / 7;
p = sub_alloc(sz);
- rand_get(RAND_GLOBAL, p, sz); /* Too much work done here! */
+ k->r->ops->fill(k->r, p, sz);
for (i = 0; i < sz; i++) {
octet x = p[i] | 0x01;
x = x ^ (x >> 4);
/* --- Generate the RSA parameters --- */
- if (rsa_gen(&rp, k->bits, &rand_global, 0,
+ if (rsa_gen(&rp, k->bits, k->r, 0,
(k->f & f_quiet) ? 0 : pgen_ev, 0))
die(EXIT_FAILURE, "RSA key generation failed");
/* --- Run a test encryption --- */
{
- grand *g = fibrand_create(rand_global.ops->word(&rand_global));
+ grand *g = fibrand_create(k->r->ops->word(k->r));
rsa_pub rpp;
mp *m = mprand_range(MP_NEW, rp.n, g, 0);
mp *c;
sz = (k->qbits + 7) >> 3;
p = sub_alloc(sz);
- rand_get(RAND_GLOBAL, p, sz);
+ k->r->ops->fill(k->r, p, sz);
/* --- Allocate the parameters --- */
/* --- Choose a private key --- */
- x = mprand_range(MP_NEWSEC, q, &rand_global, 0);
+ x = mprand_range(MP_NEWSEC, q, k->r, 0);
mpmont_create(&mm, p);
y = mpmont_exp(&mm, MP_NEW, g, x);
static void alg_dhparam(keyopts *k)
{
static const char *pl[] = { "p", "q", "g", 0 };
+ key_data *kd = &k->k->k;
if (!copyparam(k, pl)) {
dh_param dp;
- key_data *kd = &k->k->k;
int rc;
if (!k->bits)
k->qbits = 256;
rc = dh_limlee(&dp, k->qbits, k->bits,
(k->f & f_subgroup) ? DH_SUBGROUP : 0,
- 0, &rand_global, (k->f & f_quiet) ? 0 : pgen_ev, 0,
+ 0, k->r, (k->f & f_quiet) ? 0 : pgen_ev, 0,
(k->f & f_quiet) ? 0 : pgen_evspin, 0, &nf, &f);
if (!rc) {
dstr d = DSTR_INIT;
dstr_destroy(&d);
}
} else
- rc = dh_gen(&dp, k->qbits, k->bits, 0, &rand_global,
+ rc = dh_gen(&dp, k->qbits, k->bits, 0, k->r,
(k->f & f_quiet) ? 0 : pgen_ev, 0);
if (rc)
mp_drop(dp.q);
mp_drop(dp.p);
mp_drop(dp.g);
- }
+ }
}
static void alg_dh(keyopts *k)
* Since %$g$% has order %$q$%, choose %$x < q$%.
*/
- x = mprand_range(MP_NEWSEC, q, &rand_global, 0);
+ x = mprand_range(MP_NEWSEC, q, k->r, 0);
/* --- Compute the public key %$y = g^x \bmod p$% --- */
/* --- Generate the BBS parameters --- */
- if (bbs_gen(&bp, k->bits, &rand_global, 0,
+ if (bbs_gen(&bp, k->bits, k->r, 0,
(k->f & f_quiet) ? 0 : pgen_ev, 0))
die(EXIT_FAILURE, "Blum-Blum-Shub key generation failed");
if ((e = ec_getinfo(&ei, k->curve)) != 0)
die(EXIT_FAILURE, "error in curve spec: %s", e);
- if (!(k->f & f_quiet) && (e = ec_checkinfo(&ei, &rand_global)) != 0)
+ if (!(k->f & f_quiet) && (e = ec_checkinfo(&ei, k->r)) != 0)
moan("WARNING! curve check failed: %s", e);
ec_freeinfo(&ei);
/* --- Invent a private exponent and compute the public key --- */
- x = mprand_range(MP_NEWSEC, ei.r, &rand_global, 0);
+ x = mprand_range(MP_NEWSEC, ei.r, k->r, 0);
ec_mul(ei.c, &p, &ei.g, x);
/* --- Store everything away --- */
const char *c = 0;
keyalg *alg = algtab;
const char *rtag = 0;
- keyopts k = { 0, 0, DSTR_INIT, 0, 0, 0, 0 };
+ const struct seedalg *sa = SEEDALG_DEFAULT;
+ keyopts k = { 0, 0, DSTR_INIT, 0, 0, 0, 0, 0 };
+ const char *seed = 0;
+ k.r = &rand_global;
/* --- Parse options for the subcommand --- */
{ "tag", OPTF_ARGREQ, 0, 't' },
{ "rand-id", OPTF_ARGREQ, 0, 'R' },
{ "curve", OPTF_ARGREQ, 0, 'C' },
+ { "seedalg", OPTF_ARGREQ, 0, 'A' },
+ { "seed", OPTF_ARGREQ, 0, 's' },
+ { "newseed", OPTF_ARGREQ, 0, 'n' },
{ "lock", 0, 0, 'l' },
{ "quiet", 0, 0, 'q' },
{ "lim-lee", 0, 0, 'L' },
{ "subgroup", 0, 0, 'S' },
{ 0, 0, 0, 0 }
};
- int i = mdwopt(argc, argv, "+a:b:B:p:e:c:t:R:C:lqrLS", opt, 0, 0, 0);
+ int i = mdwopt(argc, argv, "+a:b:B:p:e:c:t:R:C:A:s:n:lqrLS", opt, 0, 0, 0);
if (i < 0)
break;
k.f |= f_retag;
break;
+ /* --- Seeding --- */
+
+ case 'A': {
+ const struct seedalg *ss;
+ if (strcmp(optarg, "list") == 0) {
+ printf("Seed algorithms:\n");
+ for (ss = seedtab; ss->p; ss++)
+ printf(" %s\n", ss->p);
+ exit(0);
+ }
+ if (seed) die(EXIT_FAILURE, "seed already set -- put -A first");
+ sa = 0;
+ for (ss = seedtab; ss->p; ss++) {
+ if (strcmp(optarg, ss->p) == 0)
+ sa = ss;
+ }
+ if (!sa)
+ die(EXIT_FAILURE, "seed algorithm `%s' not known", optarg);
+ } break;
+
+ case 's': {
+ base64_ctx b;
+ dstr d = DSTR_INIT;
+ if (seed) die(EXIT_FAILURE, "seed already set");
+ base64_init(&b);
+ base64_decode(&b, optarg, strlen(optarg), &d);
+ base64_decode(&b, 0, 0, &d);
+ k.r = sa->gen(d.buf, d.len);
+ seed = optarg;
+ dstr_destroy(&d);
+ } break;
+
+ case 'n': {
+ base64_ctx b;
+ dstr d = DSTR_INIT;
+ char *p;
+ unsigned n = strtoul(optarg, &p, 0);
+ if (n == 0 || *p != 0 || n % 8 != 0)
+ die(EXIT_FAILURE, "bad seed length `%s'", optarg);
+ if (seed) die(EXIT_FAILURE, "seed already set");
+ n /= 8;
+ p = xmalloc(n);
+ rand_get(RAND_GLOBAL, p, n);
+ base64_init(&b);
+ base64_encode(&b, p, n, &d);
+ base64_encode(&b, 0, 0, &d);
+ seed = d.buf;
+ k.r = sa->gen(p, n);
+ } break;
+
/* --- Other flags --- */
case 'R':
}
setattr(&f, k.k, argv + optind + 1);
+ if (seed) {
+ key_putattr(&f, k.k, "genseed", seed);
+ key_putattr(&f, k.k, "seedalg", sa->p);
+ }
key_fulltag(k.k, &k.tag);
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: mpbarrett-exp.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Modular exponentiation using Barrett reduction
+ *
+ * (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: mpbarrett-exp.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "mp.h"
+#include "mpbarrett.h"
+#include "mpbarrett-exp.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @mpbarrett_exp@ --- *
+ *
+ * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
+ * @mp *d@ = fake destination
+ * @mp *a@ = base
+ * @mp *e@ = exponent
+ *
+ * Returns: Result, %$a^e \bmod m$%.
+ */
+
+mp *mpbarrett_exp(mpbarrett *mb, mp *d, mp *a, mp *e)
+{
+ mp *x = MP_ONE;
+ mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW;
+
+ MP_COPY(a);
+ MP_SHRINK(e);
+ if (e->f & MP_NEG) {
+ mp *g = MP_NEW;
+ mp_gcd(&g, 0, &a, mb->m, a);
+ assert(MP_EQ(g, MP_ONE));
+ mp_drop(g);
+ }
+ if (!MP_LEN(e))
+ ;
+ else if (MP_LEN(e) < EXP_THRESH)
+ EXP_SIMPLE(x, a, e);
+ else
+ EXP_WINDOW(x, a, e);
+ mp_drop(d);
+ mp_drop(spare);
+ mp_drop(a);
+ return (x);
+}
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+static int vexp(dstr *v)
+{
+ mp *m = *(mp **)v[0].buf;
+ mp *a = *(mp **)v[1].buf;
+ mp *b = *(mp **)v[2].buf;
+ mp *r = *(mp **)v[3].buf;
+ mp *mr;
+ int ok = 1;
+
+ mpbarrett mb;
+ mpbarrett_create(&mb, m);
+
+ mr = mpbarrett_exp(&mb, MP_NEW, a, b);
+
+ if (!MP_EQ(mr, r)) {
+ fputs("\n*** barrett modexp failed", stderr);
+ fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
+ fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
+ fputs("\n e = ", stderr); mp_writefile(b, stderr, 10);
+ fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
+ fputs("\nmr = ", stderr); mp_writefile(mr, stderr, 10);
+ fputc('\n', stderr);
+ ok = 0;
+ }
+
+ mp_drop(m);
+ mp_drop(a);
+ mp_drop(b);
+ mp_drop(r);
+ mp_drop(mr);
+ mpbarrett_destroy(&mb);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return ok;
+}
+
+static test_chunk tests[] = {
+ { "mpbarrett-exp", vexp, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
+ { 0, 0, { 0 } }
+};
+
+int main(int argc, char *argv[])
+{
+ sub_init();
+ test_run(argc, argv, tests, SRCDIR "/tests/mpbarrett");
+ return (0);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: mpbarrett-mexp.c,v 1.1 2001/06/16 12:58:34 mdw Exp $
+ * $Id: mpbarrett-mexp.c,v 1.2 2004/04/01 12:50:09 mdw Exp $
*
* Multiple simultaneous exponentiations
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpbarrett-mexp.c,v $
+ * Revision 1.2 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.1 2001/06/16 12:58:34 mdw
* Added simultaneous exponentiation with Barrett reduction.
*
*
* Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
* @mp *d@ = fake destination
- * @mp_expfactor *f@ = pointer to array of factors
+ * @const mp_expfactor *f@ = pointer to array of factors
* @size_t n@ = number of factors supplied
*
* Returns: If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
* %$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$%
*/
-mp *mpbarrett_mexp(mpbarrett *mb, mp *d, mp_expfactor *f, size_t n)
+mp *mpbarrett_mexp(mpbarrett *mb, mp *d, const mp_expfactor *f, size_t n)
{
+ mp_expfactor *ff = xmalloc(n * sizeof(mp_expfactor));
mp *a = MP_ONE;
mp *spare;
+ mp *g = MP_NEW;
size_t i;
spare = MP_NEW;
for (i = 0; i < n; i++) {
- if (f[i].exp->f & MP_BURN) {
+ if (f[i].exp->f & MP_BURN)
spare = MP_NEWSEC;
- break;
+ if (!(f[i].exp->f & MP_NEG))
+ ff[i].base = MP_COPY(f[i].base);
+ else {
+ ff[i].base = MP_NEW;
+ mp_gcd(&g, 0, &ff[i].base, mb->m, f[i].base);
+ assert(MP_EQ(g, MP_ONE));
}
+ ff[i].exp = f[i].exp;
}
-
- EXP_SIMUL(a, f, n);
+ mp_drop(g);
+ EXP_SIMUL(a, ff, n);
mp_drop(d);
mp_drop(spare);
+ for (i = 0; i < n; i++)
+ mp_drop(ff[i].base);
+ xfree(ff);
return (a);
}
/* -*-c-*-
*
- * $Id: mpbarrett.c,v 1.8 2001/06/16 13:00:20 mdw Exp $
+ * $Id: mpbarrett.c,v 1.9 2004/04/01 12:50:09 mdw Exp $
*
* Barrett modular reduction
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpbarrett.c,v $
+ * Revision 1.9 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.8 2001/06/16 13:00:20 mdw
* Use the generic exponentiation functions.
*
#include "mp.h"
#include "mpbarrett.h"
-#include "mpbarrett-exp.h"
/*----- Main code ---------------------------------------------------------*/
return (d);
}
-/* --- @mpbarrett_exp@ --- *
- *
- * Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
- * @mp *d@ = fake destination
- * @mp *a@ = base
- * @mp *e@ = exponent
- *
- * Returns: Result, %$a^e \bmod m$%.
- */
-
-mp *mpbarrett_exp(mpbarrett *mb, mp *d, mp *a, mp *e)
-{
- mp *x = MP_ONE;
- mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW;
-
- MP_SHRINK(e);
- if (!MP_LEN(e))
- ;
- else if (MP_LEN(e) < EXP_THRESH)
- EXP_SIMPLE(x, a, e);
- else
- EXP_WINDOW(x, a, e);
- mp_drop(d);
- mp_drop(spare);
- return (x);
-}
-
/*----- Test rig ----------------------------------------------------------*/
#ifdef TEST_RIG
return (ok);
}
-static int vexp(dstr *v)
-{
- mp *m = *(mp **)v[0].buf;
- mp *a = *(mp **)v[1].buf;
- mp *b = *(mp **)v[2].buf;
- mp *r = *(mp **)v[3].buf;
- mp *mr;
- int ok = 1;
-
- mpbarrett mb;
- mpbarrett_create(&mb, m);
-
- mr = mpbarrett_exp(&mb, MP_NEW, a, b);
-
- if (!MP_EQ(mr, r)) {
- fputs("\n*** barrett modexp failed", stderr);
- fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
- fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
- fputs("\n e = ", stderr); mp_writefile(b, stderr, 10);
- fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
- fputs("\nmr = ", stderr); mp_writefile(mr, stderr, 10);
- fputc('\n', stderr);
- ok = 0;
- }
-
- mp_drop(m);
- mp_drop(a);
- mp_drop(b);
- mp_drop(r);
- mp_drop(mr);
- mpbarrett_destroy(&mb);
- assert(mparena_count(MPARENA_GLOBAL) == 0);
- return ok;
-}
-
static test_chunk tests[] = {
{ "mpbarrett-reduce", vmod, { &type_mp, &type_mp, &type_mp, 0 } },
- { "mpbarrett-exp", vexp, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
{ 0, 0, { 0 } }
};
/* -*-c-*-
*
- * $Id: mpbarrett.h,v 1.3 2001/06/16 12:58:47 mdw Exp $
+ * $Id: mpbarrett.h,v 1.4 2004/04/01 12:50:09 mdw Exp $
*
* Barrett modular reduction
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpbarrett.h,v $
+ * Revision 1.4 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.3 2001/06/16 12:58:47 mdw
* Added simultaneous exponentiation with Barrett reduction.
*
*
* Arguments: @mpbarrett *mb@ = pointer to Barrett reduction context
* @mp *d@ = fake destination
- * @mp_expfactor *f@ = pointer to array of factors
+ * @const mp_expfactor *f@ = pointer to array of factors
* @size_t n@ = number of factors supplied
*
* Returns: If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
*/
extern mp *mpbarrett_mexp(mpbarrett */*mb*/, mp */*d*/,
- mp_expfactor */*f*/, size_t /*n*/);
+ const mp_expfactor */*f*/, size_t /*n*/);
/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: mpmont-exp.c,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Modular exponentiation with Montgomery reduction
+ *
+ * (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: mpmont-exp.c,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "mp.h"
+#include "mpmont.h"
+#include "mpmont-exp.h"
+
+/*----- Exponentiation ----------------------------------------------------*/
+
+/* --- @mpmont_expr@ --- *
+ *
+ * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
+ * @mp *d@ = fake destination
+ * @mp *a@ = base
+ * @mp *e@ = exponent
+ *
+ * Returns: Result, %$(a R^{-1})^e R \bmod m$%.
+ */
+
+mp *mpmont_expr(mpmont *mm, mp *d, mp *a, mp *e)
+{
+ mp *x = MP_COPY(mm->r);
+ mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW;
+
+ MP_COPY(a);
+ MP_SHRINK(e);
+ if (e->f & MP_NEG) {
+ mp *g = MP_NEW;
+ a = mpmont_reduce(mm, a, a);
+ mp_gcd(&g, 0, &a, mm->m, a);
+ assert(MP_EQ(g, MP_ONE));
+ a = mpmont_mul(mm, a, a, mm->r2);
+ mp_drop(g);
+ }
+ if (MP_LEN(e) == 0)
+ ;
+ else if (MP_LEN(e) < EXP_THRESH)
+ EXP_SIMPLE(x, a, e);
+ else
+ EXP_WINDOW(x, a, e);
+ mp_drop(d);
+ mp_drop(spare);
+ mp_drop(a);
+ return (x);
+}
+
+/* --- @mpmont_exp@ --- *
+ *
+ * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
+ * @mp *d@ = fake destination
+ * @mp *a@ = base
+ * @mp *e@ = exponent
+ *
+ * Returns: Result, %$a^e \bmod m$%.
+ */
+
+mp *mpmont_exp(mpmont *mm, mp *d, mp *a, mp *e)
+{
+ e = MP_COPY(e);
+ d = mpmont_mul(mm, d, a, mm->r2);
+ d = mpmont_expr(mm, d, d, e);
+ d = mpmont_reduce(mm, d, d);
+ MP_DROP(e);
+ return (d);
+}
+
+/*----- Test rig ----------------------------------------------------------*/
+
+#ifdef TEST_RIG
+
+static int texp(dstr *v)
+{
+ mp *m = *(mp **)v[0].buf;
+ mp *a = *(mp **)v[1].buf;
+ mp *b = *(mp **)v[2].buf;
+ mp *r = *(mp **)v[3].buf;
+ mp *mr;
+ int ok = 1;
+
+ mpmont mm;
+ mpmont_create(&mm, m);
+
+ mr = mpmont_exp(&mm, MP_NEW, a, b);
+
+ if (!MP_EQ(mr, r)) {
+ fputs("\n*** montgomery modexp failed", stderr);
+ fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
+ fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
+ fputs("\n e = ", stderr); mp_writefile(b, stderr, 10);
+ fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
+ fputs("\nmr = ", stderr); mp_writefile(mr, stderr, 10);
+ fputc('\n', stderr);
+ ok = 0;
+ }
+
+ MP_DROP(m);
+ MP_DROP(a);
+ MP_DROP(b);
+ MP_DROP(r);
+ MP_DROP(mr);
+ mpmont_destroy(&mm);
+ assert(mparena_count(MPARENA_GLOBAL) == 0);
+ return ok;
+}
+
+
+static test_chunk tests[] = {
+ { "exp", texp, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
+ { 0, 0, { 0 } },
+};
+
+int main(int argc, char *argv[])
+{
+ sub_init();
+ test_run(argc, argv, tests, SRCDIR "/tests/mpmont");
+ return (0);
+}
+
+#endif
+
+/*----- That's all, folks -------------------------------------------------*/
/* -*-c-*-
*
- * $Id: mpmont-mexp.c,v 1.7 2002/01/13 13:49:14 mdw Exp $
+ * $Id: mpmont-mexp.c,v 1.8 2004/04/01 12:50:09 mdw Exp $
*
* Multiple simultaneous exponentiations
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpmont-mexp.c,v $
+ * Revision 1.8 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.7 2002/01/13 13:49:14 mdw
* Make @const@-correct.
*
*
* Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
* @mp *d@ = fake destination
- * @mp_expfactor *f@ = pointer to array of factors
+ * @const mp_expfactor *f@ = pointer to array of factors
* @size_t n@ = number of factors supplied
*
* Returns: If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
* except that the %$g_i$% and result are in Montgomery form.
*/
-mp *mpmont_mexpr(mpmont *mm, mp *d, mp_expfactor *f, size_t n)
+static mp *mexpr(mpmont *mm, mp *d, mp_expfactor *f, size_t n)
{
- mp *a = mp_copy(mm->r);
- mp *spare;
+ mp *a = MP_COPY(mm->r);
+ mp *spare = MP_NEW;
+ mp *g = MP_NEW;
size_t i;
- spare = MP_NEW;
for (i = 0; i < n; i++) {
- if (f[i].exp->f & MP_BURN) {
+ mp *t;
+ if (f[i].exp->f & MP_BURN)
spare = MP_NEWSEC;
- break;
+ if (f[i].exp->f & MP_NEG) {
+ t = mpmont_reduce(mm, f[i].base, f[i].base);
+ mp_gcd(&g, 0, &t, mm->m, t);
+ assert(MP_EQ(g, MP_ONE));
+ f[i].base = mpmont_mul(mm, t, t, mm->r2);
}
}
-
+ mp_drop(g);
EXP_SIMUL(a, f, n);
mp_drop(d);
mp_drop(spare);
+ for (i = 0; i < n; i++)
+ MP_DROP(f[i].base);
+ xfree(f);
return (a);
}
+mp *mpmont_mexpr(mpmont *mm, mp *d, const mp_expfactor *f, size_t n)
+{
+ mp_expfactor *ff = xmalloc(n * sizeof(mp_expfactor));
+ size_t i;
+
+ for (i = 0; i < n; i++) {
+ ff[i].base = MP_COPY(f[i].base);
+ ff[i].exp = f[i].exp;
+ }
+ return (mexpr(mm, d, ff, n));
+}
+
/* --- @mpmont_mexp@ --- *
*
* Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
mp *mpmont_mexp(mpmont *mm, mp *d, const mp_expfactor *f, size_t n)
{
- mp_expfactor *v = xmalloc(sizeof(*v) * n);
+ mp_expfactor *ff = xmalloc(n * sizeof(mp_expfactor));
size_t i;
for (i = 0; i < n; i++) {
- v[i].base = mpmont_mul(mm, MP_NEW, f[i].base, mm->r2);
- v[i].exp = f[i].exp;
+ ff[i].base = mpmont_mul(mm, MP_NEW, f[i].base, mm->r2);
+ ff[i].exp = f[i].exp;
}
- d = mpmont_mexpr(mm, d, v, n);
- for (i = 0; i < n; i++)
- MP_DROP(v[i].base);
- xfree(v);
- d = mpmont_reduce(mm, d, d);
- return (d);
+ d = mexpr(mm, d, ff, n);
+ return (mpmont_reduce(mm, d, d));
}
/*----- Test rig ----------------------------------------------------------*/
/* -*-c-*-
*
- * $Id: mpmont.c,v 1.16 2002/01/13 13:40:31 mdw Exp $
+ * $Id: mpmont.c,v 1.17 2004/04/01 12:50:09 mdw Exp $
*
* Montgomery reduction
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpmont.c,v $
+ * Revision 1.17 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.16 2002/01/13 13:40:31 mdw
* Avoid trashing arguments before we've used them.
*
#include "mp.h"
#include "mpmont.h"
-#include "mpmont-exp.h"
/*----- Tweakables --------------------------------------------------------*/
#endif
-/*----- Exponentiation ----------------------------------------------------*/
-
-/* --- @mpmont_expr@ --- *
- *
- * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
- * @mp *d@ = fake destination
- * @mp *a@ = base
- * @mp *e@ = exponent
- *
- * Returns: Result, %$(a R^{-1})^e R \bmod m$%.
- */
-
-mp *mpmont_expr(mpmont *mm, mp *d, mp *a, mp *e)
-{
- mp *x = MP_COPY(mm->r);
- mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW;
-
- MP_SHRINK(e);
- if (MP_LEN(e) == 0)
- ;
- else if (MP_LEN(e) < EXP_THRESH)
- EXP_SIMPLE(x, a, e);
- else
- EXP_WINDOW(x, a, e);
- mp_drop(d);
- mp_drop(spare);
- return (x);
-}
-
-/* --- @mpmont_exp@ --- *
- *
- * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
- * @mp *d@ = fake destination
- * @mp *a@ = base
- * @mp *e@ = exponent
- *
- * Returns: Result, %$a^e \bmod m$%.
- */
-
-mp *mpmont_exp(mpmont *mm, mp *d, mp *a, mp *e)
-{
- e = MP_COPY(e);
- d = mpmont_mul(mm, d, a, mm->r2);
- d = mpmont_expr(mm, d, d, e);
- d = mpmont_reduce(mm, d, d);
- MP_DROP(e);
- return (d);
-}
-
/*----- Test rig ----------------------------------------------------------*/
#ifdef TEST_RIG
return ok;
}
-static int texp(dstr *v)
-{
- mp *m = *(mp **)v[0].buf;
- mp *a = *(mp **)v[1].buf;
- mp *b = *(mp **)v[2].buf;
- mp *r = *(mp **)v[3].buf;
- mp *mr;
- int ok = 1;
-
- mpmont mm;
- mpmont_create(&mm, m);
-
- mr = mpmont_exp(&mm, MP_NEW, a, b);
-
- if (!MP_EQ(mr, r)) {
- fputs("\n*** montgomery modexp failed", stderr);
- fputs("\n m = ", stderr); mp_writefile(m, stderr, 10);
- fputs("\n a = ", stderr); mp_writefile(a, stderr, 10);
- fputs("\n e = ", stderr); mp_writefile(b, stderr, 10);
- fputs("\n r = ", stderr); mp_writefile(r, stderr, 10);
- fputs("\nmr = ", stderr); mp_writefile(mr, stderr, 10);
- fputc('\n', stderr);
- ok = 0;
- }
-
- MP_DROP(m);
- MP_DROP(a);
- MP_DROP(b);
- MP_DROP(r);
- MP_DROP(mr);
- mpmont_destroy(&mm);
- assert(mparena_count(MPARENA_GLOBAL) == 0);
- return ok;
-}
-
-
static test_chunk tests[] = {
{ "create", tcreate, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
{ "mul", tmul, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
- { "exp", texp, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } },
{ 0, 0, { 0 } },
};
/* -*-c-*-
*
- * $Id: mpmont.h,v 1.6 2002/01/13 13:49:25 mdw Exp $
+ * $Id: mpmont.h,v 1.7 2004/04/01 12:50:09 mdw Exp $
*
* Montgomery reduction
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpmont.h,v $
+ * Revision 1.7 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.6 2002/01/13 13:49:25 mdw
* Make @const@-correct.
*
*
* Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
* @mp *d@ = fake destination
- * @mp_expfactor *f@ = pointer to array of factors
+ * @const mp_expfactor *f@ = pointer to array of factors
* @size_t n@ = number of factors supplied
*
* Returns: If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
*/
extern mp *mpmont_mexpr(mpmont */*mm*/, mp */*d*/,
- mp_expfactor */*f*/, size_t /*n*/);
+ const mp_expfactor */*f*/, size_t /*n*/);
/* --- @mpmont_mexp@ --- *
*
/* -*-c-*-
*
- * $Id: mptext-string.c,v 1.3 2000/08/04 23:23:44 mdw Exp $
+ * $Id: mptext-string.c,v 1.4 2004/04/01 12:50:09 mdw Exp $
*
* Reading and writing large integers on strings
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mptext-string.c,v $
+ * Revision 1.4 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.3 2000/08/04 23:23:44 mdw
* Various <ctype.h> fixes.
*
mp *mp_readstring(mp *m, const char *p, char **end, int radix)
{
mptext_stringctx c;
- c.buf = (char *)p;
+ c.buf = (/*unconst */ char *)p;
c.lim = c.buf + strlen(p);
m = mp_read(m, radix, &mptext_stringops, &c);
if (end)
/* -*-c-*-
*
- * $Id: mpx.c,v 1.17 2004/03/27 00:04:46 mdw Exp $
+ * $Id: mpx.c,v 1.18 2004/04/01 12:50:09 mdw Exp $
*
* Low-level multiprecision arithmetic
*
/*----- Revision history --------------------------------------------------*
*
* $Log: mpx.c,v $
+ * Revision 1.18 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.17 2004/03/27 00:04:46 mdw
* Implement efficient reduction for pleasant-looking primes.
*
d = dvl[-1];
for (b = MPW_BITS / 2; b; b >>= 1) {
- if (d < (MPW_MAX >> b)) {
+ if (d <= (MPW_MAX >> b)) {
d <<= b;
norm += b;
}
--- /dev/null
+#! /bin/sh
+
+set -e
+
+cat <<EOF
+/* -*-c-*-
+ *
+ * Table of standard prime subgroups [generated]
+ */
+
+#include "ptab.h"
+
+#define N(x) (sizeof(x)/sizeof(*x))
+#define MP(x) { x, x + N(x), N(x), 0, MP_CONST, 0 }
+
+/*----- Prime data --------------------------------------------------------*/
+
+EOF
+
+names=""
+while read t n; do
+
+ case $t in
+ group) ;;
+ alias) names="$names $n=$f" continue;;
+ \#* | "") continue;;
+ *) echo >&2 "$0: unknown keyword $t"; exit 1;;
+ esac
+
+ names="$names $n=$n"
+ cat <<EOF
+/* --- Group $n --- */
+
+EOF
+
+ n=`echo $n | sed 's/[^a-zA-Z0-9_][^a-zA-Z0-9_]*/_/g'`
+ read t p
+ if [ $t != p ]; then echo >&2 "$0: wanted p; found $t"; exit 1; fi
+ read t q
+ if [ $t != q ]; then echo >&2 "$0: wanted q; found $t"; exit 1; fi
+ read t g
+ if [ $t != g ]; then echo >&2 "$0: wanted g; found $t"; exit 1; fi
+
+ cat <<EOF
+static mpw p_${n}_p[] = {
+EOF
+ ./mpdump $p
+ cat <<EOF
+};
+
+static mpw p_${n}_q[] = {
+EOF
+ ./mpdump $q
+ cat <<EOF
+};
+
+static mpw p_${n}_g[] = {
+EOF
+ ./mpdump $g
+ cat <<EOF
+};
+
+static pdata p_$n = {
+ MP(p_${n}_p),
+ MP(p_${n}_q),
+ MP(p_${n}_g)
+};
+
+EOF
+
+done
+
+cat <<EOF
+/*----- Main table --------------------------------------------------------*/
+
+const pentry ptab[] = {
+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", &p_$n },
+EOF
+done
+cat <<EOF
+ { 0, 0 }
+};
+
+/*----- That's all, folks -------------------------------------------------*/
+EOF
--- /dev/null
+#! /usr/bin/perl
+
+# Reads ptab.in or similarly-formatted file; writes a calc script to check
+# it.
+
+while (<>) {
+ next if /^\s*(\#[^!]|$)/;
+ @F = split;
+ if ($F[0] eq "group") {
+ $group = $F[1];
+ $_ = <>; @F = split; $F[0] eq "p" or die $F[0]; $p = $F[1];
+ $_ = <>; @F = split; $F[0] eq "q" or die $F[0]; $q = $F[1];
+ $_ = <>; @F = split; $F[0] eq "g" or die $F[0]; $g = $F[1];
+ print <<EOF;
+ print "testing $group...";
+ p = $p;
+ q = $q;
+ g = $g;
+ if (!ptest(p)) print " p not prime";
+ if (!ptest(q)) print " q not prime";
+ if ((p - 1)%q) print " q doesn't divide p - 1";
+ h = (p - 1)/q;
+ if (pmod(g, q, p) != 1) print " g doesn't have order q";
+ if (pmod(g, h, p) == 1) print " g generates overly large group";
+ ff = 2;
+EOF
+ $ll = 0;
+ for (;;) {
+ $_ = <>; @F = split; $F[0] eq "#:factor" or last; $f = $F[1];
+ print <<EOF;
+ f = $f;
+ if (!ptest(f)) print " factor not prime", f;
+ ff *= f;
+EOF
+ $ll = 1;
+ }
+ if ($ll) {
+ print <<EOF;
+ if (ff != p - 1) print " missing factors";
+EOF
+ }
+ }
+}
/* -*-c-*-
*
- * $Id: pfilt.c,v 1.4 2000/10/08 12:14:57 mdw Exp $
+ * $Id: pfilt.c,v 1.5 2004/04/01 12:50:09 mdw Exp $
*
* Finding and testing prime numbers
*
/*----- Revision history --------------------------------------------------*
*
* $Log: pfilt.c,v $
+ * Revision 1.5 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.4 2000/10/08 12:14:57 mdw
* Remove vestiges of @primorial@.
*
int rc = PGEN_TRY;
int i;
size_t sz = MP_LEN(m);
- mpw *v = mpalloc(m->a, sz);
+ mparena *a = m->a ? m->a : MPARENA_GLOBAL;
+ mpw *v = mpalloc(a, sz);
/* --- Fill in the residues --- */
/* --- Done --- */
- mpfree(m->a, v);
+ mpfree(a, v);
return (rc);
}
int rc = PGEN_TRY;
int i;
size_t sz = MP_LEN(m);
- mpw *v = mpalloc(m->a, sz);
+ mparena *a = m->a ? m->a : MPARENA_GLOBAL;
+ mpw *v = mpalloc(a, sz);
/* --- Take a copy of the number --- */
/* --- Done --- */
- mpfree(m->a, v);
+ mpfree(a, v);
return (rc);
}
/* -*-c-*-
*
- * $Id: pfilt.h,v 1.2 2000/08/15 21:42:56 mdw Exp $
+ * $Id: pfilt.h,v 1.3 2004/04/01 12:50:09 mdw Exp $
*
* Finding and testing prime numbers
*
/*----- Revision history --------------------------------------------------*
*
* $Log: pfilt.h,v $
+ * Revision 1.3 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.2 2000/08/15 21:42:56 mdw
* Use the small primes type from `genprimes' output. New function for
* doing trial division the hard way.
# include "mp.h"
#endif
-#ifndef CATACOMB_PTAB_H
+#ifndef CATACOMB_PRIMETAB_H
# include "primetab.h"
#endif
/* -*-c-*-
*
- * $Id: pgen.c,v 1.8 2002/01/13 13:42:53 mdw Exp $
+ * $Id: pgen.c,v 1.9 2004/04/01 12:50:09 mdw Exp $
*
* Prime generation glue
*
/*----- Revision history --------------------------------------------------*
*
* $Log: pgen.c,v $
+ * Revision 1.9 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.8 2002/01/13 13:42:53 mdw
* More efficient Rabin-Miller test: with random witnesses, skip redundant
* Montgomerization. (Being bijective, it can't affect the distribution.)
return (ev.m);
}
+/* --- @pgen_primep@ --- *
+ *
+ * Arguments: @mp *p@ = a number to check
+ * @grand *gr@ = a random number source
+ *
+ * Returns: Nonzero if @p@ is really prime.
+ */
+
+int pgen_primep(mp *p, grand *gr)
+{
+ int i = rabin_iters(mp_bits(p));
+ rabin r;
+ mp *x = MP_NEW;
+
+ if (MP_ISNEG(p)) return (0);
+ 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);
+}
+
/*----- Test rig ----------------------------------------------------------*/
#ifdef TEST_RIG
/* -*-c-*-
*
- * $Id: pgen.h,v 1.7 2000/08/18 19:16:12 mdw Exp $
+ * $Id: pgen.h,v 1.8 2004/04/01 12:50:09 mdw Exp $
*
* Prime generation glue
*
/*----- Revision history --------------------------------------------------*
*
* $Log: pgen.h,v $
+ * Revision 1.8 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
* Revision 1.7 2000/08/18 19:16:12 mdw
* New event handler for showing in detail sub-prime generation.
*
unsigned /*steps*/, pgen_proc */*step*/, void */*sctx*/,
unsigned /*tests*/, pgen_proc */*test*/, void */*tctx*/);
+/* --- @pgen_primep@ --- *
+ *
+ * Arguments: @mp *p@ = a number to check
+ * @grand *gr@ = a random number source
+ *
+ * Returns: Nonzero if @p@ is really prime.
+ */
+
+extern int pgen_primep(mp */*p*/, grand */*gr*/);
+
/*----- That's all, folks -------------------------------------------------*/
#ifdef __cplusplus
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: ptab.h,v 1.1 2004/04/01 12:50:09 mdw Exp $
+ *
+ * Table of standard prime groups
+ *
+ * (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: ptab.h,v $
+ * Revision 1.1 2004/04/01 12:50:09 mdw
+ * Add cyclic group abstraction, with test code. Separate off exponentation
+ * functions for better static linking. Fix a buttload of bugs on the way.
+ * Generally ensure that negative exponents do inversion correctly. Add
+ * table of standard prime-field subgroups. (Binary field subgroups are
+ * currently unimplemented but easy to add if anyone ever finds a good one.)
+ *
+ */
+
+#ifndef CATACOMB_PTAB_H
+#define CATACOMB_PTAB_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "mp.h"
+
+/*----- Data structures ---------------------------------------------------*/
+
+typedef struct pdata {
+ mp p; /* The modulus */
+ mp q; /* The group order */
+ mp g; /* The generator */
+} pdata;
+
+typedef struct pentry {
+ const char *name;
+ pdata *data;
+} pentry;
+
+/*----- Global variables --------------------------------------------------*/
+
+extern const pentry ptab[];
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
--- /dev/null
+# $Id: ptab.in,v 1.1 2004/04/01 12:50:09 mdw Exp $
+#
+# Standard prime groups
+
+#----- Groups from Oakley (RFC2412) -----------------------------------------
+
+group oakley768
+ p 1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919
+ q 776259046150354467565459065629240877815667024717257156601175597451483119974551053629334726938295821221455003840144432114575401859459023171316363806515641491872190410445098144254585345658296587683734775881559921685818610503605288959
+ g 2
+
+group oakley1024
+ p 179769313486231590770839156793787453197860296048756011706444423684197180216158519368947833795864925541502180565485980503646440548199239100050792877003355816639229553136239076508735759914822574862575007425302077447712589550957937778424442426617334727629299387668709205606050270810842907692932019128194467627007
+ q 89884656743115795385419578396893726598930148024378005853222211842098590108079259684473916897932462770751090282742990251823220274099619550025396438501677908319614776568119538254367879957411287431287503712651038723856294775478968889212221213308667363814649693834354602803025135405421453846466009564097233813503
+ g 2
+
+group oakley1536
+ p 2410312426921032588552076022197566074856950548502459942654116941958108831682612228890093858261341614673227141477904012196503648957050582631942730706805009223062734745341073406696246014589361659774041027169249453200378729434170325843778659198143763193776859869524088940195577346119843545301547043747207749969763750084308926339295559968882457872412993810129130294592999947926365264059284647209730384947211681434464714438488520940127459844288859336526896320919633919
+ q 1205156213460516294276038011098783037428475274251229971327058470979054415841306114445046929130670807336613570738952006098251824478525291315971365353402504611531367372670536703348123007294680829887020513584624726600189364717085162921889329599071881596888429934762044470097788673059921772650773521873603874984881875042154463169647779984441228936206496905064565147296499973963182632029642323604865192473605840717232357219244260470063729922144429668263448160459816959
+ g 2
+
+#----- Lim-Lee groups generated by hand -------------------------------------
+#
+# I generated each of these using the `key' command, as follows:
+#
+# ./key add -adh-param -LS -b$b -B$B -Armd160-mgf -n160 -tg$b dhp
+#
+# The seeds are printed so that they can be verified, for example by saying
+#
+# for i in \
+# 512:128:V5DGdsaGc94mN9URH3I77nsNLIg= \
+# 1024:160:XRJk5bOOi3HLn4KjIzsR1lHYARk= \
+# 1536:192:xdavXXnfLHfzffaZUOpN4aJ4yUI= \
+# 2048:256:XaRFBJQ81wVVzq8qoBeIP3vqyuE; do
+# set -- `echo $i | tr : " "`
+# b=$1 B=$2 seed=$3
+# key add -adh-param -LS -b$b -B$B -Armd160-mgf -s$seed -tg$b dhp
+# done
+
+# --- catacomb-g512 ---
+#
+# seed = V5DGdsaGc94mN9URH3I77nsNLIg=
+# fingerprint = f25bc8c6-617a09a1-754d2eaa-0522871a-760e610d
+
+group catacomb-g512
+ p 5118856347920954160378863232830631325889644197299799167911144300201784122094780184626197180489795089420405735367823610560615880134994605406941434667432423
+ q 305195864527308403703758000941688611143
+ g 3697266067523710036467093123816011201983155908266335624854330873142263159303630246637735938648226082958343061457343689503209448195311459584298640741102705
+#:factor 305195864527308403703758000941688611143
+#:factor 183466370120479092451878102554970138601
+#:factor 186700538408825324669801286998471418829
+#:factor 244828664101528731840410424550149964513
+
+# --- catacomb-g1024 ---
+#
+# seed = XRJk5bOOi3HLn4KjIzsR1lHYARk=
+# fingerprint = 0dc1bdb6-538314cf-d7b87bff-b8bd7200-90605815
+
+group catacomb-g1024
+ p 78755935681003885419264728861345379637028906441022322413456415764939641783336851042588146268355482691146885408309655771050383114167622301018690564876497648546617048801723493306649269757534973720900588265521617407576647372939590696584279495709722074618640770310739210062851628263901598357589613375395797359959
+ q 1419054345488286019529284378621915381299017390711
+ g 58825919769364968331424947271593333019269386260261303735666667702229466489655563394667916806132064369818023847262687164133692606997345477915636979837490941743124378900249509898575176837060134280677725934918181696837395720729413369903126189903716658234076491410436114815588467963968699191062139234426829304874
+#:factor 1419054345488286019529284378621915381299017390711
+#:factor 808918575263122392359194885025533099598345595673
+#:factor 837447658428460194172640743162052526375779460247
+#:factor 1176506922641176986055037627440710388833031551637
+#:factor 1440893326598068230528326457570152914912523167631
+#:factor 24163813452665907844419927325562548942785722977403812563263504533577
+
+# --- catacomb-g1536 ---
+#
+# seed = xdavXXnfLHfzffaZUOpN4aJ4yUI=
+# fingerprint = 7c8395e0-30f0ba39-3fcf305f-8405e925-8f55ec8b
+
+group catacomb-g1536
+ p 383618801425631512639679010233494027298448169109547600059502705907371439271932758179471011100378234860612705323707696845632535293731854087134152787350527588865123205717061331587664013265527474950838320241277990361233998673285302400493519384019311459331115126650720227947194082175343397026404881513921942694130897583244878286078416071034663404900503607239216267234716848423157867865924627528541625976189517370222928416617890890711958913977705458641898019793137567
+ q 3275641213331577544956079882485798541293343355151947117267
+ g 75567102998973006819236434748343962916387173892100142148230797775334350230786915953451381035927889555810159538209392484334843275305619145381031766085998906461896047057459109982258943279745411432423432727058945662406099102428838108340486817276659663329224706868534013896950343046900915527691132454858703939255112356712430338179445362271271130771412736483434334076018336540519431066737658374108259585338553305483833520027492221617458503836640494191113432119200395
+#:factor 3275641213331577544956079882485798541293343355151947117267
+#:factor 5923907098009644577374814618329026695556706671262137178497
+#:factor 3844881227882828127330776567190990999774232184254041918229
+#:factor 5430347777844125846459785226421548800285951243451322854507
+#:factor 4579813319768104593696877908030851637284891613924119865649
+#:factor 5010386120883339072065025678004772865252492789176775057011
+#:factor 4450957002678134171264816926461631570727858852456021603561
+#:factor 4635348374228446290293078229669107374406520693763884412441
+
+# --- catacomb-g2048 ---
+#
+# seed = XaRFBJQ81wVVzq8qoBeIP3vqyuE=
+# fingerprint = 83d4eccd-7ee749e0-08aa836d-f2db8476-8edd2936
+
+group catacomb-g2048
+ p 6566549572652120431689861127531558421330340455043793984482564709696337228812001308904952649568065583568587879772909497598656422677974007527961282502097075930845830281718567861929276323615100590300159375177078322480856459891862339310954032953912791719082743072006782706539621638332710884731210307201371592118143799018971643225573537115357866462994309593328388179007477192291502661723448576542875507556533074094050684884411874123801280281707321329428218433930422183253523330090184052067733393547530287435821953994285151790223917195811689888131012632526833728463264350844033754405413758744532430886373149124555575950119
+ q 85219291683194343311648709576647238772792814954178375461491931659867071278179
+ g 2712141723171795581488249576260576193761110477063764293591032009827968751431395523061136221268304777960574263879250629365586812866824369569874730255716068295729152411167722797556896531602052328323962128667798500023092663406604756526331182771005434060123484959167353575934888103970356821325588887453135264523934107731497158111619089910229366930643553779443872242586492810355327274464057143529561902987269668822923702637343147141226655673562552876847682549615031082304437898719857828585147298892788370396664494775578429846195466392714456810816881284814946617797677007757332068752054463579186298698714625622710684652210
+#:factor 85219291683194343311648709576647238772792814954178375461491931659867071278179
+#:factor 103405058914440135561022141060017648606740273177776645185302688502492969483241
+#:factor 113963865770422801273732150069066629221825734790590120001120039124679845832963
+#:factor 80265376580192980414321385617558188839311132409791112548764982795679972612671
+#:factor 85373177067927972620374408916798159155602932702094285590546968078635293574289
+#:factor 88343485680671092863800489383682034593775966659103995594051594606625920956031
+#:factor 66724081118319248356666248758604279507549823671133489207537165813489410099011
+#:factor 80938197596113813192367778019037224015451333736452277049313111439333946857553
+
+#----- That's all, folks ----------------------------------------------------