view release on metacpan or  search on metacpan

libsecp256k1/src/modules/ellswift/main_impl.h  view on Meta::CPAN

}

/** Decode ElligatorSwift encoding (u, t) to point P. */
static void secp256k1_ellswift_swiftec_var(secp256k1_ge *p, const secp256k1_fe *u, const secp256k1_fe *t) {
    secp256k1_fe x;
    secp256k1_ellswift_xswiftec_var(&x, u, t);
    secp256k1_ge_set_xo_var(p, &x, secp256k1_fe_is_odd(t));
}

/* Try to complete an ElligatorSwift encoding (u, t) for X coordinate x, given u and x.
 *
 * There may be up to 8 distinct t values such that (u, t) decodes back to x, but also
 * fewer, or none at all. Each such partial inverse can be accessed individually using a
 * distinct input argument c (in range 0-7), and some or all of these may return failure.
 * The following guarantees exist:
 * - Given (x, u), no two distinct c values give the same successful result t.
 * - Every successful result maps back to x through secp256k1_ellswift_xswiftec_var.
 * - Given (x, u), all t values that map back to x can be reached by combining the
 *   successful results from this function over all c values, with the exception of:
 *   - this function cannot be called with u=0
 *   - no result with t=0 will be returned
 *   - no result for which u^3 + t^2 + 7 = 0 will be returned.
 *
 * The rather unusual encoding of bits in c (a large "if" based on the middle bit, and then
 * using the low and high bits to pick signs of square roots) is to match the paper's
 * encoding more closely: c=0 through c=3 match branches 1..4 in the paper, while c=4 through
 * c=7 are copies of those with an additional negation of sqrt(w).
 */
static int secp256k1_ellswift_xswiftec_inv_var(secp256k1_fe *t, const secp256k1_fe *x_in, const secp256k1_fe *u_in, int c) {
    /* The implemented algorithm is this (all arithmetic, except involving c, is mod p):
     *
     * - If (c & 2) = 0:
     *   - If (-x-u) is a valid X coordinate, fail.
     *   - Let s=-(u^3+7)/(u^2+u*x+x^2).
     *   - If s is not square, fail.
     *   - Let v=x.
     * - If (c & 2) = 2:
     *   - Let s=x-u.
     *   - If s is not square, fail.
     *   - Let r=sqrt(-s*(4*(u^3+7)+3*u^2*s)); fail if it doesn't exist.
     *   - If (c & 1) = 1 and r = 0, fail.
     *   - If s=0, fail.
     *   - Let v=(r/s-u)/2.
     * - Let w=sqrt(s).
     * - If (c & 5) = 0: return -w*(c3*u + v).
     * - If (c & 5) = 1: return  w*(c4*u + v).
     * - If (c & 5) = 4: return  w*(c3*u + v).
     * - If (c & 5) = 5: return -w*(c4*u + v).
     */
    secp256k1_fe x = *x_in, u = *u_in, g, v, s, m, r, q;
    int ret;

    secp256k1_fe_normalize_weak(&x);
    secp256k1_fe_normalize_weak(&u);

    VERIFY_CHECK(c >= 0 && c < 8);
    VERIFY_CHECK(secp256k1_ge_x_on_curve_var(&x));

    if (!(c & 2)) {
        /* c is in {0, 1, 4, 5}. In this case we look for an inverse under the x1 (if c=0 or
         * c=4) formula, or x2 (if c=1 or c=5) formula. */

        /* If -u-x is a valid X coordinate, fail. This would yield an encoding that roundtrips
         * back under the x3 formula instead (which has priority over x1 and x2, so the decoding
         * would not match x). */
        m = x;                                          /* m = x */
        secp256k1_fe_add(&m, &u);                       /* m = u+x */
        secp256k1_fe_negate(&m, &m, 2);                 /* m = -u-x */
        /* Test if (-u-x) is a valid X coordinate. If so, fail. */
        if (secp256k1_ge_x_on_curve_var(&m)) return 0;

        /* Let s = -(u^3 + 7)/(u^2 + u*x + x^2) [first part] */
        secp256k1_fe_sqr(&s, &m);                       /* s = (u+x)^2 */
        secp256k1_fe_negate(&s, &s, 1);                 /* s = -(u+x)^2 */
        secp256k1_fe_mul(&m, &u, &x);                   /* m = u*x */
        secp256k1_fe_add(&s, &m);                       /* s = -(u^2 + u*x + x^2) */

        /* Note that at this point, s = 0 is impossible. If it were the case:
         *             s = -(u^2 + u*x + x^2) = 0
         * =>                 u^2 + u*x + x^2 = 0
         * =>   (u + 2*x) * (u^2 + u*x + x^2) = 0
         * => 2*x^3 + 3*x^2*u + 3*x*u^2 + u^3 = 0
         * =>                 (x + u)^3 + x^3 = 0
         * =>                             x^3 = -(x + u)^3
         * =>                         x^3 + B = (-u - x)^3 + B
         *
         * However, we know x^3 + B is square (because x is on the curve) and
         * that (-u-x)^3 + B is not square (the secp256k1_ge_x_on_curve_var(&m)
         * test above would have failed). This is a contradiction, and thus the
         * assumption s=0 is false. */
        VERIFY_CHECK(!secp256k1_fe_normalizes_to_zero_var(&s));

        /* If s is not square, fail. We have not fully computed s yet, but s is square iff
         * -(u^3+7)*(u^2+u*x+x^2) is square (because a/b is square iff a*b is square and b is
         * nonzero). */
        secp256k1_fe_sqr(&g, &u);                       /* g = u^2 */
        secp256k1_fe_mul(&g, &g, &u);                   /* g = u^3 */
        secp256k1_fe_add_int(&g, SECP256K1_B);          /* g = u^3+7 */
        secp256k1_fe_mul(&m, &s, &g);                   /* m = -(u^3 + 7)*(u^2 + u*x + x^2) */
        if (!secp256k1_fe_is_square_var(&m)) return 0;

        /* Let s = -(u^3 + 7)/(u^2 + u*x + x^2) [second part] */
        secp256k1_fe_inv_var(&s, &s);                   /* s = -1/(u^2 + u*x + x^2) [no div by 0] */
        secp256k1_fe_mul(&s, &s, &g);                   /* s = -(u^3 + 7)/(u^2 + u*x + x^2) */

        /* Let v = x. */
        v = x;
    } else {
        /* c is in {2, 3, 6, 7}. In this case we look for an inverse under the x3 formula. */

        /* Let s = x-u. */
        secp256k1_fe_negate(&m, &u, 1);                 /* m = -u */
        s = m;                                          /* s = -u */
        secp256k1_fe_add(&s, &x);                       /* s = x-u */

        /* If s is not square, fail. */
        if (!secp256k1_fe_is_square_var(&s)) return 0;

        /* Let r = sqrt(-s*(4*(u^3+7)+3*u^2*s)); fail if it doesn't exist. */
        secp256k1_fe_sqr(&g, &u);                       /* g = u^2 */
        secp256k1_fe_mul(&q, &s, &g);                   /* q = s*u^2 */
        secp256k1_fe_mul_int(&q, 3);                    /* q = 3*s*u^2 */
        secp256k1_fe_mul(&g, &g, &u);                   /* g = u^3 */
        secp256k1_fe_mul_int(&g, 4);                    /* g = 4*u^3 */
        secp256k1_fe_add_int(&g, 4 * SECP256K1_B);      /* g = 4*(u^3+7) */
        secp256k1_fe_add(&q, &g);                       /* q = 4*(u^3+7)+3*s*u^2 */
        secp256k1_fe_mul(&q, &q, &s);                   /* q = s*(4*(u^3+7)+3*u^2*s) */
        secp256k1_fe_negate(&q, &q, 1);                 /* q = -s*(4*(u^3+7)+3*u^2*s) */
        if (!secp256k1_fe_is_square_var(&q)) return 0;
        ret = secp256k1_fe_sqrt(&r, &q);                /* r = sqrt(-s*(4*(u^3+7)+3*u^2*s)) */
#ifdef VERIFY
        VERIFY_CHECK(ret);
#else
        (void)ret;
#endif

        /* If (c & 1) = 1 and r = 0, fail. */
        if (EXPECT((c & 1) && secp256k1_fe_normalizes_to_zero_var(&r), 0)) return 0;

        /* If s = 0, fail. */
        if (EXPECT(secp256k1_fe_normalizes_to_zero_var(&s), 0)) return 0;

        /* Let v = (r/s-u)/2. */
        secp256k1_fe_inv_var(&v, &s);                   /* v = 1/s [no div by 0] */
        secp256k1_fe_mul(&v, &v, &r);                   /* v = r/s */
        secp256k1_fe_add(&v, &m);                       /* v = r/s-u */
        secp256k1_fe_half(&v);                          /* v = (r/s-u)/2 */
    }

    /* Let w = sqrt(s). */
    ret = secp256k1_fe_sqrt(&m, &s);                    /* m = sqrt(s) = w */
    VERIFY_CHECK(ret);

    /* Return logic. */
    if ((c & 5) == 0 || (c & 5) == 5) {
        secp256k1_fe_negate(&m, &m, 1);                 /* m = -w */
    }
    /* Now m = {-w if c&5=0 or c&5=5; w otherwise}. */
    secp256k1_fe_mul(&u, &u, c&1 ? &secp256k1_ellswift_c4 : &secp256k1_ellswift_c3);
    /* u = {c4 if c&1=1; c3 otherwise}*u */
    secp256k1_fe_add(&u, &v);                           /* u = {c4 if c&1=1; c3 otherwise}*u + v */
    secp256k1_fe_mul(t, &m, &u);
    return 1;
}

/** Use SHA256 as a PRNG, returning SHA256(hasher || cnt).
 *
 * hasher is a SHA256 object to which an incrementing 4-byte counter is written to generate randomness.
 * Writing 13 bytes (4 bytes for counter, plus 9 bytes for the SHA256 padding) cannot cross a