Bitcoin Core  26.99.0
P2P Digital Currency
ecmult_gen_compute_table_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_COMPUTE_TABLE_IMPL_H
8 #define SECP256K1_ECMULT_GEN_COMPUTE_TABLE_IMPL_H
9 
11 #include "group_impl.h"
12 #include "field_impl.h"
13 #include "ecmult_gen.h"
14 #include "util.h"
15 
16 static void secp256k1_ecmult_gen_compute_table(secp256k1_ge_storage* table, const secp256k1_ge* gen, int bits) {
17  int g = ECMULT_GEN_PREC_G(bits);
18  int n = ECMULT_GEN_PREC_N(bits);
19 
20  secp256k1_ge* prec = checked_malloc(&default_error_callback, n * g * sizeof(*prec));
21  secp256k1_gej gj;
22  secp256k1_gej nums_gej;
23  int i, j;
24 
25  VERIFY_CHECK(g > 0);
26  VERIFY_CHECK(n > 0);
27 
28  /* get the generator */
29  secp256k1_gej_set_ge(&gj, gen);
30 
31  /* Construct a group element with no known corresponding scalar (nothing up my sleeve). */
32  {
33  static const unsigned char nums_b32[33] = "The scalar for this x is unknown";
34  secp256k1_fe nums_x;
35  secp256k1_ge nums_ge;
36  int r;
37  r = secp256k1_fe_set_b32_limit(&nums_x, nums_b32);
38  (void)r;
39  VERIFY_CHECK(r);
40  r = secp256k1_ge_set_xo_var(&nums_ge, &nums_x, 0);
41  (void)r;
42  VERIFY_CHECK(r);
43  secp256k1_gej_set_ge(&nums_gej, &nums_ge);
44  /* Add G to make the bits in x uniformly distributed. */
45  secp256k1_gej_add_ge_var(&nums_gej, &nums_gej, gen, NULL);
46  }
47 
48  /* compute prec. */
49  {
50  secp256k1_gej gbase;
51  secp256k1_gej numsbase;
52  secp256k1_gej* precj = checked_malloc(&default_error_callback, n * g * sizeof(*precj)); /* Jacobian versions of prec. */
53  gbase = gj; /* PREC_G^j * G */
54  numsbase = nums_gej; /* 2^j * nums. */
55  for (j = 0; j < n; j++) {
56  /* Set precj[j*PREC_G .. j*PREC_G+(PREC_G-1)] to (numsbase, numsbase + gbase, ..., numsbase + (PREC_G-1)*gbase). */
57  precj[j*g] = numsbase;
58  for (i = 1; i < g; i++) {
59  secp256k1_gej_add_var(&precj[j*g + i], &precj[j*g + i - 1], &gbase, NULL);
60  }
61  /* Multiply gbase by PREC_G. */
62  for (i = 0; i < bits; i++) {
63  secp256k1_gej_double_var(&gbase, &gbase, NULL);
64  }
65  /* Multiply numbase by 2. */
66  secp256k1_gej_double_var(&numsbase, &numsbase, NULL);
67  if (j == n - 2) {
68  /* In the last iteration, numsbase is (1 - 2^j) * nums instead. */
69  secp256k1_gej_neg(&numsbase, &numsbase);
70  secp256k1_gej_add_var(&numsbase, &numsbase, &nums_gej, NULL);
71  }
72  }
73  secp256k1_ge_set_all_gej_var(prec, precj, n * g);
74  free(precj);
75  }
76  for (j = 0; j < n; j++) {
77  for (i = 0; i < g; i++) {
78  secp256k1_ge_to_storage(&table[j*g + i], &prec[j*g + i]);
79  }
80  }
81  free(prec);
82 }
83 
84 #endif /* SECP256K1_ECMULT_GEN_COMPUTE_TABLE_IMPL_H */
#define ECMULT_GEN_PREC_G(bits)
Definition: ecmult_gen.h:28
#define ECMULT_GEN_PREC_N(bits)
Definition: ecmult_gen.h:29
static void secp256k1_ecmult_gen_compute_table(secp256k1_ge_storage *table, const secp256k1_ge *gen, int bits)
#define secp256k1_fe_set_b32_limit
Definition: field.h:89
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 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 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_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 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 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 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 SECP256K1_INLINE void * checked_malloc(const secp256k1_callback *cb, size_t size)
Definition: util.h:142
static const secp256k1_callback default_error_callback
Definition: util.h:97
#define VERIFY_CHECK(cond)
Definition: util.h:139
This field implementation represents the value as 10 uint32_t limbs in base 2^26.
Definition: field_10x26.h:14
A group element in affine coordinates on the secp256k1 curve, or occasionally on an isomorphic curve ...
Definition: group.h:16
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:28