Bitcoin Core  22.99.0
P2P Digital Currency
ecmult_gen_impl.h
Go to the documentation of this file.
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 https://www.opensource.org/licenses/mit-license.php.*
5  ***********************************************************************/
6 
7 #ifndef SECP256K1_ECMULT_GEN_IMPL_H
8 #define SECP256K1_ECMULT_GEN_IMPL_H
9 
10 #include "util.h"
11 #include "scalar.h"
12 #include "group.h"
13 #include "ecmult_gen.h"
14 #include "hash_impl.h"
16 
19  ctx->built = 1;
20 }
21 
23  return ctx->built;
24 }
25 
27  ctx->built = 0;
28  secp256k1_scalar_clear(&ctx->blind);
29  secp256k1_gej_clear(&ctx->initial);
30 }
31 
32 /* For accelerating the computation of a*G:
33  * To harden against timing attacks, use the following mechanism:
34  * * Break up the multiplicand into groups of PREC_BITS bits, called n_0, n_1, n_2, ..., n_(PREC_N-1).
35  * * Compute sum(n_i * (PREC_G)^i * G + U_i, i=0 ... PREC_N-1), where:
36  * * U_i = U * 2^i, for i=0 ... PREC_N-2
37  * * U_i = U * (1-2^(PREC_N-1)), for i=PREC_N-1
38  * where U is a point with no known corresponding scalar. Note that sum(U_i, i=0 ... PREC_N-1) = 0.
39  * For each i, and each of the PREC_G possible values of n_i, (n_i * (PREC_G)^i * G + U_i) is
40  * precomputed (call it prec(i, n_i)). The formula now becomes sum(prec(i, n_i), i=0 ... PREC_N-1).
41  * None of the resulting prec group elements have a known scalar, and neither do any of
42  * the intermediate sums while computing a*G.
43  * The prec values are stored in secp256k1_ecmult_gen_prec_table[i][n_i] = n_i * (PREC_G)^i * G + U_i.
44  */
46  int bits = ECMULT_GEN_PREC_BITS;
47  int g = ECMULT_GEN_PREC_G(bits);
48  int n = ECMULT_GEN_PREC_N(bits);
49 
50  secp256k1_ge add;
52  secp256k1_scalar gnb;
53  int i, j, n_i;
54 
55  memset(&adds, 0, sizeof(adds));
56  *r = ctx->initial;
57  /* Blind scalar/point multiplication by computing (n-b)G + bG instead of nG. */
58  secp256k1_scalar_add(&gnb, gn, &ctx->blind);
59  add.infinity = 0;
60  for (i = 0; i < n; i++) {
61  n_i = secp256k1_scalar_get_bits(&gnb, i * bits, bits);
62  for (j = 0; j < g; j++) {
74  }
75  secp256k1_ge_from_storage(&add, &adds);
76  secp256k1_gej_add_ge(r, r, &add);
77  }
78  n_i = 0;
79  secp256k1_ge_clear(&add);
81 }
82 
83 /* Setup blinding values for secp256k1_ecmult_gen. */
84 static void secp256k1_ecmult_gen_blind(secp256k1_ecmult_gen_context *ctx, const unsigned char *seed32) {
86  secp256k1_gej gb;
87  secp256k1_fe s;
88  unsigned char nonce32[32];
90  int overflow;
91  unsigned char keydata[64] = {0};
92  if (seed32 == NULL) {
93  /* When seed is NULL, reset the initial point and blinding value. */
95  secp256k1_gej_neg(&ctx->initial, &ctx->initial);
96  secp256k1_scalar_set_int(&ctx->blind, 1);
97  }
98  /* The prior blinding value (if not reset) is chained forward by including it in the hash. */
99  secp256k1_scalar_get_b32(nonce32, &ctx->blind);
104  memcpy(keydata, nonce32, 32);
105  if (seed32 != NULL) {
106  memcpy(keydata + 32, seed32, 32);
107  }
108  secp256k1_rfc6979_hmac_sha256_initialize(&rng, keydata, seed32 ? 64 : 32);
109  memset(keydata, 0, sizeof(keydata));
110  /* Accept unobservably small non-uniformity. */
111  secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
112  overflow = !secp256k1_fe_set_b32(&s, nonce32);
113  overflow |= secp256k1_fe_is_zero(&s);
114  secp256k1_fe_cmov(&s, &secp256k1_fe_one, overflow);
115  /* Randomize the projection to defend against multiplier sidechannels. */
116  secp256k1_gej_rescale(&ctx->initial, &s);
117  secp256k1_fe_clear(&s);
118  secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
119  secp256k1_scalar_set_b32(&b, nonce32, NULL);
120  /* A blinding value of 0 works, but would undermine the projection hardening. */
123  memset(nonce32, 0, 32);
124  secp256k1_ecmult_gen(ctx, &gb, &b);
125  secp256k1_scalar_negate(&b, &b);
126  ctx->blind = b;
127  ctx->initial = gb;
129  secp256k1_gej_clear(&gb);
130 }
131 
132 #endif /* SECP256K1_ECMULT_GEN_IMPL_H */
secp256k1_scalar_negate
static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a)
Compute the complement of a scalar (modulo the group order).
secp256k1_ecmult_gen_context_clear
static void secp256k1_ecmult_gen_context_clear(secp256k1_ecmult_gen_context *ctx)
Definition: ecmult_gen_impl.h:26
secp256k1_scalar_get_b32
static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar *a)
Convert a scalar to a byte array.
secp256k1_fe_set_b32
static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a)
Set a field element equal to 32-byte big endian value.
secp256k1_rfc6979_hmac_sha256_initialize
static void secp256k1_rfc6979_hmac_sha256_initialize(secp256k1_rfc6979_hmac_sha256 *rng, const unsigned char *key, size_t keylen)
group.h
secp256k1_rfc6979_hmac_sha256_generate
static void secp256k1_rfc6979_hmac_sha256_generate(secp256k1_rfc6979_hmac_sha256 *rng, unsigned char *out, size_t outlen)
secp256k1_ecmult_gen_context_build
static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context *ctx)
Definition: ecmult_gen_impl.h:17
util.h
secp256k1_scalar_cmov
static void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag)
If flag is true, set *r equal to *a; otherwise leave it.
secp256k1_ecmult_gen
static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *gn)
Definition: ecmult_gen_impl.h:45
secp256k1_gej_rescale
static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *b)
Rescale a jacobian point by b which must be non-zero.
secp256k1_gej_add_ge
static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b)
Set r equal to the sum of a and b (with b given in affine coordinates, and not infinity).
secp256k1_ecmult_gen_blind
static void secp256k1_ecmult_gen_blind(secp256k1_ecmult_gen_context *ctx, const unsigned char *seed32)
Definition: ecmult_gen_impl.h:84
secp256k1_ge_storage_cmov
static void secp256k1_ge_storage_cmov(secp256k1_ge_storage *r, const secp256k1_ge_storage *a, int flag)
If flag is true, set *r equal to *a; otherwise leave it.
secp256k1_scalar_add
static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Add two scalars together (modulo the group order).
secp256k1_scalar
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
secp256k1_ge_from_storage
static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a)
Convert a group element back from the storage type.
secp256k1_ge_const_g
static const secp256k1_ge secp256k1_ge_const_g
Definition: group_impl.h:62
secp256k1_gej
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:23
secp256k1_fe_one
static const secp256k1_fe secp256k1_fe_one
Definition: field_impl.h:138
secp256k1_ecmult_gen_context_is_built
static int secp256k1_ecmult_gen_context_is_built(const secp256k1_ecmult_gen_context *ctx)
Definition: ecmult_gen_impl.h:22
secp256k1_fe_clear
static void secp256k1_fe_clear(secp256k1_fe *a)
Sets a field element equal to zero, initializing all fields.
secp256k1_fe
Definition: field_10x26.h:12
secp256k1_ge_storage
Definition: group.h:33
secp256k1_gej_neg
static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a)
Set r equal to the inverse of a (i.e., mirrored around the X axis)
hash_impl.h
secp256k1_ecmult_gen_context
Definition: ecmult_gen.h:19
secp256k1_ge_clear
static void secp256k1_ge_clear(secp256k1_ge *r)
Clear a secp256k1_ge to prevent leaking sensitive information.
secp256k1_fe_cmov
static void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag)
If flag is true, set *r equal to *a; otherwise leave it.
secp256k1_scalar_one
static const secp256k1_scalar secp256k1_scalar_one
Definition: scalar_impl.h:31
scalar.h
secp256k1_ge::infinity
int infinity
Definition: group.h:20
secp256k1_fe_is_zero
static int secp256k1_fe_is_zero(const secp256k1_fe *a)
Verify whether a field element is zero.
ECMULT_GEN_PREC_BITS
#define ECMULT_GEN_PREC_BITS
Definition: libsecp256k1-config.h:12
secp256k1_scalar_clear
static void secp256k1_scalar_clear(secp256k1_scalar *r)
Clear a scalar to prevent the leak of sensitive data.
secp256k1_scalar_is_zero
static int secp256k1_scalar_is_zero(const secp256k1_scalar *a)
Check whether a scalar equals zero.
secp256k1_rfc6979_hmac_sha256
Definition: hash.h:31
ECMULT_GEN_PREC_N
#define ECMULT_GEN_PREC_N(bits)
Definition: ecmult_gen.h:17
secp256k1_ecmult_gen_prec_table
static const secp256k1_ge_storage secp256k1_ecmult_gen_prec_table[ECMULT_GEN_PREC_N(ECMULT_GEN_PREC_BITS)][ECMULT_GEN_PREC_G(ECMULT_GEN_PREC_BITS)]
Definition: ecmult_gen_static_prec_table.h:10
ECMULT_GEN_PREC_G
#define ECMULT_GEN_PREC_G(bits)
Definition: ecmult_gen.h:16
ecmult_gen.h
ecmult_gen_static_prec_table.h
secp256k1_gej_clear
static void secp256k1_gej_clear(secp256k1_gej *r)
Clear a secp256k1_gej to prevent leaking sensitive information.
secp256k1_rfc6979_hmac_sha256_finalize
static void secp256k1_rfc6979_hmac_sha256_finalize(secp256k1_rfc6979_hmac_sha256 *rng)
ByteUnit::g
@ g
secp256k1_scalar_set_b32
static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *bin, int *overflow)
Set a scalar from a big endian byte array.
secp256k1_scalar_get_bits
static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count)
Access bits from a scalar.
secp256k1_ge
A group element of the secp256k1 curve, in affine coordinates.
Definition: group.h:13
ctx
static secp256k1_context * ctx
Definition: tests.c:32
secp256k1_scalar_set_int
static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
Set a scalar to an unsigned integer.
secp256k1_gej_set_ge
static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a)
Set a group element (jacobian) equal to another which is given in affine coordinates.