Skip to content

Commit fc8285f

Browse files
sipasipa
committed
Merge pull request bitcoin#199
fcc48c4 Remove the non-storage cmov (Pieter Wuille) 55422b6 Switch ecmult_gen to use storage types (Pieter Wuille) 41f8455 Use group element storage type in EC multiplications (Pieter Wuille) e68d720 Add group element storage type (Pieter Wuille) ff889f7 Field storage type (Pieter Wuille)
2 parents fff412e + fcc48c4 commit fc8285f

File tree

10 files changed

+193
-41
lines changed

10 files changed

+193
-41
lines changed

‎src/ecmult_gen_impl.h‎

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ typedef struct {
2424
* None of the resulting prec group elements have a known scalar, and neither do any of
2525
* the intermediate sums while computing a*G.
2626
*/
27-
secp256k1_fe_t prec[64][16][2]; /* prec[j][i] = (16^j * i * G + U_i).{x,y} */
27+
secp256k1_ge_storage_t prec[64][16]; /* prec[j][i] = 16^j * i * G + U_i */
2828
} secp256k1_ecmult_gen_consts_t;
2929

3030
static const secp256k1_ecmult_gen_consts_t *secp256k1_ecmult_gen_consts = NULL;
@@ -80,9 +80,7 @@ static void secp256k1_ecmult_gen_start(void) {
8080
}
8181
for (int j=0; j<64; j++) {
8282
for (int i=0; i<16; i++) {
83-
VERIFY_CHECK(!secp256k1_ge_is_infinity(&prec[j*16 + i]));
84-
ret->prec[j][i][0] = prec[j*16 + i].x;
85-
ret->prec[j][i][1] = prec[j*16 + i].y;
83+
secp256k1_ge_to_storage(&ret->prec[j][i], &prec[j*16 + i]);
8684
}
8785
}
8886

@@ -101,16 +99,17 @@ static void secp256k1_ecmult_gen_stop(void) {
10199

102100
static void secp256k1_ecmult_gen(secp256k1_gej_t *r, const secp256k1_scalar_t *gn) {
103101
const secp256k1_ecmult_gen_consts_t *c = secp256k1_ecmult_gen_consts;
104-
secp256k1_gej_set_infinity(r);
105102
secp256k1_ge_t add;
103+
secp256k1_ge_storage_t adds;
104+
secp256k1_gej_set_infinity(r);
106105
add.infinity = 0;
107106
int bits;
108107
for (int j=0; j<64; j++) {
109108
bits = secp256k1_scalar_get_bits(gn, j * 4, 4);
110109
for (int i=0; i<16; i++) {
111-
secp256k1_fe_cmov(&add.x, &c->prec[j][i][0], i == bits);
112-
secp256k1_fe_cmov(&add.y, &c->prec[j][i][1], i == bits);
110+
secp256k1_ge_storage_cmov(&adds, &c->prec[j][i], i == bits);
113111
}
112+
secp256k1_ge_from_storage(&add, &adds);
114113
secp256k1_gej_add_ge(r, r, &add);
115114
}
116115
bits = 0;

‎src/ecmult_impl.h‎

Lines changed: 27 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -43,41 +43,54 @@ static void secp256k1_ecmult_table_precomp_gej_var(secp256k1_gej_t *pre, const s
4343
secp256k1_gej_add_var(&pre[i], &d, &pre[i-1]);
4444
}
4545

46-
static void secp256k1_ecmult_table_precomp_ge_var(secp256k1_ge_t *pre, const secp256k1_gej_t *a, int w) {
46+
static void secp256k1_ecmult_table_precomp_ge_storage_var(secp256k1_ge_storage_t *pre, const secp256k1_gej_t *a, int w) {
4747
const int table_size = 1 << (w-2);
4848
secp256k1_gej_t *prej = checked_malloc(sizeof(secp256k1_gej_t) * table_size);
49+
secp256k1_ge_t *prea = checked_malloc(sizeof(secp256k1_ge_t) * table_size);
4950
prej[0] = *a;
5051
secp256k1_gej_t d; secp256k1_gej_double_var(&d, a);
5152
for (int i=1; i<table_size; i++) {
5253
secp256k1_gej_add_var(&prej[i], &d, &prej[i-1]);
5354
}
54-
secp256k1_ge_set_all_gej_var(table_size, pre, prej);
55+
secp256k1_ge_set_all_gej_var(table_size, prea, prej);
56+
for (int i=0; i<table_size; i++) {
57+
secp256k1_ge_to_storage(&pre[i], &prea[i]);
58+
}
5559
free(prej);
60+
free(prea);
5661
}
5762

5863
/** The number of entries a table with precomputed multiples needs to have. */
5964
#define ECMULT_TABLE_SIZE(w) (1 << ((w)-2))
6065

6166
/** The following two macro retrieves a particular odd multiple from a table
6267
* of precomputed multiples. */
63-
#define ECMULT_TABLE_GET(r,pre,n,w,neg) do { \
68+
#define ECMULT_TABLE_GET_GEJ(r,pre,n,w) do { \
6469
VERIFY_CHECK(((n) & 1) == 1); \
6570
VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
6671
VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1)); \
6772
if ((n) > 0) \
6873
*(r) = (pre)[((n)-1)/2]; \
6974
else \
70-
(neg)((r), &(pre)[(-(n)-1)/2]); \
75+
secp256k1_gej_neg((r), &(pre)[(-(n)-1)/2]); \
76+
} while(0)
77+
#define ECMULT_TABLE_GET_GE_STORAGE(r,pre,n,w) do { \
78+
VERIFY_CHECK(((n) & 1) == 1); \
79+
VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
80+
VERIFY_CHECK((n) <= ((1 << ((w)-1)) - 1)); \
81+
if ((n) > 0) \
82+
secp256k1_ge_from_storage((r), &(pre)[((n)-1)/2]); \
83+
else {\
84+
secp256k1_ge_from_storage((r), &(pre)[(-(n)-1)/2]); \
85+
secp256k1_ge_neg((r), (r)); \
86+
} \
7187
} while(0)
72-
73-
#define ECMULT_TABLE_GET_GEJ(r,pre,n,w) ECMULT_TABLE_GET((r),(pre),(n),(w),secp256k1_gej_neg)
74-
#define ECMULT_TABLE_GET_GE(r,pre,n,w) ECMULT_TABLE_GET((r),(pre),(n),(w),secp256k1_ge_neg)
7588

7689
typedef struct {
7790
/* For accelerating the computation of a*P + b*G: */
78-
secp256k1_ge_t pre_g[ECMULT_TABLE_SIZE(WINDOW_G)]; /* odd multiples of the generator */
91+
secp256k1_ge_storage_t pre_g[ECMULT_TABLE_SIZE(WINDOW_G)]; /* odd multiples of the generator */
7992
#ifdef USE_ENDOMORPHISM
80-
secp256k1_ge_t pre_g_128[ECMULT_TABLE_SIZE(WINDOW_G)]; /* odd multiples of 2^128*generator */
93+
secp256k1_ge_storage_t pre_g_128[ECMULT_TABLE_SIZE(WINDOW_G)]; /* odd multiples of 2^128*generator */
8194
#endif
8295
} secp256k1_ecmult_consts_t;
8396

@@ -101,9 +114,9 @@ static void secp256k1_ecmult_start(void) {
101114
#endif
102115

103116
/* precompute the tables with odd multiples */
104-
secp256k1_ecmult_table_precomp_ge_var(ret->pre_g, &gj, WINDOW_G);
117+
secp256k1_ecmult_table_precomp_ge_storage_var(ret->pre_g, &gj, WINDOW_G);
105118
#ifdef USE_ENDOMORPHISM
106-
secp256k1_ecmult_table_precomp_ge_var(ret->pre_g_128, &g_128j, WINDOW_G);
119+
secp256k1_ecmult_table_precomp_ge_storage_var(ret->pre_g_128, &g_128j, WINDOW_G);
107120
#endif
108121

109122
/* Set the global pointer to the precomputation table. */
@@ -224,11 +237,11 @@ static void secp256k1_ecmult(secp256k1_gej_t *r, const secp256k1_gej_t *a, const
224237
secp256k1_gej_add_var(r, r, &tmpj);
225238
}
226239
if (i < bits_ng_1 && (n = wnaf_ng_1[i])) {
227-
ECMULT_TABLE_GET_GE(&tmpa, c->pre_g, n, WINDOW_G);
240+
ECMULT_TABLE_GET_GE_STORAGE(&tmpa, c->pre_g, n, WINDOW_G);
228241
secp256k1_gej_add_ge_var(r, r, &tmpa);
229242
}
230243
if (i < bits_ng_128 && (n = wnaf_ng_128[i])) {
231-
ECMULT_TABLE_GET_GE(&tmpa, c->pre_g_128, n, WINDOW_G);
244+
ECMULT_TABLE_GET_GE_STORAGE(&tmpa, c->pre_g_128, n, WINDOW_G);
232245
secp256k1_gej_add_ge_var(r, r, &tmpa);
233246
}
234247
#else
@@ -237,7 +250,7 @@ static void secp256k1_ecmult(secp256k1_gej_t *r, const secp256k1_gej_t *a, const
237250
secp256k1_gej_add_var(r, r, &tmpj);
238251
}
239252
if (i < bits_ng && (n = wnaf_ng[i])) {
240-
ECMULT_TABLE_GET_GE(&tmpa, c->pre_g, n, WINDOW_G);
253+
ECMULT_TABLE_GET_GE_STORAGE(&tmpa, c->pre_g, n, WINDOW_G);
241254
secp256k1_gej_add_ge_var(r, r, &tmpa);
242255
}
243256
#endif

‎src/field.h‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -110,7 +110,13 @@ static void secp256k1_fe_get_hex(char *r64, const secp256k1_fe_t *a);
110110
/** Convert a 64-character hexadecimal string to a field element. */
111111
static int secp256k1_fe_set_hex(secp256k1_fe_t *r, const char *a64);
112112

113+
/** Convert a field element to the storage type. */
114+
static void secp256k1_fe_to_storage(secp256k1_fe_storage_t *r, const secp256k1_fe_t*);
115+
116+
/** Convert a field element back from the storage type. */
117+
static void secp256k1_fe_from_storage(secp256k1_fe_t *r, const secp256k1_fe_storage_t*);
118+
113119
/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */
114-
static void secp256k1_fe_cmov(secp256k1_fe_t *r, const secp256k1_fe_t *a, int flag);
120+
static void secp256k1_fe_storage_cmov(secp256k1_fe_storage_t *r, const secp256k1_fe_storage_t *a, int flag);
115121

116122
#endif

‎src/field_10x26.h‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -37,4 +37,10 @@ typedef struct {
3737
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0))}
3838
#endif
3939

40+
typedef struct {
41+
uint32_t n[8];
42+
} secp256k1_fe_storage_t;
43+
44+
#define SECP256K1_FE_STORAGE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {{ (d0), (d1), (d2), (d3), (d4), (d5), (d6), (d7) }}
45+
4046
#endif

‎src/field_10x26_impl.h‎

Lines changed: 30 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1063,7 +1063,7 @@ static void secp256k1_fe_sqr(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
10631063
#endif
10641064
}
10651065

1066-
static void secp256k1_fe_cmov(secp256k1_fe_t *r, const secp256k1_fe_t *a, int flag) {
1066+
static inline void secp256k1_fe_storage_cmov(secp256k1_fe_storage_t *r, const secp256k1_fe_storage_t *a, int flag) {
10671067
uint32_t mask0 = flag + ~((uint32_t)0), mask1 = ~mask0;
10681068
r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
10691069
r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
@@ -1073,13 +1073,36 @@ static void secp256k1_fe_cmov(secp256k1_fe_t *r, const secp256k1_fe_t *a, int fl
10731073
r->n[5] = (r->n[5] & mask0) | (a->n[5] & mask1);
10741074
r->n[6] = (r->n[6] & mask0) | (a->n[6] & mask1);
10751075
r->n[7] = (r->n[7] & mask0) | (a->n[7] & mask1);
1076-
r->n[8] = (r->n[8] & mask0) | (a->n[8] & mask1);
1077-
r->n[9] = (r->n[9] & mask0) | (a->n[9] & mask1);
1076+
}
1077+
1078+
static void secp256k1_fe_to_storage(secp256k1_fe_storage_t *r, const secp256k1_fe_t *a) {
10781079
#ifdef VERIFY
1079-
if (flag) {
1080-
r->magnitude = a->magnitude;
1081-
r->normalized = a->normalized;
1082-
}
1080+
VERIFY_CHECK(a->normalized);
1081+
#endif
1082+
r->n[0] = a->n[0] | a->n[1] << 26;
1083+
r->n[1] = a->n[1] >> 6 | a->n[2] << 20;
1084+
r->n[2] = a->n[2] >> 12 | a->n[3] << 14;
1085+
r->n[3] = a->n[3] >> 18 | a->n[4] << 8;
1086+
r->n[4] = a->n[4] >> 24 | a->n[5] << 2 | a->n[6] << 28;
1087+
r->n[5] = a->n[6] >> 4 | a->n[7] << 22;
1088+
r->n[6] = a->n[7] >> 10 | a->n[8] << 16;
1089+
r->n[7] = a->n[8] >> 16 | a->n[9] << 10;
1090+
}
1091+
1092+
static inline void secp256k1_fe_from_storage(secp256k1_fe_t *r, const secp256k1_fe_storage_t *a) {
1093+
r->n[0] = a->n[0] & 0x3FFFFFFUL;
1094+
r->n[1] = a->n[0] >> 26 | ((a->n[1] << 6) & 0x3FFFFFFUL);
1095+
r->n[2] = a->n[1] >> 20 | ((a->n[2] << 12) & 0x3FFFFFFUL);
1096+
r->n[3] = a->n[2] >> 14 | ((a->n[3] << 18) & 0x3FFFFFFUL);
1097+
r->n[4] = a->n[3] >> 8 | ((a->n[4] << 24) & 0x3FFFFFFUL);
1098+
r->n[5] = (a->n[4] >> 2) & 0x3FFFFFFUL;
1099+
r->n[6] = a->n[4] >> 28 | ((a->n[5] << 4) & 0x3FFFFFFUL);
1100+
r->n[7] = a->n[5] >> 22 | ((a->n[6] << 10) & 0x3FFFFFFUL);
1101+
r->n[8] = a->n[6] >> 16 | ((a->n[7] << 16) & 0x3FFFFFFUL);
1102+
r->n[9] = a->n[7] >> 10;
1103+
#ifdef VERIFY
1104+
r->magnitude = 1;
1105+
r->normalized = 1;
10831106
#endif
10841107
}
10851108

‎src/field_5x52.h‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,4 +32,15 @@ typedef struct {
3232
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0))}
3333
#endif
3434

35+
typedef struct {
36+
uint64_t n[4];
37+
} secp256k1_fe_storage_t;
38+
39+
#define SECP256K1_FE_STORAGE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {{ \
40+
(d0) | ((uint64_t)(d1)) << 32, \
41+
(d2) | ((uint64_t)(d3)) << 32, \
42+
(d4) | ((uint64_t)(d5)) << 32, \
43+
(d6) | ((uint64_t)(d7)) << 32 \
44+
}}
45+
3546
#endif

‎src/field_5x52_impl.h‎

Lines changed: 21 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -398,18 +398,33 @@ static void secp256k1_fe_sqr(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
398398
#endif
399399
}
400400

401-
static void secp256k1_fe_cmov(secp256k1_fe_t *r, const secp256k1_fe_t *a, int flag) {
401+
static inline void secp256k1_fe_storage_cmov(secp256k1_fe_storage_t *r, const secp256k1_fe_storage_t *a, int flag) {
402402
uint64_t mask0 = flag + ~((uint64_t)0), mask1 = ~mask0;
403403
r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
404404
r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
405405
r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
406406
r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
407-
r->n[4] = (r->n[4] & mask0) | (a->n[4] & mask1);
407+
}
408+
409+
static void secp256k1_fe_to_storage(secp256k1_fe_storage_t *r, const secp256k1_fe_t *a) {
408410
#ifdef VERIFY
409-
if (flag) {
410-
r->magnitude = a->magnitude;
411-
r->normalized = a->normalized;
412-
}
411+
VERIFY_CHECK(a->normalized);
412+
#endif
413+
r->n[0] = a->n[0] | a->n[1] << 52;
414+
r->n[1] = a->n[1] >> 12 | a->n[2] << 40;
415+
r->n[2] = a->n[2] >> 24 | a->n[3] << 28;
416+
r->n[3] = a->n[3] >> 36 | a->n[4] << 16;
417+
}
418+
419+
static inline void secp256k1_fe_from_storage(secp256k1_fe_t *r, const secp256k1_fe_storage_t *a) {
420+
r->n[0] = a->n[0] & 0xFFFFFFFFFFFFFULL;
421+
r->n[1] = a->n[0] >> 52 | ((a->n[1] << 12) & 0xFFFFFFFFFFFFFULL);
422+
r->n[2] = a->n[1] >> 40 | ((a->n[2] << 24) & 0xFFFFFFFFFFFFFULL);
423+
r->n[3] = a->n[2] >> 28 | ((a->n[3] << 36) & 0xFFFFFFFFFFFFFULL);
424+
r->n[4] = a->n[3] >> 16;
425+
#ifdef VERIFY
426+
r->magnitude = 1;
427+
r->normalized = 1;
413428
#endif
414429
}
415430

‎src/group.h‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,11 @@ typedef struct {
2525
int infinity; /* whether this represents the point at infinity */
2626
} secp256k1_gej_t;
2727

28+
typedef struct {
29+
secp256k1_fe_storage_t x;
30+
secp256k1_fe_storage_t y;
31+
} secp256k1_ge_storage_t;
32+
2833
/** Set a group element equal to the point at infinity */
2934
static void secp256k1_ge_set_infinity(secp256k1_ge_t *r);
3035

@@ -99,4 +104,13 @@ static void secp256k1_gej_clear(secp256k1_gej_t *r);
99104
/** Clear a secp256k1_ge_t to prevent leaking sensitive information. */
100105
static void secp256k1_ge_clear(secp256k1_ge_t *r);
101106

107+
/** Convert a group element to the storage type. */
108+
static void secp256k1_ge_to_storage(secp256k1_ge_storage_t *r, const secp256k1_ge_t*);
109+
110+
/** Convert a group element back from the storage type. */
111+
static void secp256k1_ge_from_storage(secp256k1_ge_t *r, const secp256k1_ge_storage_t*);
112+
113+
/** If flag is true, set *r equal to *a; otherwise leave it. Constant-time. */
114+
static void secp256k1_ge_storage_cmov(secp256k1_ge_storage_t *r, const secp256k1_ge_storage_t *a, int flag);
115+
102116
#endif

‎src/group_impl.h‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -392,6 +392,28 @@ static void secp256k1_gej_get_hex(char *r131, const secp256k1_gej_t *a) {
392392
secp256k1_ge_get_hex(r131, &t);
393393
}
394394

395+
static void secp256k1_ge_to_storage(secp256k1_ge_storage_t *r, const secp256k1_ge_t *a) {
396+
secp256k1_fe_t x, y;
397+
VERIFY_CHECK(!a->infinity);
398+
x = a->x;
399+
secp256k1_fe_normalize(&x);
400+
y = a->y;
401+
secp256k1_fe_normalize(&y);
402+
secp256k1_fe_to_storage(&r->x, &x);
403+
secp256k1_fe_to_storage(&r->y, &y);
404+
}
405+
406+
static void secp256k1_ge_from_storage(secp256k1_ge_t *r, const secp256k1_ge_storage_t *a) {
407+
secp256k1_fe_from_storage(&r->x, &a->x);
408+
secp256k1_fe_from_storage(&r->y, &a->y);
409+
r->infinity = 0;
410+
}
411+
412+
static SECP256K1_INLINE void secp256k1_ge_storage_cmov(secp256k1_ge_storage_t *r, const secp256k1_ge_storage_t *a, int flag) {
413+
secp256k1_fe_storage_cmov(&r->x, &a->x, flag);
414+
secp256k1_fe_storage_cmov(&r->y, &a->y, flag);
415+
}
416+
395417
#ifdef USE_ENDOMORPHISM
396418
static void secp256k1_gej_mul_lambda(secp256k1_gej_t *r, const secp256k1_gej_t *a) {
397419
static const secp256k1_fe_t beta = SECP256K1_FE_CONST(

0 commit comments

Comments
 (0)