#include "config.h"
+#include "ct.h"
#include "f25519.h"
/*----- Basic setup -------------------------------------------------------*/
#endif
}
+/* --- @f25519_neg@ --- *
+ *
+ * Arguments: @f25519 *z@ = where to put the result (may alias @x@)
+ * @const f25519 *x@ = an operand
+ *
+ * Returns: ---
+ *
+ * Use: Set @z = -x@.
+ */
+
+void f25519_neg(f25519 *z, const f25519 *x)
+{
+#if F25519_IMPL == 26
+ z->P[0] = -x->P[0]; z->P[1] = -x->P[1];
+ z->P[2] = -x->P[2]; z->P[3] = -x->P[3];
+ z->P[4] = -x->P[4]; z->P[5] = -x->P[5];
+ z->P[6] = -x->P[6]; z->P[7] = -x->P[7];
+ z->P[8] = -x->P[8]; z->P[9] = -x->P[9];
+#elif F25519_IMPL == 10
+ unsigned i;
+ for (i = 0; i < NPIECE; i++) z->P[i] = -x->P[i];
+#endif
+}
+
/*----- Constant-time utilities -------------------------------------------*/
+/* --- @f25519_pick2@ --- *
+ *
+ * Arguments: @f25519 *z@ = where to put the result (may alias @x@ or @y@)
+ * @const f25519 *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 f25519_pick2(f25519 *z, const f25519 *x, const f25519 *y, uint32 m)
+{
+ mask32 mm = FIX_MASK32(m);
+
+#if F25519_IMPL == 26
+ z->P[0] = PICK2(x->P[0], y->P[0], mm);
+ z->P[1] = PICK2(x->P[1], y->P[1], mm);
+ z->P[2] = PICK2(x->P[2], y->P[2], mm);
+ z->P[3] = PICK2(x->P[3], y->P[3], mm);
+ z->P[4] = PICK2(x->P[4], y->P[4], mm);
+ z->P[5] = PICK2(x->P[5], y->P[5], mm);
+ z->P[6] = PICK2(x->P[6], y->P[6], mm);
+ z->P[7] = PICK2(x->P[7], y->P[7], mm);
+ z->P[8] = PICK2(x->P[8], y->P[8], mm);
+ z->P[9] = PICK2(x->P[9], y->P[9], mm);
+#elif F25519_IMPL == 10
+ unsigned i;
+ for (i = 0; i < NPIECE; i++) z->P[i] = PICK2(x->P[i], y->P[i], mm);
+#endif
+}
+
+/* --- @f25519_pickn@ --- *
+ *
+ * Arguments: @f25519 *z@ = where to put the result
+ * @const f25519 *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 f25519_pickn(f25519 *z, const f25519 *v, size_t n, size_t i)
+{
+ uint32 b = (uint32)1 << (31 - i);
+ mask32 m;
+
+#if F25519_IMPL == 26
+ z->P[0] = z->P[1] = z->P[2] = z->P[3] = z->P[4] =
+ z->P[5] = z->P[6] = z->P[7] = z->P[8] = z->P[9] = 0;
+ while (n--) {
+ m = SIGN(b);
+ CONDPICK(z->P[0], v->P[0], m);
+ CONDPICK(z->P[1], v->P[1], m);
+ CONDPICK(z->P[2], v->P[2], m);
+ CONDPICK(z->P[3], v->P[3], m);
+ CONDPICK(z->P[4], v->P[4], m);
+ CONDPICK(z->P[5], v->P[5], m);
+ CONDPICK(z->P[6], v->P[6], m);
+ CONDPICK(z->P[7], v->P[7], m);
+ CONDPICK(z->P[8], v->P[8], m);
+ CONDPICK(z->P[9], v->P[9], m);
+ v++; b <<= 1;
+ }
+#elif F25519_IMPL == 10
+ 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;
+ }
+#endif
+}
+
/* --- @f25519_condswap@ --- *
*
* Arguments: @f25519 *x, *y@ = two operands
#endif
}
+/* --- @f25519_condneg@ --- *
+ *
+ * Arguments: @f25519 *z@ = where to put the result (may alias @x@)
+ * @const f25519 *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 f25519_condneg(f25519 *z, const f25519 *x, uint32 m)
+{
+#ifdef NEG_TWOC
+ mask32 m_xor = FIX_MASK32(m);
+ piece m_add = m&1;
+# define CONDNEG(x) (((x) ^ m_xor) + m_add)
+#else
+ int s = PICK2(-1, +1, m);
+# define CONDNEG(x) (s*(x))
+#endif
+
+#if F25519_IMPL == 26
+ z->P[0] = CONDNEG(x->P[0]);
+ z->P[1] = CONDNEG(x->P[1]);
+ z->P[2] = CONDNEG(x->P[2]);
+ z->P[3] = CONDNEG(x->P[3]);
+ z->P[4] = CONDNEG(x->P[4]);
+ z->P[5] = CONDNEG(x->P[5]);
+ z->P[6] = CONDNEG(x->P[6]);
+ z->P[7] = CONDNEG(x->P[7]);
+ z->P[8] = CONDNEG(x->P[8]);
+ z->P[9] = CONDNEG(x->P[9]);
+#elif F25519_IMPL == 10
+ unsigned i;
+ for (i = 0; i < NPIECE; i++) z->P[i] = CONDNEG(x->P[i]);
+#endif
+
+#undef CONDNEG
+}
+
/*----- Multiplication ----------------------------------------------------*/
#if F25519_IMPL == 26
#undef SQRN
}
+/* --- @f25519_quosqrt@ --- *
+ *
+ * Arguments: @f25519 *z@ = where to put the result (may alias @x@ or @y@)
+ * @const f25519 *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 const piece sqrtm1_pieces[NPIECE] = {
+#if F25519_IMPL == 26
+ -32595792, -7943725, 9377950, 3500415, 12389472,
+ -272473, -25146209, -2005654, 326686, 11406482
+#elif F25519_IMPL == 10
+ 176, -88, 161, 157, -485, -196, -231, -220, -416,
+ -169, -255, 50, 189, -89, -266, -32, 202, -511,
+ 423, 357, 248, -249, 80, 288, 50, 174
+#endif
+};
+#define SQRTM1 ((const f25519 *)sqrtm1_pieces)
+
+int f25519_quosqrt(f25519 *z, const f25519 *x, const f25519 *y)
+{
+ f25519 t, u, w, beta, xy3, t2p50m1;
+ octet xb[32], b0[32], b1[32];
+ int32 rc = -1;
+ mask32 m;
+ unsigned i;
+
+#define SQRN(z, x, n) do { \
+ f25519_sqr((z), (x)); \
+ for (i = 1; i < (n); i++) f25519_sqr((z), (z)); \
+} while (0)
+
+ /* This is a bit tricky; the algorithm is from Bernstein, Duif, Lange,
+ * Schwabe, and Yang, `High-speed high-security signatures', 2011-09-26,
+ * https://ed25519.cr.yp.to/ed25519-20110926.pdf.
+ *
+ * First of all, a complicated exponentation. The addition chain here is
+ * mine. We start with some preliminary values.
+ */ /* step | value */
+ SQRN(&u, y, 1); /* 1 | 0, 2 */
+ f25519_mul(&t, &u, y); /* 2 | 0, 3 */
+ f25519_mul(&xy3, &t, x); /* 3 | 1, 3 */
+ SQRN(&u, &u, 1); /* 4 | 0, 4 */
+ f25519_mul(&w, &u, &xy3); /* 5 | 1, 7 */
+
+ /* And now we calculate w^((p - 5)/8) = w^(252 - 3). */
+ SQRN(&u, &w, 1); /* 6 | 2 */
+ f25519_mul(&t, &w, &u); /* 7 | 3 */
+ SQRN(&u, &t, 1); /* 8 | 6 */
+ f25519_mul(&t, &u, &w); /* 9 | 7 */
+ SQRN(&u, &t, 3); /* 12 | 56 */
+ f25519_mul(&t, &t, &u); /* 13 | 63 = 2^6 - 1 */
+ SQRN(&u, &t, 6); /* 19 | 2^12 - 2^6 */
+ f25519_mul(&t, &t, &u); /* 20 | 2^12 - 1 */
+ SQRN(&u, &t, 12); /* 32 | 2^24 - 2^12 */
+ f25519_mul(&t, &t, &u); /* 33 | 2^24 - 1 */
+ SQRN(&u, &t, 1); /* 34 | 2^25 - 2 */
+ f25519_mul(&t, &u, &w); /* 35 | 2^25 - 1 */
+ SQRN(&u, &t, 25); /* 60 | 2^50 - 2^25 */
+ f25519_mul(&t2p50m1, &t, &u); /* 61 | 2^50 - 1 */
+ SQRN(&u, &t2p50m1, 50); /* 111 | 2^100 - 2^50 */
+ f25519_mul(&t, &t2p50m1, &u); /* 112 | 2^100 - 1 */
+ SQRN(&u, &t, 100); /* 212 | 2^200 - 2^100 */
+ f25519_mul(&t, &t, &u); /* 213 | 2^200 - 1 */
+ SQRN(&u, &t, 50); /* 263 | 2^250 - 2^50 */
+ f25519_mul(&t, &t2p50m1, &u); /* 264 | 2^250 - 1 */
+ SQRN(&u, &t, 2); /* 266 | 2^252 - 4 */
+ f25519_mul(&t, &u, &w); /* 267 | 2^252 - 3 */
+
+ /* And finally... */
+ f25519_mul(&beta, &t, &xy3); /* 268 | ... */
+
+ /* Now we have beta = (x y^3) (x y^7)^((p - 5)/8) = (x/y)^((p + 3)/8), and
+ * we're ready to finish the computation. Suppose that alpha^2 = u/w.
+ * Then beta^4 = (x/y)^((p + 3)/2) = alpha^(p + 3) = alpha^4 = (x/y)^2, so
+ * we have beta^2 = ±x/y. If y beta^2 = x then beta is the one we wanted;
+ * if -y beta^2 = x, then we want beta sqrt(-1), which we already know. Of
+ * course, it might not match either, in which case we fail.
+ *
+ * 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.
+ */
+ f25519_sqr(&t, &beta);
+ f25519_mul(&t, &t, y);
+ f25519_neg(&u, &t);
+ f25519_store(xb, x);
+ f25519_store(b0, &t);
+ f25519_store(b1, &u);
+ f25519_mul(&u, &beta, SQRTM1);
+
+ m = -ct_memeq(b0, xb, 32);
+ rc = PICK2(0, rc, m);
+ f25519_pick2(z, &beta, &u, m);
+ m = -ct_memeq(b1, xb, 32);
+ rc = PICK2(0, rc, m);
+
+ /* And we're done. */
+ return (rc);
+}
+
/*----- Test rig ----------------------------------------------------------*/
#ifdef TEST_RIG
#include <mLib/report.h>
+#include <mLib/str.h>
#include <mLib/testrig.h>
static void fixdstr(dstr *d)
return (ok); \
}
+TEST_UNOP(neg)
TEST_UNOP(sqr)
TEST_UNOP(inv)
return (ok);
}
+static int vrf_condneg(dstr dv[])
+{
+ f25519 *x = (f25519 *)dv[0].buf;
+ uint32 m = *(uint32 *)dv[1].buf;
+ f25519 z;
+ int ok = 1;
+
+ f25519_condneg(&z, x, m);
+ if (!eq(&z, &dv[2])) {
+ ok = 0;
+ fprintf(stderr, "failed!\n");
+ fdump(stderr, "x", x->P);
+ fprintf(stderr, "m = 0x%08lx\n", (unsigned long)m);
+ fdump(stderr, "calc z", z.P);
+ f25519_load(&z, (const octet *)dv[1].buf);
+ fdump(stderr, "want z", z.P);
+ }
+
+ return (ok);
+}
+
+static int vrf_pick2(dstr dv[])
+{
+ f25519 *x = (f25519 *)dv[0].buf, *y = (f25519 *)dv[1].buf;
+ uint32 m = *(uint32 *)dv[2].buf;
+ f25519 z;
+ int ok = 1;
+
+ f25519_pick2(&z, x, y, m);
+ if (!eq(&z, &dv[3])) {
+ 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 z", z.P);
+ f25519_load(&z, (const octet *)dv[3].buf);
+ fdump(stderr, "want z", z.P);
+ }
+
+ return (ok);
+}
+
+static int vrf_pickn(dstr dv[])
+{
+ dstr d = DSTR_INIT;
+ f25519 v[32], z;
+ size_t i = *(uint32 *)dv[1].buf, j, n;
+ const char *p;
+ char *q;
+ int ok = 1;
+
+ for (q = dv[0].buf, n = 0; (p = str_qword(&q, 0)) != 0; n++)
+ { cvt_f25519(p, &d); v[n] = *(f25519 *)d.buf; }
+
+ f25519_pickn(&z, v, n, i);
+ if (!eq(&z, &dv[2])) {
+ ok = 0;
+ fprintf(stderr, "failed!\n");
+ for (j = 0; j < n; j++) {
+ fprintf(stderr, "v[%2u]", (unsigned)j);
+ fdump(stderr, "", v[j].P);
+ }
+ fprintf(stderr, "i = %u\n", (unsigned)i);
+ fdump(stderr, "calc z", z.P);
+ f25519_load(&z, (const octet *)dv[2].buf);
+ fdump(stderr, "want z", z.P);
+ }
+
+ dstr_destroy(&d);
+ return (ok);
+}
+
static int vrf_condswap(dstr dv[])
{
f25519 *x = (f25519 *)dv[0].buf, *y = (f25519 *)dv[1].buf;
return (ok);
}
+static int vrf_quosqrt(dstr dv[])
+{
+ f25519 *x = (f25519 *)dv[0].buf, *y = (f25519 *)dv[1].buf;
+ f25519 z, zz;
+ int rc;
+ int ok = 1;
+
+ if (dv[2].len) { fixdstr(&dv[2]); fixdstr(&dv[3]); }
+ rc = f25519_quosqrt(&z, x, y);
+ if (!dv[2].len ? !rc : (rc || (!eq(&z, &dv[2]) && !eq(&z, &dv[3])))) {
+ ok = 0;
+ fprintf(stderr, "failed!\n");
+ fdump(stderr, "x", x->P);
+ fdump(stderr, "y", y->P);
+ if (rc) fprintf(stderr, "calc: FAIL\n");
+ else fdump(stderr, "calc", z.P);
+ if (!dv[2].len)
+ fprintf(stderr, "exp: FAIL\n");
+ else {
+ f25519_load(&zz, (const octet *)dv[2].buf);
+ fdump(stderr, "z", zz.P);
+ f25519_load(&zz, (const octet *)dv[3].buf);
+ fdump(stderr, "z'", zz.P);
+ }
+ }
+
+ return (ok);
+}
+
static int vrf_sub_mulc_add_sub_mul(dstr dv[])
{
f25519 *u = (f25519 *)dv[0].buf, *v = (f25519 *)dv[1].buf,
static test_chunk tests[] = {
{ "add", vrf_add, { &type_f25519, &type_f25519, &type_f25519_ref } },
{ "sub", vrf_sub, { &type_f25519, &type_f25519, &type_f25519_ref } },
+ { "neg", vrf_neg, { &type_f25519, &type_f25519_ref } },
+ { "condneg", vrf_condneg,
+ { &type_f25519, &type_uint32, &type_f25519_ref } },
{ "mul", vrf_mul, { &type_f25519, &type_f25519, &type_f25519_ref } },
{ "mulconst", vrf_mulc, { &type_f25519, &type_long, &type_f25519_ref } },
+ { "pick2", vrf_pick2,
+ { &type_f25519, &type_f25519, &type_uint32, &type_f25519_ref } },
+ { "pickn", vrf_pickn,
+ { &type_string, &type_uint32, &type_f25519_ref } },
{ "condswap", vrf_condswap,
{ &type_f25519, &type_f25519, &type_uint32,
&type_f25519_ref, &type_f25519_ref } },
{ "sqr", vrf_sqr, { &type_f25519, &type_f25519_ref } },
{ "inv", vrf_inv, { &type_f25519, &type_f25519_ref } },
+ { "quosqrt", vrf_quosqrt,
+ { &type_f25519, &type_f25519, &type_hex, &type_hex } },
{ "sub-mulc-add-sub-mul", vrf_sub_mulc_add_sub_mul,
{ &type_f25519, &type_f25519, &type_long, &type_f25519,
&type_f25519, &type_f25519, &type_f25519_ref } },
~mdw / catacomb / blobdiff