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