Bitcoin Core  27.99.0
P2P Digital Currency
scalar_impl.h
Go to the documentation of this file.
1 /***********************************************************************
2  * Copyright (c) 2014 Pieter Wuille *
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_SCALAR_IMPL_H
8 #define SECP256K1_SCALAR_IMPL_H
9 
10 #ifdef VERIFY
11 #include <string.h>
12 #endif
13 
14 #include "scalar.h"
15 #include "util.h"
16 
17 #if defined(EXHAUSTIVE_TEST_ORDER)
18 #include "scalar_low_impl.h"
19 #elif defined(SECP256K1_WIDEMUL_INT128)
20 #include "scalar_4x64_impl.h"
21 #elif defined(SECP256K1_WIDEMUL_INT64)
22 #include "scalar_8x32_impl.h"
23 #else
24 #error "Please select wide multiplication implementation"
25 #endif
26 
27 static const secp256k1_scalar secp256k1_scalar_one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1);
28 static const secp256k1_scalar secp256k1_scalar_zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0);
29 
30 static int secp256k1_scalar_set_b32_seckey(secp256k1_scalar *r, const unsigned char *bin) {
31  int overflow;
32  secp256k1_scalar_set_b32(r, bin, &overflow);
33 
35  return (!overflow) & (!secp256k1_scalar_is_zero(r));
36 }
37 
40 
41  (void)r;
42 }
43 
44 #if defined(EXHAUSTIVE_TEST_ORDER)
45 /* Begin of section generated by sage/gen_exhaustive_groups.sage. */
46 # if EXHAUSTIVE_TEST_ORDER == 7
47 # define EXHAUSTIVE_TEST_LAMBDA 2
48 # elif EXHAUSTIVE_TEST_ORDER == 13
49 # define EXHAUSTIVE_TEST_LAMBDA 9
50 # elif EXHAUSTIVE_TEST_ORDER == 199
51 # define EXHAUSTIVE_TEST_LAMBDA 92
52 # else
53 # error No known lambda for the specified exhaustive test group order.
54 # endif
55 /* End of section generated by sage/gen_exhaustive_groups.sage. */
56 
65  VERIFY_CHECK(r1 != k);
66  VERIFY_CHECK(r2 != k);
67  VERIFY_CHECK(r1 != r2);
68 
69  *r2 = (*k + 5) % EXHAUSTIVE_TEST_ORDER;
70  *r1 = (*k + (EXHAUSTIVE_TEST_ORDER - *r2) * EXHAUSTIVE_TEST_LAMBDA) % EXHAUSTIVE_TEST_ORDER;
71 
74 }
75 #else
80  0x5363AD4CUL, 0xC05C30E0UL, 0xA5261C02UL, 0x8812645AUL,
81  0x122E22EAUL, 0x20816678UL, 0xDF02967CUL, 0x1B23BD72UL
82 );
83 
84 #ifdef VERIFY
85 static void secp256k1_scalar_split_lambda_verify(const secp256k1_scalar *r1, const secp256k1_scalar *r2, const secp256k1_scalar *k);
86 #endif
87 
88 /*
89  * Both lambda and beta are primitive cube roots of unity. That is lamba^3 == 1 mod n and
90  * beta^3 == 1 mod p, where n is the curve order and p is the field order.
91  *
92  * Furthermore, because (X^3 - 1) = (X - 1)(X^2 + X + 1), the primitive cube roots of unity are
93  * roots of X^2 + X + 1. Therefore lambda^2 + lamba == -1 mod n and beta^2 + beta == -1 mod p.
94  * (The other primitive cube roots of unity are lambda^2 and beta^2 respectively.)
95  *
96  * Let l = -1/2 + i*sqrt(3)/2, the complex root of X^2 + X + 1. We can define a ring
97  * homomorphism phi : Z[l] -> Z_n where phi(a + b*l) == a + b*lambda mod n. The kernel of phi
98  * is a lattice over Z[l] (considering Z[l] as a Z-module). This lattice is generated by a
99  * reduced basis {a1 + b1*l, a2 + b2*l} where
100  *
101  * - a1 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}
102  * - b1 = -{0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3}
103  * - a2 = {0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,0xd8}
104  * - b2 = {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}
105  *
106  * "Guide to Elliptic Curve Cryptography" (Hankerson, Menezes, Vanstone) gives an algorithm
107  * (algorithm 3.74) to find k1 and k2 given k, such that k1 + k2 * lambda == k mod n, and k1
108  * and k2 are small in absolute value.
109  *
110  * The algorithm computes c1 = round(b2 * k / n) and c2 = round((-b1) * k / n), and gives
111  * k1 = k - (c1*a1 + c2*a2) and k2 = -(c1*b1 + c2*b2). Instead, we use modular arithmetic, and
112  * compute r2 = k2 mod n, and r1 = k1 mod n = (k - r2 * lambda) mod n, avoiding the need for
113  * the constants a1 and a2.
114  *
115  * g1, g2 are precomputed constants used to replace division with a rounded multiplication
116  * when decomposing the scalar for an endomorphism-based point multiplication.
117  *
118  * The possibility of using precomputed estimates is mentioned in "Guide to Elliptic Curve
119  * Cryptography" (Hankerson, Menezes, Vanstone) in section 3.5.
120  *
121  * The derivation is described in the paper "Efficient Software Implementation of Public-Key
122  * Cryptography on Sensor Networks Using the MSP430X Microcontroller" (Gouvea, Oliveira, Lopez),
123  * Section 4.3 (here we use a somewhat higher-precision estimate):
124  * d = a1*b2 - b1*a2
125  * g1 = round(2^384 * b2/d)
126  * g2 = round(2^384 * (-b1)/d)
127  *
128  * (Note that d is also equal to the curve order, n, here because [a1,b1] and [a2,b2]
129  * can be found as outputs of the Extended Euclidean Algorithm on inputs n and lambda).
130  *
131  * The function below splits k into r1 and r2, such that
132  * - r1 + lambda * r2 == k (mod n)
133  * - either r1 < 2^128 or -r1 mod n < 2^128
134  * - either r2 < 2^128 or -r2 mod n < 2^128
135  *
136  * See proof below.
137  */
139  secp256k1_scalar c1, c2;
140  static const secp256k1_scalar minus_b1 = SECP256K1_SCALAR_CONST(
141  0x00000000UL, 0x00000000UL, 0x00000000UL, 0x00000000UL,
142  0xE4437ED6UL, 0x010E8828UL, 0x6F547FA9UL, 0x0ABFE4C3UL
143  );
144  static const secp256k1_scalar minus_b2 = SECP256K1_SCALAR_CONST(
145  0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL,
146  0x8A280AC5UL, 0x0774346DUL, 0xD765CDA8UL, 0x3DB1562CUL
147  );
148  static const secp256k1_scalar g1 = SECP256K1_SCALAR_CONST(
149  0x3086D221UL, 0xA7D46BCDUL, 0xE86C90E4UL, 0x9284EB15UL,
150  0x3DAA8A14UL, 0x71E8CA7FUL, 0xE893209AUL, 0x45DBB031UL
151  );
152  static const secp256k1_scalar g2 = SECP256K1_SCALAR_CONST(
153  0xE4437ED6UL, 0x010E8828UL, 0x6F547FA9UL, 0x0ABFE4C4UL,
154  0x221208ACUL, 0x9DF506C6UL, 0x1571B4AEUL, 0x8AC47F71UL
155  );
157  VERIFY_CHECK(r1 != k);
158  VERIFY_CHECK(r2 != k);
159  VERIFY_CHECK(r1 != r2);
160 
161  /* these _var calls are constant time since the shift amount is constant */
162  secp256k1_scalar_mul_shift_var(&c1, k, &g1, 384);
163  secp256k1_scalar_mul_shift_var(&c2, k, &g2, 384);
164  secp256k1_scalar_mul(&c1, &c1, &minus_b1);
165  secp256k1_scalar_mul(&c2, &c2, &minus_b2);
166  secp256k1_scalar_add(r2, &c1, &c2);
168  secp256k1_scalar_negate(r1, r1);
169  secp256k1_scalar_add(r1, r1, k);
170 
173 #ifdef VERIFY
174  secp256k1_scalar_split_lambda_verify(r1, r2, k);
175 #endif
176 }
177 
178 #ifdef VERIFY
179 /*
180  * Proof for secp256k1_scalar_split_lambda's bounds.
181  *
182  * Let
183  * - epsilon1 = 2^256 * |g1/2^384 - b2/d|
184  * - epsilon2 = 2^256 * |g2/2^384 - (-b1)/d|
185  * - c1 = round(k*g1/2^384)
186  * - c2 = round(k*g2/2^384)
187  *
188  * Lemma 1: |c1 - k*b2/d| < 2^-1 + epsilon1
189  *
190  * |c1 - k*b2/d|
191  * =
192  * |c1 - k*g1/2^384 + k*g1/2^384 - k*b2/d|
193  * <= {triangle inequality}
194  * |c1 - k*g1/2^384| + |k*g1/2^384 - k*b2/d|
195  * =
196  * |c1 - k*g1/2^384| + k*|g1/2^384 - b2/d|
197  * < {rounding in c1 and 0 <= k < 2^256}
198  * 2^-1 + 2^256 * |g1/2^384 - b2/d|
199  * = {definition of epsilon1}
200  * 2^-1 + epsilon1
201  *
202  * Lemma 2: |c2 - k*(-b1)/d| < 2^-1 + epsilon2
203  *
204  * |c2 - k*(-b1)/d|
205  * =
206  * |c2 - k*g2/2^384 + k*g2/2^384 - k*(-b1)/d|
207  * <= {triangle inequality}
208  * |c2 - k*g2/2^384| + |k*g2/2^384 - k*(-b1)/d|
209  * =
210  * |c2 - k*g2/2^384| + k*|g2/2^384 - (-b1)/d|
211  * < {rounding in c2 and 0 <= k < 2^256}
212  * 2^-1 + 2^256 * |g2/2^384 - (-b1)/d|
213  * = {definition of epsilon2}
214  * 2^-1 + epsilon2
215  *
216  * Let
217  * - k1 = k - c1*a1 - c2*a2
218  * - k2 = - c1*b1 - c2*b2
219  *
220  * Lemma 3: |k1| < (a1 + a2 + 1)/2 < 2^128
221  *
222  * |k1|
223  * = {definition of k1}
224  * |k - c1*a1 - c2*a2|
225  * = {(a1*b2 - b1*a2)/n = 1}
226  * |k*(a1*b2 - b1*a2)/n - c1*a1 - c2*a2|
227  * =
228  * |a1*(k*b2/n - c1) + a2*(k*(-b1)/n - c2)|
229  * <= {triangle inequality}
230  * a1*|k*b2/n - c1| + a2*|k*(-b1)/n - c2|
231  * < {Lemma 1 and Lemma 2}
232  * a1*(2^-1 + epslion1) + a2*(2^-1 + epsilon2)
233  * < {rounding up to an integer}
234  * (a1 + a2 + 1)/2
235  * < {rounding up to a power of 2}
236  * 2^128
237  *
238  * Lemma 4: |k2| < (-b1 + b2)/2 + 1 < 2^128
239  *
240  * |k2|
241  * = {definition of k2}
242  * |- c1*a1 - c2*a2|
243  * = {(b1*b2 - b1*b2)/n = 0}
244  * |k*(b1*b2 - b1*b2)/n - c1*b1 - c2*b2|
245  * =
246  * |b1*(k*b2/n - c1) + b2*(k*(-b1)/n - c2)|
247  * <= {triangle inequality}
248  * (-b1)*|k*b2/n - c1| + b2*|k*(-b1)/n - c2|
249  * < {Lemma 1 and Lemma 2}
250  * (-b1)*(2^-1 + epslion1) + b2*(2^-1 + epsilon2)
251  * < {rounding up to an integer}
252  * (-b1 + b2)/2 + 1
253  * < {rounding up to a power of 2}
254  * 2^128
255  *
256  * Let
257  * - r2 = k2 mod n
258  * - r1 = k - r2*lambda mod n.
259  *
260  * Notice that r1 is defined such that r1 + r2 * lambda == k (mod n).
261  *
262  * Lemma 5: r1 == k1 mod n.
263  *
264  * r1
265  * == {definition of r1 and r2}
266  * k - k2*lambda
267  * == {definition of k2}
268  * k - (- c1*b1 - c2*b2)*lambda
269  * ==
270  * k + c1*b1*lambda + c2*b2*lambda
271  * == {a1 + b1*lambda == 0 mod n and a2 + b2*lambda == 0 mod n}
272  * k - c1*a1 - c2*a2
273  * == {definition of k1}
274  * k1
275  *
276  * From Lemma 3, Lemma 4, Lemma 5 and the definition of r2, we can conclude that
277  *
278  * - either r1 < 2^128 or -r1 mod n < 2^128
279  * - either r2 < 2^128 or -r2 mod n < 2^128.
280  *
281  * Q.E.D.
282  */
283 static void secp256k1_scalar_split_lambda_verify(const secp256k1_scalar *r1, const secp256k1_scalar *r2, const secp256k1_scalar *k) {
285  unsigned char buf1[32];
286  unsigned char buf2[32];
287 
288  /* (a1 + a2 + 1)/2 is 0xa2a8918ca85bafe22016d0b917e4dd77 */
289  static const unsigned char k1_bound[32] = {
290  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
291  0xa2, 0xa8, 0x91, 0x8c, 0xa8, 0x5b, 0xaf, 0xe2, 0x20, 0x16, 0xd0, 0xb9, 0x17, 0xe4, 0xdd, 0x77
292  };
293 
294  /* (-b1 + b2)/2 + 1 is 0x8a65287bd47179fb2be08846cea267ed */
295  static const unsigned char k2_bound[32] = {
296  0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
297  0x8a, 0x65, 0x28, 0x7b, 0xd4, 0x71, 0x79, 0xfb, 0x2b, 0xe0, 0x88, 0x46, 0xce, 0xa2, 0x67, 0xed
298  };
299 
301  secp256k1_scalar_add(&s, &s, r1);
303 
304  secp256k1_scalar_negate(&s, r1);
305  secp256k1_scalar_get_b32(buf1, r1);
306  secp256k1_scalar_get_b32(buf2, &s);
307  VERIFY_CHECK(secp256k1_memcmp_var(buf1, k1_bound, 32) < 0 || secp256k1_memcmp_var(buf2, k1_bound, 32) < 0);
308 
309  secp256k1_scalar_negate(&s, r2);
310  secp256k1_scalar_get_b32(buf1, r2);
311  secp256k1_scalar_get_b32(buf2, &s);
312  VERIFY_CHECK(secp256k1_memcmp_var(buf1, k2_bound, 32) < 0 || secp256k1_memcmp_var(buf2, k2_bound, 32) < 0);
313 }
314 #endif /* VERIFY */
315 #endif /* !defined(EXHAUSTIVE_TEST_ORDER) */
316 
317 #endif /* SECP256K1_SCALAR_IMPL_H */
static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *bin, int *overflow)
Set a scalar from a big endian byte array.
static int secp256k1_scalar_is_zero(const secp256k1_scalar *a)
Check whether a scalar equals zero.
static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b)
Compare two scalars.
static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar *a)
Convert a scalar to a byte array.
static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Add two scalars together (modulo the group order).
#define SECP256K1_SCALAR_VERIFY(r)
Definition: scalar.h:103
static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Multiply two scalars (modulo the group order).
static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b, unsigned int shift)
Multiply a and b (without taking the modulus!), divide by 2**shift, and round to the nearest integer.
static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a)
Compute the complement of a scalar (modulo the group order).
#define SECP256K1_SCALAR_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
Definition: scalar_4x64.h:17
static SECP256K1_INLINE int secp256k1_scalar_check_overflow(const secp256k1_scalar *a)
static void secp256k1_scalar_verify(const secp256k1_scalar *r)
Definition: scalar_impl.h:38
static const secp256k1_scalar secp256k1_scalar_zero
Definition: scalar_impl.h:28
static int secp256k1_scalar_set_b32_seckey(secp256k1_scalar *r, const unsigned char *bin)
Definition: scalar_impl.h:30
static const secp256k1_scalar secp256k1_scalar_one
Definition: scalar_impl.h:27
static const secp256k1_scalar secp256k1_const_lambda
The Secp256k1 curve has an endomorphism, where lambda * (x, y) = (beta * x, y), where lambda is:
Definition: scalar_impl.h:79
static void secp256k1_scalar_split_lambda(secp256k1_scalar *SECP256K1_RESTRICT r1, secp256k1_scalar *SECP256K1_RESTRICT r2, const secp256k1_scalar *SECP256K1_RESTRICT k)
Definition: scalar_impl.h:138
static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n)
Semantics like memcmp.
Definition: util.h:212
#define VERIFY_CHECK(cond)
Definition: util.h:139
#define SECP256K1_RESTRICT
Definition: util.h:171
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
#define EXHAUSTIVE_TEST_ORDER