Bitcoin Core  0.20.99
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 http://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"
15 #ifdef USE_ECMULT_STATIC_PRECOMPUTATION
16 #include "ecmult_static_context.h"
17 #endif
18 
19 #ifndef USE_ECMULT_STATIC_PRECOMPUTATION
21 #else
22  static const size_t SECP256K1_ECMULT_GEN_CONTEXT_PREALLOCATED_SIZE = 0;
23 #endif
24 
26  ctx->prec = NULL;
27 }
28 
30 #ifndef USE_ECMULT_STATIC_PRECOMPUTATION
32  secp256k1_gej gj;
33  secp256k1_gej nums_gej;
34  int i, j;
35  size_t const prealloc_size = SECP256K1_ECMULT_GEN_CONTEXT_PREALLOCATED_SIZE;
36  void* const base = *prealloc;
37 #endif
38 
39  if (ctx->prec != NULL) {
40  return;
41  }
42 #ifndef USE_ECMULT_STATIC_PRECOMPUTATION
43  ctx->prec = (secp256k1_ge_storage (*)[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G])manual_alloc(prealloc, prealloc_size, base, prealloc_size);
44 
45  /* get the generator */
47 
48  /* Construct a group element with no known corresponding scalar (nothing up my sleeve). */
49  {
50  static const unsigned char nums_b32[33] = "The scalar for this x is unknown";
51  secp256k1_fe nums_x;
52  secp256k1_ge nums_ge;
53  int r;
54  r = secp256k1_fe_set_b32(&nums_x, nums_b32);
55  (void)r;
56  VERIFY_CHECK(r);
57  r = secp256k1_ge_set_xo_var(&nums_ge, &nums_x, 0);
58  (void)r;
59  VERIFY_CHECK(r);
60  secp256k1_gej_set_ge(&nums_gej, &nums_ge);
61  /* Add G to make the bits in x uniformly distributed. */
62  secp256k1_gej_add_ge_var(&nums_gej, &nums_gej, &secp256k1_ge_const_g, NULL);
63  }
64 
65  /* compute prec. */
66  {
67  secp256k1_gej precj[ECMULT_GEN_PREC_N * ECMULT_GEN_PREC_G]; /* Jacobian versions of prec. */
68  secp256k1_gej gbase;
69  secp256k1_gej numsbase;
70  gbase = gj; /* PREC_G^j * G */
71  numsbase = nums_gej; /* 2^j * nums. */
72  for (j = 0; j < ECMULT_GEN_PREC_N; j++) {
73  /* Set precj[j*PREC_G .. j*PREC_G+(PREC_G-1)] to (numsbase, numsbase + gbase, ..., numsbase + (PREC_G-1)*gbase). */
74  precj[j*ECMULT_GEN_PREC_G] = numsbase;
75  for (i = 1; i < ECMULT_GEN_PREC_G; i++) {
76  secp256k1_gej_add_var(&precj[j*ECMULT_GEN_PREC_G + i], &precj[j*ECMULT_GEN_PREC_G + i - 1], &gbase, NULL);
77  }
78  /* Multiply gbase by PREC_G. */
79  for (i = 0; i < ECMULT_GEN_PREC_B; i++) {
80  secp256k1_gej_double_var(&gbase, &gbase, NULL);
81  }
82  /* Multiply numbase by 2. */
83  secp256k1_gej_double_var(&numsbase, &numsbase, NULL);
84  if (j == ECMULT_GEN_PREC_N - 2) {
85  /* In the last iteration, numsbase is (1 - 2^j) * nums instead. */
86  secp256k1_gej_neg(&numsbase, &numsbase);
87  secp256k1_gej_add_var(&numsbase, &numsbase, &nums_gej, NULL);
88  }
89  }
90  secp256k1_ge_set_all_gej_var(prec, precj, ECMULT_GEN_PREC_N * ECMULT_GEN_PREC_G);
91  }
92  for (j = 0; j < ECMULT_GEN_PREC_N; j++) {
93  for (i = 0; i < ECMULT_GEN_PREC_G; i++) {
94  secp256k1_ge_to_storage(&(*ctx->prec)[j][i], &prec[j*ECMULT_GEN_PREC_G + i]);
95  }
96  }
97 #else
98  (void)prealloc;
99  ctx->prec = (secp256k1_ge_storage (*)[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G])secp256k1_ecmult_static_context;
100 #endif
101  secp256k1_ecmult_gen_blind(ctx, NULL);
102 }
103 
105  return ctx->prec != NULL;
106 }
107 
109 #ifndef USE_ECMULT_STATIC_PRECOMPUTATION
110  if (src->prec != NULL) {
111  /* We cast to void* first to suppress a -Wcast-align warning. */
112  dst->prec = (secp256k1_ge_storage (*)[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G])(void*)((unsigned char*)dst + ((unsigned char*)src->prec - (unsigned char*)src));
113  }
114 #else
115  (void)dst, (void)src;
116 #endif
117 }
118 
122  ctx->prec = NULL;
123 }
124 
126  secp256k1_ge add;
128  secp256k1_scalar gnb;
129  int bits;
130  int i, j;
131  memset(&adds, 0, sizeof(adds));
132  *r = ctx->initial;
133  /* Blind scalar/point multiplication by computing (n-b)G + bG instead of nG. */
134  secp256k1_scalar_add(&gnb, gn, &ctx->blind);
135  add.infinity = 0;
136  for (j = 0; j < ECMULT_GEN_PREC_N; j++) {
137  bits = secp256k1_scalar_get_bits(&gnb, j * ECMULT_GEN_PREC_B, ECMULT_GEN_PREC_B);
138  for (i = 0; i < ECMULT_GEN_PREC_G; i++) {
149  secp256k1_ge_storage_cmov(&adds, &(*ctx->prec)[j][i], i == bits);
150  }
151  secp256k1_ge_from_storage(&add, &adds);
152  secp256k1_gej_add_ge(r, r, &add);
153  }
154  bits = 0;
155  secp256k1_ge_clear(&add);
157 }
158 
159 /* Setup blinding values for secp256k1_ecmult_gen. */
160 static void secp256k1_ecmult_gen_blind(secp256k1_ecmult_gen_context *ctx, const unsigned char *seed32) {
162  secp256k1_gej gb;
163  secp256k1_fe s;
164  unsigned char nonce32[32];
166  int overflow;
167  unsigned char keydata[64] = {0};
168  if (seed32 == NULL) {
169  /* When seed is NULL, reset the initial point and blinding value. */
171  secp256k1_gej_neg(&ctx->initial, &ctx->initial);
173  }
174  /* The prior blinding value (if not reset) is chained forward by including it in the hash. */
175  secp256k1_scalar_get_b32(nonce32, &ctx->blind);
180  memcpy(keydata, nonce32, 32);
181  if (seed32 != NULL) {
182  memcpy(keydata + 32, seed32, 32);
183  }
184  secp256k1_rfc6979_hmac_sha256_initialize(&rng, keydata, seed32 ? 64 : 32);
185  memset(keydata, 0, sizeof(keydata));
186  /* Accept unobservably small non-uniformity. */
187  secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
188  overflow = !secp256k1_fe_set_b32(&s, nonce32);
189  overflow |= secp256k1_fe_is_zero(&s);
190  secp256k1_fe_cmov(&s, &secp256k1_fe_one, overflow);
191  /* Randomize the projection to defend against multiplier sidechannels. */
192  secp256k1_gej_rescale(&ctx->initial, &s);
193  secp256k1_fe_clear(&s);
194  secp256k1_rfc6979_hmac_sha256_generate(&rng, nonce32, 32);
195  secp256k1_scalar_set_b32(&b, nonce32, NULL);
196  /* A blinding value of 0 works, but would undermine the projection hardening. */
199  memset(nonce32, 0, 32);
200  secp256k1_ecmult_gen(ctx, &gb, &b);
201  secp256k1_scalar_negate(&b, &b);
202  ctx->blind = b;
203  ctx->initial = gb;
205  secp256k1_gej_clear(&gb);
206 }
207 
208 #endif /* SECP256K1_ECMULT_GEN_IMPL_H */
#define VERIFY_CHECK(cond)
Definition: util.h:68
static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_gej *b, secp256k1_fe *rzr)
Set r equal to the sum of a and b.
static int secp256k1_fe_is_zero(const secp256k1_fe *a)
Verify whether a field element is zero.
static void secp256k1_rfc6979_hmac_sha256_initialize(secp256k1_rfc6979_hmac_sha256 *rng, const unsigned char *key, size_t keylen)
static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count)
Access bits from a scalar.
#define ECMULT_GEN_PREC_B
Definition: ecmult_gen.h:16
static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a)
Compute the complement of a scalar (modulo the group order).
static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len)
Set a batch of group elements equal to the inputs given in jacobian coordinates.
static int secp256k1_scalar_is_zero(const secp256k1_scalar *a)
Check whether a scalar equals zero.
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)
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_ge_storage(* prec)[ECMULT_GEN_PREC_N][ECMULT_GEN_PREC_G]
Definition: ecmult_gen.h:33
static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *bin, int *overflow)
Set a scalar from a big endian byte array.
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:24
static SECP256K1_INLINE void * manual_alloc(void **prealloc_ptr, size_t alloc_size, void *base, size_t max_size)
Definition: util.h:134
static void secp256k1_fe_clear(secp256k1_fe *a)
Sets a field element equal to zero, initializing all fields.
static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b, secp256k1_fe *rzr)
Set r equal to the sum of a and b (with b given in affine coordinates).
static void secp256k1_gej_double_var(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr)
Set r equal to the double of a.
static const secp256k1_ge secp256k1_ge_const_g
Generator for secp256k1, value &#39;g&#39; defined in "Standards for Efficient Cryptography" (SEC2) 2...
Definition: group_impl.h:53
static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *gn)
static void secp256k1_ecmult_gen_context_init(secp256k1_ecmult_gen_context *ctx)
secp256k1_scalar blind
Definition: ecmult_gen.h:34
static secp256k1_context * ctx
Definition: tests.c:36
static void secp256k1_gej_clear(secp256k1_gej *r)
Clear a secp256k1_gej to prevent leaking sensitive information.
static void secp256k1_ecmult_gen_context_finalize_memcpy(secp256k1_ecmult_gen_context *dst, const secp256k1_ecmult_gen_context *src)
static void secp256k1_scalar_clear(secp256k1_scalar *r)
Clear a scalar to prevent the leak of sensitive data.
A group element of the secp256k1 curve, in affine coordinates.
Definition: group.h:14
static void secp256k1_ge_clear(secp256k1_ge *r)
Clear a secp256k1_ge to prevent leaking sensitive information.
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.
#define ECMULT_GEN_PREC_G
Definition: ecmult_gen.h:17
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
int infinity
Definition: group.h:17
static void secp256k1_ecmult_gen_blind(secp256k1_ecmult_gen_context *ctx, const unsigned char *seed32)
static const secp256k1_fe secp256k1_fe_one
Definition: field_impl.h:318
static int secp256k1_ecmult_gen_context_is_built(const secp256k1_ecmult_gen_context *ctx)
static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar *a)
Convert a scalar to a byte array.
static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd)
Set a group element (affine) equal to the point with the given X coordinate, and given oddness for Y...
static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a)
Set a field element equal to 32-byte big endian value.
static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context *ctx, void **prealloc)
static void secp256k1_gej_rescale(secp256k1_gej *r, const secp256k1_fe *b)
Rescale a jacobian point by b which must be non-zero.
static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Add two scalars together (modulo the group order).
static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
Set a scalar to an unsigned integer.
void * memcpy(void *a, const void *b, size_t c)
#define ECMULT_GEN_PREC_N
Definition: ecmult_gen.h:18
static void secp256k1_ecmult_gen_context_clear(secp256k1_ecmult_gen_context *ctx)
#define ROUND_TO_ALIGN(size)
Definition: util.h:116
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).
static void secp256k1_ge_from_storage(secp256k1_ge *r, const secp256k1_ge_storage *a)
Convert a group element back from the storage type.
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.
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.
static const secp256k1_scalar secp256k1_scalar_one
Definition: scalar_impl.h:31
static void secp256k1_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge *a)
Convert a group element to the storage type.
static const size_t SECP256K1_ECMULT_GEN_CONTEXT_PREALLOCATED_SIZE
static void secp256k1_rfc6979_hmac_sha256_finalize(secp256k1_rfc6979_hmac_sha256 *rng)
static void secp256k1_rfc6979_hmac_sha256_generate(secp256k1_rfc6979_hmac_sha256 *rng, unsigned char *out, size_t outlen)