PRCYCoin  2.0.0.7rc1
P2P Digital Currency
main_impl.h
Go to the documentation of this file.
1 /**********************************************************************
2  * Copyright (c) 2016 Andrew Poelstra & Pieter Wuille *
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_MODULE_GENERATOR_MAIN
8 #define SECP256K1_MODULE_GENERATOR_MAIN
9 
10 #include <stdio.h>
11 
12 #include "field.h"
13 #include "group.h"
14 #include "hash.h"
15 #include "scalar.h"
16 
18 const secp256k1_generator secp256k1_generator_const_g = {{
19  0x79, 0xbe, 0x66, 0x7e, 0xf9, 0xdc, 0xbb, 0xac, 0x55, 0xa0, 0x62, 0x95, 0xce, 0x87, 0x0b, 0x07,
20  0x02, 0x9b, 0xfc, 0xdb, 0x2d, 0xce, 0x28, 0xd9, 0x59, 0xf2, 0x81, 0x5b, 0x16, 0xf8, 0x17, 0x98,
21  0x48, 0x3a, 0xda, 0x77, 0x26, 0xa3, 0xc4, 0x65, 0x5d, 0xa4, 0xfb, 0xfc, 0x0e, 0x11, 0x08, 0xa8,
22  0xfd, 0x17, 0xb4, 0x48, 0xa6, 0x85, 0x54, 0x19, 0x9c, 0x47, 0xd0, 0x8f, 0xfb, 0x10, 0xd4, 0xb8
23 }};
24 
32 const secp256k1_generator secp256k1_generator_const_h = {{
33  0x50, 0x92, 0x9b, 0x74, 0xc1, 0xa0, 0x49, 0x54, 0xb7, 0x8b, 0x4b, 0x60, 0x35, 0xe9, 0x7a, 0x5e,
34  0x07, 0x8a, 0x5a, 0x0f, 0x28, 0xec, 0x96, 0xd5, 0x47, 0xbf, 0xee, 0x9a, 0xce, 0x80, 0x3a, 0xc0,
35  0x31, 0xd3, 0xc6, 0x86, 0x39, 0x73, 0x92, 0x6e, 0x04, 0x9e, 0x63, 0x7c, 0xb1, 0xb5, 0xf4, 0x0a,
36  0x36, 0xda, 0xc2, 0x8a, 0xf1, 0x76, 0x69, 0x68, 0xc3, 0x0c, 0x23, 0x13, 0xf3, 0xa3, 0x89, 0x04
37 }};
38 
39 static void secp256k1_generator_load(secp256k1_ge* ge, const secp256k1_generator* gen) {
40  int succeed;
41  succeed = secp256k1_fe_set_b32(&ge->x, &gen->data[0]);
42  VERIFY_CHECK(succeed != 0);
43  succeed = secp256k1_fe_set_b32(&ge->y, &gen->data[32]);
44  VERIFY_CHECK(succeed != 0);
45  ge->infinity = 0;
46  (void) succeed;
47 }
48 
49 static void secp256k1_generator_save(secp256k1_generator *gen, secp256k1_ge* ge) {
50  VERIFY_CHECK(!secp256k1_ge_is_infinity(ge));
51  secp256k1_fe_normalize_var(&ge->x);
52  secp256k1_fe_normalize_var(&ge->y);
53  secp256k1_fe_get_b32(&gen->data[0], &ge->x);
54  secp256k1_fe_get_b32(&gen->data[32], &ge->y);
55 }
56 
57 int secp256k1_generator_parse(const secp256k1_context2* ctx, secp256k1_generator* gen, const unsigned char *input) {
58  secp256k1_fe x;
59  secp256k1_ge ge;
60 
61  VERIFY_CHECK(ctx != NULL);
62  ARG_CHECK(gen != NULL);
63  ARG_CHECK(input != NULL);
64 
65  if ((input[0] & 0xFE) != 10 ||
66  !secp256k1_fe_set_b32(&x, &input[1]) ||
67  !secp256k1_ge_set_xquad(&ge, &x)) {
68  return 0;
69  }
70  if (input[0] & 1) {
71  secp256k1_ge_neg(&ge, &ge);
72  }
73  secp256k1_generator_save(gen, &ge);
74  return 1;
75 }
76 
77 int secp256k1_generator_serialize(const secp256k1_context2* ctx, unsigned char *output, const secp256k1_generator* gen) {
78  secp256k1_ge ge;
79 
80  VERIFY_CHECK(ctx != NULL);
81  ARG_CHECK(output != NULL);
82  ARG_CHECK(gen != NULL);
83 
84  secp256k1_generator_load(&ge, gen);
85 
86  output[0] = 11 ^ secp256k1_fe_is_quad_var(&ge.y);
87  secp256k1_fe_normalize_var(&ge.x);
88  secp256k1_fe_get_b32(&output[1], &ge.x);
89  return 1;
90 }
91 
92 static void shallue_van_de_woestijne(secp256k1_ge* ge, const secp256k1_fe* t) {
93  /* Implements the algorithm from:
94  * Indifferentiable Hashing to Barreto-Naehrig Curves
95  * Pierre-Alain Fouque and Mehdi Tibouchi
96  * Latincrypt 2012
97  */
98 
99  /* Basic algorithm:
100 
101  c = sqrt(-3)
102  d = (c - 1)/2
103 
104  w = c * t / (1 + b + t^2) [with b = 7]
105  x1 = d - t*w
106  x2 = -(x1 + 1)
107  x3 = 1 + 1/w^2
108 
109  To avoid the 2 divisions, compute the above in numerator/denominator form:
110  wn = c * t
111  wd = 1 + 7 + t^2
112  x1n = d*wd - t*wn
113  x1d = wd
114  x2n = -(x1n + wd)
115  x2d = wd
116  x3n = wd^2 + c^2 + t^2
117  x3d = (c * t)^2
118 
119  The joint denominator j = wd * c^2 * t^2, and
120  1 / x1d = 1/j * c^2 * t^2
121  1 / x2d = x3d = 1/j * wd
122  */
123 
124  static const secp256k1_fe c = SECP256K1_FE_CONST(0x0a2d2ba9, 0x3507f1df, 0x233770c2, 0xa797962c, 0xc61f6d15, 0xda14ecd4, 0x7d8d27ae, 0x1cd5f852);
125  static const secp256k1_fe d = SECP256K1_FE_CONST(0x851695d4, 0x9a83f8ef, 0x919bb861, 0x53cbcb16, 0x630fb68a, 0xed0a766a, 0x3ec693d6, 0x8e6afa40);
126  static const secp256k1_fe b = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 7);
127  static const secp256k1_fe b_plus_one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 8);
128 
129  secp256k1_fe wn, wd, x1n, x2n, x3n, x3d, jinv, tmp, x1, x2, x3, alphain, betain, gammain, y1, y2, y3;
130  int alphaquad, betaquad;
131 
132  secp256k1_fe_mul(&wn, &c, t); /* mag 1 */
133  secp256k1_fe_sqr(&wd, t); /* mag 1 */
134  secp256k1_fe_add(&wd, &b_plus_one); /* mag 2 */
135  secp256k1_fe_mul(&tmp, t, &wn); /* mag 1 */
136  secp256k1_fe_negate(&tmp, &tmp, 1); /* mag 2 */
137  secp256k1_fe_mul(&x1n, &d, &wd); /* mag 1 */
138  secp256k1_fe_add(&x1n, &tmp); /* mag 3 */
139  x2n = x1n; /* mag 3 */
140  secp256k1_fe_add(&x2n, &wd); /* mag 5 */
141  secp256k1_fe_negate(&x2n, &x2n, 5); /* mag 6 */
142  secp256k1_fe_mul(&x3d, &c, t); /* mag 1 */
143  secp256k1_fe_sqr(&x3d, &x3d); /* mag 1 */
144  secp256k1_fe_sqr(&x3n, &wd); /* mag 1 */
145  secp256k1_fe_add(&x3n, &x3d); /* mag 2 */
146  secp256k1_fe_mul(&jinv, &x3d, &wd); /* mag 1 */
147  secp256k1_fe_inv(&jinv, &jinv); /* mag 1 */
148  secp256k1_fe_mul(&x1, &x1n, &x3d); /* mag 1 */
149  secp256k1_fe_mul(&x1, &x1, &jinv); /* mag 1 */
150  secp256k1_fe_mul(&x2, &x2n, &x3d); /* mag 1 */
151  secp256k1_fe_mul(&x2, &x2, &jinv); /* mag 1 */
152  secp256k1_fe_mul(&x3, &x3n, &wd); /* mag 1 */
153  secp256k1_fe_mul(&x3, &x3, &jinv); /* mag 1 */
154 
155  secp256k1_fe_sqr(&alphain, &x1); /* mag 1 */
156  secp256k1_fe_mul(&alphain, &alphain, &x1); /* mag 1 */
157  secp256k1_fe_add(&alphain, &b); /* mag 2 */
158  secp256k1_fe_sqr(&betain, &x2); /* mag 1 */
159  secp256k1_fe_mul(&betain, &betain, &x2); /* mag 1 */
160  secp256k1_fe_add(&betain, &b); /* mag 2 */
161  secp256k1_fe_sqr(&gammain, &x3); /* mag 1 */
162  secp256k1_fe_mul(&gammain, &gammain, &x3); /* mag 1 */
163  secp256k1_fe_add(&gammain, &b); /* mag 2 */
164 
165  alphaquad = secp256k1_fe_sqrt(&y1, &alphain);
166  betaquad = secp256k1_fe_sqrt(&y2, &betain);
167  secp256k1_fe_sqrt(&y3, &gammain);
168 
169  secp256k1_fe_cmov(&x1, &x2, (!alphaquad) & betaquad);
170  secp256k1_fe_cmov(&y1, &y2, (!alphaquad) & betaquad);
171  secp256k1_fe_cmov(&x1, &x3, (!alphaquad) & !betaquad);
172  secp256k1_fe_cmov(&y1, &y3, (!alphaquad) & !betaquad);
173 
174  secp256k1_ge_set_xy(ge, &x1, &y1);
175 
176  /* The linked algorithm from the paper uses the Jacobi symbol of t to
177  * determine the Jacobi symbol of the produced y coordinate. Since the
178  * rest of the algorithm only uses t^2, we can safely use another criterion
179  * as long as negation of t results in negation of the y coordinate. Here
180  * we choose to use t's oddness, as it is faster to determine. */
181  secp256k1_fe_negate(&tmp, &ge->y, 1);
182  secp256k1_fe_cmov(&ge->y, &tmp, secp256k1_fe_is_odd(t));
183 }
184 
185 static int secp256k1_generator_generate_internal(const secp256k1_context2* ctx, secp256k1_generator* gen, const unsigned char *key32, const unsigned char *blind32) {
186  static const unsigned char prefix1[17] = "1st generation: ";
187  static const unsigned char prefix2[17] = "2nd generation: ";
188  secp256k1_fe t = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 4);
189  secp256k1_ge add;
190  secp256k1_gej accum;
191  int overflow;
192  secp256k1_sha256 sha256;
193  unsigned char b32[32];
194  int ret = 1;
195 
196  if (blind32) {
197  secp256k1_scalar blind;
198  secp256k1_scalar_set_b32(&blind, blind32, &overflow);
199  ret = !overflow;
200  CHECK(ret);
201  secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &accum, &blind);
202  }
203 
204  secp256k1_sha256_initialize(&sha256);
205  secp256k1_sha256_write(&sha256, prefix1, 16);
206  secp256k1_sha256_write(&sha256, key32, 32);
207  secp256k1_sha256_finalize(&sha256, b32);
208  ret &= secp256k1_fe_set_b32(&t, b32);
209  CHECK(ret);
210  shallue_van_de_woestijne(&add, &t);
211  if (blind32) {
212  secp256k1_gej_add_ge(&accum, &accum, &add);
213  } else {
214  secp256k1_gej_set_ge(&accum, &add);
215  }
216 
217  secp256k1_sha256_initialize(&sha256);
218  secp256k1_sha256_write(&sha256, prefix2, 16);
219  secp256k1_sha256_write(&sha256, key32, 32);
220  secp256k1_sha256_finalize(&sha256, b32);
221  ret &= secp256k1_fe_set_b32(&t, b32);
222  CHECK(ret);
223  shallue_van_de_woestijne(&add, &t);
224  secp256k1_gej_add_ge(&accum, &accum, &add);
225 
226  secp256k1_ge_set_gej(&add, &accum);
227  secp256k1_generator_save(gen, &add);
228  return ret;
229 }
230 
231 int secp256k1_generator_generate(const secp256k1_context2* ctx, secp256k1_generator* gen, const unsigned char *key32) {
232  VERIFY_CHECK(ctx != NULL);
233  ARG_CHECK(gen != NULL);
234  ARG_CHECK(key32 != NULL);
235  return secp256k1_generator_generate_internal(ctx, gen, key32, NULL);
236 }
237 
238 int secp256k1_generator_generate_blinded(const secp256k1_context2* ctx, secp256k1_generator* gen, const unsigned char *key32, const unsigned char *blind32) {
239  VERIFY_CHECK(ctx != NULL);
240  ARG_CHECK(gen != NULL);
241  ARG_CHECK(key32 != NULL);
242  ARG_CHECK(blind32 != NULL);
243  ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx));
244  return secp256k1_generator_generate_internal(ctx, gen, key32, blind32);
245 }
246 
247 #endif
VERIFY_CHECK
#define VERIFY_CHECK(cond)
Definition: util.h:61
secp256k1_ge::y
secp256k1_fe y
Definition: group.h:20
b
void const uint64_t * b
Definition: field_5x52_asm_impl.h:10
secp256k1_generator_serialize
int secp256k1_generator_serialize(const secp256k1_context2 *ctx, unsigned char *output, const secp256k1_generator *gen)
Serialize a 33-byte generator into a serialized byte sequence.
Definition: main_impl.h:77
sha256
Internal SHA-256 implementation.
Definition: sha256.cpp:15
secp256k1_generator_parse
int secp256k1_generator_parse(const secp256k1_context2 *ctx, secp256k1_generator *gen, const unsigned char *input)
Parse a 33-byte generator byte sequence into a generator object.
Definition: main_impl.h:57
secp256k1_generator_generate
int secp256k1_generator_generate(const secp256k1_context2 *ctx, secp256k1_generator *gen, const unsigned char *key32)
Generate a generator for the curve.
Definition: main_impl.h:231
secp256k1_sha256
Definition: hash.h:13
secp256k1_generator
Opaque data structure that stores a base point.
Definition: secp256k1_generator.h:20
secp256k1_scalar
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
secp256k1_gej
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:24
secp256k1_fe
Definition: field_10x26.h:12
secp256k1_generator_const_g
const secp256k1_generator secp256k1_generator_const_g
Standard secp256k1 generator.
Definition: main_impl.h:18
secp256k1_ge::infinity
int infinity
Definition: group.h:21
secp256k1_context_struct2
Definition: secp256k1_types.h:15
secp256k1_generator_const_h
const secp256k1_generator secp256k1_generator_const_h
Alternate secp256k1 generator, used in Elements Alpha.
Definition: main_impl.h:32
secp256k1_generator::data
unsigned char data[64]
Definition: secp256k1_generator.h:21
secp256k1_ge::x
secp256k1_fe x
Definition: group.h:19
CHECK
#define CHECK(cond)
Definition: util.h:43
secp256k1_ge
A group element of the secp256k1 curve, in affine coordinates.
Definition: group.h:14
secp256k1_context_struct2::ecmult_gen_ctx
secp256k1_ecmult_gen_context ecmult_gen_ctx
Definition: secp256k1_types.h:17
ARG_CHECK
#define ARG_CHECK(cond)
Definition: secp256k1_2.c:38
SECP256K1_FE_CONST
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
Definition: field_10x26.h:38
secp256k1_generator_generate_blinded
int secp256k1_generator_generate_blinded(const secp256k1_context2 *ctx, secp256k1_generator *gen, const unsigned char *key32, const unsigned char *blind32)
Generate a blinded generator for the curve.
Definition: main_impl.h:238
Generated on Tue Apr 28 2026 00:02:57 for PRCYCoin by   doxygen 1.8.17