Bitcoin Core  0.19.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 "scalar.h"
11 #include "group.h"
12 #include "ecmult_gen.h"
13 #include "hash_impl.h"
14 #ifdef USE_ECMULT_STATIC_PRECOMPUTATION
15 #include "ecmult_static_context.h"
16 #endif
18  ctx->prec = NULL;
19 }
20 
22 #ifndef USE_ECMULT_STATIC_PRECOMPUTATION
23  secp256k1_ge prec[1024];
24  secp256k1_gej gj;
25  secp256k1_gej nums_gej;
26  int i, j;
27 #endif
28 
29  if (ctx->prec != NULL) {
30  return;
31  }
32 #ifndef USE_ECMULT_STATIC_PRECOMPUTATION
33  ctx->prec = (secp256k1_ge_storage (*)[64][16])checked_malloc(cb, sizeof(*ctx->prec));
34 
35  /* get the generator */
37 
38  /* Construct a group element with no known corresponding scalar (nothing up my sleeve). */
39  {
40  static const unsigned char nums_b32[33] = "The scalar for this x is unknown";
41  secp256k1_fe nums_x;
42  secp256k1_ge nums_ge;
43  int r;
44  r = secp256k1_fe_set_b32(&nums_x, nums_b32);
45  (void)r;
46  VERIFY_CHECK(r);
47  r = secp256k1_ge_set_xo_var(&nums_ge, &nums_x, 0);
48  (void)r;
49  VERIFY_CHECK(r);
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);
53  }
54 
55  /* compute prec. */
56  {
57  secp256k1_gej precj[1024]; /* Jacobian versions of prec. */
58  secp256k1_gej gbase;
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);
67  }
68  /* Multiply gbase by 16. */
69  for (i = 0; i < 4; i++) {
70  secp256k1_gej_double_var(&gbase, &gbase, NULL);
71  }
72  /* Multiply numbase by 2. */
73  secp256k1_gej_double_var(&numsbase, &numsbase, NULL);
74  if (j == 62) {
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);
78  }
79  }
80  secp256k1_ge_set_all_gej_var(prec, precj, 1024);
81  }
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]);
85  }
86  }
87 #else
88  (void)cb;
89  ctx->prec = (secp256k1_ge_storage (*)[64][16])secp256k1_ecmult_static_context;
90 #endif
91  secp256k1_ecmult_gen_blind(ctx, NULL);
92 }
93 
95  return ctx->prec != NULL;
96 }
97 
99  const secp256k1_ecmult_gen_context *src, const secp256k1_callback* cb) {
100  if (src->prec == NULL) {
101  dst->prec = NULL;
102  } else {
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));
106 #else
107  (void)cb;
108  dst->prec = src->prec;
109 #endif
110  dst->initial = src->initial;
111  dst->blind = src->blind;
112  }
113 }
114 
116 #ifndef USE_ECMULT_STATIC_PRECOMPUTATION
117  free(ctx->prec);
118 #endif
121  ctx->prec = NULL;
122 }
123 
125  secp256k1_ge add;
127  secp256k1_scalar gnb;
128  int bits;
129  int i, j;
130  memset(&adds, 0, sizeof(adds));
131  *r = ctx->initial;
132  /* Blind scalar/point multiplication by computing (n-b)G + bG instead of nG. */
133  secp256k1_scalar_add(&gnb, gn, &ctx->blind);
134  add.infinity = 0;
135  for (j = 0; j < 64; j++) {
136  bits = secp256k1_scalar_get_bits(&gnb, j * 4, 4);
137  for (i = 0; i < 16; i++) {
148  secp256k1_ge_storage_cmov(&adds, &(*ctx->prec)[j][i], i == bits);
149  }
150  secp256k1_ge_from_storage(&add, &adds);
151  secp256k1_gej_add_ge(r, r, &add);
152  }
153  bits = 0;
154  secp256k1_ge_clear(&add);
156 }
157 
158 /* Setup blinding values for secp256k1_ecmult_gen. */
159 static void secp256k1_ecmult_gen_blind(secp256k1_ecmult_gen_context *ctx, const unsigned char *seed32) {
161  secp256k1_gej gb;
162  secp256k1_fe s;
163  unsigned char nonce32[32];
165  int retry;
166  unsigned char keydata[64] = {0};
167  if (seed32 == NULL) {
168  /* When seed is NULL, reset the initial point and blinding value. */
170  secp256k1_gej_neg(&ctx->initial, &ctx->initial);
172  }
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);
179  memcpy(keydata, nonce32, 32);
180  if (seed32 != NULL) {
181  memcpy(keydata + 32, seed32, 32);
182  }
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. */
186  do {
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);
194  do {
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. */
201  memset(nonce32, 0, 32);
202  secp256k1_ecmult_gen(ctx, &gb, &b);
203  secp256k1_scalar_negate(&b, &b);
204  ctx->blind = b;
205  ctx->initial = gb;
207  secp256k1_gej_clear(&gb);
208 }
209 
210 #endif /* SECP256K1_ECMULT_GEN_IMPL_H */
#define VERIFY_CHECK(cond)
Definition: util.h:67
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 void secp256k1_ecmult_gen_context_clone(secp256k1_ecmult_gen_context *dst, const secp256k1_ecmult_gen_context *src, const secp256k1_callback *cb)
static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count)
Access bits from a scalar.
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_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 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:64
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:27
static secp256k1_context * ctx
Definition: tests.c:46
static void secp256k1_gej_clear(secp256k1_gej *r)
Clear a secp256k1_gej to prevent leaking sensitive information.
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.
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 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_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)
static void secp256k1_ecmult_gen_context_clear(secp256k1_ecmult_gen_context *ctx)
static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context *ctx, const secp256k1_callback *cb)
secp256k1_ge_storage(* prec)[64][16]
Definition: ecmult_gen.h:26
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_ge_to_storage(secp256k1_ge_storage *r, const secp256k1_ge *a)
Convert a group element to the storage type.
static SECP256K1_INLINE void * checked_malloc(const secp256k1_callback *cb, size_t size)
Definition: util.h:71
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)