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