view release on metacpan or  search on metacpan

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

        /* 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
 * 64-byte block size boundary (to make sure it only triggers a single SHA256 compression). */
static void secp256k1_ellswift_prng(unsigned char* out32, const secp256k1_sha256 *hasher, uint32_t cnt) {
    secp256k1_sha256 hash = *hasher;
    unsigned char buf4[4];
#ifdef VERIFY
    size_t blocks = hash.bytes >> 6;
#endif
    buf4[0] = cnt;
    buf4[1] = cnt >> 8;
    buf4[2] = cnt >> 16;
    buf4[3] = cnt >> 24;
    secp256k1_sha256_write(&hash, buf4, 4);
    secp256k1_sha256_finalize(&hash, out32);

    /* Writing and finalizing together should trigger exactly one SHA256 compression. */
    VERIFY_CHECK(((hash.bytes) >> 6) == (blocks + 1));
}

/** Find an ElligatorSwift encoding (u, t) for X coordinate x, and random Y coordinate.
 *
 * u32 is the 32-byte big endian encoding of u; t is the output field element t that still
 * needs encoding.
 *
 * hasher is a hasher in the secp256k1_ellswift_prng sense, with the same restrictions. */
static void secp256k1_ellswift_xelligatorswift_var(unsigned char *u32, secp256k1_fe *t, const secp256k1_fe *x, const secp256k1_sha256 *hasher) {
    /* Pool of 3-bit branch values. */
    unsigned char branch_hash[32];
    /* Number of 3-bit values in branch_hash left. */
    int branches_left = 0;
    /* Field elements u and branch values are extracted from RNG based on hasher for consecutive
     * values of cnt. cnt==0 is first used to populate a pool of 64 4-bit branch values. The 64
     * cnt values that follow are used to generate field elements u. cnt==65 (and multiples
     * thereof) are used to repopulate the pool and start over, if that were ever necessary.
     * On average, 4 iterations are needed. */
    uint32_t cnt = 0;
    while (1) {
        int branch;
        secp256k1_fe u;
        /* If the pool of branch values is empty, populate it. */
        if (branches_left == 0) {
            secp256k1_ellswift_prng(branch_hash, hasher, cnt++);
            branches_left = 64;
        }
        /* Take a 3-bit branch value from the branch pool (top bit is discarded). */
        --branches_left;
        branch = (branch_hash[branches_left >> 1] >> ((branches_left & 1) << 2)) & 7;
        /* Compute a new u value by hashing. */
        secp256k1_ellswift_prng(u32, hasher, cnt++);
        /* overflow is not a problem (we prefer uniform u32 over uniform u). */
        secp256k1_fe_set_b32_mod(&u, u32);
        /* Since u is the output of a hash, it should practically never be 0. We could apply the
         * u=0 to u=1 correction here too to deal with that case still, but it's such a low
         * probability event that we do not bother. */
        VERIFY_CHECK(!secp256k1_fe_normalizes_to_zero_var(&u));

        /* Find a remainder t, and return it if found. */
        if (EXPECT(secp256k1_ellswift_xswiftec_inv_var(t, x, &u, branch), 0)) break;
    }
}

/** Find an ElligatorSwift encoding (u, t) for point P.
 *
 * This is similar secp256k1_ellswift_xelligatorswift_var, except it takes a full group element p
 * as input, and returns an encoding that matches the provided Y coordinate rather than a random
 * one.
 */
static void secp256k1_ellswift_elligatorswift_var(unsigned char *u32, secp256k1_fe *t, const secp256k1_ge *p, const secp256k1_sha256 *hasher) {
    secp256k1_ellswift_xelligatorswift_var(u32, t, &p->x, hasher);
    secp256k1_fe_normalize_var(t);
    if (secp256k1_fe_is_odd(t) != secp256k1_fe_is_odd(&p->y)) {
        secp256k1_fe_negate(t, t, 1);
        secp256k1_fe_normalize_var(t);
    }
}

/** Set hash state to the BIP340 tagged hash midstate for "secp256k1_ellswift_encode". */
static void secp256k1_ellswift_sha256_init_encode(secp256k1_sha256* hash) {
    secp256k1_sha256_initialize(hash);
    hash->s[0] = 0xd1a6524bul;
    hash->s[1] = 0x028594b3ul;
    hash->s[2] = 0x96e42f4eul;
    hash->s[3] = 0x1037a177ul;
    hash->s[4] = 0x1b8fcb8bul;
    hash->s[5] = 0x56023885ul;
    hash->s[6] = 0x2560ede1ul;
    hash->s[7] = 0xd626b715ul;

    hash->bytes = 64;
}

int secp256k1_ellswift_encode(const secp256k1_context *ctx, unsigned char *ell64, const secp256k1_pubkey *pubkey, const unsigned char *rnd32) {
    secp256k1_ge p;
    VERIFY_CHECK(ctx != NULL);
    ARG_CHECK(ell64 != NULL);