1 /**********************************************************************
2 * Copyright (c) 2013, 2014, 2015 Pieter Wuille, Gregory Maxwell *
3 * Distributed under the MIT software license, see the accompanying *
4 * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
5 **********************************************************************/
7 #ifndef SECP256K1_ECMULT_GEN_IMPL_H
8 #define SECP256K1_ECMULT_GEN_IMPL_H
12 #include "ecmult_gen.h"
13 #include "hash_impl.h"
14 #ifdef USE_ECMULT_STATIC_PRECOMPUTATION
15 #include "ecmult_static_context.h"
17 static void secp256k1_ecmult_gen_context_init(secp256k1_ecmult_gen_context
*ctx
) {
21 static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context
*ctx
, const secp256k1_callback
* cb
) {
22 #ifndef USE_ECMULT_STATIC_PRECOMPUTATION
23 secp256k1_ge prec
[1024];
25 secp256k1_gej nums_gej
;
29 if (ctx
->prec
!= NULL
) {
32 #ifndef USE_ECMULT_STATIC_PRECOMPUTATION
33 ctx
->prec
= (secp256k1_ge_storage (*)[64][16])checked_malloc(cb
, sizeof(*ctx
->prec
));
35 /* get the generator */
36 secp256k1_gej_set_ge(&gj
, &secp256k1_ge_const_g
);
38 /* Construct a group element with no known corresponding scalar (nothing up my sleeve). */
40 static const unsigned char nums_b32
[33] = "The scalar for this x is unknown";
44 r
= secp256k1_fe_set_b32(&nums_x
, nums_b32
);
47 r
= secp256k1_ge_set_xo_var(&nums_ge
, &nums_x
, 0);
50 secp256k1_gej_set_ge(&nums_gej
, &nums_ge
);
51 /* Add G to make the bits in x uniformly distributed. */
52 secp256k1_gej_add_ge_var(&nums_gej
, &nums_gej
, &secp256k1_ge_const_g
, NULL
);
57 secp256k1_gej precj
[1024]; /* Jacobian versions of prec. */
59 secp256k1_gej numsbase
;
60 gbase
= gj
; /* 16^j * G */
61 numsbase
= nums_gej
; /* 2^j * nums. */
62 for (j
= 0; j
< 64; j
++) {
63 /* Set precj[j*16 .. j*16+15] to (numsbase, numsbase + gbase, ..., numsbase + 15*gbase). */
64 precj
[j
*16] = numsbase
;
65 for (i
= 1; i
< 16; i
++) {
66 secp256k1_gej_add_var(&precj
[j
*16 + i
], &precj
[j
*16 + i
- 1], &gbase
, NULL
);
68 /* Multiply gbase by 16. */
69 for (i
= 0; i
< 4; i
++) {
70 secp256k1_gej_double_var(&gbase
, &gbase
, NULL
);
72 /* Multiply numbase by 2. */
73 secp256k1_gej_double_var(&numsbase
, &numsbase
, NULL
);
75 /* In the last iteration, numsbase is (1 - 2^j) * nums instead. */
76 secp256k1_gej_neg(&numsbase
, &numsbase
);
77 secp256k1_gej_add_var(&numsbase
, &numsbase
, &nums_gej
, NULL
);
80 secp256k1_ge_set_all_gej_var(prec
, precj
, 1024, cb
);
82 for (j
= 0; j
< 64; j
++) {
83 for (i
= 0; i
< 16; i
++) {
84 secp256k1_ge_to_storage(&(*ctx
->prec
)[j
][i
], &prec
[j
*16 + i
]);
89 ctx
->prec
= (secp256k1_ge_storage (*)[64][16])secp256k1_ecmult_static_context
;
91 secp256k1_ecmult_gen_blind(ctx
, NULL
);
94 static int secp256k1_ecmult_gen_context_is_built(const secp256k1_ecmult_gen_context
* ctx
) {
95 return ctx
->prec
!= NULL
;
98 static void secp256k1_ecmult_gen_context_clone(secp256k1_ecmult_gen_context
*dst
,
99 const secp256k1_ecmult_gen_context
*src
, const secp256k1_callback
* cb
) {
100 if (src
->prec
== NULL
) {
103 #ifndef USE_ECMULT_STATIC_PRECOMPUTATION
104 dst
->prec
= (secp256k1_ge_storage (*)[64][16])checked_malloc(cb
, sizeof(*dst
->prec
));
105 memcpy(dst
->prec
, src
->prec
, sizeof(*dst
->prec
));
108 dst
->prec
= src
->prec
;
110 dst
->initial
= src
->initial
;
111 dst
->blind
= src
->blind
;
115 static void secp256k1_ecmult_gen_context_clear(secp256k1_ecmult_gen_context
*ctx
) {
116 #ifndef USE_ECMULT_STATIC_PRECOMPUTATION
119 secp256k1_scalar_clear(&ctx
->blind
);
120 secp256k1_gej_clear(&ctx
->initial
);
124 static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context
*ctx
, secp256k1_gej
*r
, const secp256k1_scalar
*gn
) {
126 secp256k1_ge_storage adds
;
127 secp256k1_scalar gnb
;
130 memset(&adds
, 0, sizeof(adds
));
132 /* Blind scalar/point multiplication by computing (n-b)G + bG instead of nG. */
133 secp256k1_scalar_add(&gnb
, gn
, &ctx
->blind
);
135 for (j
= 0; j
< 64; j
++) {
136 bits
= secp256k1_scalar_get_bits(&gnb
, j
* 4, 4);
137 for (i
= 0; i
< 16; i
++) {
138 /** This uses a conditional move to avoid any secret data in array indexes.
139 * _Any_ use of secret indexes has been demonstrated to result in timing
140 * sidechannels, even when the cache-line access patterns are uniform.
142 * "A word of warning", CHES 2013 Rump Session, by Daniel J. Bernstein and Peter Schwabe
143 * (https://cryptojedi.org/peter/data/chesrump-20130822.pdf) and
144 * "Cache Attacks and Countermeasures: the Case of AES", RSA 2006,
145 * by Dag Arne Osvik, Adi Shamir, and Eran Tromer
146 * (http://www.tau.ac.il/~tromer/papers/cache.pdf)
148 secp256k1_ge_storage_cmov(&adds
, &(*ctx
->prec
)[j
][i
], i
== bits
);
150 secp256k1_ge_from_storage(&add
, &adds
);
151 secp256k1_gej_add_ge(r
, r
, &add
);
154 secp256k1_ge_clear(&add
);
155 secp256k1_scalar_clear(&gnb
);
158 /* Setup blinding values for secp256k1_ecmult_gen. */
159 static void secp256k1_ecmult_gen_blind(secp256k1_ecmult_gen_context
*ctx
, const unsigned char *seed32
) {
163 unsigned char nonce32
[32];
164 secp256k1_rfc6979_hmac_sha256_t rng
;
166 unsigned char keydata
[64] = {0};
167 if (seed32
== NULL
) {
168 /* When seed is NULL, reset the initial point and blinding value. */
169 secp256k1_gej_set_ge(&ctx
->initial
, &secp256k1_ge_const_g
);
170 secp256k1_gej_neg(&ctx
->initial
, &ctx
->initial
);
171 secp256k1_scalar_set_int(&ctx
->blind
, 1);
173 /* The prior blinding value (if not reset) is chained forward by including it in the hash. */
174 secp256k1_scalar_get_b32(nonce32
, &ctx
->blind
);
175 /** Using a CSPRNG allows a failure free interface, avoids needing large amounts of random data,
176 * and guards against weak or adversarial seeds. This is a simpler and safer interface than
177 * asking the caller for blinding values directly and expecting them to retry on failure.
179 memcpy(keydata
, nonce32
, 32);
180 if (seed32
!= NULL
) {
181 memcpy(keydata
+ 32, seed32
, 32);
183 secp256k1_rfc6979_hmac_sha256_initialize(&rng
, keydata
, seed32
? 64 : 32);
184 memset(keydata
, 0, sizeof(keydata
));
185 /* Retry for out of range results to achieve uniformity. */
187 secp256k1_rfc6979_hmac_sha256_generate(&rng
, nonce32
, 32);
188 retry
= !secp256k1_fe_set_b32(&s
, nonce32
);
189 retry
|= secp256k1_fe_is_zero(&s
);
190 } while (retry
); /* This branch true is cryptographically unreachable. Requires sha256_hmac output > Fp. */
191 /* Randomize the projection to defend against multiplier sidechannels. */
192 secp256k1_gej_rescale(&ctx
->initial
, &s
);
193 secp256k1_fe_clear(&s
);
195 secp256k1_rfc6979_hmac_sha256_generate(&rng
, nonce32
, 32);
196 secp256k1_scalar_set_b32(&b
, nonce32
, &retry
);
197 /* A blinding value of 0 works, but would undermine the projection hardening. */
198 retry
|= secp256k1_scalar_is_zero(&b
);
199 } while (retry
); /* This branch true is cryptographically unreachable. Requires sha256_hmac output > order. */
200 secp256k1_rfc6979_hmac_sha256_finalize(&rng
);
201 memset(nonce32
, 0, 32);
202 secp256k1_ecmult_gen(ctx
, &gb
, &b
);
203 secp256k1_scalar_negate(&b
, &b
);
206 secp256k1_scalar_clear(&b
);
207 secp256k1_gej_clear(&gb
);
210 #endif /* SECP256K1_ECMULT_GEN_IMPL_H */