Page MenuHomePhabricator
Differential D8047 Diff 24972 src/secp256k1/src/scalar_impl.h

Changeset View

Standalone View

View Options

src/secp256k1/src/scalar_impl.h

Show First 20 Lines • Show All 261 Lines • ▼ Show 20 Lines
# define EXHAUSTIVE_TEST_LAMBDA 9 # define EXHAUSTIVE_TEST_LAMBDA 9
# elif EXHAUSTIVE_TEST_ORDER == 199 # elif EXHAUSTIVE_TEST_ORDER == 199
# define EXHAUSTIVE_TEST_LAMBDA 92 # define EXHAUSTIVE_TEST_LAMBDA 92
# else # else
# error No known lambda for the specified exhaustive test group order. # error No known lambda for the specified exhaustive test group order.
# endif # endif
/** /**
* Find k1 and k2 given k, such that k1 + k2 * lambda == k mod n; unlike in the * Find r1 and r2 given k, such that r1 + r2 * lambda == k mod n; unlike in the
* full case we don't bother making k1 and k2 be small, we just want them to be * full case we don't bother making r1 and r2 be small, we just want them to be
* nontrivial to get full test coverage for the exhaustive tests. We therefore * nontrivial to get full test coverage for the exhaustive tests. We therefore
* (arbitrarily) set k2 = k + 5 and k1 = k - k2 * lambda. * (arbitrarily) set r2 = k + 5 (mod n) and r1 = k - r2 * lambda (mod n).
*/ */
static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a) { static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *k) {
*r2 = (*a + 5) % EXHAUSTIVE_TEST_ORDER; *r2 = (*k + 5) % EXHAUSTIVE_TEST_ORDER;
*r1 = (*a + (EXHAUSTIVE_TEST_ORDER - *r2) * EXHAUSTIVE_TEST_LAMBDA) % EXHAUSTIVE_TEST_ORDER; *r1 = (*k + (EXHAUSTIVE_TEST_ORDER - *r2) * EXHAUSTIVE_TEST_LAMBDA) % EXHAUSTIVE_TEST_ORDER;
} }
#else #else
/** /**
* The Secp256k1 curve has an endomorphism, where lambda * (x, y) = (beta * x, y), where * The Secp256k1 curve has an endomorphism, where lambda * (x, y) = (beta * x, y), where
* lambda is: */ * lambda is: */
static const secp256k1_scalar secp256k1_const_lambda = SECP256K1_SCALAR_CONST( static const secp256k1_scalar secp256k1_const_lambda = SECP256K1_SCALAR_CONST(
0x5363AD4CUL, 0xC05C30E0UL, 0xA5261C02UL, 0x8812645AUL, 0x5363AD4CUL, 0xC05C30E0UL, 0xA5261C02UL, 0x8812645AUL,
0x122E22EAUL, 0x20816678UL, 0xDF02967CUL, 0x1B23BD72UL 0x122E22EAUL, 0x20816678UL, 0xDF02967CUL, 0x1B23BD72UL
Show All 18 Lines
* *
* - a1 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15} * - a1 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}
* - b1 = -{0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3} * - b1 = -{0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3}
* - a2 = {0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,0xd8} * - a2 = {0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,0xd8}
* - b2 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15} * - b2 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}
* *
* "Guide to Elliptic Curve Cryptography" (Hankerson, Menezes, Vanstone) gives an algorithm * "Guide to Elliptic Curve Cryptography" (Hankerson, Menezes, Vanstone) gives an algorithm
* (algorithm 3.74) to find k1 and k2 given k, such that k1 + k2 * lambda == k mod n, and k1 * (algorithm 3.74) to find k1 and k2 given k, such that k1 + k2 * lambda == k mod n, and k1
* and k2 have a small size. * and k2 are small in absolute value.
* *
* The algorithm computes c1 = round(b2 * k / n) and c2 = round((-b1) * k / n), and gives * The algorithm computes c1 = round(b2 * k / n) and c2 = round((-b1) * k / n), and gives
* k1 = k - (c1*a1 + c2*a2) and k2 = -(c1*b1 + c2*b2). Instead, we use modular arithmetic, and * k1 = k - (c1*a1 + c2*a2) and k2 = -(c1*b1 + c2*b2). Instead, we use modular arithmetic, and
* compute k - k2 * lambda (mod n) which is equivalent to k1 (mod n), avoiding the need for * compute r2 = k2 mod n, and r1 = k1 mod n = (k - r2 * lambda) mod n, avoiding the need for
* the constants a1 and a2. * the constants a1 and a2.
* *
* g1, g2 are precomputed constants used to replace division with a rounded multiplication * g1, g2 are precomputed constants used to replace division with a rounded multiplication
* when decomposing the scalar for an endomorphism-based point multiplication. * when decomposing the scalar for an endomorphism-based point multiplication.
* *
* The possibility of using precomputed estimates is mentioned in "Guide to Elliptic Curve * The possibility of using precomputed estimates is mentioned in "Guide to Elliptic Curve
* Cryptography" (Hankerson, Menezes, Vanstone) in section 3.5. * Cryptography" (Hankerson, Menezes, Vanstone) in section 3.5.
* *
▲ Show 20 Lines • Show All 192 Lines • Show Last 20 Lines