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