scalar_impl.h (12811B)
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 haskellsecp256k1_v0_1_0_scalar haskellsecp256k1_v0_1_0_scalar_one = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 1); 28 static const haskellsecp256k1_v0_1_0_scalar haskellsecp256k1_v0_1_0_scalar_zero = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 0); 29 30 static int haskellsecp256k1_v0_1_0_scalar_set_b32_seckey(haskellsecp256k1_v0_1_0_scalar *r, const unsigned char *bin) { 31 int overflow; 32 haskellsecp256k1_v0_1_0_scalar_set_b32(r, bin, &overflow); 33 34 SECP256K1_SCALAR_VERIFY(r); 35 return (!overflow) & (!haskellsecp256k1_v0_1_0_scalar_is_zero(r)); 36 } 37 38 static void haskellsecp256k1_v0_1_0_scalar_verify(const haskellsecp256k1_v0_1_0_scalar *r) { 39 VERIFY_CHECK(haskellsecp256k1_v0_1_0_scalar_check_overflow(r) == 0); 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 57 /** 58 * Find r1 and r2 given k, such that r1 + r2 * lambda == k mod n; unlike in the 59 * full case we don't bother making r1 and r2 be small, we just want them to be 60 * nontrivial to get full test coverage for the exhaustive tests. We therefore 61 * (arbitrarily) set r2 = k + 5 (mod n) and r1 = k - r2 * lambda (mod n). 62 */ 63 static void haskellsecp256k1_v0_1_0_scalar_split_lambda(haskellsecp256k1_v0_1_0_scalar * SECP256K1_RESTRICT r1, haskellsecp256k1_v0_1_0_scalar * SECP256K1_RESTRICT r2, const haskellsecp256k1_v0_1_0_scalar * SECP256K1_RESTRICT k) { 64 SECP256K1_SCALAR_VERIFY(k); 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 72 SECP256K1_SCALAR_VERIFY(r1); 73 SECP256K1_SCALAR_VERIFY(r2); 74 } 75 #else 76 /** 77 * The Secp256k1 curve has an endomorphism, where lambda * (x, y) = (beta * x, y), where 78 * lambda is: */ 79 static const haskellsecp256k1_v0_1_0_scalar haskellsecp256k1_v0_1_0_const_lambda = SECP256K1_SCALAR_CONST( 80 0x5363AD4CUL, 0xC05C30E0UL, 0xA5261C02UL, 0x8812645AUL, 81 0x122E22EAUL, 0x20816678UL, 0xDF02967CUL, 0x1B23BD72UL 82 ); 83 84 #ifdef VERIFY 85 static void haskellsecp256k1_v0_1_0_scalar_split_lambda_verify(const haskellsecp256k1_v0_1_0_scalar *r1, const haskellsecp256k1_v0_1_0_scalar *r2, const haskellsecp256k1_v0_1_0_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 */ 138 static void haskellsecp256k1_v0_1_0_scalar_split_lambda(haskellsecp256k1_v0_1_0_scalar * SECP256K1_RESTRICT r1, haskellsecp256k1_v0_1_0_scalar * SECP256K1_RESTRICT r2, const haskellsecp256k1_v0_1_0_scalar * SECP256K1_RESTRICT k) { 139 haskellsecp256k1_v0_1_0_scalar c1, c2; 140 static const haskellsecp256k1_v0_1_0_scalar minus_b1 = SECP256K1_SCALAR_CONST( 141 0x00000000UL, 0x00000000UL, 0x00000000UL, 0x00000000UL, 142 0xE4437ED6UL, 0x010E8828UL, 0x6F547FA9UL, 0x0ABFE4C3UL 143 ); 144 static const haskellsecp256k1_v0_1_0_scalar minus_b2 = SECP256K1_SCALAR_CONST( 145 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL, 146 0x8A280AC5UL, 0x0774346DUL, 0xD765CDA8UL, 0x3DB1562CUL 147 ); 148 static const haskellsecp256k1_v0_1_0_scalar g1 = SECP256K1_SCALAR_CONST( 149 0x3086D221UL, 0xA7D46BCDUL, 0xE86C90E4UL, 0x9284EB15UL, 150 0x3DAA8A14UL, 0x71E8CA7FUL, 0xE893209AUL, 0x45DBB031UL 151 ); 152 static const haskellsecp256k1_v0_1_0_scalar g2 = SECP256K1_SCALAR_CONST( 153 0xE4437ED6UL, 0x010E8828UL, 0x6F547FA9UL, 0x0ABFE4C4UL, 154 0x221208ACUL, 0x9DF506C6UL, 0x1571B4AEUL, 0x8AC47F71UL 155 ); 156 SECP256K1_SCALAR_VERIFY(k); 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 haskellsecp256k1_v0_1_0_scalar_mul_shift_var(&c1, k, &g1, 384); 163 haskellsecp256k1_v0_1_0_scalar_mul_shift_var(&c2, k, &g2, 384); 164 haskellsecp256k1_v0_1_0_scalar_mul(&c1, &c1, &minus_b1); 165 haskellsecp256k1_v0_1_0_scalar_mul(&c2, &c2, &minus_b2); 166 haskellsecp256k1_v0_1_0_scalar_add(r2, &c1, &c2); 167 haskellsecp256k1_v0_1_0_scalar_mul(r1, r2, &haskellsecp256k1_v0_1_0_const_lambda); 168 haskellsecp256k1_v0_1_0_scalar_negate(r1, r1); 169 haskellsecp256k1_v0_1_0_scalar_add(r1, r1, k); 170 171 SECP256K1_SCALAR_VERIFY(r1); 172 SECP256K1_SCALAR_VERIFY(r2); 173 #ifdef VERIFY 174 haskellsecp256k1_v0_1_0_scalar_split_lambda_verify(r1, r2, k); 175 #endif 176 } 177 178 #ifdef VERIFY 179 /* 180 * Proof for haskellsecp256k1_v0_1_0_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 + epsilon1) + 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 + epsilon1) + 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 haskellsecp256k1_v0_1_0_scalar_split_lambda_verify(const haskellsecp256k1_v0_1_0_scalar *r1, const haskellsecp256k1_v0_1_0_scalar *r2, const haskellsecp256k1_v0_1_0_scalar *k) { 284 haskellsecp256k1_v0_1_0_scalar s; 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 300 haskellsecp256k1_v0_1_0_scalar_mul(&s, &haskellsecp256k1_v0_1_0_const_lambda, r2); 301 haskellsecp256k1_v0_1_0_scalar_add(&s, &s, r1); 302 VERIFY_CHECK(haskellsecp256k1_v0_1_0_scalar_eq(&s, k)); 303 304 haskellsecp256k1_v0_1_0_scalar_negate(&s, r1); 305 haskellsecp256k1_v0_1_0_scalar_get_b32(buf1, r1); 306 haskellsecp256k1_v0_1_0_scalar_get_b32(buf2, &s); 307 VERIFY_CHECK(haskellsecp256k1_v0_1_0_memcmp_var(buf1, k1_bound, 32) < 0 || haskellsecp256k1_v0_1_0_memcmp_var(buf2, k1_bound, 32) < 0); 308 309 haskellsecp256k1_v0_1_0_scalar_negate(&s, r2); 310 haskellsecp256k1_v0_1_0_scalar_get_b32(buf1, r2); 311 haskellsecp256k1_v0_1_0_scalar_get_b32(buf2, &s); 312 VERIFY_CHECK(haskellsecp256k1_v0_1_0_memcmp_var(buf1, k2_bound, 32) < 0 || haskellsecp256k1_v0_1_0_memcmp_var(buf2, k2_bound, 32) < 0); 313 } 314 #endif /* VERIFY */ 315 #endif /* !defined(EXHAUSTIVE_TEST_ORDER) */ 316 317 #endif /* SECP256K1_SCALAR_IMPL_H */