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_REPR_IMPL_H
8 #define SECP256K1_SCALAR_REPR_IMPL_H
9
10 #include "modinv32_impl.h"
11
12 /* Limbs of the secp256k1 order. */
13 #define SECP256K1_N_0 ((uint32_t)0xD0364141UL)
14 #define SECP256K1_N_1 ((uint32_t)0xBFD25E8CUL)
15 #define SECP256K1_N_2 ((uint32_t)0xAF48A03BUL)
16 #define SECP256K1_N_3 ((uint32_t)0xBAAEDCE6UL)
17 #define SECP256K1_N_4 ((uint32_t)0xFFFFFFFEUL)
18 #define SECP256K1_N_5 ((uint32_t)0xFFFFFFFFUL)
19 #define SECP256K1_N_6 ((uint32_t)0xFFFFFFFFUL)
20 #define SECP256K1_N_7 ((uint32_t)0xFFFFFFFFUL)
21
22 /* Limbs of 2^256 minus the secp256k1 order. */
23 #define SECP256K1_N_C_0 (~SECP256K1_N_0 + 1)
24 #define SECP256K1_N_C_1 (~SECP256K1_N_1)
25 #define SECP256K1_N_C_2 (~SECP256K1_N_2)
26 #define SECP256K1_N_C_3 (~SECP256K1_N_3)
27 #define SECP256K1_N_C_4 (1)
28
29 /* Limbs of half the secp256k1 order. */
30 #define SECP256K1_N_H_0 ((uint32_t)0x681B20A0UL)
31 #define SECP256K1_N_H_1 ((uint32_t)0xDFE92F46UL)
32 #define SECP256K1_N_H_2 ((uint32_t)0x57A4501DUL)
33 #define SECP256K1_N_H_3 ((uint32_t)0x5D576E73UL)
34 #define SECP256K1_N_H_4 ((uint32_t)0xFFFFFFFFUL)
35 #define SECP256K1_N_H_5 ((uint32_t)0xFFFFFFFFUL)
36 #define SECP256K1_N_H_6 ((uint32_t)0xFFFFFFFFUL)
37 #define SECP256K1_N_H_7 ((uint32_t)0x7FFFFFFFUL)
38
secp256k1_scalar_clear(secp256k1_scalar * r)39 SECP256K1_INLINE static void secp256k1_scalar_clear(secp256k1_scalar *r) {
40 r->d[0] = 0;
41 r->d[1] = 0;
42 r->d[2] = 0;
43 r->d[3] = 0;
44 r->d[4] = 0;
45 r->d[5] = 0;
46 r->d[6] = 0;
47 r->d[7] = 0;
48 }
49
secp256k1_scalar_set_int(secp256k1_scalar * r,unsigned int v)50 SECP256K1_INLINE static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v) {
51 r->d[0] = v;
52 r->d[1] = 0;
53 r->d[2] = 0;
54 r->d[3] = 0;
55 r->d[4] = 0;
56 r->d[5] = 0;
57 r->d[6] = 0;
58 r->d[7] = 0;
59 }
60
secp256k1_scalar_get_bits(const secp256k1_scalar * a,unsigned int offset,unsigned int count)61 SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count) {
62 VERIFY_CHECK((offset + count - 1) >> 5 == offset >> 5);
63 return (a->d[offset >> 5] >> (offset & 0x1F)) & ((1 << count) - 1);
64 }
65
secp256k1_scalar_get_bits_var(const secp256k1_scalar * a,unsigned int offset,unsigned int count)66 SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count) {
67 VERIFY_CHECK(count < 32);
68 VERIFY_CHECK(offset + count <= 256);
69 if ((offset + count - 1) >> 5 == offset >> 5) {
70 return secp256k1_scalar_get_bits(a, offset, count);
71 } else {
72 VERIFY_CHECK((offset >> 5) + 1 < 8);
73 return ((a->d[offset >> 5] >> (offset & 0x1F)) | (a->d[(offset >> 5) + 1] << (32 - (offset & 0x1F)))) & ((((uint32_t)1) << count) - 1);
74 }
75 }
76
secp256k1_scalar_check_overflow(const secp256k1_scalar * a)77 SECP256K1_INLINE static int secp256k1_scalar_check_overflow(const secp256k1_scalar *a) {
78 int yes = 0;
79 int no = 0;
80 no |= (a->d[7] < SECP256K1_N_7); /* No need for a > check. */
81 no |= (a->d[6] < SECP256K1_N_6); /* No need for a > check. */
82 no |= (a->d[5] < SECP256K1_N_5); /* No need for a > check. */
83 no |= (a->d[4] < SECP256K1_N_4);
84 yes |= (a->d[4] > SECP256K1_N_4) & ~no;
85 no |= (a->d[3] < SECP256K1_N_3) & ~yes;
86 yes |= (a->d[3] > SECP256K1_N_3) & ~no;
87 no |= (a->d[2] < SECP256K1_N_2) & ~yes;
88 yes |= (a->d[2] > SECP256K1_N_2) & ~no;
89 no |= (a->d[1] < SECP256K1_N_1) & ~yes;
90 yes |= (a->d[1] > SECP256K1_N_1) & ~no;
91 yes |= (a->d[0] >= SECP256K1_N_0) & ~no;
92 return yes;
93 }
94
secp256k1_scalar_reduce(secp256k1_scalar * r,uint32_t overflow)95 SECP256K1_INLINE static int secp256k1_scalar_reduce(secp256k1_scalar *r, uint32_t overflow) {
96 uint64_t t;
97 VERIFY_CHECK(overflow <= 1);
98 t = (uint64_t)r->d[0] + overflow * SECP256K1_N_C_0;
99 r->d[0] = t & 0xFFFFFFFFUL; t >>= 32;
100 t += (uint64_t)r->d[1] + overflow * SECP256K1_N_C_1;
101 r->d[1] = t & 0xFFFFFFFFUL; t >>= 32;
102 t += (uint64_t)r->d[2] + overflow * SECP256K1_N_C_2;
103 r->d[2] = t & 0xFFFFFFFFUL; t >>= 32;
104 t += (uint64_t)r->d[3] + overflow * SECP256K1_N_C_3;
105 r->d[3] = t & 0xFFFFFFFFUL; t >>= 32;
106 t += (uint64_t)r->d[4] + overflow * SECP256K1_N_C_4;
107 r->d[4] = t & 0xFFFFFFFFUL; t >>= 32;
108 t += (uint64_t)r->d[5];
109 r->d[5] = t & 0xFFFFFFFFUL; t >>= 32;
110 t += (uint64_t)r->d[6];
111 r->d[6] = t & 0xFFFFFFFFUL; t >>= 32;
112 t += (uint64_t)r->d[7];
113 r->d[7] = t & 0xFFFFFFFFUL;
114 return overflow;
115 }
116
secp256k1_scalar_add(secp256k1_scalar * r,const secp256k1_scalar * a,const secp256k1_scalar * b)117 static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) {
118 int overflow;
119 uint64_t t = (uint64_t)a->d[0] + b->d[0];
120 r->d[0] = t & 0xFFFFFFFFULL; t >>= 32;
121 t += (uint64_t)a->d[1] + b->d[1];
122 r->d[1] = t & 0xFFFFFFFFULL; t >>= 32;
123 t += (uint64_t)a->d[2] + b->d[2];
124 r->d[2] = t & 0xFFFFFFFFULL; t >>= 32;
125 t += (uint64_t)a->d[3] + b->d[3];
126 r->d[3] = t & 0xFFFFFFFFULL; t >>= 32;
127 t += (uint64_t)a->d[4] + b->d[4];
128 r->d[4] = t & 0xFFFFFFFFULL; t >>= 32;
129 t += (uint64_t)a->d[5] + b->d[5];
130 r->d[5] = t & 0xFFFFFFFFULL; t >>= 32;
131 t += (uint64_t)a->d[6] + b->d[6];
132 r->d[6] = t & 0xFFFFFFFFULL; t >>= 32;
133 t += (uint64_t)a->d[7] + b->d[7];
134 r->d[7] = t & 0xFFFFFFFFULL; t >>= 32;
135 overflow = t + secp256k1_scalar_check_overflow(r);
136 VERIFY_CHECK(overflow == 0 || overflow == 1);
137 secp256k1_scalar_reduce(r, overflow);
138 return overflow;
139 }
140
secp256k1_scalar_cadd_bit(secp256k1_scalar * r,unsigned int bit,int flag)141 static void secp256k1_scalar_cadd_bit(secp256k1_scalar *r, unsigned int bit, int flag) {
142 uint64_t t;
143 VERIFY_CHECK(bit < 256);
144 bit += ((uint32_t) flag - 1) & 0x100; /* forcing (bit >> 5) > 7 makes this a noop */
145 t = (uint64_t)r->d[0] + (((uint32_t)((bit >> 5) == 0)) << (bit & 0x1F));
146 r->d[0] = t & 0xFFFFFFFFULL; t >>= 32;
147 t += (uint64_t)r->d[1] + (((uint32_t)((bit >> 5) == 1)) << (bit & 0x1F));
148 r->d[1] = t & 0xFFFFFFFFULL; t >>= 32;
149 t += (uint64_t)r->d[2] + (((uint32_t)((bit >> 5) == 2)) << (bit & 0x1F));
150 r->d[2] = t & 0xFFFFFFFFULL; t >>= 32;
151 t += (uint64_t)r->d[3] + (((uint32_t)((bit >> 5) == 3)) << (bit & 0x1F));
152 r->d[3] = t & 0xFFFFFFFFULL; t >>= 32;
153 t += (uint64_t)r->d[4] + (((uint32_t)((bit >> 5) == 4)) << (bit & 0x1F));
154 r->d[4] = t & 0xFFFFFFFFULL; t >>= 32;
155 t += (uint64_t)r->d[5] + (((uint32_t)((bit >> 5) == 5)) << (bit & 0x1F));
156 r->d[5] = t & 0xFFFFFFFFULL; t >>= 32;
157 t += (uint64_t)r->d[6] + (((uint32_t)((bit >> 5) == 6)) << (bit & 0x1F));
158 r->d[6] = t & 0xFFFFFFFFULL; t >>= 32;
159 t += (uint64_t)r->d[7] + (((uint32_t)((bit >> 5) == 7)) << (bit & 0x1F));
160 r->d[7] = t & 0xFFFFFFFFULL;
161 #ifdef VERIFY
162 VERIFY_CHECK((t >> 32) == 0);
163 VERIFY_CHECK(secp256k1_scalar_check_overflow(r) == 0);
164 #endif
165 }
166
secp256k1_scalar_set_b32(secp256k1_scalar * r,const unsigned char * b32,int * overflow)167 static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *b32, int *overflow) {
168 int over;
169 r->d[0] = (uint32_t)b32[31] | (uint32_t)b32[30] << 8 | (uint32_t)b32[29] << 16 | (uint32_t)b32[28] << 24;
170 r->d[1] = (uint32_t)b32[27] | (uint32_t)b32[26] << 8 | (uint32_t)b32[25] << 16 | (uint32_t)b32[24] << 24;
171 r->d[2] = (uint32_t)b32[23] | (uint32_t)b32[22] << 8 | (uint32_t)b32[21] << 16 | (uint32_t)b32[20] << 24;
172 r->d[3] = (uint32_t)b32[19] | (uint32_t)b32[18] << 8 | (uint32_t)b32[17] << 16 | (uint32_t)b32[16] << 24;
173 r->d[4] = (uint32_t)b32[15] | (uint32_t)b32[14] << 8 | (uint32_t)b32[13] << 16 | (uint32_t)b32[12] << 24;
174 r->d[5] = (uint32_t)b32[11] | (uint32_t)b32[10] << 8 | (uint32_t)b32[9] << 16 | (uint32_t)b32[8] << 24;
175 r->d[6] = (uint32_t)b32[7] | (uint32_t)b32[6] << 8 | (uint32_t)b32[5] << 16 | (uint32_t)b32[4] << 24;
176 r->d[7] = (uint32_t)b32[3] | (uint32_t)b32[2] << 8 | (uint32_t)b32[1] << 16 | (uint32_t)b32[0] << 24;
177 over = secp256k1_scalar_reduce(r, secp256k1_scalar_check_overflow(r));
178 if (overflow) {
179 *overflow = over;
180 }
181 }
182
secp256k1_scalar_get_b32(unsigned char * bin,const secp256k1_scalar * a)183 static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar* a) {
184 bin[0] = a->d[7] >> 24; bin[1] = a->d[7] >> 16; bin[2] = a->d[7] >> 8; bin[3] = a->d[7];
185 bin[4] = a->d[6] >> 24; bin[5] = a->d[6] >> 16; bin[6] = a->d[6] >> 8; bin[7] = a->d[6];
186 bin[8] = a->d[5] >> 24; bin[9] = a->d[5] >> 16; bin[10] = a->d[5] >> 8; bin[11] = a->d[5];
187 bin[12] = a->d[4] >> 24; bin[13] = a->d[4] >> 16; bin[14] = a->d[4] >> 8; bin[15] = a->d[4];
188 bin[16] = a->d[3] >> 24; bin[17] = a->d[3] >> 16; bin[18] = a->d[3] >> 8; bin[19] = a->d[3];
189 bin[20] = a->d[2] >> 24; bin[21] = a->d[2] >> 16; bin[22] = a->d[2] >> 8; bin[23] = a->d[2];
190 bin[24] = a->d[1] >> 24; bin[25] = a->d[1] >> 16; bin[26] = a->d[1] >> 8; bin[27] = a->d[1];
191 bin[28] = a->d[0] >> 24; bin[29] = a->d[0] >> 16; bin[30] = a->d[0] >> 8; bin[31] = a->d[0];
192 }
193
secp256k1_scalar_is_zero(const secp256k1_scalar * a)194 SECP256K1_INLINE static int secp256k1_scalar_is_zero(const secp256k1_scalar *a) {
195 return (a->d[0] | a->d[1] | a->d[2] | a->d[3] | a->d[4] | a->d[5] | a->d[6] | a->d[7]) == 0;
196 }
197
secp256k1_scalar_negate(secp256k1_scalar * r,const secp256k1_scalar * a)198 static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a) {
199 uint32_t nonzero = 0xFFFFFFFFUL * (secp256k1_scalar_is_zero(a) == 0);
200 uint64_t t = (uint64_t)(~a->d[0]) + SECP256K1_N_0 + 1;
201 r->d[0] = t & nonzero; t >>= 32;
202 t += (uint64_t)(~a->d[1]) + SECP256K1_N_1;
203 r->d[1] = t & nonzero; t >>= 32;
204 t += (uint64_t)(~a->d[2]) + SECP256K1_N_2;
205 r->d[2] = t & nonzero; t >>= 32;
206 t += (uint64_t)(~a->d[3]) + SECP256K1_N_3;
207 r->d[3] = t & nonzero; t >>= 32;
208 t += (uint64_t)(~a->d[4]) + SECP256K1_N_4;
209 r->d[4] = t & nonzero; t >>= 32;
210 t += (uint64_t)(~a->d[5]) + SECP256K1_N_5;
211 r->d[5] = t & nonzero; t >>= 32;
212 t += (uint64_t)(~a->d[6]) + SECP256K1_N_6;
213 r->d[6] = t & nonzero; t >>= 32;
214 t += (uint64_t)(~a->d[7]) + SECP256K1_N_7;
215 r->d[7] = t & nonzero;
216 }
217
secp256k1_scalar_is_one(const secp256k1_scalar * a)218 SECP256K1_INLINE static int secp256k1_scalar_is_one(const secp256k1_scalar *a) {
219 return ((a->d[0] ^ 1) | a->d[1] | a->d[2] | a->d[3] | a->d[4] | a->d[5] | a->d[6] | a->d[7]) == 0;
220 }
221
secp256k1_scalar_is_high(const secp256k1_scalar * a)222 static int secp256k1_scalar_is_high(const secp256k1_scalar *a) {
223 int yes = 0;
224 int no = 0;
225 no |= (a->d[7] < SECP256K1_N_H_7);
226 yes |= (a->d[7] > SECP256K1_N_H_7) & ~no;
227 no |= (a->d[6] < SECP256K1_N_H_6) & ~yes; /* No need for a > check. */
228 no |= (a->d[5] < SECP256K1_N_H_5) & ~yes; /* No need for a > check. */
229 no |= (a->d[4] < SECP256K1_N_H_4) & ~yes; /* No need for a > check. */
230 no |= (a->d[3] < SECP256K1_N_H_3) & ~yes;
231 yes |= (a->d[3] > SECP256K1_N_H_3) & ~no;
232 no |= (a->d[2] < SECP256K1_N_H_2) & ~yes;
233 yes |= (a->d[2] > SECP256K1_N_H_2) & ~no;
234 no |= (a->d[1] < SECP256K1_N_H_1) & ~yes;
235 yes |= (a->d[1] > SECP256K1_N_H_1) & ~no;
236 yes |= (a->d[0] > SECP256K1_N_H_0) & ~no;
237 return yes;
238 }
239
secp256k1_scalar_cond_negate(secp256k1_scalar * r,int flag)240 static int secp256k1_scalar_cond_negate(secp256k1_scalar *r, int flag) {
241 /* If we are flag = 0, mask = 00...00 and this is a no-op;
242 * if we are flag = 1, mask = 11...11 and this is identical to secp256k1_scalar_negate */
243 uint32_t mask = !flag - 1;
244 uint32_t nonzero = 0xFFFFFFFFUL * (secp256k1_scalar_is_zero(r) == 0);
245 uint64_t t = (uint64_t)(r->d[0] ^ mask) + ((SECP256K1_N_0 + 1) & mask);
246 r->d[0] = t & nonzero; t >>= 32;
247 t += (uint64_t)(r->d[1] ^ mask) + (SECP256K1_N_1 & mask);
248 r->d[1] = t & nonzero; t >>= 32;
249 t += (uint64_t)(r->d[2] ^ mask) + (SECP256K1_N_2 & mask);
250 r->d[2] = t & nonzero; t >>= 32;
251 t += (uint64_t)(r->d[3] ^ mask) + (SECP256K1_N_3 & mask);
252 r->d[3] = t & nonzero; t >>= 32;
253 t += (uint64_t)(r->d[4] ^ mask) + (SECP256K1_N_4 & mask);
254 r->d[4] = t & nonzero; t >>= 32;
255 t += (uint64_t)(r->d[5] ^ mask) + (SECP256K1_N_5 & mask);
256 r->d[5] = t & nonzero; t >>= 32;
257 t += (uint64_t)(r->d[6] ^ mask) + (SECP256K1_N_6 & mask);
258 r->d[6] = t & nonzero; t >>= 32;
259 t += (uint64_t)(r->d[7] ^ mask) + (SECP256K1_N_7 & mask);
260 r->d[7] = t & nonzero;
261 return 2 * (mask == 0) - 1;
262 }
263
264
265 /* Inspired by the macros in OpenSSL's crypto/bn/asm/x86_64-gcc.c. */
266
267 /** Add a*b to the number defined by (c0,c1,c2). c2 must never overflow. */
268 #define muladd(a,b) { \
269 uint32_t tl, th; \
270 { \
271 uint64_t t = (uint64_t)a * b; \
272 th = t >> 32; /* at most 0xFFFFFFFE */ \
273 tl = t; \
274 } \
275 c0 += tl; /* overflow is handled on the next line */ \
276 th += (c0 < tl); /* at most 0xFFFFFFFF */ \
277 c1 += th; /* overflow is handled on the next line */ \
278 c2 += (c1 < th); /* never overflows by contract (verified in the next line) */ \
279 VERIFY_CHECK((c1 >= th) || (c2 != 0)); \
280 }
281
282 /** Add a*b to the number defined by (c0,c1). c1 must never overflow. */
283 #define muladd_fast(a,b) { \
284 uint32_t tl, th; \
285 { \
286 uint64_t t = (uint64_t)a * b; \
287 th = t >> 32; /* at most 0xFFFFFFFE */ \
288 tl = t; \
289 } \
290 c0 += tl; /* overflow is handled on the next line */ \
291 th += (c0 < tl); /* at most 0xFFFFFFFF */ \
292 c1 += th; /* never overflows by contract (verified in the next line) */ \
293 VERIFY_CHECK(c1 >= th); \
294 }
295
296 /** Add a to the number defined by (c0,c1,c2). c2 must never overflow. */
297 #define sumadd(a) { \
298 unsigned int over; \
299 c0 += (a); /* overflow is handled on the next line */ \
300 over = (c0 < (a)); \
301 c1 += over; /* overflow is handled on the next line */ \
302 c2 += (c1 < over); /* never overflows by contract */ \
303 }
304
305 /** Add a to the number defined by (c0,c1). c1 must never overflow, c2 must be zero. */
306 #define sumadd_fast(a) { \
307 c0 += (a); /* overflow is handled on the next line */ \
308 c1 += (c0 < (a)); /* never overflows by contract (verified the next line) */ \
309 VERIFY_CHECK((c1 != 0) | (c0 >= (a))); \
310 VERIFY_CHECK(c2 == 0); \
311 }
312
313 /** Extract the lowest 32 bits of (c0,c1,c2) into n, and left shift the number 32 bits. */
314 #define extract(n) { \
315 (n) = c0; \
316 c0 = c1; \
317 c1 = c2; \
318 c2 = 0; \
319 }
320
321 /** Extract the lowest 32 bits of (c0,c1,c2) into n, and left shift the number 32 bits. c2 is required to be zero. */
322 #define extract_fast(n) { \
323 (n) = c0; \
324 c0 = c1; \
325 c1 = 0; \
326 VERIFY_CHECK(c2 == 0); \
327 }
328
secp256k1_scalar_reduce_512(secp256k1_scalar * r,const uint32_t * l)329 static void secp256k1_scalar_reduce_512(secp256k1_scalar *r, const uint32_t *l) {
330 uint64_t c;
331 uint32_t n0 = l[8], n1 = l[9], n2 = l[10], n3 = l[11], n4 = l[12], n5 = l[13], n6 = l[14], n7 = l[15];
332 uint32_t m0, m1, m2, m3, m4, m5, m6, m7, m8, m9, m10, m11, m12;
333 uint32_t p0, p1, p2, p3, p4, p5, p6, p7, p8;
334
335 /* 96 bit accumulator. */
336 uint32_t c0, c1, c2;
337
338 /* Reduce 512 bits into 385. */
339 /* m[0..12] = l[0..7] + n[0..7] * SECP256K1_N_C. */
340 c0 = l[0]; c1 = 0; c2 = 0;
341 muladd_fast(n0, SECP256K1_N_C_0);
342 extract_fast(m0);
343 sumadd_fast(l[1]);
344 muladd(n1, SECP256K1_N_C_0);
345 muladd(n0, SECP256K1_N_C_1);
346 extract(m1);
347 sumadd(l[2]);
348 muladd(n2, SECP256K1_N_C_0);
349 muladd(n1, SECP256K1_N_C_1);
350 muladd(n0, SECP256K1_N_C_2);
351 extract(m2);
352 sumadd(l[3]);
353 muladd(n3, SECP256K1_N_C_0);
354 muladd(n2, SECP256K1_N_C_1);
355 muladd(n1, SECP256K1_N_C_2);
356 muladd(n0, SECP256K1_N_C_3);
357 extract(m3);
358 sumadd(l[4]);
359 muladd(n4, SECP256K1_N_C_0);
360 muladd(n3, SECP256K1_N_C_1);
361 muladd(n2, SECP256K1_N_C_2);
362 muladd(n1, SECP256K1_N_C_3);
363 sumadd(n0);
364 extract(m4);
365 sumadd(l[5]);
366 muladd(n5, SECP256K1_N_C_0);
367 muladd(n4, SECP256K1_N_C_1);
368 muladd(n3, SECP256K1_N_C_2);
369 muladd(n2, SECP256K1_N_C_3);
370 sumadd(n1);
371 extract(m5);
372 sumadd(l[6]);
373 muladd(n6, SECP256K1_N_C_0);
374 muladd(n5, SECP256K1_N_C_1);
375 muladd(n4, SECP256K1_N_C_2);
376 muladd(n3, SECP256K1_N_C_3);
377 sumadd(n2);
378 extract(m6);
379 sumadd(l[7]);
380 muladd(n7, SECP256K1_N_C_0);
381 muladd(n6, SECP256K1_N_C_1);
382 muladd(n5, SECP256K1_N_C_2);
383 muladd(n4, SECP256K1_N_C_3);
384 sumadd(n3);
385 extract(m7);
386 muladd(n7, SECP256K1_N_C_1);
387 muladd(n6, SECP256K1_N_C_2);
388 muladd(n5, SECP256K1_N_C_3);
389 sumadd(n4);
390 extract(m8);
391 muladd(n7, SECP256K1_N_C_2);
392 muladd(n6, SECP256K1_N_C_3);
393 sumadd(n5);
394 extract(m9);
395 muladd(n7, SECP256K1_N_C_3);
396 sumadd(n6);
397 extract(m10);
398 sumadd_fast(n7);
399 extract_fast(m11);
400 VERIFY_CHECK(c0 <= 1);
401 m12 = c0;
402
403 /* Reduce 385 bits into 258. */
404 /* p[0..8] = m[0..7] + m[8..12] * SECP256K1_N_C. */
405 c0 = m0; c1 = 0; c2 = 0;
406 muladd_fast(m8, SECP256K1_N_C_0);
407 extract_fast(p0);
408 sumadd_fast(m1);
409 muladd(m9, SECP256K1_N_C_0);
410 muladd(m8, SECP256K1_N_C_1);
411 extract(p1);
412 sumadd(m2);
413 muladd(m10, SECP256K1_N_C_0);
414 muladd(m9, SECP256K1_N_C_1);
415 muladd(m8, SECP256K1_N_C_2);
416 extract(p2);
417 sumadd(m3);
418 muladd(m11, SECP256K1_N_C_0);
419 muladd(m10, SECP256K1_N_C_1);
420 muladd(m9, SECP256K1_N_C_2);
421 muladd(m8, SECP256K1_N_C_3);
422 extract(p3);
423 sumadd(m4);
424 muladd(m12, SECP256K1_N_C_0);
425 muladd(m11, SECP256K1_N_C_1);
426 muladd(m10, SECP256K1_N_C_2);
427 muladd(m9, SECP256K1_N_C_3);
428 sumadd(m8);
429 extract(p4);
430 sumadd(m5);
431 muladd(m12, SECP256K1_N_C_1);
432 muladd(m11, SECP256K1_N_C_2);
433 muladd(m10, SECP256K1_N_C_3);
434 sumadd(m9);
435 extract(p5);
436 sumadd(m6);
437 muladd(m12, SECP256K1_N_C_2);
438 muladd(m11, SECP256K1_N_C_3);
439 sumadd(m10);
440 extract(p6);
441 sumadd_fast(m7);
442 muladd_fast(m12, SECP256K1_N_C_3);
443 sumadd_fast(m11);
444 extract_fast(p7);
445 p8 = c0 + m12;
446 VERIFY_CHECK(p8 <= 2);
447
448 /* Reduce 258 bits into 256. */
449 /* r[0..7] = p[0..7] + p[8] * SECP256K1_N_C. */
450 c = p0 + (uint64_t)SECP256K1_N_C_0 * p8;
451 r->d[0] = c & 0xFFFFFFFFUL; c >>= 32;
452 c += p1 + (uint64_t)SECP256K1_N_C_1 * p8;
453 r->d[1] = c & 0xFFFFFFFFUL; c >>= 32;
454 c += p2 + (uint64_t)SECP256K1_N_C_2 * p8;
455 r->d[2] = c & 0xFFFFFFFFUL; c >>= 32;
456 c += p3 + (uint64_t)SECP256K1_N_C_3 * p8;
457 r->d[3] = c & 0xFFFFFFFFUL; c >>= 32;
458 c += p4 + (uint64_t)p8;
459 r->d[4] = c & 0xFFFFFFFFUL; c >>= 32;
460 c += p5;
461 r->d[5] = c & 0xFFFFFFFFUL; c >>= 32;
462 c += p6;
463 r->d[6] = c & 0xFFFFFFFFUL; c >>= 32;
464 c += p7;
465 r->d[7] = c & 0xFFFFFFFFUL; c >>= 32;
466
467 /* Final reduction of r. */
468 secp256k1_scalar_reduce(r, c + secp256k1_scalar_check_overflow(r));
469 }
470
secp256k1_scalar_mul_512(uint32_t * l,const secp256k1_scalar * a,const secp256k1_scalar * b)471 static void secp256k1_scalar_mul_512(uint32_t *l, const secp256k1_scalar *a, const secp256k1_scalar *b) {
472 /* 96 bit accumulator. */
473 uint32_t c0 = 0, c1 = 0, c2 = 0;
474
475 /* l[0..15] = a[0..7] * b[0..7]. */
476 muladd_fast(a->d[0], b->d[0]);
477 extract_fast(l[0]);
478 muladd(a->d[0], b->d[1]);
479 muladd(a->d[1], b->d[0]);
480 extract(l[1]);
481 muladd(a->d[0], b->d[2]);
482 muladd(a->d[1], b->d[1]);
483 muladd(a->d[2], b->d[0]);
484 extract(l[2]);
485 muladd(a->d[0], b->d[3]);
486 muladd(a->d[1], b->d[2]);
487 muladd(a->d[2], b->d[1]);
488 muladd(a->d[3], b->d[0]);
489 extract(l[3]);
490 muladd(a->d[0], b->d[4]);
491 muladd(a->d[1], b->d[3]);
492 muladd(a->d[2], b->d[2]);
493 muladd(a->d[3], b->d[1]);
494 muladd(a->d[4], b->d[0]);
495 extract(l[4]);
496 muladd(a->d[0], b->d[5]);
497 muladd(a->d[1], b->d[4]);
498 muladd(a->d[2], b->d[3]);
499 muladd(a->d[3], b->d[2]);
500 muladd(a->d[4], b->d[1]);
501 muladd(a->d[5], b->d[0]);
502 extract(l[5]);
503 muladd(a->d[0], b->d[6]);
504 muladd(a->d[1], b->d[5]);
505 muladd(a->d[2], b->d[4]);
506 muladd(a->d[3], b->d[3]);
507 muladd(a->d[4], b->d[2]);
508 muladd(a->d[5], b->d[1]);
509 muladd(a->d[6], b->d[0]);
510 extract(l[6]);
511 muladd(a->d[0], b->d[7]);
512 muladd(a->d[1], b->d[6]);
513 muladd(a->d[2], b->d[5]);
514 muladd(a->d[3], b->d[4]);
515 muladd(a->d[4], b->d[3]);
516 muladd(a->d[5], b->d[2]);
517 muladd(a->d[6], b->d[1]);
518 muladd(a->d[7], b->d[0]);
519 extract(l[7]);
520 muladd(a->d[1], b->d[7]);
521 muladd(a->d[2], b->d[6]);
522 muladd(a->d[3], b->d[5]);
523 muladd(a->d[4], b->d[4]);
524 muladd(a->d[5], b->d[3]);
525 muladd(a->d[6], b->d[2]);
526 muladd(a->d[7], b->d[1]);
527 extract(l[8]);
528 muladd(a->d[2], b->d[7]);
529 muladd(a->d[3], b->d[6]);
530 muladd(a->d[4], b->d[5]);
531 muladd(a->d[5], b->d[4]);
532 muladd(a->d[6], b->d[3]);
533 muladd(a->d[7], b->d[2]);
534 extract(l[9]);
535 muladd(a->d[3], b->d[7]);
536 muladd(a->d[4], b->d[6]);
537 muladd(a->d[5], b->d[5]);
538 muladd(a->d[6], b->d[4]);
539 muladd(a->d[7], b->d[3]);
540 extract(l[10]);
541 muladd(a->d[4], b->d[7]);
542 muladd(a->d[5], b->d[6]);
543 muladd(a->d[6], b->d[5]);
544 muladd(a->d[7], b->d[4]);
545 extract(l[11]);
546 muladd(a->d[5], b->d[7]);
547 muladd(a->d[6], b->d[6]);
548 muladd(a->d[7], b->d[5]);
549 extract(l[12]);
550 muladd(a->d[6], b->d[7]);
551 muladd(a->d[7], b->d[6]);
552 extract(l[13]);
553 muladd_fast(a->d[7], b->d[7]);
554 extract_fast(l[14]);
555 VERIFY_CHECK(c1 == 0);
556 l[15] = c0;
557 }
558
559 #undef sumadd
560 #undef sumadd_fast
561 #undef muladd
562 #undef muladd_fast
563 #undef extract
564 #undef extract_fast
565
secp256k1_scalar_mul(secp256k1_scalar * r,const secp256k1_scalar * a,const secp256k1_scalar * b)566 static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b) {
567 uint32_t l[16];
568 secp256k1_scalar_mul_512(l, a, b);
569 secp256k1_scalar_reduce_512(r, l);
570 }
571
secp256k1_scalar_shr_int(secp256k1_scalar * r,int n)572 static int secp256k1_scalar_shr_int(secp256k1_scalar *r, int n) {
573 int ret;
574 VERIFY_CHECK(n > 0);
575 VERIFY_CHECK(n < 16);
576 ret = r->d[0] & ((1 << n) - 1);
577 r->d[0] = (r->d[0] >> n) + (r->d[1] << (32 - n));
578 r->d[1] = (r->d[1] >> n) + (r->d[2] << (32 - n));
579 r->d[2] = (r->d[2] >> n) + (r->d[3] << (32 - n));
580 r->d[3] = (r->d[3] >> n) + (r->d[4] << (32 - n));
581 r->d[4] = (r->d[4] >> n) + (r->d[5] << (32 - n));
582 r->d[5] = (r->d[5] >> n) + (r->d[6] << (32 - n));
583 r->d[6] = (r->d[6] >> n) + (r->d[7] << (32 - n));
584 r->d[7] = (r->d[7] >> n);
585 return ret;
586 }
587
secp256k1_scalar_split_128(secp256k1_scalar * r1,secp256k1_scalar * r2,const secp256k1_scalar * k)588 static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *k) {
589 r1->d[0] = k->d[0];
590 r1->d[1] = k->d[1];
591 r1->d[2] = k->d[2];
592 r1->d[3] = k->d[3];
593 r1->d[4] = 0;
594 r1->d[5] = 0;
595 r1->d[6] = 0;
596 r1->d[7] = 0;
597 r2->d[0] = k->d[4];
598 r2->d[1] = k->d[5];
599 r2->d[2] = k->d[6];
600 r2->d[3] = k->d[7];
601 r2->d[4] = 0;
602 r2->d[5] = 0;
603 r2->d[6] = 0;
604 r2->d[7] = 0;
605 }
606
secp256k1_scalar_eq(const secp256k1_scalar * a,const secp256k1_scalar * b)607 SECP256K1_INLINE static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar *b) {
608 return ((a->d[0] ^ b->d[0]) | (a->d[1] ^ b->d[1]) | (a->d[2] ^ b->d[2]) | (a->d[3] ^ b->d[3]) | (a->d[4] ^ b->d[4]) | (a->d[5] ^ b->d[5]) | (a->d[6] ^ b->d[6]) | (a->d[7] ^ b->d[7])) == 0;
609 }
610
secp256k1_scalar_mul_shift_var(secp256k1_scalar * r,const secp256k1_scalar * a,const secp256k1_scalar * b,unsigned int shift)611 SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b, unsigned int shift) {
612 uint32_t l[16];
613 unsigned int shiftlimbs;
614 unsigned int shiftlow;
615 unsigned int shifthigh;
616 VERIFY_CHECK(shift >= 256);
617 secp256k1_scalar_mul_512(l, a, b);
618 shiftlimbs = shift >> 5;
619 shiftlow = shift & 0x1F;
620 shifthigh = 32 - shiftlow;
621 r->d[0] = shift < 512 ? (l[0 + shiftlimbs] >> shiftlow | (shift < 480 && shiftlow ? (l[1 + shiftlimbs] << shifthigh) : 0)) : 0;
622 r->d[1] = shift < 480 ? (l[1 + shiftlimbs] >> shiftlow | (shift < 448 && shiftlow ? (l[2 + shiftlimbs] << shifthigh) : 0)) : 0;
623 r->d[2] = shift < 448 ? (l[2 + shiftlimbs] >> shiftlow | (shift < 416 && shiftlow ? (l[3 + shiftlimbs] << shifthigh) : 0)) : 0;
624 r->d[3] = shift < 416 ? (l[3 + shiftlimbs] >> shiftlow | (shift < 384 && shiftlow ? (l[4 + shiftlimbs] << shifthigh) : 0)) : 0;
625 r->d[4] = shift < 384 ? (l[4 + shiftlimbs] >> shiftlow | (shift < 352 && shiftlow ? (l[5 + shiftlimbs] << shifthigh) : 0)) : 0;
626 r->d[5] = shift < 352 ? (l[5 + shiftlimbs] >> shiftlow | (shift < 320 && shiftlow ? (l[6 + shiftlimbs] << shifthigh) : 0)) : 0;
627 r->d[6] = shift < 320 ? (l[6 + shiftlimbs] >> shiftlow | (shift < 288 && shiftlow ? (l[7 + shiftlimbs] << shifthigh) : 0)) : 0;
628 r->d[7] = shift < 288 ? (l[7 + shiftlimbs] >> shiftlow) : 0;
629 secp256k1_scalar_cadd_bit(r, 0, (l[(shift - 1) >> 5] >> ((shift - 1) & 0x1f)) & 1);
630 }
631
secp256k1_scalar_cmov(secp256k1_scalar * r,const secp256k1_scalar * a,int flag)632 static SECP256K1_INLINE void secp256k1_scalar_cmov(secp256k1_scalar *r, const secp256k1_scalar *a, int flag) {
633 uint32_t mask0, mask1;
634 VG_CHECK_VERIFY(r->d, sizeof(r->d));
635 mask0 = flag + ~((uint32_t)0);
636 mask1 = ~mask0;
637 r->d[0] = (r->d[0] & mask0) | (a->d[0] & mask1);
638 r->d[1] = (r->d[1] & mask0) | (a->d[1] & mask1);
639 r->d[2] = (r->d[2] & mask0) | (a->d[2] & mask1);
640 r->d[3] = (r->d[3] & mask0) | (a->d[3] & mask1);
641 r->d[4] = (r->d[4] & mask0) | (a->d[4] & mask1);
642 r->d[5] = (r->d[5] & mask0) | (a->d[5] & mask1);
643 r->d[6] = (r->d[6] & mask0) | (a->d[6] & mask1);
644 r->d[7] = (r->d[7] & mask0) | (a->d[7] & mask1);
645 }
646
secp256k1_scalar_from_signed30(secp256k1_scalar * r,const secp256k1_modinv32_signed30 * a)647 static void secp256k1_scalar_from_signed30(secp256k1_scalar *r, const secp256k1_modinv32_signed30 *a) {
648 const uint32_t a0 = a->v[0], a1 = a->v[1], a2 = a->v[2], a3 = a->v[3], a4 = a->v[4],
649 a5 = a->v[5], a6 = a->v[6], a7 = a->v[7], a8 = a->v[8];
650
651 /* The output from secp256k1_modinv32{_var} should be normalized to range [0,modulus), and
652 * have limbs in [0,2^30). The modulus is < 2^256, so the top limb must be below 2^(256-30*8).
653 */
654 VERIFY_CHECK(a0 >> 30 == 0);
655 VERIFY_CHECK(a1 >> 30 == 0);
656 VERIFY_CHECK(a2 >> 30 == 0);
657 VERIFY_CHECK(a3 >> 30 == 0);
658 VERIFY_CHECK(a4 >> 30 == 0);
659 VERIFY_CHECK(a5 >> 30 == 0);
660 VERIFY_CHECK(a6 >> 30 == 0);
661 VERIFY_CHECK(a7 >> 30 == 0);
662 VERIFY_CHECK(a8 >> 16 == 0);
663
664 r->d[0] = a0 | a1 << 30;
665 r->d[1] = a1 >> 2 | a2 << 28;
666 r->d[2] = a2 >> 4 | a3 << 26;
667 r->d[3] = a3 >> 6 | a4 << 24;
668 r->d[4] = a4 >> 8 | a5 << 22;
669 r->d[5] = a5 >> 10 | a6 << 20;
670 r->d[6] = a6 >> 12 | a7 << 18;
671 r->d[7] = a7 >> 14 | a8 << 16;
672
673 #ifdef VERIFY
674 VERIFY_CHECK(secp256k1_scalar_check_overflow(r) == 0);
675 #endif
676 }
677
secp256k1_scalar_to_signed30(secp256k1_modinv32_signed30 * r,const secp256k1_scalar * a)678 static void secp256k1_scalar_to_signed30(secp256k1_modinv32_signed30 *r, const secp256k1_scalar *a) {
679 const uint32_t M30 = UINT32_MAX >> 2;
680 const uint32_t a0 = a->d[0], a1 = a->d[1], a2 = a->d[2], a3 = a->d[3],
681 a4 = a->d[4], a5 = a->d[5], a6 = a->d[6], a7 = a->d[7];
682
683 #ifdef VERIFY
684 VERIFY_CHECK(secp256k1_scalar_check_overflow(a) == 0);
685 #endif
686
687 r->v[0] = a0 & M30;
688 r->v[1] = (a0 >> 30 | a1 << 2) & M30;
689 r->v[2] = (a1 >> 28 | a2 << 4) & M30;
690 r->v[3] = (a2 >> 26 | a3 << 6) & M30;
691 r->v[4] = (a3 >> 24 | a4 << 8) & M30;
692 r->v[5] = (a4 >> 22 | a5 << 10) & M30;
693 r->v[6] = (a5 >> 20 | a6 << 12) & M30;
694 r->v[7] = (a6 >> 18 | a7 << 14) & M30;
695 r->v[8] = a7 >> 16;
696 }
697
698 static const secp256k1_modinv32_modinfo secp256k1_const_modinfo_scalar = {
699 {{0x10364141L, 0x3F497A33L, 0x348A03BBL, 0x2BB739ABL, -0x146L, 0, 0, 0, 65536}},
700 0x2A774EC1L
701 };
702
secp256k1_scalar_inverse(secp256k1_scalar * r,const secp256k1_scalar * x)703 static void secp256k1_scalar_inverse(secp256k1_scalar *r, const secp256k1_scalar *x) {
704 secp256k1_modinv32_signed30 s;
705 #ifdef VERIFY
706 int zero_in = secp256k1_scalar_is_zero(x);
707 #endif
708 secp256k1_scalar_to_signed30(&s, x);
709 secp256k1_modinv32(&s, &secp256k1_const_modinfo_scalar);
710 secp256k1_scalar_from_signed30(r, &s);
711
712 #ifdef VERIFY
713 VERIFY_CHECK(secp256k1_scalar_is_zero(r) == zero_in);
714 #endif
715 }
716
secp256k1_scalar_inverse_var(secp256k1_scalar * r,const secp256k1_scalar * x)717 static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *x) {
718 secp256k1_modinv32_signed30 s;
719 #ifdef VERIFY
720 int zero_in = secp256k1_scalar_is_zero(x);
721 #endif
722 secp256k1_scalar_to_signed30(&s, x);
723 secp256k1_modinv32_var(&s, &secp256k1_const_modinfo_scalar);
724 secp256k1_scalar_from_signed30(r, &s);
725
726 #ifdef VERIFY
727 VERIFY_CHECK(secp256k1_scalar_is_zero(r) == zero_in);
728 #endif
729 }
730
secp256k1_scalar_is_even(const secp256k1_scalar * a)731 SECP256K1_INLINE static int secp256k1_scalar_is_even(const secp256k1_scalar *a) {
732 return !(a->d[0] & 1);
733 }
734
735 #endif /* SECP256K1_SCALAR_REPR_IMPL_H */
736