Bitcoin Core  0.20.99
P2P Digital Currency
field_impl.h
Go to the documentation of this file.
1 /**********************************************************************
2  * Copyright (c) 2013, 2014 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_FIELD_IMPL_H
8 #define SECP256K1_FIELD_IMPL_H
9 
10 #if defined HAVE_CONFIG_H
11 #include "libsecp256k1-config.h"
12 #endif
13 
14 #include "util.h"
15 #include "num.h"
16 
17 #if defined(USE_FIELD_10X26)
18 #include "field_10x26_impl.h"
19 #elif defined(USE_FIELD_5X52)
20 #include "field_5x52_impl.h"
21 #else
22 #error "Please select field implementation"
23 #endif
24 
26  secp256k1_fe na;
27  secp256k1_fe_negate(&na, a, 1);
28  secp256k1_fe_add(&na, b);
30 }
31 
33  secp256k1_fe na;
34  secp256k1_fe_negate(&na, a, 1);
35  secp256k1_fe_add(&na, b);
37 }
38 
39 static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a) {
49  secp256k1_fe x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1;
50  int j;
51 
52  VERIFY_CHECK(r != a);
53 
59  secp256k1_fe_sqr(&x2, a);
60  secp256k1_fe_mul(&x2, &x2, a);
61 
62  secp256k1_fe_sqr(&x3, &x2);
63  secp256k1_fe_mul(&x3, &x3, a);
64 
65  x6 = x3;
66  for (j=0; j<3; j++) {
67  secp256k1_fe_sqr(&x6, &x6);
68  }
69  secp256k1_fe_mul(&x6, &x6, &x3);
70 
71  x9 = x6;
72  for (j=0; j<3; j++) {
73  secp256k1_fe_sqr(&x9, &x9);
74  }
75  secp256k1_fe_mul(&x9, &x9, &x3);
76 
77  x11 = x9;
78  for (j=0; j<2; j++) {
79  secp256k1_fe_sqr(&x11, &x11);
80  }
81  secp256k1_fe_mul(&x11, &x11, &x2);
82 
83  x22 = x11;
84  for (j=0; j<11; j++) {
85  secp256k1_fe_sqr(&x22, &x22);
86  }
87  secp256k1_fe_mul(&x22, &x22, &x11);
88 
89  x44 = x22;
90  for (j=0; j<22; j++) {
91  secp256k1_fe_sqr(&x44, &x44);
92  }
93  secp256k1_fe_mul(&x44, &x44, &x22);
94 
95  x88 = x44;
96  for (j=0; j<44; j++) {
97  secp256k1_fe_sqr(&x88, &x88);
98  }
99  secp256k1_fe_mul(&x88, &x88, &x44);
100 
101  x176 = x88;
102  for (j=0; j<88; j++) {
103  secp256k1_fe_sqr(&x176, &x176);
104  }
105  secp256k1_fe_mul(&x176, &x176, &x88);
106 
107  x220 = x176;
108  for (j=0; j<44; j++) {
109  secp256k1_fe_sqr(&x220, &x220);
110  }
111  secp256k1_fe_mul(&x220, &x220, &x44);
112 
113  x223 = x220;
114  for (j=0; j<3; j++) {
115  secp256k1_fe_sqr(&x223, &x223);
116  }
117  secp256k1_fe_mul(&x223, &x223, &x3);
118 
119  /* The final result is then assembled using a sliding window over the blocks. */
120 
121  t1 = x223;
122  for (j=0; j<23; j++) {
123  secp256k1_fe_sqr(&t1, &t1);
124  }
125  secp256k1_fe_mul(&t1, &t1, &x22);
126  for (j=0; j<6; j++) {
127  secp256k1_fe_sqr(&t1, &t1);
128  }
129  secp256k1_fe_mul(&t1, &t1, &x2);
130  secp256k1_fe_sqr(&t1, &t1);
131  secp256k1_fe_sqr(r, &t1);
132 
133  /* Check that a square root was actually calculated */
134 
135  secp256k1_fe_sqr(&t1, r);
136  return secp256k1_fe_equal(&t1, a);
137 }
138 
139 static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *a) {
140  secp256k1_fe x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1;
141  int j;
142 
148  secp256k1_fe_sqr(&x2, a);
149  secp256k1_fe_mul(&x2, &x2, a);
150 
151  secp256k1_fe_sqr(&x3, &x2);
152  secp256k1_fe_mul(&x3, &x3, a);
153 
154  x6 = x3;
155  for (j=0; j<3; j++) {
156  secp256k1_fe_sqr(&x6, &x6);
157  }
158  secp256k1_fe_mul(&x6, &x6, &x3);
159 
160  x9 = x6;
161  for (j=0; j<3; j++) {
162  secp256k1_fe_sqr(&x9, &x9);
163  }
164  secp256k1_fe_mul(&x9, &x9, &x3);
165 
166  x11 = x9;
167  for (j=0; j<2; j++) {
168  secp256k1_fe_sqr(&x11, &x11);
169  }
170  secp256k1_fe_mul(&x11, &x11, &x2);
171 
172  x22 = x11;
173  for (j=0; j<11; j++) {
174  secp256k1_fe_sqr(&x22, &x22);
175  }
176  secp256k1_fe_mul(&x22, &x22, &x11);
177 
178  x44 = x22;
179  for (j=0; j<22; j++) {
180  secp256k1_fe_sqr(&x44, &x44);
181  }
182  secp256k1_fe_mul(&x44, &x44, &x22);
183 
184  x88 = x44;
185  for (j=0; j<44; j++) {
186  secp256k1_fe_sqr(&x88, &x88);
187  }
188  secp256k1_fe_mul(&x88, &x88, &x44);
189 
190  x176 = x88;
191  for (j=0; j<88; j++) {
192  secp256k1_fe_sqr(&x176, &x176);
193  }
194  secp256k1_fe_mul(&x176, &x176, &x88);
195 
196  x220 = x176;
197  for (j=0; j<44; j++) {
198  secp256k1_fe_sqr(&x220, &x220);
199  }
200  secp256k1_fe_mul(&x220, &x220, &x44);
201 
202  x223 = x220;
203  for (j=0; j<3; j++) {
204  secp256k1_fe_sqr(&x223, &x223);
205  }
206  secp256k1_fe_mul(&x223, &x223, &x3);
207 
208  /* The final result is then assembled using a sliding window over the blocks. */
209 
210  t1 = x223;
211  for (j=0; j<23; j++) {
212  secp256k1_fe_sqr(&t1, &t1);
213  }
214  secp256k1_fe_mul(&t1, &t1, &x22);
215  for (j=0; j<5; j++) {
216  secp256k1_fe_sqr(&t1, &t1);
217  }
218  secp256k1_fe_mul(&t1, &t1, a);
219  for (j=0; j<3; j++) {
220  secp256k1_fe_sqr(&t1, &t1);
221  }
222  secp256k1_fe_mul(&t1, &t1, &x2);
223  for (j=0; j<2; j++) {
224  secp256k1_fe_sqr(&t1, &t1);
225  }
226  secp256k1_fe_mul(r, a, &t1);
227 }
228 
229 static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a) {
230 #if defined(USE_FIELD_INV_BUILTIN)
231  secp256k1_fe_inv(r, a);
232 #elif defined(USE_FIELD_INV_NUM)
233  secp256k1_num n, m;
234  static const secp256k1_fe negone = SECP256K1_FE_CONST(
235  0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL,
236  0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL, 0xFFFFFC2EUL
237  );
238  /* secp256k1 field prime, value p defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */
239  static const unsigned char prime[32] = {
240  0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
241  0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
242  0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
243  0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFC,0x2F
244  };
245  unsigned char b[32];
246  int res;
247  secp256k1_fe c = *a;
249  secp256k1_fe_get_b32(b, &c);
250  secp256k1_num_set_bin(&n, b, 32);
251  secp256k1_num_set_bin(&m, prime, 32);
252  secp256k1_num_mod_inverse(&n, &n, &m);
253  secp256k1_num_get_bin(b, 32, &n);
254  res = secp256k1_fe_set_b32(r, b);
255  (void)res;
256  VERIFY_CHECK(res);
257  /* Verify the result is the (unique) valid inverse using non-GMP code. */
258  secp256k1_fe_mul(&c, &c, r);
259  secp256k1_fe_add(&c, &negone);
261 #else
262 #error "Please select field inverse implementation"
263 #endif
264 }
265 
266 static void secp256k1_fe_inv_all_var(secp256k1_fe *r, const secp256k1_fe *a, size_t len) {
267  secp256k1_fe u;
268  size_t i;
269  if (len < 1) {
270  return;
271  }
272 
273  VERIFY_CHECK((r + len <= a) || (a + len <= r));
274 
275  r[0] = a[0];
276 
277  i = 0;
278  while (++i < len) {
279  secp256k1_fe_mul(&r[i], &r[i - 1], &a[i]);
280  }
281 
282  secp256k1_fe_inv_var(&u, &r[--i]);
283 
284  while (i > 0) {
285  size_t j = i--;
286  secp256k1_fe_mul(&r[j], &r[i], &u);
287  secp256k1_fe_mul(&u, &u, &a[j]);
288  }
289 
290  r[0] = u;
291 }
292 
294 #ifndef USE_NUM_NONE
295  unsigned char b[32];
296  secp256k1_num n;
297  secp256k1_num m;
298  /* secp256k1 field prime, value p defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */
299  static const unsigned char prime[32] = {
300  0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
301  0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
302  0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
303  0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFC,0x2F
304  };
305 
306  secp256k1_fe c = *a;
308  secp256k1_fe_get_b32(b, &c);
309  secp256k1_num_set_bin(&n, b, 32);
310  secp256k1_num_set_bin(&m, prime, 32);
311  return secp256k1_num_jacobi(&n, &m) >= 0;
312 #else
313  secp256k1_fe r;
314  return secp256k1_fe_sqrt(&r, a);
315 #endif
316 }
317 
318 static const secp256k1_fe secp256k1_fe_one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1);
319 
320 #endif /* SECP256K1_FIELD_IMPL_H */
#define VERIFY_CHECK(cond)
Definition: util.h:68
static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe *SECP256K1_RESTRICT b)
Sets a field element to be the product of two others.
static void secp256k1_fe_normalize_var(secp256k1_fe *r)
Normalize a field element, without constant-time guarantee.
static void secp256k1_num_set_bin(secp256k1_num *r, const unsigned char *a, unsigned int alen)
Set a number to the value of a binary big-endian string.
static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m)
Set a field element equal to the additive inverse of another.
static SECP256K1_INLINE int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b)
Definition: field_impl.h:25
static SECP256K1_INLINE int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b)
Definition: field_impl.h:32
static void secp256k1_num_mod_inverse(secp256k1_num *r, const secp256k1_num *a, const secp256k1_num *m)
Compute a modular inverse.
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
Definition: field_10x26.h:40
static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a)
Adds a field element to another.
#define SECP256K1_INLINE
Definition: secp256k1.h:124
static int secp256k1_fe_is_quad_var(const secp256k1_fe *a)
Definition: field_impl.h:293
static int secp256k1_num_jacobi(const secp256k1_num *a, const secp256k1_num *b)
Compute the jacobi symbol (a|b).
static void secp256k1_fe_inv(secp256k1_fe *r, const secp256k1_fe *a)
Definition: field_impl.h:139
static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *a)
Definition: field_impl.h:229
static int secp256k1_fe_normalizes_to_zero(secp256k1_fe *r)
Verify whether a field element represents zero i.e.
#define CHECK(cond)
Definition: util.h:53
static const secp256k1_fe secp256k1_fe_one
Definition: field_impl.h:318
static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a)
Sets a field element to be the square of another.
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 int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a)
Definition: field_impl.h:39
static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe *a)
Convert a field element to a 32-byte big endian value.
static void secp256k1_fe_inv_all_var(secp256k1_fe *r, const secp256k1_fe *a, size_t len)
Definition: field_impl.h:266
static void secp256k1_num_get_bin(unsigned char *r, unsigned int rlen, const secp256k1_num *a)
Convert a number&#39;s absolute value to a binary big-endian string.
static int secp256k1_fe_normalizes_to_zero_var(secp256k1_fe *r)
Verify whether a field element represents zero i.e.