Skip to content

Commit 4401500

Browse files
apoelstraapoelstra
committed
Add constant-time multiply secp256k1_ecmult_const for ECDH
Designed with clear separation of the wNAF conversion, precomputation and exponentiation (since the precomp at least we will probably want to separate in the API for users who reuse points a lot. Future work: - actually separate precomp in the API - do multiexp rather than single exponentiation
1 parent baa75da commit 4401500

File tree

11 files changed

+424
-1
lines changed

11 files changed

+424
-1
lines changed

‎Makefile.am‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,8 @@ noinst_HEADERS += src/eckey.h
1919
noinst_HEADERS += src/eckey_impl.h
2020
noinst_HEADERS += src/ecmult.h
2121
noinst_HEADERS += src/ecmult_impl.h
22+
noinst_HEADERS += src/ecmult_const.h
23+
noinst_HEADERS += src/ecmult_const_impl.h
2224
noinst_HEADERS += src/ecmult_gen.h
2325
noinst_HEADERS += src/ecmult_gen_impl.h
2426
noinst_HEADERS += src/num.h

‎src/ecmult_const.h‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
/**********************************************************************
2+
* Copyright (c) 2015 Andrew Poelstra *
3+
* Distributed under the MIT software license, see the accompanying *
4+
* file COPYING or http://www.opensource.org/licenses/mit-license.php.*
5+
**********************************************************************/
6+
7+
#ifndef _SECP256K1_ECMULT_CONST_
8+
#define _SECP256K1_ECMULT_CONST_
9+
10+
#include "scalar.h"
11+
#include "group.h"
12+
13+
static void secp256k1_ecmult_const(secp256k1_gej_t *r, const secp256k1_ge_t *a, const secp256k1_scalar_t *q);
14+
15+
#endif

‎src/ecmult_const_impl.h‎

Lines changed: 139 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,139 @@
1+
/**********************************************************************
2+
* Copyright (c) 2015 Pieter Wuille, Andrew Poelstra *
3+
* Distributed under the MIT software license, see the accompanying *
4+
* file COPYING or http://www.opensource.org/licenses/mit-license.php.*
5+
**********************************************************************/
6+
7+
#ifndef _SECP256K1_ECMULT_CONST_IMPL_
8+
#define _SECP256K1_ECMULT_CONST_IMPL_
9+
10+
#include "scalar.h"
11+
#include "group.h"
12+
#include "ecmult_const.h"
13+
#include "ecmult_impl.h"
14+
15+
#define WNAF_BITS 256
16+
#define WNAF_SIZE(w) ((WNAF_BITS + (w) - 1) / (w))
17+
18+
/* This is like `ECMULT_TABLE_GET_GE` but is constant time */
19+
#define ECMULT_CONST_TABLE_GET_GE(r,pre,n,w) do { \
20+
int m; \
21+
int abs_n = (n) * (((n) > 0) * 2 - 1); \
22+
secp256k1_fe_t neg_y; \
23+
VERIFY_CHECK(((n) & 1) == 1); \
24+
VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
25+
VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1)); \
26+
for (m = 1; m < (1 << ((w) - 1)); m += 2) { \
27+
/* This loop is used to avoid secret data in array indices. See
28+
* the comment in ecmult_gen_impl.h for rationale. */ \
29+
secp256k1_fe_cmov(&(r)->x, &(pre)[(m - 1) / 2].x, m == abs_n); \
30+
secp256k1_fe_cmov(&(r)->y, &(pre)[(m - 1) / 2].y, m == abs_n); \
31+
} \
32+
(r)->infinity = 0; \
33+
secp256k1_fe_normalize_weak(&(r)->x); \
34+
secp256k1_fe_normalize_weak(&(r)->y); \
35+
secp256k1_fe_negate(&neg_y, &(r)->y, 1); \
36+
secp256k1_fe_cmov(&(r)->y, &neg_y, (n) != abs_n); \
37+
} while(0)
38+
39+
40+
/** Convert a number to WNAF notation. The number becomes represented by sum(2^{wi} * wnaf[i], i=0..return_val)
41+
* with the following guarantees:
42+
* - each wnaf[i] an odd integer between -(1 << w) and (1 << w)
43+
* - each wnaf[i] is nonzero
44+
* - the number of words set is returned; this is always (WNAF_BITS + w - 1) / w
45+
*
46+
* Adapted from `The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar
47+
* Multiplications Secure against Side Channel Attacks`, Okeya and Tagaki. M. Joye (Ed.)
48+
* CT-RSA 2003, LNCS 2612, pp. 328-443, 2003. Springer-Verlagy Berlin Heidelberg 2003
49+
*
50+
* Numbers reference steps of `Algorithm SPA-resistant Width-w NAF with Odd Scalar` on pp. 335
51+
*/
52+
static void secp256k1_wnaf_const(int *wnaf, const secp256k1_scalar_t *a, int w) {
53+
secp256k1_scalar_t s = *a;
54+
/* Negate to force oddness */
55+
int is_even = secp256k1_scalar_is_even(&s);
56+
int global_sign = secp256k1_scalar_cond_negate(&s, is_even);
57+
58+
int word = 0;
59+
/* 1 2 3 */
60+
int u_last = secp256k1_scalar_shr_int(&s, w);
61+
int u;
62+
/* 4 */
63+
while (word * w < WNAF_BITS) {
64+
int sign;
65+
int even;
66+
67+
/* 4.1 4.4 */
68+
u = secp256k1_scalar_shr_int(&s, w);
69+
/* 4.2 */
70+
even = ((u & 1) == 0);
71+
sign = 2 * (u_last > 0) - 1;
72+
u += sign * even;
73+
u_last -= sign * even * (1 << w);
74+
75+
/* 4.3, adapted for global sign change */
76+
wnaf[word++] = u_last * global_sign;
77+
78+
u_last = u;
79+
}
80+
wnaf[word] = u * global_sign;
81+
82+
VERIFY_CHECK(secp256k1_scalar_is_zero(&s));
83+
VERIFY_CHECK(word == WNAF_SIZE(w));
84+
}
85+
86+
87+
static void secp256k1_ecmult_const(secp256k1_gej_t *r, const secp256k1_ge_t *a, const secp256k1_scalar_t *scalar) {
88+
secp256k1_ge_t pre_a[ECMULT_TABLE_SIZE(WINDOW_A)];
89+
secp256k1_ge_t tmpa;
90+
secp256k1_fe_t Z;
91+
92+
int wnaf[1 + WNAF_SIZE(WINDOW_A - 1)];
93+
94+
int i;
95+
int is_zero = secp256k1_scalar_is_zero(scalar);
96+
secp256k1_scalar_t sc = *scalar;
97+
/* the wNAF ladder cannot handle zero, so bump this to one .. we will
98+
* correct the result after the fact */
99+
sc.d[0] += is_zero;
100+
101+
/* build wnaf representation for q. */
102+
secp256k1_wnaf_const(wnaf, &sc, WINDOW_A - 1);
103+
104+
/* Calculate odd multiples of a.
105+
* All multiples are brought to the same Z 'denominator', which is stored
106+
* in Z. Due to secp256k1' isomorphism we can do all operations pretending
107+
* that the Z coordinate was 1, use affine addition formulae, and correct
108+
* the Z coordinate of the result once at the end.
109+
*/
110+
secp256k1_gej_set_ge(r, a);
111+
secp256k1_ecmult_odd_multiples_table_globalz_windowa(pre_a, &Z, r);
112+
113+
/* first loop iteration (separated out so we can directly set r, rather
114+
* than having it start at infinity, get doubled several times, then have
115+
* its new value added to it) */
116+
i = wnaf[WNAF_SIZE(WINDOW_A - 1)];
117+
VERIFY_CHECK(i != 0);
118+
ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a, i, WINDOW_A);
119+
secp256k1_gej_set_ge(r, &tmpa);
120+
/* remaining loop iterations */
121+
for (i = WNAF_SIZE(WINDOW_A - 1) - 1; i >= 0; i--) {
122+
int n;
123+
int j;
124+
for (j = 0; j < WINDOW_A - 1; ++j) {
125+
secp256k1_gej_double_nonzero(r, r, NULL);
126+
}
127+
n = wnaf[i];
128+
VERIFY_CHECK(n != 0);
129+
ECMULT_CONST_TABLE_GET_GE(&tmpa, pre_a, n, WINDOW_A);
130+
secp256k1_gej_add_ge(r, r, &tmpa);
131+
}
132+
133+
secp256k1_fe_mul(&r->z, &r->z, &Z);
134+
135+
/* correct for zero */
136+
r->infinity |= is_zero;
137+
}
138+
139+
#endif

‎src/group.h‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -94,6 +94,10 @@ static void secp256k1_gej_neg(secp256k1_gej_t *r, const secp256k1_gej_t *a);
9494
/** Check whether a group element is the point at infinity. */
9595
static int secp256k1_gej_is_infinity(const secp256k1_gej_t *a);
9696

97+
/** Set r equal to the double of a. If rzr is not-NULL, r->z = a->z * *rzr (where infinity means an implicit z = 0).
98+
* a may not be zero. Constant time. */
99+
static void secp256k1_gej_double_nonzero(secp256k1_gej_t *r, const secp256k1_gej_t *a, secp256k1_fe_t *rzr);
100+
97101
/** Set r equal to the double of a. If rzr is not-NULL, r->z = a->z * *rzr (where infinity means an implicit z = 0). */
98102
static void secp256k1_gej_double_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, secp256k1_fe_t *rzr);
99103

‎src/group_impl.h‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -301,6 +301,11 @@ static void secp256k1_gej_double_var(secp256k1_gej_t *r, const secp256k1_gej_t *
301301
secp256k1_fe_add(&r->y, &t2); /* Y' = 36*X^3*Y^2 - 27*X^6 - 8*Y^4 (4) */
302302
}
303303

304+
static SECP256K1_INLINE void secp256k1_gej_double_nonzero(secp256k1_gej_t *r, const secp256k1_gej_t *a, secp256k1_fe_t *rzr) {
305+
VERIFY_CHECK(!secp256k1_gej_is_infinity(a));
306+
secp256k1_gej_double_var(r, a, rzr);
307+
}
308+
304309
static void secp256k1_gej_add_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_gej_t *b, secp256k1_fe_t *rzr) {
305310
/* Operations: 12 mul, 4 sqr, 2 normalize, 12 mul_int/add/negate */
306311
secp256k1_fe_t z22, z12, u1, u2, s1, s2, h, i, i2, h2, h3, t;

‎src/scalar.h‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -48,6 +48,10 @@ static void secp256k1_scalar_add_bit(secp256k1_scalar_t *r, unsigned int bit);
4848
/** Multiply two scalars (modulo the group order). */
4949
static void secp256k1_scalar_mul(secp256k1_scalar_t *r, const secp256k1_scalar_t *a, const secp256k1_scalar_t *b);
5050

51+
/** Shift a scalar right by some amount strictly between 0 and 16, returning
52+
* the low bits that were shifted off */
53+
static int secp256k1_scalar_shr_int(secp256k1_scalar_t *r, int n);
54+
5155
/** Compute the square of a scalar (modulo the group order). */
5256
static void secp256k1_scalar_sqr(secp256k1_scalar_t *r, const secp256k1_scalar_t *a);
5357

@@ -66,9 +70,16 @@ static int secp256k1_scalar_is_zero(const secp256k1_scalar_t *a);
6670
/** Check whether a scalar equals one. */
6771
static int secp256k1_scalar_is_one(const secp256k1_scalar_t *a);
6872

73+
/** Check whether a scalar, considered as an nonnegative integer, is even. */
74+
static int secp256k1_scalar_is_even(const secp256k1_scalar_t *a);
75+
6976
/** Check whether a scalar is higher than the group order divided by 2. */
7077
static int secp256k1_scalar_is_high(const secp256k1_scalar_t *a);
7178

79+
/** Conditionally negate a number, in constant time.
80+
* Returns -1 if the number was negated, 1 otherwise */
81+
static int secp256k1_scalar_cond_negate(secp256k1_scalar_t *a, int flag);
82+
7283
#ifndef USE_NUM_NONE
7384
/** Convert a scalar to a number. */
7485
static void secp256k1_scalar_get_num(secp256k1_num_t *r, const secp256k1_scalar_t *a);

‎src/scalar_4x64_impl.h‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -164,6 +164,22 @@ static int secp256k1_scalar_is_high(const secp256k1_scalar_t *a) {
164164
return yes;
165165
}
166166

167+
static int secp256k1_scalar_cond_negate(secp256k1_scalar_t *r, int flag) {
168+
/* If we are flag = 0, mask = 00...00 and this is a no-op;
169+
* if we are flag = 1, mask = 11...11 and this is identical to secp256k1_scalar_negate */
170+
uint64_t mask = !flag - 1;
171+
uint64_t nonzero = (secp256k1_scalar_is_zero(r) != 0) - 1;
172+
uint128_t t = (uint128_t)(r->d[0] ^ mask) + ((SECP256K1_N_0 + 1) & mask);
173+
r->d[0] = t & nonzero; t >>= 64;
174+
t += (uint128_t)(r->d[1] ^ mask) + (SECP256K1_N_1 & mask);
175+
r->d[1] = t & nonzero; t >>= 64;
176+
t += (uint128_t)(r->d[2] ^ mask) + (SECP256K1_N_2 & mask);
177+
r->d[2] = t & nonzero; t >>= 64;
178+
t += (uint128_t)(r->d[3] ^ mask) + (SECP256K1_N_3 & mask);
179+
r->d[3] = t & nonzero;
180+
return 2 * (mask == 0) - 1;
181+
}
182+
167183
/* Inspired by the macros in OpenSSL's crypto/bn/asm/x86_64-gcc.c. */
168184

169185
/** Add a*b to the number defined by (c0,c1,c2). c2 must never overflow. */
@@ -877,6 +893,18 @@ static void secp256k1_scalar_mul(secp256k1_scalar_t *r, const secp256k1_scalar_t
877893
secp256k1_scalar_reduce_512(r, l);
878894
}
879895

896+
static int secp256k1_scalar_shr_int(secp256k1_scalar_t *r, int n) {
897+
int ret;
898+
VERIFY_CHECK(n > 0);
899+
VERIFY_CHECK(n < 16);
900+
ret = r->d[0] & ((1 << n) - 1);
901+
r->d[0] = (r->d[0] >> n) + (r->d[1] << (64 - n));
902+
r->d[1] = (r->d[1] >> n) + (r->d[2] << (64 - n));
903+
r->d[2] = (r->d[2] >> n) + (r->d[3] << (64 - n));
904+
r->d[3] = (r->d[3] >> n);
905+
return ret;
906+
}
907+
880908
static void secp256k1_scalar_sqr(secp256k1_scalar_t *r, const secp256k1_scalar_t *a) {
881909
uint64_t l[8];
882910
secp256k1_scalar_sqr_512(l, a);

‎src/scalar_8x32_impl.h‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -234,6 +234,31 @@ static int secp256k1_scalar_is_high(const secp256k1_scalar_t *a) {
234234
return yes;
235235
}
236236

237+
static int secp256k1_scalar_cond_negate(secp256k1_scalar_t *r, int flag) {
238+
/* If we are flag = 0, mask = 00...00 and this is a no-op;
239+
* if we are flag = 1, mask = 11...11 and this is identical to secp256k1_scalar_negate */
240+
uint32_t mask = !flag - 1;
241+
uint32_t nonzero = 0xFFFFFFFFUL * (secp256k1_scalar_is_zero(r) == 0);
242+
uint64_t t = (uint64_t)(r->d[0] ^ mask) + ((SECP256K1_N_0 + 1) & mask);
243+
r->d[0] = t & nonzero; t >>= 32;
244+
t += (uint64_t)(r->d[1] ^ mask) + (SECP256K1_N_1 & mask);
245+
r->d[1] = t & nonzero; t >>= 32;
246+
t += (uint64_t)(r->d[2] ^ mask) + (SECP256K1_N_2 & mask);
247+
r->d[2] = t & nonzero; t >>= 32;
248+
t += (uint64_t)(r->d[3] ^ mask) + (SECP256K1_N_3 & mask);
249+
r->d[3] = t & nonzero; t >>= 32;
250+
t += (uint64_t)(r->d[4] ^ mask) + (SECP256K1_N_4 & mask);
251+
r->d[4] = t & nonzero; t >>= 32;
252+
t += (uint64_t)(r->d[5] ^ mask) + (SECP256K1_N_5 & mask);
253+
r->d[5] = t & nonzero; t >>= 32;
254+
t += (uint64_t)(r->d[6] ^ mask) + (SECP256K1_N_6 & mask);
255+
r->d[6] = t & nonzero; t >>= 32;
256+
t += (uint64_t)(r->d[7] ^ mask) + (SECP256K1_N_7 & mask);
257+
r->d[7] = t & nonzero;
258+
return 2 * (mask == 0) - 1;
259+
}
260+
261+
237262
/* Inspired by the macros in OpenSSL's crypto/bn/asm/x86_64-gcc.c. */
238263

239264
/** Add a*b to the number defined by (c0,c1,c2). c2 must never overflow. */
@@ -624,6 +649,22 @@ static void secp256k1_scalar_mul(secp256k1_scalar_t *r, const secp256k1_scalar_t
624649
secp256k1_scalar_reduce_512(r, l);
625650
}
626651

652+
static int secp256k1_scalar_shr_int(secp256k1_scalar_t *r, int n) {
653+
int ret;
654+
VERIFY_CHECK(n > 0);
655+
VERIFY_CHECK(n < 16);
656+
ret = r->d[0] & ((1 << n) - 1);
657+
r->d[0] = (r->d[0] >> n) + (r->d[1] << (32 - n));
658+
r->d[1] = (r->d[1] >> n) + (r->d[2] << (32 - n));
659+
r->d[2] = (r->d[2] >> n) + (r->d[3] << (32 - n));
660+
r->d[3] = (r->d[3] >> n) + (r->d[4] << (32 - n));
661+
r->d[4] = (r->d[4] >> n) + (r->d[5] << (32 - n));
662+
r->d[5] = (r->d[5] >> n) + (r->d[6] << (32 - n));
663+
r->d[6] = (r->d[6] >> n) + (r->d[7] << (32 - n));
664+
r->d[7] = (r->d[7] >> n);
665+
return ret;
666+
}
667+
627668
static void secp256k1_scalar_sqr(secp256k1_scalar_t *r, const secp256k1_scalar_t *a) {
628669
uint32_t l[16];
629670
secp256k1_scalar_sqr_512(l, a);

‎src/scalar_impl.h‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -234,6 +234,11 @@ static void secp256k1_scalar_inverse(secp256k1_scalar_t *r, const secp256k1_scal
234234
secp256k1_scalar_mul(r, t, &x6); /* 111111 */
235235
}
236236

237+
SECP256K1_INLINE static int secp256k1_scalar_is_even(const secp256k1_scalar_t *a) {
238+
/* d[0] is present and is the lowest word for all representations */
239+
return !(a->d[0] & 1);
240+
}
241+
237242
static void secp256k1_scalar_inverse_var(secp256k1_scalar_t *r, const secp256k1_scalar_t *x) {
238243
#if defined(USE_SCALAR_INV_BUILTIN)
239244
secp256k1_scalar_inverse(r, x);

‎src/secp256k1.c‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,7 @@
1414
#include "scalar_impl.h"
1515
#include "group_impl.h"
1616
#include "ecmult_impl.h"
17+
#include "ecmult_const_impl.h"
1718
#include "ecmult_gen_impl.h"
1819
#include "ecdsa_impl.h"
1920
#include "eckey_impl.h"

0 commit comments

Comments
 (0)