Page MenuHomePhabricator
Differential D9405 Diff 28172 src/secp256k1/src/scalar_8x32_impl.h

Changeset View

Standalone View

View Options

src/secp256k1/src/scalar_8x32_impl.h

/*********************************************************************** /***********************************************************************
* Copyright (c) 2014 Pieter Wuille * * Copyright (c) 2014 Pieter Wuille *
* Distributed under the MIT software license, see the accompanying * * Distributed under the MIT software license, see the accompanying *
* file COPYING or https://www.opensource.org/licenses/mit-license.php.* * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
***********************************************************************/ ***********************************************************************/
#ifndef SECP256K1_SCALAR_REPR_IMPL_H #ifndef SECP256K1_SCALAR_REPR_IMPL_H
#define SECP256K1_SCALAR_REPR_IMPL_H #define SECP256K1_SCALAR_REPR_IMPL_H
#include "modinv32_impl.h"
/* Limbs of the secp256k1 order. */ /* Limbs of the secp256k1 order. */
#define SECP256K1_N_0 ((uint32_t)0xD0364141UL) #define SECP256K1_N_0 ((uint32_t)0xD0364141UL)
#define SECP256K1_N_1 ((uint32_t)0xBFD25E8CUL) #define SECP256K1_N_1 ((uint32_t)0xBFD25E8CUL)
#define SECP256K1_N_2 ((uint32_t)0xAF48A03BUL) #define SECP256K1_N_2 ((uint32_t)0xAF48A03BUL)
#define SECP256K1_N_3 ((uint32_t)0xBAAEDCE6UL) #define SECP256K1_N_3 ((uint32_t)0xBAAEDCE6UL)
#define SECP256K1_N_4 ((uint32_t)0xFFFFFFFEUL) #define SECP256K1_N_4 ((uint32_t)0xFFFFFFFEUL)
#define SECP256K1_N_5 ((uint32_t)0xFFFFFFFFUL) #define SECP256K1_N_5 ((uint32_t)0xFFFFFFFFUL)
#define SECP256K1_N_6 ((uint32_t)0xFFFFFFFFUL) #define SECP256K1_N_6 ((uint32_t)0xFFFFFFFFUL)
▲ Show 20 Lines • Show All 708 Lines • ▼ Show 20 Linesstatic SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) {
r->d[2] = (r->d[2] & mask0) | (a->d[2] & mask1); r->d[2] = (r->d[2] & mask0) | (a->d[2] & mask1);
r->d[3] = (r->d[3] & mask0) | (a->d[3] & mask1); r->d[3] = (r->d[3] & mask0) | (a->d[3] & mask1);
r->d[4] = (r->d[4] & mask0) | (a->d[4] & mask1); r->d[4] = (r->d[4] & mask0) | (a->d[4] & mask1);
r->d[5] = (r->d[5] & mask0) | (a->d[5] & mask1); r->d[5] = (r->d[5] & mask0) | (a->d[5] & mask1);
r->d[6] = (r->d[6] & mask0) | (a->d[6] & mask1); r->d[6] = (r->d[6] & mask0) | (a->d[6] & mask1);
r->d[7] = (r->d[7] & mask0) | (a->d[7] & mask1); r->d[7] = (r->d[7] & mask0) | (a->d[7] & mask1);
} }
static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *x) { static void secp256k1_scalar_from_signed30(secp256k1_scalar *r, const secp256k1_modinv32_signed30 *a) {
secp256k1_scalar *t; const uint32_t a0 = a->v[0], a1 = a->v[1], a2 = a->v[2], a3 = a->v[3], a4 = a->v[4],
int i; a5 = a->v[5], a6 = a->v[6], a7 = a->v[7], a8 = a->v[8];
/* First compute xN as x ^ (2^N - 1) for some values of N,
* and uM as x ^ M for some values of M. */ /* The output from secp256k1_modinv32{_var} should be normalized to range [0,modulus), and
secp256k1_scalar x2, x3, x6, x8, x14, x28, x56, x112, x126; * have limbs in [0,2^30). The modulus is < 2^256, so the top limb must be below 2^(256-30*8).
secp256k1_scalar u2, u5, u9, u11, u13; */
VERIFY_CHECK(a0 >> 30 == 0);
secp256k1_scalar_sqr(&u2, x); VERIFY_CHECK(a1 >> 30 == 0);
secp256k1_scalar_mul(&x2, &u2, x); VERIFY_CHECK(a2 >> 30 == 0);
secp256k1_scalar_mul(&u5, &u2, &x2); VERIFY_CHECK(a3 >> 30 == 0);
secp256k1_scalar_mul(&x3, &u5, &u2); VERIFY_CHECK(a4 >> 30 == 0);
secp256k1_scalar_mul(&u9, &x3, &u2); VERIFY_CHECK(a5 >> 30 == 0);
secp256k1_scalar_mul(&u11, &u9, &u2); VERIFY_CHECK(a6 >> 30 == 0);
secp256k1_scalar_mul(&u13, &u11, &u2); VERIFY_CHECK(a7 >> 30 == 0);
VERIFY_CHECK(a8 >> 16 == 0);
r->d[0] = a0 | a1 << 30;
r->d[1] = a1 >> 2 | a2 << 28;
r->d[2] = a2 >> 4 | a3 << 26;
r->d[3] = a3 >> 6 | a4 << 24;
r->d[4] = a4 >> 8 | a5 << 22;
r->d[5] = a5 >> 10 | a6 << 20;
r->d[6] = a6 >> 12 | a7 << 18;
r->d[7] = a7 >> 14 | a8 << 16;
secp256k1_scalar_sqr(&x6, &u13); #ifdef VERIFY
secp256k1_scalar_sqr(&x6, &x6); VERIFY_CHECK(secp256k1_scalar_check_overflow(r) == 0);
secp256k1_scalar_mul(&x6, &x6, &u11); #endif
secp256k1_scalar_sqr(&x8, &x6);
secp256k1_scalar_sqr(&x8, &x8);
secp256k1_scalar_mul(&x8, &x8, &x2);
secp256k1_scalar_sqr(&x14, &x8);
for (i = 0; i < 5; i++) {
secp256k1_scalar_sqr(&x14, &x14);
} }
secp256k1_scalar_mul(&x14, &x14, &x6);
secp256k1_scalar_sqr(&x28, &x14); static void secp256k1_scalar_to_signed30(secp256k1_modinv32_signed30 *r, const secp256k1_scalar *a) {
for (i = 0; i < 13; i++) { const uint32_t M30 = UINT32_MAX >> 2;
secp256k1_scalar_sqr(&x28, &x28); const uint32_t a0 = a->d[0], a1 = a->d[1], a2 = a->d[2], a3 = a->d[3],
} a4 = a->d[4], a5 = a->d[5], a6 = a->d[6], a7 = a->d[7];
secp256k1_scalar_mul(&x28, &x28, &x14);
secp256k1_scalar_sqr(&x56, &x28); #ifdef VERIFY
for (i = 0; i < 27; i++) { VERIFY_CHECK(secp256k1_scalar_check_overflow(a) == 0);
secp256k1_scalar_sqr(&x56, &x56); #endif
}
secp256k1_scalar_mul(&x56, &x56, &x28);
secp256k1_scalar_sqr(&x112, &x56); r->v[0] = a0 & M30;
for (i = 0; i < 55; i++) { r->v[1] = (a0 >> 30 | a1 << 2) & M30;
secp256k1_scalar_sqr(&x112, &x112); r->v[2] = (a1 >> 28 | a2 << 4) & M30;
r->v[3] = (a2 >> 26 | a3 << 6) & M30;
r->v[4] = (a3 >> 24 | a4 << 8) & M30;
r->v[5] = (a4 >> 22 | a5 << 10) & M30;
r->v[6] = (a5 >> 20 | a6 << 12) & M30;
r->v[7] = (a6 >> 18 | a7 << 14) & M30;
r->v[8] = a7 >> 16;
} }
secp256k1_scalar_mul(&x112, &x112, &x56);
secp256k1_scalar_sqr(&x126, &x112); static const secp256k1_modinv32_modinfo secp256k1_const_modinfo_scalar = {
for (i = 0; i < 13; i++) { {{0x10364141L, 0x3F497A33L, 0x348A03BBL, 0x2BB739ABL, -0x146L, 0, 0, 0, 65536}},
secp256k1_scalar_sqr(&x126, &x126); 0x2A774EC1L
} };
secp256k1_scalar_mul(&x126, &x126, &x14);
/* Then accumulate the final result (t starts at x126). */ static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *x) {
t = &x126; secp256k1_modinv32_signed30 s;
for (i = 0; i < 3; i++) { #ifdef VERIFY
secp256k1_scalar_sqr(t, t); int zero_in = secp256k1_scalar_is_zero(x);
} #endif
secp256k1_scalar_mul(t, t, &u5); /* 101 */ secp256k1_scalar_to_signed30(&s, x);
for (i = 0; i < 4; i++) { /* 0 */ secp256k1_modinv32(&s, &secp256k1_const_modinfo_scalar);
secp256k1_scalar_sqr(t, t); secp256k1_scalar_from_signed30(r, &s);
}
secp256k1_scalar_mul(t, t, &x3); /* 111 */ #ifdef VERIFY
for (i = 0; i < 4; i++) { /* 0 */ VERIFY_CHECK(secp256k1_scalar_is_zero(r) == zero_in);
secp256k1_scalar_sqr(t, t); #endif
}
secp256k1_scalar_mul(t, t, &u5); /* 101 */
for (i = 0; i < 5; i++) { /* 0 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &u11); /* 1011 */
for (i = 0; i < 4; i++) {
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &u11); /* 1011 */
for (i = 0; i < 4; i++) { /* 0 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &x3); /* 111 */
for (i = 0; i < 5; i++) { /* 00 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &x3); /* 111 */
for (i = 0; i < 6; i++) { /* 00 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &u13); /* 1101 */
for (i = 0; i < 4; i++) { /* 0 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &u5); /* 101 */
for (i = 0; i < 3; i++) {
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &x3); /* 111 */
for (i = 0; i < 5; i++) { /* 0 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &u9); /* 1001 */
for (i = 0; i < 6; i++) { /* 000 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &u5); /* 101 */
for (i = 0; i < 10; i++) { /* 0000000 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &x3); /* 111 */
for (i = 0; i < 4; i++) { /* 0 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &x3); /* 111 */
for (i = 0; i < 9; i++) { /* 0 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &x8); /* 11111111 */
for (i = 0; i < 5; i++) { /* 0 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &u9); /* 1001 */
for (i = 0; i < 6; i++) { /* 00 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &u11); /* 1011 */
for (i = 0; i < 4; i++) {
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &u13); /* 1101 */
for (i = 0; i < 5; i++) {
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &x2); /* 11 */
for (i = 0; i < 6; i++) { /* 00 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &u13); /* 1101 */
for (i = 0; i < 10; i++) { /* 000000 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &u13); /* 1101 */
for (i = 0; i < 4; i++) {
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, &u9); /* 1001 */
for (i = 0; i < 6; i++) { /* 00000 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(t, t, x); /* 1 */
for (i = 0; i < 8; i++) { /* 00 */
secp256k1_scalar_sqr(t, t);
}
secp256k1_scalar_mul(r, t, &x6); /* 111111 */
} }
static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *x) { static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *x) {
#if defined(USE_SCALAR_INV_BUILTIN) secp256k1_modinv32_signed30 s;
secp256k1_scalar_inverse(r, x); #ifdef VERIFY
#elif defined(USE_SCALAR_INV_NUM) int zero_in = secp256k1_scalar_is_zero(x);
unsigned char b[32]; #endif
secp256k1_num n, m; secp256k1_scalar_to_signed30(&s, x);
secp256k1_scalar t = *x; secp256k1_modinv32_var(&s, &secp256k1_const_modinfo_scalar);
secp256k1_scalar_get_b32(b, &t); secp256k1_scalar_from_signed30(r, &s);
secp256k1_num_set_bin(&n, b, 32);
secp256k1_scalar_order_get_num(&m); #ifdef VERIFY
secp256k1_num_mod_inverse(&n, &n, &m); VERIFY_CHECK(secp256k1_scalar_is_zero(r) == zero_in);
secp256k1_num_get_bin(b, 32, &n);
secp256k1_scalar_set_b32(r, b, NULL);
/* Verify that the inverse was computed correctly, without GMP code. */
secp256k1_scalar_mul(&t, &t, r);
CHECK(secp256k1_scalar_is_one(&t));
#else
#error "Please select scalar inverse implementation"
#endif #endif
} }
SECP256K1_INLINE static int secp256k1_scalar_is_even(const secp256k1_scalar *a) { SECP256K1_INLINE static int secp256k1_scalar_is_even(const secp256k1_scalar *a) {
return !(a->d[0] & 1); return !(a->d[0] & 1);
} }
#endif /* SECP256K1_SCALAR_REPR_IMPL_H */ #endif /* SECP256K1_SCALAR_REPR_IMPL_H */