X-Git-Url: https://git.distorted.org.uk/~mdw/secnet/blobdiff_plain/b7a5ecfcbac18c56d0b044975f6ed6835dd86ab4..0bcb8184cfce875a4dde57621139dd44c433f3a5:/fgoldi.c diff --git a/fgoldi.c b/fgoldi.c index 5b2889f..6a8d35b 100644 --- a/fgoldi.c +++ b/fgoldi.c @@ -1,3 +1,41 @@ +/* + * fgoldi.c: arithmetic modulo 2^448 - 2^224 - 1 + */ +/* + * This file is Free Software. It has been modified to as part of its + * incorporation into secnet. + * + * Copyright 2017 Mark Wooding + * + * You may redistribute this file and/or modify it under the terms of + * the permissive licence shown below. + * + * You may redistribute secnet as a whole and/or modify it under the + * terms of the GNU General Public License as published by the Free + * Software Foundation; either version 3, or (at your option) any + * later version. + * + * This program 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 this program; if not, see + * https://www.gnu.org/licenses/gpl.html. + */ +/* + * Imported from Catacomb, and modified for Secnet (2017-04-30): + * + * * Use `fake-mLib-bits.h' in place of the real . + * + * * Remove the 16/32-bit implementation, since C99 always has 64-bit + * arithmetic. + * + * * Remove the test rig code: a replacement is in a separate source file. + * + * The file's original comment headers are preserved below. + */ /* -*-c-*- * * Arithmetic in the Goldilocks field GF(2^448 - 2^224 - 1) @@ -27,8 +65,6 @@ /*----- Header files ------------------------------------------------------*/ -#include "config.h" - #include "fgoldi.h" /*----- Basic setup -------------------------------------------------------* @@ -37,7 +73,6 @@ * (hence the name). */ -#if FGOLDI_IMPL == 28 /* We represent an element of GF(p) as 16 28-bit signed integer pieces x_i: * x = SUM_{0<=i<16} x_i 2^(28i). */ @@ -54,32 +89,9 @@ typedef uint32 upiece; typedef uint64 udblpiece; #define M27 0x07ffffffu #define M32 0xffffffffu -#elif FGOLDI_IMPL == 12 -/* We represent an element of GF(p) as 40 signed integer pieces x_i: x = - * SUM_{0<=i<40} x_i 2^ceil(224i/20). Pieces i with i == 0 (mod 5) are 12 - * bits wide; the others are 11 bits wide, so they form eight groups of 56 - * bits. - */ - -typedef int16 piece; typedef int32 dblpiece; -typedef uint16 upiece; typedef uint32 udblpiece; -#define PIECEWD(i) ((i)%5 ? 11 : 12) -#define NPIECE 40 -#define P p12 - -#define B12 0x1000u -#define B11 0x0800u -#define B10 0x0400u -#define M12 0xfffu -#define M11 0x7ffu -#define M10 0x3ffu -#define M8 0xffu - -#endif - /*----- Debugging machinery -----------------------------------------------*/ -#if defined(FGOLDI_DEBUG) || defined(TEST_RIG) +#if defined(FGOLDI_DEBUG) #include @@ -123,8 +135,6 @@ DEF_FDUMP(fdump, piece, PIECEWD, NPIECE, 56, get_pgoldi()) void fgoldi_load(fgoldi *z, const octet xv[56]) { -#if FGOLDI_IMPL == 28 - unsigned i; uint32 xw[14]; piece b, c; @@ -158,35 +168,6 @@ void fgoldi_load(fgoldi *z, const octet xv[56]) for (i = NPIECE - 1; i--; ) { b = z->P[i]&B27; z->P[i] -= b << 1; z->P[i + 1] += b >> 27; } z->P[0] += c; z->P[8] += c; - -#elif FGOLDI_IMPL == 12 - - unsigned i, j, n, w, b; - uint32 a; - int c; - - /* First, convert the bytes into nonnegative pieces. */ - for (i = j = a = n = 0, w = PIECEWD(0); i < 56; i++) { - a |= (uint32)xv[i] << n; n += 8; - if (n >= w) { - z->P[j++] = a&MASK(w); - a >>= w; n -= w; w = PIECEWD(j); - } - } - - /* Convert the nonnegative pieces into a balanced signed representation, so - * each piece ends up in the interval |z_i| <= 2^11 + 1. - */ - b = z->P[39]&B10; z->P[39] -= b << 1; c = b >> 10; - for (i = NPIECE - 1; i--; ) { - w = PIECEWD(i) - 1; - b = z->P[i]&BIT(w); - z->P[i] -= b << 1; - z->P[i + 1] += b >> w; - } - z->P[0] += c; z->P[20] += c; - -#endif } /* --- @fgoldi_store@ --- * @@ -202,8 +183,6 @@ void fgoldi_load(fgoldi *z, const octet xv[56]) void fgoldi_store(octet zv[56], const fgoldi *x) { -#if FGOLDI_IMPL == 28 - piece y[NPIECE], yy[NPIECE], c, d; uint32 u, v; mask32 m; @@ -269,80 +248,6 @@ void fgoldi_store(octet zv[56], const fgoldi *x) STORE32_L(zv + 4*i, u); STORE32_L(zv + 4*i + 28, v); } - -#elif FGOLDI_IMPL == 12 - - piece y[NPIECE], yy[NPIECE], c, d; - uint32 a; - mask32 m, mm; - unsigned i, j, n, w; - - for (i = 0; i < NPIECE; i++) y[i] = x->P[i]; - - /* First, propagate the carries. By the end of this, we'll have all of the - * the pieces canonically sized and positive, and maybe there'll be - * (signed) carry out. The carry c is in { -1, 0, +1 }, and the remaining - * value will be in the half-open interval [0, φ^2). The whole represented - * value is then y + φ^2 c. - * - * Assume that we start out with |y_i| <= 2^14. We start off by cutting - * off and reducing the carry c_39 from the topmost piece, y_39. This - * leaves 0 <= y_39 < 2^11; and we'll have |c_39| <= 16. We'll add this - * onto y_0 and y_20, and propagate the carries. It's very clear that - * we'll end up with |y + (φ + 1) c_39 - φ^2/2| << φ^2. - * - * Here, the y_i are signed, so we must be cautious about bithacking them. - */ - c = ASR(piece, y[39], 11); y[39] = (piece)y[39]&M11; y[20] += c; - for (i = 0; i < NPIECE; i++) { - w = PIECEWD(i); m = (1 << w) - 1; - y[i] += c; c = ASR(piece, y[i], w); y[i] = (upiece)y[i]&m; - } - - /* Now we have a slightly fiddly job to do. If c = +1, or if c = 0 and - * y >= p, then we should subtract p from the whole value; if c = -1 then - * we should add p; and otherwise we should do nothing. - * - * But conditional behaviour is bad, m'kay. So here's what we do instead. - * - * The first job is to sort out what we wanted to do. If c = -1 then we - * want to (a) invert the constant addend and (b) feed in a carry-in; - * otherwise, we don't. - */ - mm = SIGN(c); - d = m&1; - - /* Now do the addition/subtraction. Remember that all of the y_i are - * nonnegative, so shifting and masking are safe and easy. - */ - d += y[ 0] + (1 ^ (mm&M12)); yy[ 0] = d&M12; d >>= 12; - for (i = 1; i < 20; i++) { - w = PIECEWD(i); m = MASK(w); - d += y[ i] + (mm&m); yy[ i] = d&m; d >>= w; - } - d += y[20] + (1 ^ (mm&M12)); yy[20] = d&M12; d >>= 12; - for (i = 21; i < 40; i++) { - w = PIECEWD(i); m = MASK(w); - d += y[ i] + (mm&m); yy[ i] = d&m; d >>= w; - } - - /* The final carry-out is in d; since we only did addition, and the y_i are - * nonnegative, then d is in { 0, 1 }. We want to keep y', rather than y, - * if (a) c /= 0 (in which case we know that the old value was - * unsatisfactory), or (b) if d = 1 (in which case, if c = 0, we know that - * the subtraction didn't cause a borrow, so we must be in the case where - * p <= y < φ^2. - */ - m = NONZEROP(c) | ~NONZEROP(d - 1); - for (i = 0; i < NPIECE; i++) y[i] = (yy[i]&m) | (y[i]&~m); - - /* Convert that back into octets. */ - for (i = j = a = n = 0; i < NPIECE; i++) { - a |= (uint32)y[i] << n; n += PIECEWD(i); - while (n >= 8) { zv[j++] = a&M8; a >>= 8; n -= 8; } - } - -#endif } /* --- @fgoldi_set@ --- * @@ -421,8 +326,6 @@ void fgoldi_condswap(fgoldi *x, fgoldi *y, uint32 m) /*----- Multiplication ----------------------------------------------------*/ -#if FGOLDI_IMPL == 28 - /* Let B = 2^63 - 1 be the largest value such that +B and -B can be * represented in a double-precision piece. On entry, it must be the case * that |X_i| <= M <= B - 2^27 for some M. If this is the case, then, on @@ -447,58 +350,6 @@ void fgoldi_condswap(fgoldi *x, fgoldi *y, uint32 m) (z)[8] += _c; \ } while (0) -#elif FGOLDI_IMPL == 12 - -static void carry_reduce(dblpiece x[NPIECE]) -{ - /* Initial bounds: we assume |x_i| < 2^31 - 2^27. */ - - unsigned i, j; - dblpiece c; - - /* The result is nearly canonical, because we do sequential carry - * propagation, because smaller processors are more likely to prefer the - * smaller working set than the instruction-level parallelism. - * - * Start at x_37; truncate it to 10 bits, and propagate the carry to x_38. - * Truncate x_38 to 10 bits, and add the carry onto x_39. Truncate x_39 to - * 10 bits, and add the carry onto x_0 and x_20. And so on. - * - * Once we reach x_37 for the second time, we start with |x_37| <= 2^10. - * The carry into x_37 is at most 2^21; so the carry out into x_38 has - * magnitude at most 2^10. In turn, |x_38| <= 2^10 before the carry, so is - * now no more than 2^11 in magnitude, and the carry out into x_39 is at - * most 1. This leaves |x_39| <= 2^10 + 1 after carry propagation. - * - * Be careful with the bit hacking because the quantities involved are - * signed. - */ - - /* For each piece, we bias it so that floor division (as done by an - * arithmetic right shift) and modulus (as done by bitwise-AND) does the - * right thing. - */ -#define CARRY(i, wd, b, m) do { \ - x[i] += (b); \ - c = ASR(dblpiece, x[i], (wd)); \ - x[i] = (dblpiece)((udblpiece)x[i]&(m)) - (b); \ -} while (0) - - { CARRY(37, 11, B10, M11); } - { x[38] += c; CARRY(38, 11, B10, M11); } - { x[39] += c; CARRY(39, 11, B10, M11); } - x[20] += c; - for (i = 0; i < 35; ) { - { x[i] += c; CARRY( i, 12, B11, M12); i++; } - for (j = i + 4; i < j; ) { x[i] += c; CARRY( i, 11, B10, M11); i++; } - } - { x[i] += c; CARRY( i, 12, B11, M12); i++; } - while (i < 39) { x[i] += c; CARRY( i, 11, B10, M11); i++; } - x[39] += c; -} - -#endif - /* --- @fgoldi_mulconst@ --- * * * Arguments: @fgoldi *z@ = where to put the result (may alias @x@) @@ -516,12 +367,7 @@ void fgoldi_mulconst(fgoldi *z, const fgoldi *x, long a) dblpiece zz[NPIECE], aa = a; for (i = 0; i < NPIECE; i++) zz[i] = aa*x->P[i]; -#if FGOLDI_IMPL == 28 CARRY_REDUCE(z->P, zz); -#elif FGOLDI_IMPL == 12 - carry_reduce(zz); - for (i = 0; i < NPIECE; i++) z->P[i] = zz[i]; -#endif } /* --- @fgoldi_mul@ --- * @@ -543,24 +389,8 @@ void fgoldi_mul(fgoldi *z, const fgoldi *x, const fgoldi *y) *c = y->P + NPIECE/2, *d = y->P; unsigned i, j; -#if FGOLDI_IMPL == 28 - # define M(x,i, y,j) ((dblpiece)(x)[i]*(y)[j]) -#elif FGOLDI_IMPL == 12 - - static const unsigned short off[39] = { - 0, 12, 23, 34, 45, 56, 68, 79, 90, 101, - 112, 124, 135, 146, 157, 168, 180, 191, 202, 213, - 224, 236, 247, 258, 269, 280, 292, 303, 314, 325, - 336, 348, 359, 370, 381, 392, 404, 415, 426 - }; - -#define M(x,i, y,j) \ - (((dblpiece)(x)[i]*(y)[j]) << (off[i] + off[j] - off[(i) + (j)])) - -#endif - /* Behold the magic. * * Write x = a φ + b, and y = c φ + d. Then x y = a c φ^2 + @@ -614,7 +444,6 @@ void fgoldi_mul(fgoldi *z, const fgoldi *x, const fgoldi *y) #undef M -#if FGOLDI_IMPL == 28 /* That wraps it up for the multiplication. Let's figure out some bounds. * Fortunately, Karatsuba is a polynomial identity, so all of the pieces * end up the way they'd be if we'd done the thing the easy way, which @@ -630,10 +459,6 @@ void fgoldi_mul(fgoldi *z, const fgoldi *x, const fgoldi *y) */ for (i = 0; i < 2; i++) CARRY_REDUCE(zz, zz); for (i = 0; i < NPIECE; i++) z->P[i] = zz[i]; -#elif FGOLDI_IMPL == 12 - carry_reduce(zz); - for (i = 0; i < NPIECE; i++) z->P[i] = zz[i]; -#endif } /* --- @fgoldi_sqr@ --- * @@ -648,8 +473,6 @@ void fgoldi_mul(fgoldi *z, const fgoldi *x, const fgoldi *y) void fgoldi_sqr(fgoldi *z, const fgoldi *x) { -#if FGOLDI_IMPL == 28 - dblpiece zz[NPIECE], u[NPIECE]; piece ab[NPIECE]; const piece *a = x->P + NPIECE/2, *b = x->P; @@ -721,9 +544,6 @@ void fgoldi_sqr(fgoldi *z, const fgoldi *x) for (i = 0; i < 2; i++) CARRY_REDUCE(zz, zz); for (i = 0; i < NPIECE; i++) z->P[i] = zz[i]; -#elif FGOLDI_IMPL == 12 - fgoldi_mul(z, x, x); -#endif } /*----- More advanced operations ------------------------------------------*/ @@ -783,206 +603,4 @@ void fgoldi_inv(fgoldi *z, const fgoldi *x) #undef SQRN } -/*----- Test rig ----------------------------------------------------------*/ - -#ifdef TEST_RIG - -#include -#include -#include - -static void fixdstr(dstr *d) -{ - if (d->len > 56) - die(1, "invalid length for fgoldi"); - else if (d->len < 56) { - dstr_ensure(d, 56); - memset(d->buf + d->len, 0, 56 - d->len); - d->len = 56; - } -} - -static void cvt_fgoldi(const char *buf, dstr *d) -{ - dstr dd = DSTR_INIT; - - type_hex.cvt(buf, &dd); fixdstr(&dd); - dstr_ensure(d, sizeof(fgoldi)); d->len = sizeof(fgoldi); - fgoldi_load((fgoldi *)d->buf, (const octet *)dd.buf); - dstr_destroy(&dd); -} - -static void dump_fgoldi(dstr *d, FILE *fp) - { fdump(stderr, "???", (const piece *)d->buf); } - -static void cvt_fgoldi_ref(const char *buf, dstr *d) - { type_hex.cvt(buf, d); fixdstr(d); } - -static void dump_fgoldi_ref(dstr *d, FILE *fp) -{ - fgoldi x; - - fgoldi_load(&x, (const octet *)d->buf); - fdump(stderr, "???", x.P); -} - -static int eq(const fgoldi *x, dstr *d) - { octet b[56]; fgoldi_store(b, x); return (memcmp(b, d->buf, 56) == 0); } - -static const test_type - type_fgoldi = { cvt_fgoldi, dump_fgoldi }, - type_fgoldi_ref = { cvt_fgoldi_ref, dump_fgoldi_ref }; - -#define TEST_UNOP(op) \ - static int vrf_##op(dstr dv[]) \ - { \ - fgoldi *x = (fgoldi *)dv[0].buf; \ - fgoldi z, zz; \ - int ok = 1; \ - \ - fgoldi_##op(&z, x); \ - if (!eq(&z, &dv[1])) { \ - ok = 0; \ - fprintf(stderr, "failed!\n"); \ - fdump(stderr, "x", x->P); \ - fdump(stderr, "calc", z.P); \ - fgoldi_load(&zz, (const octet *)dv[1].buf); \ - fdump(stderr, "z", zz.P); \ - } \ - \ - return (ok); \ - } - -TEST_UNOP(sqr) -TEST_UNOP(inv) - -#define TEST_BINOP(op) \ - static int vrf_##op(dstr dv[]) \ - { \ - fgoldi *x = (fgoldi *)dv[0].buf, *y = (fgoldi *)dv[1].buf; \ - fgoldi z, zz; \ - int ok = 1; \ - \ - fgoldi_##op(&z, x, y); \ - if (!eq(&z, &dv[2])) { \ - ok = 0; \ - fprintf(stderr, "failed!\n"); \ - fdump(stderr, "x", x->P); \ - fdump(stderr, "y", y->P); \ - fdump(stderr, "calc", z.P); \ - fgoldi_load(&zz, (const octet *)dv[2].buf); \ - fdump(stderr, "z", zz.P); \ - } \ - \ - return (ok); \ - } - -TEST_BINOP(add) -TEST_BINOP(sub) -TEST_BINOP(mul) - -static int vrf_mulc(dstr dv[]) -{ - fgoldi *x = (fgoldi *)dv[0].buf; - long a = *(const long *)dv[1].buf; - fgoldi z, zz; - int ok = 1; - - fgoldi_mulconst(&z, x, a); - if (!eq(&z, &dv[2])) { - ok = 0; - fprintf(stderr, "failed!\n"); - fdump(stderr, "x", x->P); - fprintf(stderr, "a = %ld\n", a); - fdump(stderr, "calc", z.P); - fgoldi_load(&zz, (const octet *)dv[2].buf); - fdump(stderr, "z", zz.P); - } - - return (ok); -} - -static int vrf_condswap(dstr dv[]) -{ - fgoldi *x = (fgoldi *)dv[0].buf, *y = (fgoldi *)dv[1].buf; - fgoldi xx = *x, yy = *y; - uint32 m = *(uint32 *)dv[2].buf; - int ok = 1; - - fgoldi_condswap(&xx, &yy, m); - if (!eq(&xx, &dv[3]) || !eq(&yy, &dv[4])) { - ok = 0; - fprintf(stderr, "failed!\n"); - fdump(stderr, "x", x->P); - fdump(stderr, "y", y->P); - fprintf(stderr, "m = 0x%08lx\n", (unsigned long)m); - fdump(stderr, "calc xx", xx.P); - fdump(stderr, "calc yy", yy.P); - fgoldi_load(&xx, (const octet *)dv[3].buf); - fgoldi_load(&yy, (const octet *)dv[4].buf); - fdump(stderr, "want xx", xx.P); - fdump(stderr, "want yy", yy.P); - } - - return (ok); -} - -static int vrf_sub_mulc_add_sub_mul(dstr dv[]) -{ - fgoldi *u = (fgoldi *)dv[0].buf, *v = (fgoldi *)dv[1].buf, - *w = (fgoldi *)dv[3].buf, *x = (fgoldi *)dv[4].buf, - *y = (fgoldi *)dv[5].buf; - long a = *(const long *)dv[2].buf; - fgoldi umv, aumv, wpaumv, xmy, z, zz; - int ok = 1; - - fgoldi_sub(&umv, u, v); - fgoldi_mulconst(&aumv, &umv, a); - fgoldi_add(&wpaumv, w, &aumv); - fgoldi_sub(&xmy, x, y); - fgoldi_mul(&z, &wpaumv, &xmy); - - if (!eq(&z, &dv[6])) { - ok = 0; - fprintf(stderr, "failed!\n"); - fdump(stderr, "u", u->P); - fdump(stderr, "v", v->P); - fdump(stderr, "u - v", umv.P); - fprintf(stderr, "a = %ld\n", a); - fdump(stderr, "a (u - v)", aumv.P); - fdump(stderr, "w + a (u - v)", wpaumv.P); - fdump(stderr, "x", x->P); - fdump(stderr, "y", y->P); - fdump(stderr, "x - y", xmy.P); - fdump(stderr, "(x - y) (w + a (u - v))", z.P); - fgoldi_load(&zz, (const octet *)dv[6].buf); fdump(stderr, "z", zz.P); - } - - return (ok); -} - -static test_chunk tests[] = { - { "add", vrf_add, { &type_fgoldi, &type_fgoldi, &type_fgoldi_ref } }, - { "sub", vrf_sub, { &type_fgoldi, &type_fgoldi, &type_fgoldi_ref } }, - { "mul", vrf_mul, { &type_fgoldi, &type_fgoldi, &type_fgoldi_ref } }, - { "mulconst", vrf_mulc, { &type_fgoldi, &type_long, &type_fgoldi_ref } }, - { "condswap", vrf_condswap, - { &type_fgoldi, &type_fgoldi, &type_uint32, - &type_fgoldi_ref, &type_fgoldi_ref } }, - { "sqr", vrf_sqr, { &type_fgoldi, &type_fgoldi_ref } }, - { "inv", vrf_inv, { &type_fgoldi, &type_fgoldi_ref } }, - { "sub-mulc-add-sub-mul", vrf_sub_mulc_add_sub_mul, - { &type_fgoldi, &type_fgoldi, &type_long, &type_fgoldi, - &type_fgoldi, &type_fgoldi, &type_fgoldi_ref } }, - { 0, 0, { 0 } } -}; - -int main(int argc, char *argv[]) -{ - test_run(argc, argv, tests, SRCDIR "/t/fgoldi"); - return (0); -} - -#endif - /*----- That's all, folks -------------------------------------------------*/