From 25f673625c9f2d3a323fed185f4b0c4b4a241976 Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Wed, 26 Apr 2017 11:53:05 +0100 Subject: [PATCH] math/f25519.[ch]: More field operations. Most are fairly simple utilities, except for `f25519_quosqrt' which does a combined division and square root. --- math/f25519.c | 370 +++++++++++++++++++++++++++++ math/f25519.h | 76 ++++++ math/t/f25519 | 641 ++++++++++++++++++++++++++++++++++++++++++++++++++ utils/curve25519.sage | 86 +++++++ utils/qfarith-test | 29 +++ 5 files changed, 1202 insertions(+) diff --git a/math/f25519.c b/math/f25519.c index 220a73c8..6dfc511c 100644 --- a/math/f25519.c +++ b/math/f25519.c @@ -29,6 +29,7 @@ #include "config.h" +#include "ct.h" #include "f25519.h" /*----- Basic setup -------------------------------------------------------*/ @@ -498,8 +499,114 @@ void f25519_sub(f25519 *z, const f25519 *x, const f25519 *y) #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 @@ -533,6 +640,49 @@ void f25519_condswap(f25519 *x, f25519 *y, uint32 m) #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 @@ -913,11 +1063,119 @@ void f25519_inv(f25519 *z, const f25519 *x) #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 +#include #include static void fixdstr(dstr *d) @@ -982,6 +1240,7 @@ static const test_type return (ok); \ } +TEST_UNOP(neg) TEST_UNOP(sqr) TEST_UNOP(inv) @@ -1031,6 +1290,79 @@ static int vrf_mulc(dstr dv[]) 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; @@ -1056,6 +1388,35 @@ static int vrf_condswap(dstr dv[]) 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, @@ -1093,13 +1454,22 @@ static int vrf_sub_mulc_add_sub_mul(dstr dv[]) 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 } }, diff --git a/math/f25519.h b/math/f25519.h index a70ca2df..fc755464 100644 --- a/math/f25519.h +++ b/math/f25519.h @@ -108,6 +108,39 @@ extern void f25519_load(f25519 */*z*/, const octet /*xv*/[32]); extern void f25519_store(octet /*zv*/[32], const f25519 */*x*/); +/* --- @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. + */ + +extern void f25519_pick2(f25519 */*z*/, const f25519 */*x*/, + const f25519 */*y*/, uint32 /*m*/); + +/* --- @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. + */ + +extern void f25519_pickn(f25519 */*z*/, const f25519 */*v*/, size_t /*n*/, + size_t /*i*/); + /* --- @f25519_condswap@ --- * * * Arguments: @f25519 *x, *y@ = two operands @@ -148,6 +181,33 @@ extern void f25519_add(f25519 */*z*/, extern void f25519_sub(f25519 */*z*/, const f25519 */*x*/, const f25519 */*y*/); +/* --- @f25519_neg@ --- * + * + * Arguments: @f25519 *z@ = where to put the result (may alias @x@) + * @const f25519 *x@ = an operand + * + * Returns: --- + * + * Use: Set @z = -x@. + */ + +extern void f25519_neg(f25519 */*z*/, const f25519 */*x*/); + +/* --- @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. + */ + +extern void f25519_condneg(f25519 */*z*/, const f25519 */*x*/, uint32 /*m*/); + /* --- @f25519_mulconst@ --- * * * Arguments: @f25519 *z@ = where to put the result (may alias @x@) @@ -200,6 +260,22 @@ extern void f25519_sqr(f25519 */*z*/, const f25519 */*x*/); extern void f25519_inv(f25519 */*z*/, const f25519 */*x*/); +/* --- @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. + */ + +extern int f25519_quosqrt(f25519 */*z*/, + const f25519 */*x*/, const f25519 */*y*/); + /*----- That's all, folks -------------------------------------------------*/ #ifdef __cplusplus diff --git a/math/t/f25519 b/math/t/f25519 index a2264bc6..96d4ac77 100644 --- a/math/t/f25519 +++ b/math/t/f25519 @@ -138,6 +138,574 @@ sub { c5f42c73614ca5377a0ea473c6bc4ac35e696855b9685b10dd64ad2ae42cf467; } +neg { + 0000000000000000000000000000000000000000000000000000000000000000 + 0000000000000000000000000000000000000000000000000000000000000000; + 23d767107e23d5ce14189cce939c4b5334d6736da3da40a715236b9d8319efc1 + b72898ef81dc2a31ebe763316c63b4accb298c925c25bf58eadc94627ce6103e; + 9bb944cfb58b186cc551e0a0eca74528c7618ff47485bf6a723f43d990f69f6e + 5246bb304a74e7933aae1f5f1358bad7389e700b8b7a40958dc0bc266f096011; + bff36d2aa923d5a9af5398e2cfcba4acdf3c3181a8ff00b8a1099cd97a4e8542 + 2e0c92d556dc2a5650ac671d30345b5320c3ce7e5700ff475ef6632685b17a3d; + 1b65a51746eabb7c0d8d9844dda03bde7128407e94661db2d5fd9c0f3790d120 + d29a5ae8b9154483f27267bb225fc4218ed7bf816b99e24d2a0263f0c86f2e5f; + 88f4cf29a610c4465f63a272fde2f19a4874a70a0829885014379b637ab0e82d + 650b30d659ef3bb9a09c5d8d021d0e65b78b58f5f7d677afebc8649c854f1752; + 94ca4d567efcf088e6bf1cb3698f6b8bf2164db4f523e28781aebfcbb501ec63 + 5935b2a981030f771940e34c967094740de9b24b0adc1d787e5140344afe131c; + 3f8d7ae4f1698921524e49ccb2ce4459e4c048f76f04c5e60179f5417d2d52db + 9b72851b0e9676deadb1b6334d31bba61b3fb70890fb3a19fe860abe82d2ad24; + 1eaa0c45af0d8f85d865cc66ff3d0dc3355f1ac36821cdd95a6b9232a27f9044 + cf55f3ba50f2707a279a339900c2f23ccaa0e53c97de3226a5946dcd5d806f3b; + 33e142c78ee87a7980ade6c796e7ff949cee6d3af0415bf5b6901f84c2db910a + ba1ebd38711785867f5219386918006b631192c50fbea40a496fe07b3d246e75; + 24a0c185c47787caf1a666a62002a503f2a3e591e5f2946e148a47b9b114a884 + b65f3e7a3b8878350e599959dffd5afc0d5c1a6e1a0d6b91eb75b8464eeb577b; + a8bd0c1c3f219a97de87b22e8cb3eb5daea33b5646589b6925ec4ec83ca37455 + 4542f3e3c0de656821784dd1734c14a2515cc4a9b9a76496da13b137c35c8b2a; + 1a340d2679ca205f6b198cff4bffadcde1afeeed124ef0c574655dbe8732b681 + c0cbf2d98635dfa094e67300b40052321e501112edb10f3a8b9aa24178cd497e; + da43c139a1f92ba1b5fc996befe5218368eac3c46b42e98a9cca8b8f6f1540f5 + 00bc3ec65e06d45e4a036694101ade7c97153c3b94bd16756335747090eabf0a; + 81aad864a31e5f4afa32c29eb97f22c103dfe5b1323db05fc9b1545312aa6c0d + 6c55279b5ce1a0b505cd3d614680dd3efc201a4ecdc24fa0364eabaced559372; + 28231ad38d214f1421df7005eddb4f4c12e522b10d1cbcd10ee26dfcc222a62c + c5dce52c72deb0ebde208ffa1224b0b3ed1add4ef2e3432ef11d92033ddd5953; + c1facefef35c1ed00db767ed0281ebfad1f3c915c6649f5e1c26a6f3f9478b43 + 2c0531010ca3e12ff2489812fd7e14052e0c36ea399b60a1e3d9590c06b8743c; + c2e4046e7200386ca2afea8ecc9c98c105fbf6e31b598e21e482796a69956040 + 2b1bfb918dffc7935d5015713363673efa04091ce4a671de1b7d8695966a9f3f; + a42fedea4eac90580a0bbcb0491a7e8cc82de7a99aa74ed35f705c536afa0236 + 49d01215b1536fa7f5f4434fb6e5817337d218566558b12ca08fa3ac9505fd49; + d1ab8c50d54279ceac870d0ce4a2af56bf8c03e87482dcb7775183a4908ac739 + 1c5473af2abd86315378f2f31b5d50a94073fc178b7d234888ae7c5b6f753846; + 1ffd85fa5ead53ff509756fc28051ef65eca040303b65f7b5b7e1d1a8508e030 + ce027a05a152ac00af68a903d7fae109a135fbfcfc49a084a481e2e57af71f4f; +} + +condneg { + 5330763b29dff20501a1d6c64025c36279083473721f5cacf89168189ff9810d + 0x00000000 + 5330763b29dff20501a1d6c64025c36279083473721f5cacf89168189ff9810d; + 9d9c36e2126d911a503e1cc1a8489ee74949ae2a8408dc7d72ed0d75e4350545 + 0x00000000 + 9d9c36e2126d911a503e1cc1a8489ee74949ae2a8408dc7d72ed0d75e4350545; + 47da10abec2cb54c5890e5945999deb1d89ffd268bbbe2eafc86f1acc8bf5f7e + 0x00000000 + 47da10abec2cb54c5890e5945999deb1d89ffd268bbbe2eafc86f1acc8bf5f7e; + 3e6ec07de86be6ffab2dfa1deb9ed67844645be92bdbb22b7ba91379babcdfed + 0x00000000 + 516ec07de86be6ffab2dfa1deb9ed67844645be92bdbb22b7ba91379babcdf6d; + 5f5c0730649586b5c0b60a14d3b669b3649eb6725d71d834e78ff2aa0e5450e5 + 0xffffffff + 7ba3f8cf9b6a794a3f49f5eb2c49964c9b61498da28e27cb18700d55f1abaf1a; + c357befcc6836d89387915e368e5e6162252b433eb58d94eb3cc4b783e98c226 + 0xffffffff + 2aa84103397c9276c786ea1c971a19e9ddad4bcc14a726b14c33b487c1673d59; + 713ad0f656a8fcd75fdee2c4ac248ee7ad09a5f357c565daa94ae46d8590d2c8 + 0x00000000 + 843ad0f656a8fcd75fdee2c4ac248ee7ad09a5f357c565daa94ae46d8590d248; + 909d669185e98b4a88a6531b830193b23035d64665929e34e86d53c4a9eef30a + 0xffffffff + 5d62996e7a1674b57759ace47cfe6c4dcfca29b99a6d61cb1792ac3b56110c75; + 8f23ec139f93258e6d57fa278339f1cb5da193c5d1ad7183fb2b151111262285 + 0x00000000 + a223ec139f93258e6d57fa278339f1cb5da193c5d1ad7183fb2b151111262205; + a9a5480c72157f389be80ae7ad63502434c380ccd1cef813dc9bd2e9a85e2f22 + 0xffffffff + 445ab7f38dea80c76417f518529cafdbcb3c7f332e3107ec23642d1657a1d05d; + 316f98b6697e7daa8775d3aa91dee8fbbae4e935a2f62cd2975e2d552f0c9846 + 0xffffffff + bc90674996818255788a2c556e211704451b16ca5d09d32d68a1d2aad0f36739; + 70128d6dd5fb42f287fba3533c71cb5dc2361b6d91c3d9626c58849e27f7d349 + 0xffffffff + 7ded72922a04bd0d78045cacc38e34a23dc9e4926e3c269d93a77b61d8082c36; + 66a6f3dc6274e4122dc401ef23529175d71d96b660a52cdcd64556073b5430b2 + 0x00000000 + 79a6f3dc6274e4122dc401ef23529175d71d96b660a52cdcd64556073b543032; + 3909505812b228e6ca5cc6c0b17824ef765923eded6105e6eb0f176781624c5a + 0xffffffff + b4f6afa7ed4dd71935a3393f4e87db1089a6dc12129efa1914f0e8987e9db325; + b7febd7d63efae3bcc60c1c344f2f6166b272eed785a9e541d3ff4f12e82a5f3 + 0xffffffff + 230142829c1051c4339f3e3cbb0d09e994d8d11287a561abe2c00b0ed17d5a0c; + d1cacc1db40de13351224046975319d7546ae9e88e1909c2a8f46792a140d279 + 0xffffffff + 1c3533e24bf21eccaeddbfb968ace628ab95161771e6f63d570b986d5ebf2d06; + 4c449a50fc1e145be1463e4c171b3c51c9683c41c45005d8aeca607911c9b3be + 0xffffffff + 8ebb65af03e1eba41eb9c1b3e8e4c3ae3697c3be3baffa2751359f86ee364c41; + c929c50eedbad6ceacdefb00bd58a32820c874c906741e9d93cd0f668819edcc + 0x00000000 + dc29c50eedbad6ceacdefb00bd58a32820c874c906741e9d93cd0f668819ed4c; + 1c57449dcfc7e8f9fab77d226d4b50d7dee06c29d08d3d4f4ae7c8ad238a0a82 + 0xffffffff + bea8bb6230381706054882dd92b4af28211f93d62f72c2b0b5183752dc75f57d; + 396a2ddc48f158e73c95dc289da3f0d3b2128875e20c401cb50fd6cc7a28dd18 + 0xffffffff + b495d223b70ea718c36a23d7625c0f2c4ded778a1df3bfe34af0293385d72267; +} + +pick2 { + e6f52222f35081896f3d9ecc0ffb27fa3e75c8ad1c98e161878d2c3cffd72c78 + a24cd71f7acb653466b7d67bb41efb5a29503d2627d2ce28fe19680ccd939be5 + 0x00000000 + b54cd71f7acb653466b7d67bb41efb5a29503d2627d2ce28fe19680ccd939b65; + 4e51fe2dac96a664d0675962116b7af4e605194a1c9fb774c621a3107994c9ed + 508934be10ce5e11e6940d56e84b148e20f48369e748536846763c80bab9af49 + 0x00000000 + 508934be10ce5e11e6940d56e84b148e20f48369e748536846763c80bab9af49; + 530175217081c3fb3ecd17702ad334ad48f05affd5ab3754ef10be5b0eb5375d + 8aebc7e01e2bb2829f21311462175948d85cd3e65d676eec893e3df13f639d07 + 0xffffffff + 530175217081c3fb3ecd17702ad334ad48f05affd5ab3754ef10be5b0eb5375d; + 0e53c5141d72c8c81d80b1a1283b0267b278f98e28ce08ccac7b010022e5adae + 2215cc15e950d6abfffa26113f269628f50f9ac37ad3260ae9189958d75080b6 + 0xffffffff + 2153c5141d72c8c81d80b1a1283b0267b278f98e28ce08ccac7b010022e5ad2e; + 3dc16434679d30686d5023fda4cc574563841caf1d588e965fe1ec1c4ba54398 + 4ca50330751d33ebba981277926a3fb801d216474cb183f90947680f5ea383a2 + 0xffffffff + 50c16434679d30686d5023fda4cc574563841caf1d588e965fe1ec1c4ba54318; + 09e68cb66b5ae2f3160a71738d1e9a042b9b76335eddc4b9466d0c6b8100eeb6 + 270eb833ae635bed17df9218a53a91b7afeb74f0df3bfffb8334c04773cf716d + 0xffffffff + 1ce68cb66b5ae2f3160a71738d1e9a042b9b76335eddc4b9466d0c6b8100ee36; + 831b8a99e3b44bf21cdd4f3c06da7c16a95e98f3dc42cf2ac282edec67d9b2ca + 482840e31c7620de6d290d747afc63ca199c60169f8eb62d28ca1142c5336990 + 0xffffffff + 961b8a99e3b44bf21cdd4f3c06da7c16a95e98f3dc42cf2ac282edec67d9b24a; + a022ace6772d82d30832328c7cbfedb622b710d1fe9313a77dc4cc5ca577a7bb + 39c86c57bf581c16d8c03b4ef0fe813815b5da1281f03bb3f2cdb0ddf19868d0 + 0xffffffff + b322ace6772d82d30832328c7cbfedb622b710d1fe9313a77dc4cc5ca577a73b; + 719d3f13c38b915873bcb14308bfd9bb6f4a6cfd249a745bceb55787ce480caa + c72de6e206ed24555d091763644d4405f2ee5dbd846a036d6a21442a6c40e0c6 + 0x00000000 + da2de6e206ed24555d091763644d4405f2ee5dbd846a036d6a21442a6c40e046; + 07cdd3cd677a3c1783bcf7855bf1dbb453809b66c66c7bbbb67690cea33ca581 + c9d889281ac117390875739e4b62df6dc3cca6c65439c46bb907c81d3a961fa3 + 0x00000000 + dcd889281ac117390875739e4b62df6dc3cca6c65439c46bb907c81d3a961f23; + a69a728035cc69d5d3f96dd4a8081864333e53e434820dd569deb9e58393d4b7 + 3f4ef71dfa1eccd817d3192dbe2e08466e4a66b4d836b0892b3636dc523098ed + 0x00000000 + 524ef71dfa1eccd817d3192dbe2e08466e4a66b4d836b0892b3636dc5230986d; + d249414415ac4960e934d29e08c75ff1b18431a6e18f7404e638293d3d8e81d5 + 33cd02e07762f74976834d1b6dd3b8eb7e2ad7a5d04ba90bbe747476071f10cb + 0x00000000 + 46cd02e07762f74976834d1b6dd3b8eb7e2ad7a5d04ba90bbe747476071f104b; + efb782aba4dca351a5c9279b370073840b977b2458c6c84c9c9046dc92cc5507 + 6d9f50eb56b84989aab77c54987f05c715b74185417863f2c275635d2d6f2eeb + 0x00000000 + 809f50eb56b84989aab77c54987f05c715b74185417863f2c275635d2d6f2e6b; + 10c4381ed467e27d756ff7a260a6ffd282ad757b10c9956c518a43117699ee91 + 9b9a70c67be3296ef9d65fdd8014c4b263c28fd31f3299f4461c688c469ff704 + 0x00000000 + 9b9a70c67be3296ef9d65fdd8014c4b263c28fd31f3299f4461c688c469ff704; + 5a30428bee407ee673ec7d2cb4854efd80b9761df5dec906463f888f60be7152 + fc2e139be53203eb73041e9335253534c420208164682c2e02f31f084f5582f0 + 0xffffffff + 5a30428bee407ee673ec7d2cb4854efd80b9761df5dec906463f888f60be7152; + 43c7cd903c7dd7cdab85c6b5585955163e0da7dd0c5b5882ac620246619af342 + 0eb52162c69425ad75b778c39746014789f7929119d4e122d4b98bf64784fcde + 0xffffffff + 43c7cd903c7dd7cdab85c6b5585955163e0da7dd0c5b5882ac620246619af342; + f37f3707e4609d389096c1fea551b572a6b4644fd6af2e9e7a0fa93a91ae38e5 + d10dd4d911346a5952e3123d4f156a7e40807d142c4afb4bc314ac6f9346dfa8 + 0xffffffff + 06803707e4609d389096c1fea551b572a6b4644fd6af2e9e7a0fa93a91ae3865; + a4f4c203cb892691a6d6e9dff8a10ac1a8d9470b13ba24e1bddac05d6d7f9c0e + b88145fabdeaa9fa108bb04a4d283ac034b4c8d8ffe1b2174de9a80254762c54 + 0xffffffff + a4f4c203cb892691a6d6e9dff8a10ac1a8d9470b13ba24e1bddac05d6d7f9c0e; + 649d8ce64f623228553de99b823c5f5c5ef37f00e2ddf658fc9bc2405afde715 + 0f24ace92223d2db75e2d82e8a5bc8b0e7981478216b999d2bdde9c72732d58f + 0xffffffff + 649d8ce64f623228553de99b823c5f5c5ef37f00e2ddf658fc9bc2405afde715; + 3f466e24ed4169ca3df624d747f054f97422d5eee3fade2fa3c4eba488694a6c + 37e3171c9aa56d07ffcde4f1fd0fdcc41e2086ecf93c9e53f3f6a4c3e4db587c + 0xffffffff + 3f466e24ed4169ca3df624d747f054f97422d5eee3fade2fa3c4eba488694a6c; +} + +pickn { + "91aaaaf3ff9e58f299c0f6d0a4a3851d100423e4b7380d5a32a86cde6cb19562 + e586b4ab140cd20bfc70aa5ae1c389941a8c631ce033f54793d77c91b5e3d50b + 911122291921aced748e1346261ce8dc0e50704bf59495c3d7c1a9806ae58b5e + dac7c42fc0253029c78310ea1508b2464db2c44689fa7d485fb5863b7c136f15" + 0 + 91aaaaf3ff9e58f299c0f6d0a4a3851d100423e4b7380d5a32a86cde6cb19562; + "e8864778a3aecd6f35f8afa097072e94c4e50680baf91a6036f4f24fb0dcf111 + 5dec44933a517f5a8bf6d858920e1200c74e65132baf0d08ca033e36e15a1c46 + 4fca88e6d122c0a460b5dd502281d80616edd30bede891226b4b3c4b3eb9eea0 + 5fbf4e034d45326d89ffe92bf4738a7120c63ea42568c25acacf4dd7915b9e8f + 343001277d416dd31dc770232fc47c7d02884fef3fc10eaddf6f8b42fbb00b26" + 1 + 5dec44933a517f5a8bf6d858920e1200c74e65132baf0d08ca033e36e15a1c46; + "f0cfc16fe0cb8910c26f6f46e69954dd34277d171044140c2dc448b6f63e053c + d54feccab8d55297eb24f622818aaa2ac5b7fcafee5efe872bb600cbdce85a3a + 5f1cb6c6b4e8eedb566150a99a7c92228e7f737efa1810b9d40f9a4ea020e56d + c762a32a3f3a6f8cd956412eacdaa75ee56b347b952a7c18dd19c0ee2e50b8fc + b6e76d1d2cdf04692036f26515ca6b92d57b1bba625f07553d2d4adf89de9611 + 874c9e94d425fe9590aa1cde396ec56531342207a0e3b42ef0ae710bc9b68418 + 872ebc0bbd45d07727887aa8116a5743880093c73b3048c3b46920c04e0f64e2 + 9cde037629d20a4481ba7050546eca2dfd293b0953aa708764531bd8d0fba387 + e9f7cb8ed4af14ac61722de66406e97ee9a87d9362dfa87e489a9c98f8b891b6 + 6c5bb4410d83505ad34d10409d02fc005a47ef802b5d9130f3b5d385ff78957e + ff40983b47e7263665a03e4396421fc34209afaf52d7d69012833b4a228e6c40 + 4588ed141f6401c460ff6ad4888172c9d19f15f214d96bedd59f818d7c03b720 + 99ede977304bc4e8f5edc44463b48fc13c001f5c584f2b100c791ae472fdddba + 8ba76d6aa98a062e1091ca60e05ecf21208657bf287f20c6cacaaeff41a537ff + a18760b118187f5b392637dd5c5f97ccce583b5b84b69f8e37d8caf77c616db0 + 7e921cc5caa3b3884358cb0ffd2d9d160ed54256049fa1540d861dbb6dd1631d + aa8102188fbba89c45259c52080b3969c234d070411bc4b91870a8b482eedfbf + d98da58b248507edf310beb9fb522dd23d88bc0412ef3b5bd7a13b7a15070647 + 0626183221836da09c9bb5a1dd07df570883af17a9a8fed1c4bc7e8770e348fe + 16b01a5593b3eaf0902d0ade7e00da7b7a57556c2e7169e8b6ba5df5c5fb02a5 + e40715b07034e109d79a95a8b031eebc6c59dd0bb77de6cb960fe65a6d1be59e" + 20 + f70715b07034e109d79a95a8b031eebc6c59dd0bb77de6cb960fe65a6d1be51e; + "e30f85631b4ea4aadb9487c76cbec40ab63101a482e5aa2e3ee329fc21071bf4 + 8bc9fdd41fe1ecf5c2cc2075c72e4ceab370b099ddc672ee16bbd7a7de19dbb4 + ede086a76fedddb463d9f0fb44b39ac7fb64665061eb96015d4ed39eb33cd772 + a7cd74dc0c94aa8bfa480a88396b7f293f1ac329e4ce79e04507be4edbf4fef1 + 45f5c114a46bf0b2c8be1ecb8fc7c81e7fef668a2e4e9769f2f2dfecf405af92 + 123d101a02348f81088beeb6fafb7f720b49631736829d2f19e95b8d833684a3 + ba936ae1b5555b05601c2e59bf9585846ac01b5b7f6fe4bbd45e0653e961deaf + 51c0c307d99e34a617ead92dd37e1a0f36ebe2e45ef5b3690fd114099d483dc6 + af94cee7979c057995680c3a5adfe26e7dea759e2640b0b09aff383fa355d289 + 6ddb6908532c513f463473e449747f88d47766460ad316734c2cca87963b3060 + 88192953b60710667d47633be71d87214d2dc8be882ceb6928daf311499d2e83 + 37da1b76c2c16025f0644b6451027c8bc9768379c3aa7ab8410d34d8c8222706 + 1a46c0531cc13f546e001a67721931f4f6bf8eeeadaaab667ee651db0b272509" + 7 + 64c0c307d99e34a617ead92dd37e1a0f36ebe2e45ef5b3690fd114099d483d46; + "9929839bce983fe53c4f8f9d07a462f82e8eebabba2c0daee1378abf585bb53d + 4e47d3997d6562c7b0347acc96925bd1907bf3a9c57d51b099c4a574d7bf8fc7 + a0de02656ba18dd1cfdb2938fbb864f9f59001110391ee1818f5c1dfee64f61a + 9c4153154f5b827bb847edfa04ce754e442f2e96ea001fc27f6d94ea8b06fc00 + 7ba90562980966abd857be3a84c1bffeabbb589415e722e51225f8317e829777 + ac4657b264ccfad4f5ba3f7a470458101d5c6025c45d00191ddd4bf85ca48705 + 8b11cfc6ceb02c5d4b3e19c19f1ae745fd0cdfd9da1a80e9df1be8f7bb99ace3 + 1202bae1f86d05ed8fca09965bb1cfa3fb696a3f2b7089ee10589394639da2bd + 143f799fc9ebec77aa444eb5ec95f64029cf61b875a2f94e228323844cb8eff9 + dcf99568b397db79bd2e8ae49778e1e49865e91525f932a1813d1c395420a43c + 84fdfee8137558f0b9f2441c375fce466e3212c0d0de3179919fb130e61b711a + 602454ffaf59610f76863a7456146f866539740d6dae63a3628d408e34db8e76 + 86ae4475d41ea312a97c821ac78b815e459dc6bb4d52c236a39e5e53ff17f5fb + 0fd56e878b74a2daebc2acc30c31c279f3dab146d748e7aa9b17eda7ac039c8f + e559e8bbd51113f84ebbe35ab16bfd46cf610a5c61307b986111ddbee3037f7a + bac90f3afdf4f4828368090958aef5e49aa83d25fc5dc15d9b8a354a30961e75 + 253eee8f614306e59a31d9fab5423ea269b67babd54c52243b86b8af1372f3ab + 69828b787af1831f772a3bb9a410dac8bc47909ac6bddc94a5c600a3167ce780 + 1903e9ca239847045875b0bd4e1575a724d9f729e3cbfc377de17ad29839a121 + 57bc65c0fd8495014f31e3be740967f3fd1884bee743b20b947339923530d63d + cf7427ebf6088e6f3385275f993b5c06ee14f738b59d49ecc327521ddced2a4a + 74c2a4122225e97b646d6a38584626a6ed811506ee7cd00b48ba563b7a776380 + 604f163d7d7f4987c8aaf2e7a946cec1597ebeb59aaeaad0dbd0737527b9350a + 30e7ae69cd5fb42ec00ca840988a59bf5688aa0b810bb2e9ea24fb5b322891a0 + 68caff542deb61b055bf65127a94d8ab107f5d2496764f97351dbbfbf34928e4 + c0d307ece7f18150d958bd88bf11912dc818fac7cae06ca9ec3fafd15d452af8 + 731b9ae286f29660fd0814568351bd6da114f3ee8b87c217cfe531746faa8c90" + 8 + 273f799fc9ebec77aa444eb5ec95f64029cf61b875a2f94e228323844cb8ef79; + "85b3448d0292edc0b14cfae9225989a16a61ee8441166d5b97faf876b0ab6c7d + 88b0f7c78f8390b6cc1de0afda111326dbb41e7603b82033902eb56ea542c2dc + daf45d38b24294648a7b203758ff0654d42507e958bbd98c72229aae0a9e5757 + 98b44fbbf6e45c81c2473b626307506881a9fa609c546741b3637b731ff62adb + c0779c0f0a35658998ee9cb6b0cb6b7e089b7f288ea171c18bd2664ca5c3fc1d + 8da42494a2c1e2034d2009fd486cc230085fcc8af171e2bc2cf428bbf9b4bc86 + 6dfb99cec539941c9e7d26e5640641e4ef2c3f1a732f9c85759858a95c346ea1 + 471a369f8d1d3341ac707f1c41e5f0655cae51d8a170037ee349b3c14e01be2d + c1b75b02941ae0c2e398a2c8871955c8306f6ab88cdc6d751e11b35605d10829 + ea508e41e33ca0b03b5d93a54ec359e01a5a00a98a80f7e6d998641a6cb7ef58 + bb009a72b5d5be344a3ba9509b6e8eafbafdab4b0ec9202c8d29983935c6937a + fdce2ff0df8548fd7df3b8a087aa30c819af0eff3b8931e5ddedfdb0f4450919 + eea3990f7f4045a3b6cdae27e4dc8a8062049ac4423ce46108ab464d866b80f3 + a18000f37c8c4a30195e71864b14f170a3f5c427f4769c736fbdc18b3fe68887 + ba9aa19e99a69b34f357f92d95a6c409f1bb331d1d27b693164cd0dbb552c771 + b5863e0215351b2f9b6f661ab94c833016bdef73a34b100b6db79ea8d4b22ec3 + 983eb31be6cd1cd4cb53e489e4535683e21c00e6c52f685e84bd3cfc98f9ab2b + c31c18c6c12feb3be4e51a1671fa6001c1dfadc0ebb35349766d9d07d5a70025 + 6f81695294071c711947499c2c3d96969a70948c29ea9506ff675d25052f0950 + 3b42ffd7fb054072e7fb93bfa63d24511e6c93455cdd5b9be3c8382a3cdbfba4 + 6d7463ce0227e29a2706b8ad6be0d6cefa173c261697520b23edb87a189d31eb + f6cea0722a490515f48632f42f167a911ba00fd9883604e52d713210f3d9475c + 6281bf17cc14876c75e9620d8bb9bfd6e4dceae1ad3cb675769f94623ab3a955 + 2c943465a6d4484c71b2c5ae26e1d738059667093450cff54e6b45f12a7588f4 + 3d9ba6aad36754c5c767a0f288b6dbfcd2f1e21bd14094f4ddfb7c4bb79ef882 + 052e95ca0672218808e36c18e1fdee412a945ad735ea883abd527dfe8343a51d + 3f8ec0ccd82005e01ffd1fd7413a2a1dce1a177cf53474904cc46abdffd22a22 + 2030168387fa230e7a77eae5f051b4e0f1cbc53a78a5df640479c9fc373b9d78 + 3abd6a4fb5a585bb1b4609cebbbd1035392c7565654331a173092c098e1583a2 + 6bceb64086f3874854b4c89d31d20d8772b2f48be6a5fa1fe572be9927345103" + 2 + daf45d38b24294648a7b203758ff0654d42507e958bbd98c72229aae0a9e5757; + "8a9e76766b2eeda9b4de923344005a825bd2475bc4d529b033de3510cd405b73 + 5206880a0e1c282a10e03253c787e005bc9a18613b6e238f1eb72c604844a2ab + acd4fe99d1df199ca20c743238a2bf9562ea4de7b82061d1a6861d77146bdfb8 + 6dccfdff241fd837508913d7e0b1ca3e7a426be578c2e82612f7d2b2491f08f1 + 76aa8f5fb4b3592ff58785ea27d287fa5f250fb84fc9838fad8d6a2cfc223dad + 71019d81508491afb6a33d8c99aba13d59c63bb88a2ba1182c144f171ed5a815 + f6ab8f0b95fcaad29def12e05f348a9a35449c7ef5e2859748e69c517f4f3f65 + 237b33cbba9ebcae93f8a4fd863f62a03651be2e936ddb5a62dd3b6a68734b2a + 4bbe3113be34a9f7fa26dd96258d1776797b8ea454a2f596ae076bdc0f5d0ff0 + 19ae0acbd7ba59869b51caa13e1041bcffed633235a858f39d0d583575a64123 + cc5e18fdfedf9a416727f81b24a227c0c0771565fff69fc3e19399a254d8c9c5 + 50765357fa421d9153c1f02adcc98f188d2aac6a39fc8d522c5e81fbb775bdbe + 10e3e53b7605240cadc28c4d3aeb1afe40b7d1d547f4ad60c8d03006b42fb499 + aec6bfd729a6e2898890c9ee15338aec209c94141dad7b7884f7be481a2f0d6d + 8f9620a5b985a3a1dc4825f1f4c683457a98f799118691bc57b17ab42713b593 + 92c24c6920edb4f37e73dd795ac9bbfcd8035dba28421fce290109c222bfbc86 + 45bdcd99b590e64aeb5173c7538e77a7cd10a9d786338c43e3a0946b33a9c822 + e0b86e6b4752ea2cae053b1bd897c6d749c7fa46308be876b8006c3ffa2d6479 + 6cb53b7769f0da52c697c8640c029099d84afb55c20c9ac84b959ff36c339e92 + a21436f9a4c876375d16c41bd3780f024b867f6fe6394c5c64b4ea5a6f306c7e + 93b40e751d291e90ec3adf902935285a5746781bfc1c594d520dc5828ba53d3f + 6dc080d82251557b9804deeaae90bb1a45d9895c5067f3b04dbfcbb5ab0be3e2 + 22783694c9ab9d652dc216306ea4fc09734e90bd08625e688b9bc1b8c73e3366 + 078b0d30cc5fbb248a5e84a416a3d849772ef6eadf20f73eeb82125f68a216e6 + 83dd79bd150e5f7bf7a357236ed41ca06b8c40bcce840e118f6cf457ff151654 + 72169420815aa9a38719072be9c824d68a0cc5d6b4251ff9180938def3dcb0ac + 63f1febc1579b537b71e1fd12687ec49885dbcf93db68f44660bca4780ca9aa8 + dc337f8a3699ff549dfa26c1a5ddab43cdac7062d90fc2a779ff528c414035f7" + 16 + 45bdcd99b590e64aeb5173c7538e77a7cd10a9d786338c43e3a0946b33a9c822; + "aa199ae7d7c298e11aa74e5bcff2f206fe6b53962f3bb39767ad6df19c58d93d + 4b95d1e296609760e06e7e476af7182db41712d73be94a3533b7332a7dbb780d + b72f91cbf1117db1982b035f0e76e51bf4cd8e968b932606450bdae0d588906b + a1de9fc4d0e579aad319de0280fb45b5fed6c9d38dab5216ff8401376fce0230 + fc216489a815b0c98969118c9ada3f7152c4eb07217abe54fae4fd4d63e96811 + b660cb7ac499821dc872c3400fb2590527659ecd72df16c7ec5376075fca7d7e + 3bbbd9dbbc9263d289de49b1648fd64751d8b0e6d5d506a356fee0ed6452ce89 + d17efdc8cff826d28ab55b51211209a27054f2d33f108f34ce7bdc5c71b918e1 + 21da90e37be817920404ff5015346dd05ef32e018632e09b7cea35d42eb1de1d + 66da40ef6fae8df49b5aca9a2400ea4fba527a9513c821e00985625615e71416 + 61e5b60766ca457b36aeca26a62e6f4831691ef79bdc72158c2a2b85fe3b5cb2 + 9a0917795f936a5384c4a504b2ba3d7056906ea4e34474c310b873f88890bd37 + af65ade7e8f0022420932d50d0a8587c43ac4436bc511248358886e2c7072c1f + fadd2a9fa72f438f147964180ffba490beaa55baf6275d8ca347ce5f5f94fd05 + debd9beec2527f284790a9ca8fbc074ec359f4a89974c2ff49780fcb21c5ea91 + f6a57794ba1265d9974e52f856acd3dddd0f6a50844172466c82f0d49eef676d + 97cbe03e723431b6c14bf1681e845d530e083ddaa26f055d3e162615f57c113f + b89054ac8b7135c1e6d215e4e5dcf679298fdcf6ef35301002be560389f8cd08 + 8ba6a9d5ee4bf15d87170e7c050699e858c6316bc92d5f4e19eeb3ed82e012b0 + bf0f272aabf63cd98397f4da2fd3c5742373529c91ab455fdf394fb6d0b8272d + 7a2a4980dec077abbd6a06f8b90219b818d4990b8f62b9dfc50bc4feec31eaf6 + f1d55b4e207cf5b7bdff5f59a63b55fbce6704b5ace5c5183f6be8e4770c567c + d55b23bebc2f16fc9adddf06ece363add71c4cfd73ab228461cfb926addee0cd + 76ac92ee62c2bb928bb5ec11673b51c2f1fec44ca27741a647cadfe55733eb41 + 1544a9b6c6cf77fec3e83bb08056bf18f3eb440611249f60cc97b58b5a93d364 + 702a0023d8ff6a108a2eadb777569f54df2c3b85634bb872611ccd8cf74e2807 + 8dc8889dae004e88a94f3c3beb4d39da7c074a038ff8899c5798f7a26fd17ec9" + 19 + bf0f272aabf63cd98397f4da2fd3c5742373529c91ab455fdf394fb6d0b8272d; + "63eca008f74f57babb34dde1fbaa5264656007f7479d8df3ba5cccadbe83925f + 001a67bf61d077528bf9b386694a99d7293d6b49f368ad54767a2829643621b0 + 4c124850c332a4e2a6a335e5f5676f803ede7958719b083f648137cfccb82f50 + 39f293fdd5b28c882b824d1cfef38a327334776139bc2d814834a86d6b2d93bf + 114df0c93aebb6a764740e43a67c6b582b49f6d0c393a23db42611023c044d9a + cd9e11bd49d7ee82e52f89d7100fd64c4474695054cd22442ed2bf17991cebe8 + 56931f05328bd38dea431af6537fe4a4f1e419a24c5181974e61b64367a65a5b + 2bec95a108b7a500937b5a3f3c54ae9b2cc7b11629ac581f7d8663b9c910af96 + 380777fd3ab97d140a142d3d37c7786264ea00b63083219652376d7fd56ea846 + f0fb2846d9cb0b88751db963f9360ff2bda25052eba9edd2ec561807c1f0fc27 + 34294c58ff5ff91f1472dc3d7b3099c81ef434126c58de3751c788a71f2a78de + 05c5a1c0bf29c1bef5da9298450b8ce6c5856b3f7e2037133734a03959573927 + 7fd9db5b2418267e94db49ea0534ec8d397f32f90981448c944a4ff3cb6d9c3f + 7015d096ddd557e669fcedd9b3b2624b910505f756e8ea160c5436bab604669b + 46858fe7612b43ba805a6c7999a3be02b1e635963792d228f1414fbdf13e175b + 70422706d36540ece562d1c36bfc5b178d1cf47c1ed87bea38be5a9f95010521 + 250e48d385aefbc10776582e71e4139148c99d6f9ea8c46a8e57194986eb2ef8 + 44accaac045de3183f7a45f89d4bdb5534594c90296ea664061f3f8a142f2d7e" + 9 + f0fb2846d9cb0b88751db963f9360ff2bda25052eba9edd2ec561807c1f0fc27; + "3fca772e14531611cf82782ecff97358f710763698b73e84479056a97d7d352f" + 0 + 3fca772e14531611cf82782ecff97358f710763698b73e84479056a97d7d352f; + "fd8d6560ef50712fb5f0707c342f618cbbe5697d261d249ad4887dc5ebac4f07 + 89c98bc89a81402e218e377257bd1532d524dd33a3b8c0458b2e5211d4d7b305 + e48938f9271a8861d46fa6063563b92c0a6fd59634151b075316faad9c87008e + 332fb871bf280cb18dc5d444a565ab1e505d274e52c231808af7d52cc28990de + 9073abe824ac2d30ec9562a5a67836af5cf9c038aee85ae1f7d387da64f558d5 + 04c3ffe8e6ed014162fbe6f3b8467114afdb6d5d51ad878c4462d8a926d9966a + 5864d08abd45dd3d4b6e59762a8feb76cdbcbab01a66e512d40bc070e2754ce9 + 0a780e6ecd9b4ed16cb4fd1b4b060c74d97a4268733855102b036f89cb4d5bac + 34bddd4d2ac8a920864e6b9cff04ab70f9978a16d0ceb06aee33aaa78e49328e + b65e8424be6a9247ad08f01a28e887bca33b3f5c28ef3adebf37798972eb99fc + ebd2aa397fc49104dc1c3f82f275bf625984c8c84a6f699e801b736c667a8cb8 + 8a704e508538e1d8a64c4c9052f46a07151c79dcf95e6359a8e5f41370ba40e2" + 4 + a373abe824ac2d30ec9562a5a67836af5cf9c038aee85ae1f7d387da64f55855; + "fb1b4c61b9b2fbe2faa5c0e3227e3c2fd4c8277aa629fc88fc18a4a29df3d6f0 + 3431d240f65ae76dcca41df165a4eb4c5af155027844d80a0c7f0d07ca4b5761 + 67e879347f3adcd41cac36e8c80a0f4c2ea80eb08ae9ee2b21e528769eb4c7bb + ce843b0190451928f2e637449b5ed95580645a0e0440ab017026631c619d2bcb + cc85641974b86dfa780e3edeafc0d6730da6f579826ba8f9bb8ab065b1e149b7 + 2f0c812e2c9114bef4810a01d108ff001fe328d575cff750e30133b464e2648b + 407a5a8964f840ca90aa4cf79a18f5760f7a8ff23bd6bf2d6dfc88c980728aaf + 26c2b3f4075ede77023b2de230edf8ce5e75a0cb9f1d81a0d154ba5d79de83f6 + cd98878185983eebc6f188559d9bbf8dc422eca6598a7df35449d0b39106c706 + 42aea74be96565c44c08df95a6aa58603085152d4f7fcf38375283859d17a46c + 31383c1609e8be3dc7279916eb5bb5d3e95e745a96f55ed3d69f296bfda19a28 + dc140f380ac16ab63124f9f7a02aa458ceeffbed4a9b8e31f45c67ce6ce1c394 + 81bb67da90b02b5b19ce9863902f12f33a85795994d7d22b914f0e82a44a4f11 + fd76e39b1d68f07e538353c0ffeb0c1225f5de64166ccd419c10134329f954de + e9f40437c324cacfc6974bee082cdb82c432a86d8465a0229a1e05fb19dec82d" + 0 + 0e1c4c61b9b2fbe2faa5c0e3227e3c2fd4c8277aa629fc88fc18a4a29df3d670; + "c2b1fe3853bbed5be05536475b2f1bb818eb5ed0111f3be6c6b3bb8ede2d0beb + a692dee2a40878814b9ded7ba7ba47a391585ac93af04a0addec3904ed912ec6 + 015e98f69b98f157f559f8282bfbd20e07cc4a9e2929feab5a8c246011d1098f + 76761cf13e45886da2b747f0de3a238be8aaf5868eca88c4de6b614ff3902e12 + b6b06a046fa5f2e43e698fc96818cc7bf888d5c4f4f2f0bda86cc35c1b48679c + d7ecabc614122bb6908ebabcf7bcfa9a4fae88bb8450d559297c778dd35279f8 + cdd96bbd24cc00b4fa5c8b20efa66a3db1d62e76f001dbd87800fc59f4a29a1d + 9c16ca817b43101672fd1cb3583a6b44bfe2ab5956794280a3a32bd2aa651656 + 4d7ba5f8240527b3c9de386b00dafc163314b3f1311bc30b8434993b50e08d67 + c4ab9766eee58337a92412440f12083a0205c39ba27e0877613b4288dfce9899 + 71ca275f3f7df242b5770d37c92425bde86184ab23c06c6b6bec799c47651433 + 49da5429ec1ade01eba828ad21d230cced84c8a28f239a69194cc0b5de9a0f20 + fc17ee1656b6f0de36158fe2db82ad3f63c196c54002728bde4c5e27e6c0d7db + ece944bcc82f520e8171aefe728863b99a9772cc48b714d82426224b302b7be2 + d2ea262ae062bc1167e79a7bd8abc2b6c7cbbdc03622495d1ff3a56e23c03f72 + 9be5176e8e873f9c320cff256e7b8801cdc1cee0b32ddd715d71abeaf909e0bd + 0e666632a0ea9c9c5cc3fa519a42c34313ed2f64057106e38dddec87d68146b0 + dc48385d46bcedbdf17f43e7b2de274556b411a0ac4b7e89a2f5f71a1d1ea5ba + 76919d83ecc757cfcd916e23e5cadbdda21793a322c0fadad4e581819ebc0b18 + 84830e7a1b4b50e6ba90fd5f8b1198aa60b0c8987c962e9eb12adc2cc389ee1d" + 11 + 49da5429ec1ade01eba828ad21d230cced84c8a28f239a69194cc0b5de9a0f20; + "99f065bb53134babd50f3f46adb63c64f7600acb39487718bc0a39fd3a5f4ebd + f70702612b9b45f7833232a7267492299c23caeffdc4f8a494653cde777861ab + 16c9b6b125cb9cbb201cd0a558fd58cc29f2d197b9b160a0cff88ac890b9e429 + ff87c5e3356c8fb8dbeb739aaedd0df3da2ec3072e5a806569a5847fcbcb4267 + 01d23260fa58bc7c077e05cac9e1359a9f4f2c9f2bc8312e0832376e3c3cc554 + b7b5071166d68c704410d4e9123a261631822060c336b8cf0f5685a7df6ae6ea + 621633e25b1ba392baaa31fc2d6a57e8286f6bf6e5edd5a0268a895af91d61c8 + a29ab1d52fde5e7026124c3cec2be1fa674d37692165f46d1d91bb9f41156a55 + 26d8eb53078f2e515bdee3adc377a16b54ae575343888c27c6d72e07dd7ded04 + ba5d57dae01659afb41b3b4712f0ccfa3b6b2a0d8a99fa5f1078203925897618 + 8cf51cab05199e2154a5bf655e6a9e9498c20cd08b564936b164b0a7f49a1e30 + c5b3977228539a7f573c88800633f1da39a3f1bff9e1018af48f94f211a812b3 + 149a93a1ded07e398fe248962a7656f9b0f15ce62c4aa0bba4a3c6f00cc362f7 + 234974b4054622b0672626f111ea5b44afd81dcb15f29974585c9b77476d9290 + 4be4b2338d92909e6a138d4d2e53e72707a4af62acc8cf2a121c8105ec4ebf32 + 1e6192c030263e3847898afaf5003000552b9ccba7caf6361c1f34fa0890b086 + ba698e634085f7dd38da012c8c97efb97a9b3c08c829d660e72e46d12eba79ea + 712198efd6734fb564278f1bd0dde082482078548dcf4681e65e6dce39328c1e + 8cff8caee2ed08e384331fc0509c1ab44b291d840d19ee991c9978bb7642b4c7 + 98a539cf588938c8ee31d80ff0254e13460f50d7907885f2debf7b68be91edf0 + f0cc67c038324ed37948dfd94ab50dc6fd07ea8b441009ea2c4e185f0d800b85 + 09ae723e872da1687e02c883a254e033e8c67e784ed33e3a28eb8cc92be37d32" + 6 + 751633e25b1ba392baaa31fc2d6a57e8286f6bf6e5edd5a0268a895af91d6148; + "97379391993ac07a0b019c4b6d2d08d4555e5761b4faa7bea8eac269844c6106 + a2aff4f6141eedf254a8f7122ee37a1403b97fddc2805ce4ad010829aee1575e + a54665a1ac19c8ab83dad06bb5ce855b45246a9ad338516c5d67948f86eb1aa7 + b8fa1fa064f6bd0af94d427686a09472b6a841576754500464ac3310cc147d40 + dbb4cd734b211f5ad48452a193489fa25b0c82a594105a96ad627c5cd5328596 + 5396b8de36ade038e4424344fb2083226410f771c8ec979e916f37710b56cffe + 039b59e759c9a380200b129e08d77ef53d703689b60ba5f117111ddd27f1674a + b3456d7bfa566b925ef014c6538c89251b7c0fa9fea89fd1806f97bcbfc3cdb7 + 4ab7a386cbc720b5676de0e76d584d6fa538a0015debe30c37e1839165763d5c + f7f55c12c67c1ca28b3947fb7bd7c4ed9a5240f962425b9b4810191d448af7c5 + 8dc0a95877c2ea17052b55c9f93440319ec38bbf80b375177e84ad14bab558dd + 246d97123750b41e5bf2d96f10b3c9e66e92759373999bd94191a65f25a864f3 + 5bfa2905cb0b0aef125fb39deb2cd392b3cfe3f3ec58f8361e8cd5f12bd2db98 + 192413efd53bb958417f65a818d48d6bbf94dcc77210d9623adbca15633bd7ad + ee95faf7a7f31c7afd13d393ff2ff4e448799c87c62092e9e646efa4c635d1f4 + 77c00984400bbdcc81aeb42085c44be70137db5a0464f6081aa9c8e646e96e1c + 743cd93d6f6a48161881d2224b7d7c0ce96d56d54adff0b719955cde417b35a6 + 92b99335dcf6b33de126d05329d8884802cc3afd0f93e9dea7db5f6dbdc6c623 + 584ccd19fe7395f9f2dc53f2a9da292e0cccfabe82bc46aa64c29581fc570deb + f9321c751abb9df278fbc2054e3fa368734cc852589891b49580332a52b6bf72 + debc2bf3cedb7c897924936aac0b485bc05eb89530c886299e8d1ccad277355a + 472d49f8ccc249b8271fd0630ab575721852e98015ea27732915ed06775b444e + 7b29b054a2347baeda4dbd1b739072e6d144aae3547adc8287c3af84285057d1 + d7a79b1f1ca757e17729436fe744ea7d99a64d13bf85737b6a71d41ab13343e4 + a957b6345193173a231d9db8acb3a6c09bb411d210e0e52c94e75a4d68602aba + 6277d818cbecae95f1aea85481ee631ff1e7c77c6693e6349d1804db784238f2 + 27e1d5a11dd9025508168d9d11cce0b8f0768b6846105161eca53abfa4aeeff6 + 1823372e2c7cb9fdcdc97ca64ffa06564907b09015472cfa73bf0a45d7c90bec + 08cfef24b9eb875598779315de4fcfc918931e05f49b374113c25cb5b23a4944 + 3a5d9db56bac2f413a3d33b6d7a2f54053aa3a641d6554d6f008779939f2682f + 22d0256cb1a53aaefd5d2fde14b63e5adce607ee5a22e8498f29982f88088938" + 18 + 6b4ccd19fe7395f9f2dc53f2a9da292e0cccfabe82bc46aa64c29581fc570d6b; + "91a76b64122a404fbf873d65089a7613bd3d93c4227a4b05817223640ec20ee9 + ab46f7649122de1d73278608e02d44a1367f4f5a7c01d1c17f2a50fb3148dfcf" + 0 + a4a76b64122a404fbf873d65089a7613bd3d93c4227a4b05817223640ec20e69; + "1c12d157172079be7ecc31716fac8946f5517a3da6612bf4a0db65707e72764b + 9d9ec126bd404e82448a16c187152307ab6319fdd5d4280f070275cedf1cced2 + 25be86a2abbf7619f7b92855cc50572af4fcf6ee071078d24baa24d623ebe4e5 + 9b3a13dd1b67a284a9ed869de2663d82035342bc0cad65484da1c7b60b82a55b + fb82840bfd348ccaa0d3d362c1123096a5103a09f979e2f4acdf7aa600e55a84 + c64642a4946ed50924eb1a4c6ab73b53942c5a17cc868f8c6c5ef92ce5986830 + 8e7aaf58bc15be92a31af4f0b092969a250222e7ccbdb638aa846f8253c33d50 + 375bb009118659c831591bd6861e9c9eaec85c0fd9a1facd5f2767ff27e3d36f + f5b4b72840ef438fb8f7fd1419aa5248dc38126cfc29099cffe68aa94b215b31 + 3b0cf55a0dc7856788375bfa1390fe4c628c271c99ea76ac78517ad5f36f61ac + 82cf74084903490f30152c730970f8b622de5414e1a60e1efafc6aa57ff2fba3 + 9d476226e3c4f844f392e7efea7726b02bea64c9aa1e78513efb28a000cf9624" + 11 + 9d476226e3c4f844f392e7efea7726b02bea64c9aa1e78513efb28a000cf9624; + "4f8b3919461d4408a4d4375688f8985332745cb5253671dd7fea3c58b8e33e5b + ecd4f6bf71be54fa88e51fd9d98f60c009fa1b4f15ccacdfa7b26a5ba52b1794 + b0bc276ac01ed6b25fb569ec8c614f4a9299faadcb93bdee4dc637c888381d29 + 2fbc1564ecd906f5d56838c9ceb3ba5b5f13925cadd653008f1ee9f54c18ea37 + 66e9f3ed35f45675f9601181ddcff688229371c6428c1d9dc67699821e3130b6 + 6b08a213ca51403db7e08bf6945b23ccb62465f582248661b901b6e550345516 + abdb83672459dad5b11c3cf9e4d21235ff92c01ab00b2d44aa6f10bfe9b274d0 + f609191b4efb288359af7170acd0904c57d45c7c658c0d670e0fb22f9ebc0044 + e4056ab4b8afad5e6951c8168477f15ee3e11fe3f236a1d19ea201f78b8898a5 + f3b253fd18515ee3dcfd4a14409838a3d993a5274bd77a1e5a7088d20ba6c592 + 710b8819a202ab80bcf308aa94d3305944dc739e33648df045bba215160f8ee9 + 1b63314e9fbd605ac063546ee4249bf9f37da0b6b78d99848f487c6880f70c3e + fb04f3e49a44c4eea104c213446b0e6b81da047a0862604f488e0c6128238d3c + 43b1624809a253f46b12d97aa08dc3f16b25613022483b8044cb01b6d23cfb28 + 0796291d8916b0b70ebdab0f42b8cc55c14734cf7a398d48f94b48d9871ff0c2 + c55cc772bb71392f13258339eaa1d8b01c402e8f6c9b6061f0e1c564feb98234 + 882ad3994d999ac7243ebe9955468a52b2242564a295a9740af8980043f9ef0a + 201f86fc5826d74580c3bd3fe04cda2a823c2a4d1ace3e862a9bf6873ba25055 + 5c39347c213f6e1b5ded1de9f92ed21d99721c4e4216d5abe207321caa426971 + 38ba53a577809f2d2c3cc33016e6141f4a87b6f57b75be70b9cd3d287f07ab00 + 7b9e12c5293fd99ed3fb50a2eac4587bca4aa8bb97c147626dcb9688593ad2e9 + 4852c30283c1ffa109aade1353d11e9712d8c4e6d416926f231a2b89b78fbdbd + 80d25270ef8002232cd0e35433ecefc135cbcaa06511ba3ac14484b6e41c953a + 6159366a1aee4692a9986a12234728c685cf766ad3e2c4cc842f1142c0fb856e + 95d34152d18b9942bb13c6bec8e533c259adfd69dbeb06da63c351997463cee9 + dd5890be52cd0207fecd0f93dbd3a6819aa2c5a592ca0975a419104e7ff4c284 + d9c3f02b7644b3580d190f03bfc9accc8abf9546463a2171d9cb19b3783e0c92 + e59449e7a9d07631450d85d108f3cfec2d67d63ad65a7311b310bb10137fcdbc" + 27 + f89449e7a9d07631450d85d108f3cfec2d67d63ad65a7311b310bb10137fcd3c; + "e5d98efcc2879f32793efa8f96dda9c87b70834fc9d468dc464b0940a7dc160b + 04d4bc5cd4690a0c6561feae82c6be57195c7553276f12aa16fb930ac47e315f" + 0 + e5d98efcc2879f32793efa8f96dda9c87b70834fc9d468dc464b0940a7dc160b; + "bfbed3f0a31b886bd96a817e0b65be1b1e374fddb237514e89fee7ce34a08c45 + eedd85cd817fc74938e60c366445e6bd5383dedd290db3633d5ed2ff320139a2 + 006b1e62b3aa1830de71c0ae063fbf090e536304d601e6c851800ff1d501d249 + a4a63dcc680646b69c8e651dd9c3e043bad07eb9bd6b55bc5bc854d82bbc6b00 + ffa2e97c95ef5efb87b78e89f35e95f89c1c1b2591673fd2166fcc9765abb4b8 + 030984d84d3d9667e436996578a3ae58853d44e111990221cd15795167475426 + da8350e83ac6d67029c24a8d386c6352a27bd22fd6a207474a952742790e4be9 + 0618b6f82b936b5eca87e9ab8dcd9a2e3744586bae01a75cfabb23b1b64f7aab + 5a3e077d0d0d28ba3b6d6fefecc6c2f7ca530fa63bf414976ac8b26ed6596a3b + 381e56750672340b18b60612bd462ade52d3b0d5b487f1af8438140740df484a + 65275cc865fc4b5d94023fdcb929dd27dcd64870773c79f015d4a5f30751ef2f + 724f96fe61888b5a885713d0c52e759726b877031b3f4f80ad24bcf417a3dbba + 17f55299b7cd1d851091052401612078978bf2b09fca8c9e2189474e9d24b81f + 14b82eebd7325586c1ed8be9353fe5ad9375290a92e76d13947c6405febb2f52 + eb5a5c7771ccf698a2e803a3a4e6db056ceb0da4d808db5758f2cb28ccc44bee + 96db7bfd64b7d41430ca6fd0714487926d02dc71571161f8deea0f6a3b52ba80" + 6 + ed8350e83ac6d67029c24a8d386c6352a27bd22fd6a207474a952742790e4b69; +} + condswap { 14e55571df646a69a8280bf8dbf8e9afc15bf5558bb8b8236ebcaa19a96053bd 8bef5021598a8175565e1f2b522ed1c4306fef4e0e973b50d3a03db1fcf11a43 @@ -439,6 +1007,79 @@ inv { 0f5ccf4920d617c9b4f7fe6e2c9e95e89b5516555d5e3f5f9900485451d7425f; } +quosqrt { + 18798551568191dbfe6bcacf95bf4bf00290de4c773a1d4233d1eae272b3085b + 2ee52110807ab6e31e0ed7b4de818d6474b514c63c99206e58a6df38e149123f + 3819accb91d97a3f4dbca732f19723fc772a19b3eb4d307acad706cc7c7e1c1f + b5e653346e2685c0b24358cd0e68dc0388d5e64c14b2cf853528f9338381e360; + 8671a0ecb7344f2e44fc9066aeb42661e848417e8c51b353680573830857d90f + 9c4cfb1aa650924ceaf3e23b260d02b7d8b7dd4445360cad0bd4270428f55292 + "" ""; + bb0d27e1743f444e2f612c2ff575c6c6663f01869eaa8666774b8baa59b2a714 + 2fecb156c393d27d7b9a5e4cc2b57cb5524d5b945e92c5b4bdccdd6d00e684c6 + "" ""; + 59af963f7245901807a46a59d4e49bab5b1fdf3001f63ef4e600ef8150d0e13a + b5ac3372ca5435577c416ba46a57879b0ca1df29057c540cac4edacc507b5e23 + "" ""; + a7b8659775a53e1fa315066be6a37a3f645d782cb69ec6b4f27fcf4daed3d82e + 4550c4697a5d29d1a97b50ea65e98ec839567a3fc556ec3790b016c24b867d89 + a190875f536f94ae2af8aae90bf0afabed437b36cf640d85529b150155eed53e + 4c6f78a0ac906b51d5075516f40f505412bc84c9309bf27aad64eafeaa112a41; + 7163512100699c32d5fadbe3583f2f6f314c347f1e66c434b15ac06a5733f3ed + 2806d76598a43c24820daaf87afa5a9a4d414e5d8f51993f1b01166bb5479c27 + 01d5d023a6c5f7ec1d5df3179bb240e3003a9e3be8ad4e154c6e8f7cb7af6536 + ec2a2fdc593a0813e2a20ce8644dbf1cffc561c41752b1eab391708348509a49; + e950533666a4a1edc3dae30637d6b005e34b614fe75555be0e1759def06a2aee + ac5a603347a585ca19eba141b1dd1b8833855e9807776627e8c9f92001a4b9b0 + "" ""; + d3c5ccb02442548901b3ffa2ed5564735b0b041386fd38e6c40844dc9183006e + 5e6f23ccef94660e569bc42093d2b862ca605b81d64bb3589331d015082b4996 + d7d578a72f1ea2dcacd0a96be285e9635230dc297fa7f6e1f2b9754e2d29190c + 162a8758d0e15d23532f56941d7a169cadcf23d68058091e0d468ab1d2d6e673; + 37cad075017c111f99135be6a0f553535d56153cef8839eee1e70614d65df1c2 + e5f9944a377be3ab64daccfc9e711f4aa522c68a80efd0a70c72cdd4507014b7 + "" ""; + 85dedba748f478537d016f20b9871e830e513514fbd27141aa54ca77b2a673be + 950bc6fb51f6d8c36b7ddc8cb28d9efd498690a46c57888b279de0e549e84c52 + fb7871031556b171a25dfd0483f0e2ed8d24a8acc2d9fc201f42f0b892fd541a + f2868efceaa94e8e5da202fb7c0f1d1272db57533d2603dfe0bd0f476d02ab65; + d70f399a983c6ad48acca796d9106c5e7681f34bdf34248f6dc54620282bb327 + cad23bcd1fb96331bc8139f2a8f21d24492e56a7b80e343a7002acc96a739454 + ff70c5bffe08911fb5522b21beecfd80fb018f0afef24fe85cfb7e4a5024960a + ee8e3a4001f76ee04aadd4de4113027f04fe70f5010db017a30481b5afdb6975; + 71ee96ced0b50bc560f2477a88ea2447573490f71850f084ae0b318cafd8a75f + 15c61eefd2c05d72fb07e44a006dfe314d8797f978bab1fe9f9276bcc82b542a + "" ""; + c27a9f169b8096308f313ab5a521886084f03ec6d9e8b30e4773d0a3ab1a7c67 + a7ca0e7fc5566dfc3790a3de164ef26d6452715db428994d438e79f65034d174 + 129427bd4c2195fac5a0da4c52ff634c697f18c3b02d0e7aad45a64d03b6e922 + db6bd842b3de6a053a5f25b3ad009cb39680e73c4fd2f18552ba59b2fc49165d; + dd73476aeab865af0775723ebd2128ca71621b1d95231813c3d3cb32b805f418 + dc6621f2ba82deb8272243baa5d2e177a60b1b780daa3ba081040e05b1d1b2f9 + 32ae54f7a7dfa101bad00f723898d29a7307454f86cd1197c44b07d1b997fa1f + bb51ab0858205efe452ff08dc7672d658cf8bab07932ee683bb4f82e46680560; + 3a3ee482bf7075fa38780616603133ecea7b56acab59d96ebf7192e21c49a806 + b7e6d647792961137dadce55ce69634379338bbda45fbef9d56be52620738d06 + 122b696683c2d1f3feedaf6166037ddbd7281e0c4c875724177f240b54e0dc22 + dbd496997c3d2e0c0112509e99fc822428d7e1f3b378a8dbe880dbf4ab1f235d; + 71f31797a8a36123e4a0b173ee4bc5a04d7799d1eba246df51cf943aeba0270c + 7340069440d6c72b4536018eec373f50a1142c9e79de8a5396f994e53c64ab18 + "" ""; + 0d2a6a9de4d52289cc724840670abcc5a4ee04f1197bd1d230689431b01afce0 + 21457f6784da81822df90f09b44782bd50a12c4fb378091cd33b177c734e0728 + 2b272304b3cca59e26431d91118a95c965bd542191c7cef760b085673e96a432 + c2d8dcfb4c335a61d9bce26eee756a369a42abde6e3831089f4f7a98c1695b4d; + 288b09090258a71747c1a08a51b0894a0c096f5b88ee38ea56a3aaefc1afa0f5 + a7f6391e06b8972b18e899753bf3853270cae7971774041fa9bf09a55349f950 + "" ""; + e912e39e2199c3980c5fe3cac6d8bed394367f28213524f006a9b2c0cce4a6dc + e6b4a592e37fb5d3af73c486cc211a57d4077c093a161276dcb6eb44303d3ec6 + "" ""; + ec6785be59b890e07176c09195430b7f5daee0b0898ee744e578ac25873012b6 + b3cd2df2c2531beeca882607d73f38403d8ff384f99be1ce582536bc3d4bfcd1 + "" ""; +} + sub-mulc-add-sub-mul { ## A very basic smoke-test. 03 01 5 01 07 02 37; diff --git a/utils/curve25519.sage b/utils/curve25519.sage index ec21d4b2..8047aeb5 100644 --- a/utils/curve25519.sage +++ b/utils/curve25519.sage @@ -10,6 +10,42 @@ def ld(v): def st(x, n): return ''.join(chr((x >> 8*i)&0xff) for i in xrange(n)) +def piece_widths_offsets(wd, n): + o = [ceil(wd*i/n) for i in xrange(n + 1)] + w = [o[i + 1] - o[i] for i in xrange(n)] + return w, o + +def pieces(x, wd, n, bias = 0): + + ## Figure out widths and offsets. + w, o = piece_widths_offsets(wd, n) + + ## First, normalize |n| < bias/2. + if bias and n >= bias/2: n -= bias + + ## First, collect the bits. + nn = [] + for i in xrange(n - 1): + m = (1 << w[i]) - 1 + nn.append(x&m) + x >>= w[i] + nn.append(x) + + ## Now normalize them to the appropriate interval. + c = 0 + for i in xrange(n - 1): + b = 1 << (w[i] - 1) + if nn[i] >= b: + nn[i] -= 2*b + nn[i + 1] += 1 + + ## And we're done. + return nn + +def combine(v, wd, n): + w, o = piece_widths_offsets(wd, n) + return sum(v[i] << o[i] for i in xrange(n)) + ###-------------------------------------------------------------------------- ### Define the curve. @@ -45,6 +81,8 @@ def sqrn(x, n): for i in xrange(n): x = x*x return x +sqrtm1 = sqrt(k(-1)) + def inv(x): t2 = sqrn(x, 1) # 1 | 2 u = sqrn(t2, 2) # 3 | 8 @@ -70,7 +108,55 @@ def inv(x): t = u*t11 # 265 | 2^255 - 21 return t +def quosqrt(x, y): + + ## First, some preliminary values. + y2 = sqrn(y, 1) # 1 | 0, 2 + y3 = y2*y # 2 | 0, 3 + xy3 = x*y3 # 3 | 1, 3 + y4 = sqrn(y2, 1) # 4 | 0, 4 + w = xy3*y4 # 5 | 1, 7 + + ## Now calculate w^(p - 5)/8. Notice that (p - 5)/8 = + ## (2^255 - 24)/8 = 2^252 - 3. + u = sqrn(w, 1) # 6 | 2 + t = u*w # 7 | 3 + u = sqrn(t, 1) # 8 | 6 + t = u*w # 9 | 7 + u = sqrn(t, 3) # 12 | 56 + t = u*t # 13 | 63 = 2^6 - 1 + u = sqrn(t, 6) # 19 | 2^12 - 2^6 + t = u*t # 20 | 2^12 - 1 + u = sqrn(t, 12) # 32 | 2^24 - 2^12 + t = u*t # 33 | 2^24 - 1 + u = sqrn(t, 1) # 34 | 2^25 - 2 + t = u*w # 35 | 2^25 - 1 + u = sqrn(t, 25) # 60 | 2^50 - 2^25 + t2p50m1 = u*t # 61 | 2^50 - 1 + u = sqrn(t2p50m1, 50) # 111 | 2^100 - 2^50 + t = u*t2p50m1 # 112 | 2^100 - 1 + u = sqrn(t, 100) # 212 | 2^200 - 2^100 + t = u*t # 213 | 2^200 - 1 + u = sqrn(t, 50) # 263 | 2^250 - 2^50 + t = u*t2p50m1 # 264 | 2^250 - 1 + u = sqrn(t, 2) # 266 | 2^252 - 4 + t = u*w # 267 | 2^252 - 3 + beta = t*xy3 # 268 | + + ## Now we have beta = (x y^3) (x y^7)^((p - 5)/8) = + ## x^((p + 3)/8) y^((7 p - 11)/8) = (x/y)^((p + 3)/8). + ## Suppose alpha^2 = x/y. Then beta^4 = (x/y)^((p + 3)/2) = + ## alpha^(p + 3) = alpha^4 = (x/y)^2, so beta^2 = ±x/y. If + ## y beta^2 = x then alpha = beta and we're done; if + ## y beta^2 = -x, then alpha = beta sqrt(-1); otherwise x/y + ## wasn't actually a square after all. + t = y*beta^2 + if t == x: return beta + elif t == -x: return beta*sqrtm1 + else: raise ValueError, 'not a square' + assert inv(k(9))*9 == 1 +assert 5*quosqrt(k(4), k(5))^2 == 4 ###-------------------------------------------------------------------------- ### The Montgomery ladder. diff --git a/utils/qfarith-test b/utils/qfarith-test index 3904d42c..45f233ff 100755 --- a/utils/qfarith-test +++ b/utils/qfarith-test @@ -73,6 +73,9 @@ def add(k): binop(k, lambda x, y: x + y) def sub(k): binop(k, lambda x, y: x - y) @test +def neg(k): unop(k, lambda x: -x) + +@test def mul(k): binop(k, lambda x, y: x*y) @test @@ -82,6 +85,15 @@ def sqr(k): unop(k, lambda x: x*x) def inv(k): unop(k, lambda x: x and x.inv() or k(0)) @test +def quosqrt(k): + x = k.rand(); y = k.rand() + yy = +y + u = yy and x/y or k(0) + try: zz = u.sqrt() + except ValueError: print ' %s\n %s\n "" "";' % (x, y) + else: print ' %s\n %s\n %s\n %s;' % (x, y, zz, -zz) + +@test def mulconst(k): x = k.rand() a = C.rand.range(1 << 20) - (1 << 19) @@ -90,6 +102,23 @@ def mulconst(k): def mask(): return C.rand.range(2)*0xffffffff @test +def pick2(k): + x = k.rand(); y = k.rand(); m = mask() + print ' %s\n %s\n 0x%08x\n %s;' % (x, y, m, +(m and x or y)) + +@test +def condneg(k): + x = k.rand(); m = mask() + print ' %s\n 0x%08x\n %s;' % (x, m, x*(m and -1 or +1)) + +@test +def pickn(k): + n = C.rand.range(31) + 1 + v = [k.rand() for i in xrange(n)] + i = C.rand.range(n) + print ' "%s"\n %d\n %s;' % ('\n '.join(map(str, v)), i, +v[i]) + +@test def condswap(k): x = k.rand(); y = k.rand(); m = mask() xx, yy = m and (+y, +x) or (+x, +y) -- 2.11.0