X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/1589affab225db500965e2cb869c534d6860e6bd..4edc47b89bc56cd4041fdb0f4e8e892acd589ed8:/gfn.c diff --git a/gfn.c b/gfn.c new file mode 100644 index 0000000..1b5a98c --- /dev/null +++ b/gfn.c @@ -0,0 +1,284 @@ +/* -*-c-*- + * + * $Id: gfn.c,v 1.1 2004/04/01 21:28:41 mdw Exp $ + * + * Normal-basis translation for binary fields + * + * (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: gfn.c,v $ + * Revision 1.1 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 + * for repeated constants. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "gfreduce.h" +#include "gfn.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @gfn_copy@ --- * + * + * Arguments: @gfn *d@ = where to put the copy + * @const gfn *s@ = where the source is + * + * Returns: --- + * + * Use: Makes a copy of a translation matrix. + */ + +void gfn_copy(gfn *d, const gfn *s) +{ + size_t i; + + d->n = s->n; + d->r = xmalloc(s->n * sizeof(mp *)); + for (i = 0; i < s->n; i++) + d->r[i] = MP_COPY(s->r[i]); +} + +/* --- @gfn_destroy@ --- * + * + * Arguments: @gfn *m@ = a transformation matrix to free + * + * Returns: --- + * + * Use: Frees up a transformation matrix when it's no longer wanted. + */ + +void gfn_destroy(gfn *m) + { size_t i; for (i = 0; i < m->n; i++) MP_DROP(m->r[i]); xfree(m->r); } + +/* --- @gfn_identity@ --- * + * + * Arguments: @gfn *m@ = where to put the matrix + * @size_t n@ = size of the matrix + * + * Returns: --- + * + * Use: Fills @m@ with an identity matrix. + */ + +void gfn_identity(gfn *m, size_t n) +{ + size_t i; + + m->n = n; + m->r = xmalloc(n * sizeof(mp *)); + m->r[0] = MP_ONE; + for (i = 1; i < n; i++) + m->r[i] = mp_lsl(MP_NEW, m->r[i - 1], 1); +} + +/* --- @gfn_invert@ --- * + * + * Arguments: @gfn *m@ = a transformation matrix + * + * Returns: Zero if successful, nonzero if the matrix was singular. + * + * Use: Inverts a transformation matrix. + */ + +int gfn_invert(gfn *m) +{ + size_t i, j; + gfn mm; + mp *t; + int rc = -1; + + mm = *m; + gfn_identity(m, mm.n); + for (i = 0; i < mm.n; i++) { + if (!mp_testbit(mm.r[i], i)) { + for (j = i + 1; j < mm.n; j++) { + if (mp_testbit(mm.r[j], i)) + goto found_set; + } + goto fail; + found_set: + t = mm.r[i]; mm.r[i] = mm.r[j]; mm.r[j] = t; + t = m->r[i]; m->r[i] = m->r[j]; m->r[j] = t; + } + for (j = 0; j < mm.n; j++) { + if (j == i) continue; + if (mp_testbit(mm.r[j], i)) { + mm.r[j] = mp_xor(mm.r[j], mm.r[j], mm.r[i]); + m->r[j] = mp_xor(m->r[j], m->r[j], m->r[i]); + } + } + } + rc = 0; +fail: + gfn_destroy(&mm); + return (rc); +} + +/* --- @gfn_transform@ --- * + * + * Arguments: @gfn *m@ = conversion matrix to apply + * @mp *d@ = destination pointer + * @mp *x@ = input value + * + * Returns: The transformed element. + * + * Use: Transforms a field element according to the given matrix. + */ + +mp *gfn_transform(gfn *m, mp *d, mp *x) +{ + mp *y = MP_ZERO; + size_t i; + mpscan sc; + + for (i = 0, mp_scan(&sc, x); i < m->n && mp_step(&sc); i++) + if (mp_bit(&sc)) y = mp_xor(y, y, m->r[i]); + mp_drop(d); + return (y); +} + +/* --- @gfn_create@ --- * + * + * Arguments: @mp *p@ = modulus for polynomial basis + * @mp *beta@ = the generator of the normal basis, expressed + * relative to the polynomial basis + * @gfn *ntop@ = output normal-to-polynomail conversion matrix + * @gfn *pton@ = output polynomial-to-normal conversion matrix + * + * Returns: Zero if it worked, nonzero otherwise (e.g., if %$\beta$% + * doesn't generate a proper basis). + * + * Use: Constructs conversion matrices between polynomial and normal + * basis representations of binary field elements. + */ + +int gfn_create(mp *p, mp *beta, gfn *ntop, gfn *pton) +{ + size_t m = mp_bits(p) - 1; + size_t i; + gfreduce gr; + gfn *np, tmp; + + /* --- We start by building the the @ntop@ matrix --- * + * + * For mad reasons, the string representation of normal-basis elements is + * backwards. + */ + + gfreduce_create(&gr, p); + np = ntop ? ntop : &tmp; + np->n = m; + np->r = xmalloc(m * sizeof(mp *)); + np->r[m - 1] = MP_COPY(beta); + for (i = m - 1; i--; ) { + mp *x = gf_sqr(MP_NEW, np->r[i + 1]); + np->r[i] = gfreduce_do(&gr, x, x); + } + gfreduce_destroy(&gr); + + /* --- That was easy -- now invert it --- */ + + if (pton) { + if (ntop) gfn_copy(pton, np); else *pton = *np; + if (gfn_invert(pton)) { + gfn_destroy(pton); + if (ntop) gfn_destroy(ntop); + return (-1); + } + } + + /* --- And we're done --- */ + + return (0); +} + +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + +static int check(dstr *v) +{ + mp *p = *(mp **)v[0].buf; + mp *beta = *(mp **)v[1].buf; + mp *xp = *(mp **)v[2].buf; + mp *xn = *(mp **)v[3].buf; + mp *y = MP_NEW; + gfn pton, ntop, ii; + size_t i; + int ok = 1; + + gfn_create(p, beta, &ntop, &pton); + gfn_identity(&ii, pton.n); + for (i = 0; i < pton.n; i++) { + y = gfn_transform(&ntop, y, pton.r[i]); + if (!MP_EQ(y, ii.r[i])) { + ok = 0; + fprintf(stderr, "*** inverse pton->ntop check failed (row %lu)\n", + (unsigned long)i); + MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta); + MP_EPRINTX("*** computed", y); + } + } + gfn_destroy(&ii); + y = gfn_transform(&pton, y, xp); + if (!MP_EQ(y, xn)) { + ok = 0; + fprintf(stderr, "*** pton failed\n"); + MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta); + MP_EPRINTX("*** xp", xp); MP_EPRINTX("*** xn", xn); + MP_EPRINTX("*** computed", y); + } + y = gfn_transform(&ntop, y, xn); + if (!MP_EQ(y, xp)) { + ok = 0; + fprintf(stderr, "*** ntop failed\n"); + MP_EPRINTX("*** p", p); MP_EPRINTX("*** beta", beta); + MP_EPRINTX("*** xp", xp); MP_EPRINTX("*** xn", xn); + MP_EPRINTX("*** computed", y); + } + gfn_destroy(&pton); gfn_destroy(&ntop); + mp_drop(p); mp_drop(beta); mp_drop(xp); mp_drop(xn); mp_drop(y); + assert(mparena_count(MPARENA_GLOBAL) == 0); + return (ok); +} + +static test_chunk tests[] = { + { "gfn", check, { &type_mp, &type_mp, &type_mp, &type_mp } }, + { 0 } +}; + +int main(int argc, char *argv[]) +{ + test_run(argc, argv, tests, SRCDIR "/tests/gfn"); + return (0); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/