From 0f3faccdf5f2f0cfa40bd9bec495c4930052a51f Mon Sep 17 00:00:00 2001 From: mdw Date: Sun, 4 Apr 2004 19:04:11 +0000 Subject: [PATCH] Raw I/O of elliptic curve points and group elements. --- Makefile.m4 | 9 ++++-- ec-raw.c | 104 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ec-raw.h | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++++ g-ec.c | 23 +++++++++++-- g-prime.c | 22 +++++++++++-- group-file.c | 7 ++-- group-test.c | 74 +++++++++++++++++++++++++++++++++++++++++- group.h | 11 +++++-- tests/group | 38 +++++++++++++++++++++- 9 files changed, 367 insertions(+), 14 deletions(-) create mode 100644 ec-raw.c create mode 100644 ec-raw.h diff --git a/Makefile.m4 b/Makefile.m4 index e15b5eb..bd832ab 100644 --- a/Makefile.m4 +++ b/Makefile.m4 @@ -1,6 +1,6 @@ ## -*-m4-*- ## -## $Id: Makefile.m4,v 1.77 2004/04/01 21:28:41 mdw Exp $ +## $Id: Makefile.m4,v 1.78 2004/04/04 19:04:11 mdw Exp $ ## ## Makefile for Catacomb ## @@ -29,6 +29,9 @@ ##----- Revision history ---------------------------------------------------- ## ## $Log: Makefile.m4,v $ +## Revision 1.78 2004/04/04 19:04:11 mdw +## Raw I/O of elliptic curve points and group elements. +## ## Revision 1.77 2004/04/01 21:28:41 mdw ## Normal basis support (translates to poly basis internally). Rewrite ## EC and prime group table generators in awk, so that they can reuse data @@ -394,7 +397,7 @@ pkginclude_HEADERS = \ oaep.h pkcs1.h pss.h tlsprf.h sslprf.h \ gfshare.h share.h \ rho.h \ - field.h ec.h ec-exp.h ec-test.h ectab.h ec-keys.h \ + field.h ec.h ec-exp.h ec-test.h ectab.h ec-keys.h ec-raw.h \ ptab.h group.h \ allwithsuffix(`ciphers', `cipher_modes', `.h') \ allwithsuffix(`hashes', `hash_modes', `.h') \ @@ -423,7 +426,7 @@ define(`GF_SOURCES', define(`EC_SOURCES', `field.c field-parse.c f-prime.c f-niceprime.c f-binpoly.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') + ec-fetch.c ec-raw.c g-ec.c') define(`PGEN_SOURCES', `pfilt.c rabin.c \ diff --git a/ec-raw.c b/ec-raw.c new file mode 100644 index 0000000..ad9b583 --- /dev/null +++ b/ec-raw.c @@ -0,0 +1,104 @@ +/* -*-c-*- + * + * $Id: ec-raw.c,v 1.1 2004/04/04 19:04:11 mdw Exp $ + * + * Raw formatting of elliptic curve points + * + * (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-raw.c,v $ + * Revision 1.1 2004/04/04 19:04:11 mdw + * Raw I/O of elliptic curve points and group elements. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "ec.h" +#include "ec-raw.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @ec_putraw@ --- * + * + * Arguments: @ec_curve *c@ = elliptic curve + * @buf *b@ = pointer to a buffer + * @const ec *p@ = an elliptic curve point + * + * Returns: Zero on success, nonzero on failure. + * + * Use: Puts an elliptic curve point to the given buffer using the + * standard uncompressed format described in P1383 and SEC1. + * This requires at most @1 + 2 * c->f->noctets@ space in the + * buffer. We don't do point compression. + */ + +int ec_putraw(ec_curve *c, buf *b, const ec *p) +{ + octet *q; + size_t n; + + if (EC_ATINF(p)) return (buf_putbyte(b, 0)); + buf_putbyte(b, 4); + n = c->f->noctets; + if ((q = buf_get(b, n * 2)) == 0) return (-1); + mp_storeb(p->x, q, n); + mp_storeb(p->y, q + n, n); + return (0); +} + +/* --- @ec_getraw@ --- * + * + * Arguments: @ec_curve *c@ = elliptic curve + * @buf *b@ = pointer to a buffer + * @ec *d@ = an elliptic curve point + * + * Returns: Zero on success, nonzero on failure. + * + * Use: Reads an elliptic curve point from the given buffer using the + * standard uncompressed format described in P1383 and SEC1. + * We don't do point compression. + */ + +int ec_getraw(ec_curve *c, buf *b, ec *d) +{ + const octet *q; + size_t n; + int u; + + if ((u = buf_getbyte(b)) < 0) return (-1); + if (!u) { EC_SETINF(d); return (0); } + if (!(u & 4)) return (-1); + n = c->f->noctets; + if ((q = buf_get(b, n * 2)) == 0) return (-1); + EC_DESTROY(d); + d->x = mp_loadb(MP_NEW, q, n); + d->y = mp_loadb(MP_NEW, q + n, n); + d->z = 0; + return (0); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/ec-raw.h b/ec-raw.h new file mode 100644 index 0000000..e0fde75 --- /dev/null +++ b/ec-raw.h @@ -0,0 +1,93 @@ +/* -*-c-*- + * + * $Id: ec-raw.h,v 1.1 2004/04/04 19:04:11 mdw Exp $ + * + * Raw formatting of elliptic curve points + * + * (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-raw.h,v $ + * Revision 1.1 2004/04/04 19:04:11 mdw + * Raw I/O of elliptic curve points and group elements. + * + */ + +#ifndef CATACOMB_EC_RAW_H +#define CATACOMB_EC_RAW_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#ifndef CATACOMB_BUF_H +# include "buf.h" +#endif + +#ifndef CATACOMB_EC_H +# include "ec.h" +#endif + +/*----- Data formatting ---------------------------------------------------*/ + +/* --- @ec_putraw@ --- * + * + * Arguments: @ec_curve *c@ = elliptic curve + * @buf *b@ = pointer to a buffer + * @const ec *p@ = an elliptic curve point + * + * Returns: Zero on success, nonzero on failure. + * + * Use: Puts an elliptic curve point to the given buffer using the + * standard uncompressed format described in P1383 and SEC1. + * We don't do point compression. + */ + +extern int ec_putraw(ec_curve */*c*/, buf */*b*/, const ec */*p*/); + +/* --- @ec_getraw@ --- * + * + * Arguments: @ec_curve *c@ = elliptic curve + * @buf *b@ = pointer to a buffer + * @ec *d@ = an elliptic curve point + * + * Returns: Zero on success, nonzero on failure. + * + * Use: Reads an elliptic curve point from the given buffer using the + * standard uncompressed format described in P1383 and SEC1. + * We don't do point compression. + */ + +extern int ec_getraw(ec_curve */*c*/, buf */*b*/, ec */*d*/); + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/g-ec.c b/g-ec.c index 91583bb..dcf8a10 100644 --- a/g-ec.c +++ b/g-ec.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: g-ec.c,v 1.2 2004/04/03 03:32:05 mdw Exp $ + * $Id: g-ec.c,v 1.3 2004/04/04 19:04:11 mdw Exp $ * * Abstraction for elliptic curve groups * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: g-ec.c,v $ + * Revision 1.3 2004/04/04 19:04:11 mdw + * Raw I/O of elliptic curve points and group elements. + * * Revision 1.2 2004/04/03 03:32:05 mdw * General robustification. * @@ -50,6 +53,7 @@ #define ge ec #include "group.h" +#include "ec-raw.h" /*----- Data structures ---------------------------------------------------*/ @@ -182,6 +186,19 @@ static int gfrombuf(group *gg, buf *b, ec *d) { if (!rc) EC_COPY(d, &t); EC_DESTROY(&t); return (rc); } +static int gtoraw(group *gg, buf *b, ec *x) { + gctx *g = (gctx *)gg; ec t = EC_INIT; int rc; + EC_OUT(g->ei.c, &t, x); rc = ec_putraw(g->ei.c, b, &t); + EC_DESTROY(&t); return (rc); +} + +static int gfromraw(group *gg, buf *b, ec *d) { + gctx *g = (gctx *)gg; ec t = EC_INIT; int rc; + if (ec_getraw(g->ei.c, 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 @@ -202,7 +219,7 @@ static const group_ops gops = { gcheck, gmul, gsqr, ginv, gdiv, gexp, gmexp, gread, gwrite, - gtoint, gfromint, gtoec, gfromec, gtobuf, gfrombuf + gtoint, gfromint, gtoec, gfromec, gtobuf, gfrombuf, gtoraw, gfromraw }; group *group_ec(const ec_info *ei) @@ -211,7 +228,7 @@ group *group_ec(const ec_info *ei) g->g.ops = &gops; g->g.nbits = ei->c->f->nbits * 2; - g->g.noctets = ei->c->f->noctets * 2; + g->g.noctets = ei->c->f->noctets * 2 + 1; g->ei = *ei; EC_CREATE(&g->id); g->g.i = &g->id; diff --git a/g-prime.c b/g-prime.c index 03cce55..97f455f 100644 --- a/g-prime.c +++ b/g-prime.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: g-prime.c,v 1.2 2004/04/03 03:32:05 mdw Exp $ + * $Id: g-prime.c,v 1.3 2004/04/04 19:04:11 mdw Exp $ * * Abstraction for prime groups * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: g-prime.c,v $ + * Revision 1.3 2004/04/04 19:04:11 mdw + * Raw I/O of elliptic curve points and group elements. + * * Revision 1.2 2004/04/03 03:32:05 mdw * General robustification. * @@ -149,6 +152,20 @@ static int gfrombuf(group *gg, buf *b, mp **d) { *d = mpmont_mul(&g->mm, x, x, g->mm.r2); return(0); } +static int gtoraw(group *gg, buf *b, mp **x) { + gctx *g = (gctx *)gg; octet *q; mp *t = mpmont_reduce(&g->mm, MP_NEW, *x); + if ((q = buf_get(b, g->g.noctets)) == 0) { MP_DROP(t); return (-1); } + mp_storeb(t, q, g->g.noctets); MP_DROP(t); return (0); +} + +static int gfromraw(group *gg, buf *b, mp **d) { + gctx * g = (gctx *)gg; mp *x; octet *q; + if ((q = buf_get(b, g->g.noctets)) == 0) return (-1); + x = mp_loadb(MP_NEW, q, g->g.noctets); + mp_div(0, &x, x, g->mm.m); mp_drop(*d); + *d = mpmont_mul(&g->mm, x, x, g->mm.r2); return(0); +} + /* --- @group_prime@ --- * * * Arguments: @const gprime_param *gp@ = group parameters @@ -166,7 +183,8 @@ static const group_ops gops = { gcheck, gmul, gsqr, ginv, group_stddiv, gexp, gmexp, gread, gwrite, - gtoint, gfromint, group_stdtoec, group_stdfromec, gtobuf, gfrombuf + gtoint, gfromint, group_stdtoec, group_stdfromec, gtobuf, gfrombuf, + gtoraw, gfromraw }; group *group_prime(const gprime_param *gp) diff --git a/group-file.c b/group-file.c index 64e0e4b..a819f92 100644 --- a/group-file.c +++ b/group-file.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: group-file.c,v 1.1 2004/04/01 12:50:09 mdw Exp $ + * $Id: group-file.c,v 1.2 2004/04/04 19:04:11 mdw Exp $ * * File I/O for group elements * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: group-file.c,v $ + * Revision 1.2 2004/04/04 19:04:11 mdw + * Raw I/O of elliptic curve points and group elements. + * * 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. @@ -71,6 +74,6 @@ int group_readfile(group *g, ge *d, FILE *fp) */ int group_writefile(group *g, ge *x, FILE *fp) - { return (G_WRITE(g, x, &mptext_stringops, fp)); } + { return (G_WRITE(g, x, &mptext_fileops, fp)); } /*----- That's all, folks -------------------------------------------------*/ diff --git a/group-test.c b/group-test.c index 5fdf147..7c1936b 100644 --- a/group-test.c +++ b/group-test.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: group-test.c,v 1.1 2004/04/01 12:50:09 mdw Exp $ + * $Id: group-test.c,v 1.2 2004/04/04 19:04:11 mdw Exp $ * * Testing group operations * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: group-test.c,v $ + * Revision 1.2 2004/04/04 19:04:11 mdw + * Raw I/O of elliptic curve points and group elements. + * * 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. @@ -450,6 +453,71 @@ static int vfrombuf(dstr *v) return (ok); } +static int vtoraw(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_TORAW(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, "*** toraw 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 vfromraw(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_FROMRAW(g, &b, c); + if ((ic < 0) != (ir < 0) || (ir >= 0 && + (ir != BLEN(&b) || !G_EQ(g, r, c)))) { + ok = 0; + fprintf(stderr, "*** fromraw 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 } }, @@ -493,6 +561,10 @@ static const test_chunk tests[] = { &type_int, &type_hex } }, { "frombuf", vfrombuf, { &type_string, &type_hex, &type_int, &type_string } }, + { "toraw", vtoraw, { &type_string, &type_string, + &type_int, &type_hex } }, + { "fromraw", vfromraw, { &type_string, &type_hex, + &type_int, &type_string } }, { 0 } }; diff --git a/group.h b/group.h index d099a8f..0e32de6 100644 --- a/group.h +++ b/group.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: group.h,v 1.2 2004/04/03 03:32:05 mdw Exp $ + * $Id: group.h,v 1.3 2004/04/04 19:04:11 mdw Exp $ * * General cyclic group abstraction * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: group.h,v $ + * Revision 1.3 2004/04/04 19:04:11 mdw + * Raw I/O of elliptic curve points and group elements. + * * Revision 1.2 2004/04/03 03:32:05 mdw * General robustification. * @@ -82,7 +85,7 @@ 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 */ + size_t noctets; /* Size of raw element in octets */ ge *i; /* Identity element */ ge *g; /* Generator element */ mp *r; /* Order of the generator */ @@ -140,6 +143,8 @@ typedef struct group_ops { int (*fromec)(group */*g*/, ge */*d*/, ec */*p*/); int (*tobuf)(group */*h*/, buf */*b*/, ge */*x*/); int (*frombuf)(group */*h*/, buf */*b*/, ge */*d*/); + int (*toraw)(group */*h*/, buf */*b*/, ge */*x*/); + int (*fromraw)(group */*h*/, buf */*b*/, ge */*d*/); } group_ops; @@ -177,6 +182,8 @@ enum { #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)) +#define G_TORAW(g, b, x) (g)->ops->toraw((g), (b), (x)) +#define G_FROMRAW(g, b, d) (g)->ops->fromraw((g), (b), (d)) /*----- Handy functions ---------------------------------------------------*/ diff --git a/tests/group b/tests/group index eb9c1fa..0c2035a 100644 --- a/tests/group +++ b/tests/group @@ -1,4 +1,4 @@ -# $Id: group,v 1.1 2004/04/01 12:50:41 mdw Exp $ +# $Id: group,v 1.2 2004/04/04 19:04:11 mdw Exp $ # # Test group abstraction, and a bunch of other things. @@ -282,3 +282,39 @@ frombuf { "00010000188497a9fa119ff34c9c24a156ed0d44a0c5f5d1f19fc9f0eddead" 29, "0, 0x8497a9fa119ff34c9c24a156ed0d44a0c5f5d1f19fc9f0ed"; } + +toraw { + "prime { 29, 7, 16}" 22 -1 ""; + "prime { 29, 7, 16}" 22 0 "16"; + "prime { 29, 7, 16}" 0 -1 ""; + "prime { 29, 7, 16}" 0 0 "00"; + "prime { 4294967311, 364289, 18767 }" 4285559121 0 "00ff707151"; + "prime { 4294967311, 364289, 18767 }" 4285559121 -1 "ff707151"; + + "ec { secp112r1 }" inf 0 "00"; + "ec { secp112r1 }" + "0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500" + 0 "0409487239995a5ee76b55f9c2f098a89ce5af8724c0a23e0e0ff77500"; + "ec { nist-p192 }" + "0, 0x8497a9fa119ff34c9c24a156ed0d44a0c5f5d1f19fc9f0ed" + 0 "040000000000000000000000000000000000000000000000008497a9fa119ff34c9c24a156ed0d44a0c5f5d1f19fc9f0ed"; +} + +fromraw { + "prime { 29, 7, 16}" "" -1 0; + "prime { 29, 7, 16}" "160bad" 1 22; + "prime { 29, 7, 16}" "00" 1 0; + "prime { 4294967311, 364289, 18767 }" "00ff707151e7c0" 5 4285559121; + "prime { 4294967311, 364289, 18767 }" "ff707151" -1 0; + + "ec { secp112r1 }" "" -1 inf; + "ec { secp112r1 }" "00" 1 inf; + "ec { secp112r1 }" + "0409487239995a5ee76b55f9c2f098a89ce5af8724c0a23e0e0ff775" -1 inf; + "ec { secp112r1 }" + "0409487239995a5ee76b55f9c2f098a89ce5af8724c0a23e0e0ff77500" + 29 "0x09487239995a5ee76b55f9c2f098, 0xa89ce5af8724c0a23e0e0ff77500"; + "ec { nist-p192 }" + "070000000000000000000000000000000000000000000000008497a9fa119ff34c9c24a156ed0d44a0c5f5d1f19fc9f0ed00deadbeef" + 49 "0, 0x8497a9fa119ff34c9c24a156ed0d44a0c5f5d1f19fc9f0ed"; +} -- 2.11.0