view release on metacpan or  search on metacpan

libsecp256k1/src/ecmult_const_impl.h  view on Meta::CPAN

#endif

#define ECMULT_CONST_TABLE_SIZE (1L << (ECMULT_CONST_GROUP_SIZE - 1))
#define ECMULT_CONST_GROUPS ((129 + ECMULT_CONST_GROUP_SIZE - 1) / ECMULT_CONST_GROUP_SIZE)
#define ECMULT_CONST_BITS (ECMULT_CONST_GROUPS * ECMULT_CONST_GROUP_SIZE)

/** Fill a table 'pre' with precomputed odd multiples of a.
 *
 *  The resulting point set is brought to a single constant Z denominator, stores the X and Y
 *  coordinates as ge points in pre, and stores the global Z in globalz.
 *
 *  'pre' must be an array of size ECMULT_CONST_TABLE_SIZE.
 */
static void secp256k1_ecmult_const_odd_multiples_table_globalz(secp256k1_ge *pre, secp256k1_fe *globalz, const secp256k1_gej *a) {
    secp256k1_fe zr[ECMULT_CONST_TABLE_SIZE];

    secp256k1_ecmult_odd_multiples_table(ECMULT_CONST_TABLE_SIZE, pre, zr, globalz, a);
    secp256k1_ge_table_set_globalz(ECMULT_CONST_TABLE_SIZE, pre, zr);
}

/* Given a table 'pre' with odd multiples of a point, put in r the signed-bit multiplication of n with that point.
 *
 * For example, if ECMULT_CONST_GROUP_SIZE is 4, then pre is expected to contain 8 entries:
 * [1*P, 3*P, 5*P, 7*P, 9*P, 11*P, 13*P, 15*P]. n is then expected to be a 4-bit integer (range 0-15), and its
 * bits are interpreted as signs of powers of two to look up.
 *
 * For example, if n=4, which is 0100 in binary, which is interpreted as [- + - -], so the looked up value is
 * [ -(2^3) + (2^2) - (2^1) - (2^0) ]*P = -7*P. Every valid n translates to an odd number in range [-15,15],
 * which means we just need to look up one of the precomputed values, and optionally negate it.
 */
#define ECMULT_CONST_TABLE_GET_GE(r,pre,n) do { \
    unsigned int m = 0; \
    /* If the top bit of n is 0, we want the negation. */ \
    volatile unsigned int negative = ((n) >> (ECMULT_CONST_GROUP_SIZE - 1)) ^ 1; \
    /* Let n[i] be the i-th bit of n, then the index is
     *     sum(cnot(n[i]) * 2^i, i=0..l-2)
     * where cnot(b) = b if n[l-1] = 1 and 1 - b otherwise.
     * For example, if n = 4, in binary 0100, the index is 3, in binary 011.
     *
     * Proof:
     *     Let
     *         x = sum((2*n[i] - 1)*2^i, i=0..l-1)
     *           = 2*sum(n[i] * 2^i, i=0..l-1) - 2^l + 1
     *     be the value represented by n.
     *     The index is (x - 1)/2 if x > 0 and -(x + 1)/2 otherwise.
     *     Case x > 0:
     *         n[l-1] = 1
     *         index = sum(n[i] * 2^i, i=0..l-1) - 2^(l-1)
     *               = sum(n[i] * 2^i, i=0..l-2)
     *     Case x <= 0:
     *         n[l-1] = 0
     *          index = -(2*sum(n[i] * 2^i, i=0..l-1) - 2^l + 2)/2
     *                = 2^(l-1) - 1 - sum(n[i] * 2^i, i=0..l-1)
     *                = sum((1 - n[i]) * 2^i, i=0..l-2)
     */ \
    unsigned int index = ((unsigned int)(-negative) ^ n) & ((1U << (ECMULT_CONST_GROUP_SIZE - 1)) - 1U); \
    secp256k1_fe neg_y; \
    VERIFY_CHECK((n) < (1U << ECMULT_CONST_GROUP_SIZE)); \
    VERIFY_CHECK(index < (1U << (ECMULT_CONST_GROUP_SIZE - 1))); \
    /* Unconditionally set r->x = (pre)[m].x. r->y = (pre)[m].y. because it's either the correct one
     * or will get replaced in the later iterations, this is needed to make sure `r` is initialized. */ \
    (r)->x = (pre)[m].x; \
    (r)->y = (pre)[m].y; \
    for (m = 1; m < ECMULT_CONST_TABLE_SIZE; m++) { \
        /* This loop is used to avoid secret data in array indices. See
         * the comment in ecmult_gen_impl.h for rationale. */ \
        secp256k1_fe_cmov(&(r)->x, &(pre)[m].x, m == index); \
        secp256k1_fe_cmov(&(r)->y, &(pre)[m].y, m == index); \
    } \
    (r)->infinity = 0; \
    secp256k1_fe_negate(&neg_y, &(r)->y, 1); \
    secp256k1_fe_cmov(&(r)->y, &neg_y, negative); \
} while(0)

/* For K as defined in the comment of secp256k1_ecmult_const, we have several precomputed
 * formulas/constants.
 * - in exhaustive test mode, we give an explicit expression to compute it at compile time: */
#ifdef EXHAUSTIVE_TEST_ORDER
static const secp256k1_scalar secp256k1_ecmult_const_K = ((SECP256K1_SCALAR_CONST(0, 0, 0, (1U << (ECMULT_CONST_BITS - 128)) - 2U, 0, 0, 0, 0) + EXHAUSTIVE_TEST_ORDER - 1U) * (1U + EXHAUSTIVE_TEST_LAMBDA)) % EXHAUSTIVE_TEST_ORDER;
/* - for the real secp256k1 group we have constants for various ECMULT_CONST_BITS values. */
#elif ECMULT_CONST_BITS == 129
/* For GROUP_SIZE = 1,3. */
static const secp256k1_scalar secp256k1_ecmult_const_K = SECP256K1_SCALAR_CONST(0xac9c52b3ul, 0x3fa3cf1ful, 0x5ad9e3fdul, 0x77ed9ba4ul, 0xa880b9fcul, 0x8ec739c2ul, 0xe0cfc810ul, 0xb51283ceul);
#elif ECMULT_CONST_BITS == 130
/* For GROUP_SIZE = 2,5. */
static const secp256k1_scalar secp256k1_ecmult_const_K = SECP256K1_SCALAR_CONST(0xa4e88a7dul, 0xcb13034eul, 0xc2bdd6bful, 0x7c118d6bul, 0x589ae848ul, 0x26ba29e4ul, 0xb5c2c1dcul, 0xde9798d9ul);
#elif ECMULT_CONST_BITS == 132
/* For GROUP_SIZE = 4,6 */
static const secp256k1_scalar secp256k1_ecmult_const_K = SECP256K1_SCALAR_CONST(0x76b1d93dul, 0x0fae3c6bul, 0x3215874bul, 0x94e93813ul, 0x7937fe0dul, 0xb66bcaaful, 0xb3749ca5ul, 0xd7b6171bul);
#else
#  error "Unknown ECMULT_CONST_BITS"
#endif

static void secp256k1_ecmult_const(secp256k1_gej *r, const secp256k1_ge *a, const secp256k1_scalar *q) {
    /* The approach below combines the signed-digit logic from Mike Hamburg's
     * "Fast and compact elliptic-curve cryptography" (https://eprint.iacr.org/2012/309)
     * Section 3.3, with the GLV endomorphism.
     *
     * The idea there is to interpret the bits of a scalar as signs (1 = +, 0 = -), and compute a
     * point multiplication in that fashion. Let v be an n-bit non-negative integer (0 <= v < 2^n),
     * and v[i] its i'th bit (so v = sum(v[i] * 2^i, i=0..n-1)). Then define:
     *
     *   C_l(v, A) = sum((2*v[i] - 1) * 2^i*A, i=0..l-1)
     *
     * Then it holds that C_l(v, A) = sum((2*v[i] - 1) * 2^i*A, i=0..l-1)
     *                              = (2*sum(v[i] * 2^i, i=0..l-1) + 1 - 2^l) * A
     *                              = (2*v + 1 - 2^l) * A
     *
     * Thus, one can compute q*A as C_256((q + 2^256 - 1) / 2, A). This is the basis for the
     * paper's signed-digit multi-comb algorithm for multiplication using a precomputed table.
     *
     * It is appealing to try to combine this with the GLV optimization: the idea that a scalar
     * s can be written as s1 + lambda*s2, where lambda is a curve-specific constant such that
     * lambda*A is easy to compute, and where s1 and s2 are small. In particular we have the
     * secp256k1_scalar_split_lambda function which performs such a split with the resulting s1
     * and s2 in range (-2^128, 2^128) mod n. This does work, but is uninteresting:
     *
     *   To compute q*A:
     *   - Let s1, s2 = split_lambda(q)
     *   - Let R1 = C_256((s1 + 2^256 - 1) / 2, A)
     *   - Let R2 = C_256((s2 + 2^256 - 1) / 2, lambda*A)