X-Git-Url: https://git.distorted.org.uk/~mdw/secnet/blobdiff_plain/b7a5ecfcbac18c56d0b044975f6ed6835dd86ab4..refs/heads/mdw/xdh:/fgoldi.c diff --git a/fgoldi.c b/fgoldi.c index 5b2889f..08e6592 100644 --- a/fgoldi.c +++ b/fgoldi.c @@ -7,7 +7,26 @@ /*----- Licensing notice --------------------------------------------------* * - * This file is part of Catacomb. + * This file is part of secnet. + * See README for full list of copyright holders. + * + * secnet 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 d of the License, or + * (at your option) any later version. + * + * secnet 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 + * version 3 along with secnet; if not, see + * https://www.gnu.org/licenses/gpl.html. + * + * This file was originally part of Catacomb, but has been automatically + * modified for incorporation into secnet: see `import-catacomb-crypto' + * for details. * * Catacomb is free software; you can redistribute it and/or modify * it under the terms of the GNU Library General Public License as @@ -27,8 +46,6 @@ /*----- Header files ------------------------------------------------------*/ -#include "config.h" - #include "fgoldi.h" /*----- Basic setup -------------------------------------------------------* @@ -37,49 +54,25 @@ * (hence the name). */ -#if FGOLDI_IMPL == 28 +typedef fgoldi_piece piece; + /* 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). */ -typedef int32 piece; typedef int64 dblpiece; + typedef int64 dblpiece; typedef uint32 upiece; typedef uint64 udblpiece; #define PIECEWD(i) 28 #define NPIECE 16 #define P p28 -#define B28 0x10000000u #define B27 0x08000000u #define M28 0x0fffffffu -#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,7 +116,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]; @@ -158,35 +150,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,7 +165,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; @@ -269,80 +231,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@ --- * @@ -397,8 +285,72 @@ void fgoldi_sub(fgoldi *z, const fgoldi *x, const fgoldi *y) for (i = 0; i < NPIECE; i++) z->P[i] = x->P[i] - y->P[i]; } +/* --- @fgoldi_neg@ --- * + * + * Arguments: @fgoldi *z@ = where to put the result (may alias @x@) + * @const fgoldi *x@ = an operand + * + * Returns: --- + * + * Use: Set @z = -x@. + */ + +void fgoldi_neg(fgoldi *z, const fgoldi *x) +{ + unsigned i; + for (i = 0; i < NPIECE; i++) z->P[i] = -x->P[i]; +} + /*----- Constant-time utilities -------------------------------------------*/ +/* --- @fgoldi_pick2@ --- * + * + * Arguments: @fgoldi *z@ = where to put the result (may alias @x@ or @y@) + * @const fgoldi *x, *y@ = two operands + * @uint32 m@ = a mask + * + * Returns: --- + * + * Use: If @m@ is zero, set @z = y@; if @m@ is all-bits-set, then set + * @z = x@. If @m@ has some other value, then scramble @z@ in + * an unhelpful way. + */ + +void fgoldi_pick2(fgoldi *z, const fgoldi *x, const fgoldi *y, uint32 m) +{ + mask32 mm = FIX_MASK32(m); + unsigned i; + for (i = 0; i < NPIECE; i++) z->P[i] = PICK2(x->P[i], y->P[i], mm); +} + +/* --- @fgoldi_pickn@ --- * + * + * Arguments: @fgoldi *z@ = where to put the result + * @const fgoldi *v@ = a table of entries + * @size_t n@ = the number of entries in @v@ + * @size_t i@ = an index + * + * Returns: --- + * + * Use: If @0 <= i < n < 32@ then set @z = v[i]@. If @n >= 32@ then + * do something unhelpful; otherwise, if @i >= n@ then set @z@ + * to zero. + */ + +void fgoldi_pickn(fgoldi *z, const fgoldi *v, size_t n, size_t i) +{ + uint32 b = (uint32)1 << (31 - i); + mask32 m; + unsigned j; + + for (j = 0; j < NPIECE; j++) z->P[j] = 0; + while (n--) { + m = SIGN(b); + for (j = 0; j < NPIECE; j++) CONDPICK(z->P[j], v->P[j], m); + v++; b <<= 1; + } +} + /* --- @fgoldi_condswap@ --- * * * Arguments: @fgoldi *x, *y@ = two operands @@ -419,9 +371,32 @@ void fgoldi_condswap(fgoldi *x, fgoldi *y, uint32 m) for (i = 0; i < NPIECE; i++) CONDSWAP(x->P[i], y->P[i], mm); } -/*----- Multiplication ----------------------------------------------------*/ +/* --- @fgoldi_condneg@ --- * + * + * Arguments: @fgoldi *z@ = where to put the result (may alias @x@) + * @const fgoldi *x@ = an operand + * @uint32 m@ = a mask + * + * Returns: --- + * + * Use: If @m@ is zero, set @z = x@; if @m@ is all-bits-set, then set + * @z = -x@. If @m@ has some other value then scramble @z@ in + * an unhelpful way. + */ + +void fgoldi_condneg(fgoldi *z, const fgoldi *x, uint32 m) +{ + mask32 m_xor = FIX_MASK32(m); + piece m_add = m&1; +# define CONDNEG(x) (((x) ^ m_xor) + m_add) + + unsigned i; + for (i = 0; i < NPIECE; i++) z->P[i] = CONDNEG(x->P[i]); + +#undef CONDNEG +} -#if FGOLDI_IMPL == 28 +/*----- Multiplication ----------------------------------------------------*/ /* 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 @@ -447,58 +422,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 +439,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 +461,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 +516,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 +531,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,7 +545,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]; @@ -720,10 +616,6 @@ void fgoldi_sqr(fgoldi *z, const fgoldi *x) /* Finally, carrying. */ 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 +675,86 @@ 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) +/* --- @fgoldi_quosqrt@ --- * + * + * Arguments: @fgoldi *z@ = where to put the result (may alias @x@ or @y@) + * @const fgoldi *x, *y@ = two operands + * + * Returns: Zero if successful, @-1@ if %$x/y$% is not a square. + * + * Use: Stores in @z@ the one of the square roots %$\pm\sqrt{x/y}$%. + * If %$x = y = 0% then the result is zero; if %$y = 0$% but %$x + * \ne 0$% then the operation fails. If you wanted a specific + * square root then you'll have to pick it yourself. + */ -static int vrf_mulc(dstr dv[]) +int fgoldi_quosqrt(fgoldi *z, const fgoldi *x, const fgoldi *y) { - 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); -} + fgoldi t, u, v; + octet xb[56], b0[56]; + int32 rc = -1; + mask32 m; + unsigned i; -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); - } +#define SQRN(z, x, n) do { \ + fgoldi_sqr((z), (x)); \ + for (i = 1; i < (n); i++) fgoldi_sqr((z), (z)); \ +} while (0) - return (ok); -} + /* This is, fortunately, significantly easier than the equivalent problem + * in GF(2^255 - 19), since p == 3 (mod 4). + * + * If x/y is square, then so is v = y^2 x/y = x y, and therefore u has + * order r = (p - 1)/2. Let w = v^{(p-3)/4}. Then w^2 = v^{(p-3)/2} = + * u^{r-1} = 1/v = 1/x y. Clearly, then, (x w)^2 = x^2/x y = x/y, so x w + * is one of the square roots we seek. + * + * The addition chain, then, is a prefix of the previous one. + */ + fgoldi_mul(&v, x, y); -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); - } + fgoldi_sqr(&u, &v); /* 1 | 2 */ + fgoldi_mul(&t, &u, &v); /* 2 | 3 */ + SQRN(&u, &t, 2); /* 4 | 12 */ + fgoldi_mul(&t, &u, &t); /* 5 | 15 */ + SQRN(&u, &t, 4); /* 9 | 240 */ + fgoldi_mul(&u, &u, &t); /* 10 | 255 = 2^8 - 1 */ + SQRN(&u, &u, 4); /* 14 | 2^12 - 16 */ + fgoldi_mul(&t, &u, &t); /* 15 | 2^12 - 1 */ + SQRN(&u, &t, 12); /* 27 | 2^24 - 2^12 */ + fgoldi_mul(&u, &u, &t); /* 28 | 2^24 - 1 */ + SQRN(&u, &u, 12); /* 40 | 2^36 - 2^12 */ + fgoldi_mul(&t, &u, &t); /* 41 | 2^36 - 1 */ + fgoldi_sqr(&t, &t); /* 42 | 2^37 - 2 */ + fgoldi_mul(&t, &t, &v); /* 43 | 2^37 - 1 */ + SQRN(&u, &t, 37); /* 80 | 2^74 - 2^37 */ + fgoldi_mul(&u, &u, &t); /* 81 | 2^74 - 1 */ + SQRN(&u, &u, 37); /* 118 | 2^111 - 2^37 */ + fgoldi_mul(&t, &u, &t); /* 119 | 2^111 - 1 */ + SQRN(&u, &t, 111); /* 230 | 2^222 - 2^111 */ + fgoldi_mul(&t, &u, &t); /* 231 | 2^222 - 1 */ + fgoldi_sqr(&u, &t); /* 232 | 2^223 - 2 */ + fgoldi_mul(&u, &u, &v); /* 233 | 2^223 - 1 */ + SQRN(&u, &u, 223); /* 456 | 2^446 - 2^223 */ + fgoldi_mul(&t, &u, &t); /* 457 | 2^446 - 2^222 - 1 */ - return (ok); -} +#undef SQRN -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); + /* Now we must decide whether the answer was right. We should have z^2 = + * x/y, so y z^2 = x. + * + * The easiest way to compare is to encode. This isn't as wasteful as it + * sounds: the hard part is normalizing the representations, which we have + * to do anyway. + */ + fgoldi_mul(z, x, &t); + fgoldi_sqr(&t, z); + fgoldi_mul(&t, &t, y); + fgoldi_store(xb, x); + fgoldi_store(b0, &t); + m = -consttime_memeq(xb, b0, 56); + rc = PICK2(0, rc, m); + return (rc); } -#endif - /*----- That's all, folks -------------------------------------------------*/