From: mdw Date: Thu, 1 Apr 2004 12:50:09 +0000 (+0000) Subject: Add cyclic group abstraction, with test code. Separate off exponentation X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/commitdiff_plain/34e4f738bcba58e6d8c4cabbb0b3232a65b42a9d 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.) --- diff --git a/Makefile.m4 b/Makefile.m4 index c6885f1..12c4dd0 100644 --- a/Makefile.m4 +++ b/Makefile.m4 @@ -1,6 +1,6 @@ ## -*-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 ## @@ -29,6 +29,13 @@ ##----- 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. ## @@ -333,7 +340,8 @@ gen_tables 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 @@ -344,6 +352,10 @@ ectab.c: ectab.in ec-gentab.sh mpdump $(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') \ @@ -375,6 +387,7 @@ pkginclude_HEADERS = \ 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') \ @@ -387,20 +400,22 @@ define(`MP_SOURCES', 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 \ @@ -409,7 +424,7 @@ define(`PGEN_SOURCES', 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 \ @@ -447,8 +462,8 @@ mars.lo: mars-tab.h 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 --- @@ -517,7 +532,8 @@ man_MANS = key.1 hashsum.1 keyring.5 pixie.1 ## --- 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 \ @@ -546,7 +562,7 @@ define(`CTESTRIG', $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) @@ -570,8 +586,10 @@ CTESTRIG(mp-sqrt) CTESTRIG(mptext) CTESTRIG(mpint) CTESTRIG(mpbarrett) +CTESTRIG(mpbarrett-exp) CTESTRIG(mpbarrett-mexp) CTESTRIG(mpmont) +CTESTRIG(mpmont-exp) CTESTRIG(mpmont-mexp) CTESTRIG(mpreduce) CTESTRIG(mpcrt) @@ -586,6 +604,8 @@ CTESTRIG(ec-prime) CTESTRIG(ec-bin) CTESTRIG(ec-test) CTESTRIG(ec-info) +CTESTRIG(dh-param) +CTESTRIG(group-test) CTESTRIG(pgen) CTESTRIG(dsa-gen) CTESTRIG(dsa-sign) diff --git a/buf.c b/buf.c index 5e0a069..b4cbb71 100644 --- a/buf.c +++ b/buf.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -56,6 +63,7 @@ #include #include "mp.h" +#include "ec.h" #include "buf.h" /*----- Main code ---------------------------------------------------------*/ @@ -280,11 +288,13 @@ int buf_putu32(buf *b, uint32 w) 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); } @@ -306,6 +316,7 @@ int buf_putmp(buf *b, mp *m) { 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); @@ -313,4 +324,45 @@ int buf_putmp(buf *b, mp *m) 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 -------------------------------------------------*/ diff --git a/buf.h b/buf.h index 0131681..6307c26 100644 --- a/buf.h +++ b/buf.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -58,6 +65,10 @@ # include "mp.h" #endif +#ifndef CATACOMB_EC_H +# include "ec.h" +#endif + /*----- Data structures ---------------------------------------------------*/ /* --- Buffers --- * @@ -258,6 +269,31 @@ extern mp *buf_getmp(buf */*b*/); 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 diff --git a/dh-param.c b/dh-param.c new file mode 100644 index 0000000..66bee09 --- /dev/null +++ b/dh-param.c @@ -0,0 +1,124 @@ +/* -*-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 -------------------------------------------------*/ diff --git a/dh.h b/dh.h index 90fdaa3..56dbf0a 100644 --- a/dh.h +++ b/dh.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -57,6 +64,10 @@ /*----- Header files ------------------------------------------------------*/ +#ifndef CATACOMB_GROUP_H +# include "group.h" +#endif + #ifndef CATACOMB_GRAND_H # include "grand.h" #endif @@ -73,12 +84,13 @@ # 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 */ @@ -198,6 +210,20 @@ extern int dh_limlee(dh_param */*dp*/, unsigned /*ql*/, unsigned /*pl*/, 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 diff --git a/ec-bin.c b/ec-bin.c index 0efb72f..36c5098 100644 --- a/ec-bin.c +++ b/ec-bin.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -322,6 +329,7 @@ static int eccheck(ec_curve *c, const ec *p) 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); @@ -393,12 +401,12 @@ ec_curve *ec_binproj(field *f, mp *a, mp *b) } 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 }; diff --git a/ec-exp.c b/ec-exp.c new file mode 100644 index 0000000..26953e7 --- /dev/null +++ b/ec-exp.c @@ -0,0 +1,155 @@ +/* -*-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 -------------------------------------------------*/ diff --git a/ec-gentab.sh b/ec-gentab.sh index ea63094..40fd853 100755 --- a/ec-gentab.sh +++ b/ec-gentab.sh @@ -11,6 +11,7 @@ cat <&2 "$0: wanted b; found $t"; exit 1; fi cat <&2 "$0: wanted gy; found $t"; exit 1; fi cat <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 @@ -176,7 +219,8 @@ fail: * 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 `/' @@ -192,14 +236,22 @@ int ec_infoparse(qd_parse *qd, ec_info *ei) 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: @@ -210,64 +262,6 @@ 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 @@ -282,19 +276,11 @@ static void getinfo(ec_info *ei, const ecdata *ed) 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"); @@ -302,6 +288,22 @@ found: 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 @@ -330,28 +332,6 @@ void ec_freeinfo(ec_info *ei) * 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)); @@ -368,7 +348,7 @@ static const char *primecheck(const ec_info *ei, grand *gr) /* --- 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)$% --- */ @@ -399,7 +379,7 @@ static const char *primecheck(const ec_info *ei, grand *gr) /* --- 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$% --- */ @@ -486,7 +466,7 @@ static const char *bincheck(const ec_info *ei, grand *gr) /* --- 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$% --- */ diff --git a/ec-keys.h b/ec-keys.h index 847bc6a..c7561e7 100644 --- a/ec-keys.h +++ b/ec-keys.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -72,7 +79,30 @@ typedef struct ec_priv { 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 -------------------------------------------------*/ diff --git a/ec-prime.c b/ec-prime.c index ce81ba1..b2652b2 100644 --- a/ec-prime.c +++ b/ec-prime.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -349,10 +356,12 @@ static ec *ecprojadd(ec_curve *c, ec *d, const ec *a, const ec *b) 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); @@ -422,17 +431,17 @@ extern ec_curve *ec_primeproj(field *f, mp *a, mp *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 }; diff --git a/ec-test.c b/ec-test.c index 2f81015..1307e32 100644 --- a/ec-test.c +++ b/ec-test.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -110,8 +117,14 @@ static int ecCHECK(ec_curve *cc, const ec *p) 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 }; @@ -120,6 +133,8 @@ static ec_curve *ec_cutout(ec_curve *real, const char *name) 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; diff --git a/ec.c b/ec.c index d4dfafb..13e9b84 100644 --- a/ec.c +++ b/ec.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -63,10 +70,25 @@ /*----- 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 @@ -135,6 +157,20 @@ int ec_eq(const ec *p, const ec *q) { return (EC_EQ(p, q)); } /*----- 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 @@ -432,48 +468,4 @@ ec *ec_rand(ec_curve *c, ec *d, grand *r) 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 -------------------------------------------------*/ diff --git a/ec.h b/ec.h index 79e3654..f556193 100644 --- a/ec.h +++ b/ec.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -126,6 +133,7 @@ typedef struct ec_mulfactor { 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*/); @@ -137,6 +145,7 @@ typedef struct ec_ops { 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)) @@ -278,6 +287,19 @@ extern int ec_eq(const ec *p, const ec *q); /*----- 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 @@ -410,6 +432,17 @@ extern ec *ec_immul(ec_curve */*c*/, ec */*d*/, /*----- 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 @@ -574,6 +607,17 @@ extern int ec_infoparse(qd_parse */*qd*/, ec_info */*ei*/); 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 diff --git a/ectab.h b/ectab.h index d8d4302..925924d 100644 --- a/ectab.h +++ b/ectab.h @@ -1,8 +1,8 @@ /* -*-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 */ @@ -30,6 +30,13 @@ /*----- 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. * @@ -50,13 +57,11 @@ 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 { @@ -67,7 +72,7 @@ enum { typedef struct ecentry { const char *name; - const ecdata *data; + ecdata *data; } ecentry; /*----- Global variables --------------------------------------------------*/ diff --git a/f-binpoly.c b/f-binpoly.c index bd4d8b0..aeec0cf 100644 --- a/f-binpoly.c +++ b/f-binpoly.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -132,7 +139,7 @@ static mp *fquadsolve(field *ff, mp *d, mp *x) 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, diff --git a/f-niceprime.c b/f-niceprime.c index b4b4091..4ffc028 100644 --- a/f-niceprime.c +++ b/f-niceprime.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -183,7 +190,7 @@ static mp *fhlv(field *ff, mp *d, mp *x) 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, diff --git a/f-prime.c b/f-prime.c index a82f3a0..473ba4c 100644 --- a/f-prime.c +++ b/f-prime.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -225,7 +232,7 @@ static mp *fhlv(field *ff, mp *d, mp *x) 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, diff --git a/field.c b/field.c index c310b93..f0968dd 100644 --- a/field.c +++ b/field.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -67,4 +74,35 @@ mp *field_id(field *f, mp *d, mp *x) 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 -------------------------------------------------*/ diff --git a/field.h b/field.h index 7af9b4f..bf0428a 100644 --- a/field.h +++ b/field.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -109,6 +116,7 @@ typedef struct field_ops { 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*/); @@ -141,6 +149,7 @@ typedef struct field_ops { #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)) @@ -178,6 +187,31 @@ typedef struct field_ops { 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@ --- * diff --git a/g-ec.c b/g-ec.c new file mode 100644 index 0000000..1f214f7 --- /dev/null +++ b/g-ec.c @@ -0,0 +1,222 @@ +/* -*-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 + +#include + +#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 -------------------------------------------------*/ diff --git a/g-prime.c b/g-prime.c new file mode 100644 index 0000000..03843be --- /dev/null +++ b/g-prime.c @@ -0,0 +1,183 @@ +/* -*-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 + +#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 -------------------------------------------------*/ diff --git a/genprimes.c b/genprimes.c index 2961621..56e388e 100644 --- a/genprimes.c +++ b/genprimes.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -71,13 +78,14 @@ int main(int argc, char *argv[]) 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) { @@ -101,6 +109,9 @@ int main(int argc, char *argv[]) case 't': type = optarg; break; + case 's': + sym = optarg; + break; default: pquis(stderr, "Usage: $ [-n nprimes] [-m maxprime] [-t type]\n"); exit(EXIT_FAILURE); @@ -131,15 +142,18 @@ int main(int argc, char *argv[]) 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\ @@ -157,7 +171,7 @@ extern smallprime %s[];\n\ \n\ #endif\n\ ", - d.buf, d.buf, + sym, sym, (unsigned long)DA_LEN(&p), DA_LAST(&p), type, name); diff --git a/group-dstr.c b/group-dstr.c new file mode 100644 index 0000000..7fe67a0 --- /dev/null +++ b/group-dstr.c @@ -0,0 +1,97 @@ +/* -*-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 -------------------------------------------------*/ diff --git a/group-exp.c b/group-exp.c new file mode 100644 index 0000000..72bd5a0 --- /dev/null +++ b/group-exp.c @@ -0,0 +1,121 @@ +/* -*-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 -------------------------------------------------*/ diff --git a/group-exp.h b/group-exp.h new file mode 100644 index 0000000..a736d29 --- /dev/null +++ b/group-exp.h @@ -0,0 +1,80 @@ +/* -*-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 diff --git a/group-file.c b/group-file.c new file mode 100644 index 0000000..64e0e4b --- /dev/null +++ b/group-file.c @@ -0,0 +1,76 @@ +/* -*-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 -------------------------------------------------*/ diff --git a/group-parse.c b/group-parse.c new file mode 100644 index 0000000..47998c6 --- /dev/null +++ b/group-parse.c @@ -0,0 +1,107 @@ +/* -*-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 -------------------------------------------------*/ diff --git a/group-stdops.c b/group-stdops.c new file mode 100644 index 0000000..2e3e6d4 --- /dev/null +++ b/group-stdops.c @@ -0,0 +1,183 @@ +/* -*-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 -------------------------------------------------*/ diff --git a/group-string.c b/group-string.c new file mode 100644 index 0000000..598e973 --- /dev/null +++ b/group-string.c @@ -0,0 +1,96 @@ +/* -*-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 -------------------------------------------------*/ diff --git a/group-test.c b/group-test.c new file mode 100644 index 0000000..5fdf147 --- /dev/null +++ b/group-test.c @@ -0,0 +1,506 @@ +/* -*-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 + +#include + +#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 -------------------------------------------------*/ diff --git a/group.h b/group.h new file mode 100644 index 0000000..383bc82 --- /dev/null +++ b/group.h @@ -0,0 +1,396 @@ +/* -*-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 + +#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 diff --git a/key-binary.c b/key-binary.c index c05adee..82a1ecb 100644 --- a/key-binary.c +++ b/key-binary.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -122,12 +129,13 @@ int key_decode(const void *p, size_t sz, key_data *k) 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; @@ -256,17 +264,26 @@ int key_encode(key_data *k, dstr *d, const key_filter *kf) 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; diff --git a/keyutil.c b/keyutil.c index 0911021..1619707 100644 --- a/keyutil.c +++ b/keyutil.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -111,6 +118,7 @@ #include "bbs.h" #include "dh.h" #include "dsa.h" +#include "dsarand.h" #include "ec.h" #include "ec-keys.h" #include "ectab.h" @@ -124,6 +132,19 @@ #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"; @@ -199,6 +220,26 @@ static void setattr(key_file *f, key *k, char *v[]) } } +/*----- 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 --- */ @@ -210,6 +251,7 @@ typedef struct keyopts { 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; @@ -388,7 +430,7 @@ static void alg_binary(keyopts *k) 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; @@ -412,7 +454,7 @@ static void alg_des(keyopts *k) 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); @@ -441,14 +483,14 @@ static void alg_rsa(keyopts *k) /* --- 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; @@ -508,7 +550,7 @@ static void alg_dsaparam(keyopts *k) 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 --- */ @@ -559,7 +601,7 @@ static void alg_dsa(keyopts *k) /* --- 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); @@ -578,9 +620,9 @@ static void alg_dsa(keyopts *k) 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) @@ -595,7 +637,7 @@ static void alg_dhparam(keyopts *k) 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; @@ -610,7 +652,7 @@ static void alg_dhparam(keyopts *k) 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) @@ -623,7 +665,7 @@ static void alg_dhparam(keyopts *k) mp_drop(dp.q); mp_drop(dp.p); mp_drop(dp.g); - } + } } static void alg_dh(keyopts *k) @@ -645,7 +687,7 @@ 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$% --- */ @@ -679,7 +721,7 @@ static void alg_bbs(keyopts *k) /* --- 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"); @@ -727,7 +769,7 @@ static void alg_ecparam(keyopts *k) 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); @@ -761,7 +803,7 @@ static void alg_ec(keyopts *k) /* --- 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 --- */ @@ -811,7 +853,10 @@ static int cmd_add(int argc, char *argv[]) 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 --- */ @@ -826,13 +871,16 @@ static int cmd_add(int argc, char *argv[]) { "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; @@ -934,6 +982,56 @@ static int cmd_add(int argc, char *argv[]) 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': @@ -1016,6 +1114,10 @@ static int cmd_add(int argc, char *argv[]) } 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); diff --git a/mpbarrett-exp.c b/mpbarrett-exp.c new file mode 100644 index 0000000..87d8af2 --- /dev/null +++ b/mpbarrett-exp.c @@ -0,0 +1,138 @@ +/* -*-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 -------------------------------------------------*/ diff --git a/mpbarrett-mexp.c b/mpbarrett-mexp.c index e97c064..68917aa 100644 --- a/mpbarrett-mexp.c +++ b/mpbarrett-mexp.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -49,7 +56,7 @@ * * 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 @@ -59,23 +66,34 @@ * %$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); } diff --git a/mpbarrett.c b/mpbarrett.c index b38aa91..934097d 100644 --- a/mpbarrett.c +++ b/mpbarrett.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -64,7 +71,6 @@ #include "mp.h" #include "mpbarrett.h" -#include "mpbarrett-exp.h" /*----- Main code ---------------------------------------------------------*/ @@ -193,33 +199,6 @@ mp *mpbarrett_reduce(mpbarrett *mb, mp *d, mp *m) 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 @@ -254,44 +233,8 @@ static int vmod(dstr *v) 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 } } }; diff --git a/mpbarrett.h b/mpbarrett.h index eaec41d..3168205 100644 --- a/mpbarrett.h +++ b/mpbarrett.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -136,7 +143,7 @@ extern mp *mpbarrett_exp(mpbarrett */*mb*/, mp */*d*/, mp */*a*/, mp */*e*/); * * 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 @@ -147,7 +154,7 @@ extern mp *mpbarrett_exp(mpbarrett */*mb*/, mp */*d*/, mp */*a*/, mp */*e*/); */ 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 -------------------------------------------------*/ diff --git a/mpmont-exp.c b/mpmont-exp.c new file mode 100644 index 0000000..f67a8ec --- /dev/null +++ b/mpmont-exp.c @@ -0,0 +1,161 @@ +/* -*-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 -------------------------------------------------*/ diff --git a/mpmont-mexp.c b/mpmont-mexp.c index a3f3f4b..7589990 100644 --- a/mpmont-mexp.c +++ b/mpmont-mexp.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -70,7 +77,7 @@ * * 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 @@ -82,26 +89,46 @@ * 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 @@ -116,19 +143,15 @@ mp *mpmont_mexpr(mpmont *mm, mp *d, mp_expfactor *f, size_t n) 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 ----------------------------------------------------------*/ diff --git a/mpmont.c b/mpmont.c index c644801..926fde8 100644 --- a/mpmont.c +++ b/mpmont.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -94,7 +101,6 @@ #include "mp.h" #include "mpmont.h" -#include "mpmont-exp.h" /*----- Tweakables --------------------------------------------------------*/ @@ -370,55 +376,6 @@ mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) #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 @@ -528,46 +485,9 @@ static int tmul(dstr *v) 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 } }, }; diff --git a/mpmont.h b/mpmont.h index 58b051b..913f6f5 100644 --- a/mpmont.h +++ b/mpmont.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -189,7 +196,7 @@ extern mp *mpmont_exp(mpmont */*mm*/, mp */*d*/, mp */*a*/, mp */*e*/); * * 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 @@ -203,7 +210,7 @@ extern mp *mpmont_exp(mpmont */*mm*/, mp */*d*/, mp */*a*/, mp */*e*/); */ extern mp *mpmont_mexpr(mpmont */*mm*/, mp */*d*/, - mp_expfactor */*f*/, size_t /*n*/); + const mp_expfactor */*f*/, size_t /*n*/); /* --- @mpmont_mexp@ --- * * diff --git a/mptext-string.c b/mptext-string.c index ea734f8..bdd6230 100644 --- a/mptext-string.c +++ b/mptext-string.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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 fixes. * @@ -88,7 +95,7 @@ const mptext_ops mptext_stringops = { get, unget, put }; 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) diff --git a/mpx.c b/mpx.c index f1cbbd9..1591f98 100644 --- a/mpx.c +++ b/mpx.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -1179,7 +1186,7 @@ void mpx_udiv(mpw *qv, mpw *qvl, mpw *rv, mpw *rvl, 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; } diff --git a/p-gentab.sh b/p-gentab.sh new file mode 100755 index 0000000..210073b --- /dev/null +++ b/p-gentab.sh @@ -0,0 +1,90 @@ +#! /bin/sh + +set -e + +cat <&2 "$0: unknown keyword $t"; exit 1;; + esac + + names="$names $n=$n" + cat <&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 <) { + 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 <; @F = split; $F[0] eq "#:factor" or last; $f = $F[1]; + print <a, sz); + mparena *a = m->a ? m->a : MPARENA_GLOBAL; + mpw *v = mpalloc(a, sz); /* --- Fill in the residues --- */ @@ -133,7 +141,7 @@ int pfilt_smallfactor(mp *m) /* --- Done --- */ - mpfree(m->a, v); + mpfree(a, v); return (rc); } @@ -155,7 +163,8 @@ int pfilt_create(pfilt *p, mp *m) 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 --- */ @@ -181,7 +190,7 @@ int pfilt_create(pfilt *p, mp *m) /* --- Done --- */ - mpfree(m->a, v); + mpfree(a, v); return (rc); } diff --git a/pfilt.h b/pfilt.h index 9076701..963b765 100644 --- a/pfilt.h +++ b/pfilt.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. @@ -61,7 +68,7 @@ # include "mp.h" #endif -#ifndef CATACOMB_PTAB_H +#ifndef CATACOMB_PRIMETAB_H # include "primetab.h" #endif diff --git a/pgen.c b/pgen.c index dca61d9..9cc4334 100644 --- a/pgen.c +++ b/pgen.c @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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.) @@ -334,6 +341,37 @@ mp *pgen(const char *name, mp *d, mp *m, pgen_proc *event, void *ectx, 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 diff --git a/pgen.h b/pgen.h index 459f360..1834f03 100644 --- a/pgen.h +++ b/pgen.h @@ -1,6 +1,6 @@ /* -*-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 * @@ -30,6 +30,13 @@ /*----- 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. * @@ -293,6 +300,16 @@ extern mp *pgen(const char */*name*/, mp */*d*/, mp */*m*/, 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 diff --git a/ptab.h b/ptab.h new file mode 100644 index 0000000..271eb57 --- /dev/null +++ b/ptab.h @@ -0,0 +1,76 @@ +/* -*-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 diff --git a/ptab.in b/ptab.in new file mode 100644 index 0000000..7f99f64 --- /dev/null +++ b/ptab.in @@ -0,0 +1,106 @@ +# $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 ----------------------------------------------------