main_impl.h (29495B)
1 /*********************************************************************** 2 * Distributed under the MIT software license, see the accompanying * 3 * file COPYING or https://www.opensource.org/licenses/mit-license.php.* 4 ***********************************************************************/ 5 6 #ifndef SECP256K1_MODULE_ELLSWIFT_MAIN_H 7 #define SECP256K1_MODULE_ELLSWIFT_MAIN_H 8 9 #include "../../../include/secp256k1.h" 10 #include "../../../include/secp256k1_ellswift.h" 11 #include "../../eckey.h" 12 #include "../../hash.h" 13 14 /** c1 = (sqrt(-3)-1)/2 */ 15 static const haskellsecp256k1_v0_1_0_fe haskellsecp256k1_v0_1_0_ellswift_c1 = SECP256K1_FE_CONST(0x851695d4, 0x9a83f8ef, 0x919bb861, 0x53cbcb16, 0x630fb68a, 0xed0a766a, 0x3ec693d6, 0x8e6afa40); 16 /** c2 = (-sqrt(-3)-1)/2 = -(c1+1) */ 17 static const haskellsecp256k1_v0_1_0_fe haskellsecp256k1_v0_1_0_ellswift_c2 = SECP256K1_FE_CONST(0x7ae96a2b, 0x657c0710, 0x6e64479e, 0xac3434e9, 0x9cf04975, 0x12f58995, 0xc1396c28, 0x719501ee); 18 /** c3 = (-sqrt(-3)+1)/2 = -c1 = c2+1 */ 19 static const haskellsecp256k1_v0_1_0_fe haskellsecp256k1_v0_1_0_ellswift_c3 = SECP256K1_FE_CONST(0x7ae96a2b, 0x657c0710, 0x6e64479e, 0xac3434e9, 0x9cf04975, 0x12f58995, 0xc1396c28, 0x719501ef); 20 /** c4 = (sqrt(-3)+1)/2 = -c2 = c1+1 */ 21 static const haskellsecp256k1_v0_1_0_fe haskellsecp256k1_v0_1_0_ellswift_c4 = SECP256K1_FE_CONST(0x851695d4, 0x9a83f8ef, 0x919bb861, 0x53cbcb16, 0x630fb68a, 0xed0a766a, 0x3ec693d6, 0x8e6afa41); 22 23 /** Decode ElligatorSwift encoding (u, t) to a fraction xn/xd representing a curve X coordinate. */ 24 static void haskellsecp256k1_v0_1_0_ellswift_xswiftec_frac_var(haskellsecp256k1_v0_1_0_fe *xn, haskellsecp256k1_v0_1_0_fe *xd, const haskellsecp256k1_v0_1_0_fe *u, const haskellsecp256k1_v0_1_0_fe *t) { 25 /* The implemented algorithm is the following (all operations in GF(p)): 26 * 27 * - Let c0 = sqrt(-3) = 0xa2d2ba93507f1df233770c2a797962cc61f6d15da14ecd47d8d27ae1cd5f852. 28 * - If u = 0, set u = 1. 29 * - If t = 0, set t = 1. 30 * - If u^3+7+t^2 = 0, set t = 2*t. 31 * - Let X = (u^3+7-t^2)/(2*t). 32 * - Let Y = (X+t)/(c0*u). 33 * - If x3 = u+4*Y^2 is a valid x coordinate, return it. 34 * - If x2 = (-X/Y-u)/2 is a valid x coordinate, return it. 35 * - Return x1 = (X/Y-u)/2 (which is now guaranteed to be a valid x coordinate). 36 * 37 * Introducing s=t^2, g=u^3+7, and simplifying x1=-(x2+u) we get: 38 * 39 * - Let c0 = ... 40 * - If u = 0, set u = 1. 41 * - If t = 0, set t = 1. 42 * - Let s = t^2 43 * - Let g = u^3+7 44 * - If g+s = 0, set t = 2*t, s = 4*s 45 * - Let X = (g-s)/(2*t). 46 * - Let Y = (X+t)/(c0*u) = (g+s)/(2*c0*t*u). 47 * - If x3 = u+4*Y^2 is a valid x coordinate, return it. 48 * - If x2 = (-X/Y-u)/2 is a valid x coordinate, return it. 49 * - Return x1 = -(x2+u). 50 * 51 * Now substitute Y^2 = -(g+s)^2/(12*s*u^2) and X/Y = c0*u*(g-s)/(g+s). This 52 * means X and Y do not need to be evaluated explicitly anymore. 53 * 54 * - ... 55 * - If g+s = 0, set s = 4*s. 56 * - If x3 = u-(g+s)^2/(3*s*u^2) is a valid x coordinate, return it. 57 * - If x2 = (-c0*u*(g-s)/(g+s)-u)/2 is a valid x coordinate, return it. 58 * - Return x1 = -(x2+u). 59 * 60 * Simplifying x2 using 2 additional constants: 61 * 62 * - Let c1 = (c0-1)/2 = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40. 63 * - Let c2 = (-c0-1)/2 = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee. 64 * - ... 65 * - If x2 = u*(c1*s+c2*g)/(g+s) is a valid x coordinate, return it. 66 * - ... 67 * 68 * Writing x3 as a fraction: 69 * 70 * - ... 71 * - If x3 = (3*s*u^3-(g+s)^2)/(3*s*u^2) ... 72 * - ... 73 74 * Overall, we get: 75 * 76 * - Let c1 = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40. 77 * - Let c2 = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee. 78 * - If u = 0, set u = 1. 79 * - If t = 0, set s = 1, else set s = t^2. 80 * - Let g = u^3+7. 81 * - If g+s = 0, set s = 4*s. 82 * - If x3 = (3*s*u^3-(g+s)^2)/(3*s*u^2) is a valid x coordinate, return it. 83 * - If x2 = u*(c1*s+c2*g)/(g+s) is a valid x coordinate, return it. 84 * - Return x1 = -(x2+u). 85 */ 86 haskellsecp256k1_v0_1_0_fe u1, s, g, p, d, n, l; 87 u1 = *u; 88 if (EXPECT(haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(&u1), 0)) u1 = haskellsecp256k1_v0_1_0_fe_one; 89 haskellsecp256k1_v0_1_0_fe_sqr(&s, t); 90 if (EXPECT(haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(t), 0)) s = haskellsecp256k1_v0_1_0_fe_one; 91 haskellsecp256k1_v0_1_0_fe_sqr(&l, &u1); /* l = u^2 */ 92 haskellsecp256k1_v0_1_0_fe_mul(&g, &l, &u1); /* g = u^3 */ 93 haskellsecp256k1_v0_1_0_fe_add_int(&g, SECP256K1_B); /* g = u^3 + 7 */ 94 p = g; /* p = g */ 95 haskellsecp256k1_v0_1_0_fe_add(&p, &s); /* p = g+s */ 96 if (EXPECT(haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(&p), 0)) { 97 haskellsecp256k1_v0_1_0_fe_mul_int(&s, 4); 98 /* Recompute p = g+s */ 99 p = g; /* p = g */ 100 haskellsecp256k1_v0_1_0_fe_add(&p, &s); /* p = g+s */ 101 } 102 haskellsecp256k1_v0_1_0_fe_mul(&d, &s, &l); /* d = s*u^2 */ 103 haskellsecp256k1_v0_1_0_fe_mul_int(&d, 3); /* d = 3*s*u^2 */ 104 haskellsecp256k1_v0_1_0_fe_sqr(&l, &p); /* l = (g+s)^2 */ 105 haskellsecp256k1_v0_1_0_fe_negate(&l, &l, 1); /* l = -(g+s)^2 */ 106 haskellsecp256k1_v0_1_0_fe_mul(&n, &d, &u1); /* n = 3*s*u^3 */ 107 haskellsecp256k1_v0_1_0_fe_add(&n, &l); /* n = 3*s*u^3-(g+s)^2 */ 108 if (haskellsecp256k1_v0_1_0_ge_x_frac_on_curve_var(&n, &d)) { 109 /* Return x3 = n/d = (3*s*u^3-(g+s)^2)/(3*s*u^2) */ 110 *xn = n; 111 *xd = d; 112 return; 113 } 114 *xd = p; 115 haskellsecp256k1_v0_1_0_fe_mul(&l, &haskellsecp256k1_v0_1_0_ellswift_c1, &s); /* l = c1*s */ 116 haskellsecp256k1_v0_1_0_fe_mul(&n, &haskellsecp256k1_v0_1_0_ellswift_c2, &g); /* n = c2*g */ 117 haskellsecp256k1_v0_1_0_fe_add(&n, &l); /* n = c1*s+c2*g */ 118 haskellsecp256k1_v0_1_0_fe_mul(&n, &n, &u1); /* n = u*(c1*s+c2*g) */ 119 /* Possible optimization: in the invocation below, p^2 = (g+s)^2 is computed, 120 * which we already have computed above. This could be deduplicated. */ 121 if (haskellsecp256k1_v0_1_0_ge_x_frac_on_curve_var(&n, &p)) { 122 /* Return x2 = n/p = u*(c1*s+c2*g)/(g+s) */ 123 *xn = n; 124 return; 125 } 126 haskellsecp256k1_v0_1_0_fe_mul(&l, &p, &u1); /* l = u*(g+s) */ 127 haskellsecp256k1_v0_1_0_fe_add(&n, &l); /* n = u*(c1*s+c2*g)+u*(g+s) */ 128 haskellsecp256k1_v0_1_0_fe_negate(xn, &n, 2); /* n = -u*(c1*s+c2*g)-u*(g+s) */ 129 130 VERIFY_CHECK(haskellsecp256k1_v0_1_0_ge_x_frac_on_curve_var(xn, &p)); 131 /* Return x3 = n/p = -(u*(c1*s+c2*g)/(g+s)+u) */ 132 } 133 134 /** Decode ElligatorSwift encoding (u, t) to X coordinate. */ 135 static void haskellsecp256k1_v0_1_0_ellswift_xswiftec_var(haskellsecp256k1_v0_1_0_fe *x, const haskellsecp256k1_v0_1_0_fe *u, const haskellsecp256k1_v0_1_0_fe *t) { 136 haskellsecp256k1_v0_1_0_fe xn, xd; 137 haskellsecp256k1_v0_1_0_ellswift_xswiftec_frac_var(&xn, &xd, u, t); 138 haskellsecp256k1_v0_1_0_fe_inv_var(&xd, &xd); 139 haskellsecp256k1_v0_1_0_fe_mul(x, &xn, &xd); 140 } 141 142 /** Decode ElligatorSwift encoding (u, t) to point P. */ 143 static void haskellsecp256k1_v0_1_0_ellswift_swiftec_var(haskellsecp256k1_v0_1_0_ge *p, const haskellsecp256k1_v0_1_0_fe *u, const haskellsecp256k1_v0_1_0_fe *t) { 144 haskellsecp256k1_v0_1_0_fe x; 145 haskellsecp256k1_v0_1_0_ellswift_xswiftec_var(&x, u, t); 146 haskellsecp256k1_v0_1_0_ge_set_xo_var(p, &x, haskellsecp256k1_v0_1_0_fe_is_odd(t)); 147 } 148 149 /* Try to complete an ElligatorSwift encoding (u, t) for X coordinate x, given u and x. 150 * 151 * There may be up to 8 distinct t values such that (u, t) decodes back to x, but also 152 * fewer, or none at all. Each such partial inverse can be accessed individually using a 153 * distinct input argument c (in range 0-7), and some or all of these may return failure. 154 * The following guarantees exist: 155 * - Given (x, u), no two distinct c values give the same successful result t. 156 * - Every successful result maps back to x through haskellsecp256k1_v0_1_0_ellswift_xswiftec_var. 157 * - Given (x, u), all t values that map back to x can be reached by combining the 158 * successful results from this function over all c values, with the exception of: 159 * - this function cannot be called with u=0 160 * - no result with t=0 will be returned 161 * - no result for which u^3 + t^2 + 7 = 0 will be returned. 162 * 163 * The rather unusual encoding of bits in c (a large "if" based on the middle bit, and then 164 * using the low and high bits to pick signs of square roots) is to match the paper's 165 * encoding more closely: c=0 through c=3 match branches 1..4 in the paper, while c=4 through 166 * c=7 are copies of those with an additional negation of sqrt(w). 167 */ 168 static int haskellsecp256k1_v0_1_0_ellswift_xswiftec_inv_var(haskellsecp256k1_v0_1_0_fe *t, const haskellsecp256k1_v0_1_0_fe *x_in, const haskellsecp256k1_v0_1_0_fe *u_in, int c) { 169 /* The implemented algorithm is this (all arithmetic, except involving c, is mod p): 170 * 171 * - If (c & 2) = 0: 172 * - If (-x-u) is a valid X coordinate, fail. 173 * - Let s=-(u^3+7)/(u^2+u*x+x^2). 174 * - If s is not square, fail. 175 * - Let v=x. 176 * - If (c & 2) = 2: 177 * - Let s=x-u. 178 * - If s is not square, fail. 179 * - Let r=sqrt(-s*(4*(u^3+7)+3*u^2*s)); fail if it doesn't exist. 180 * - If (c & 1) = 1 and r = 0, fail. 181 * - If s=0, fail. 182 * - Let v=(r/s-u)/2. 183 * - Let w=sqrt(s). 184 * - If (c & 5) = 0: return -w*(c3*u + v). 185 * - If (c & 5) = 1: return w*(c4*u + v). 186 * - If (c & 5) = 4: return w*(c3*u + v). 187 * - If (c & 5) = 5: return -w*(c4*u + v). 188 */ 189 haskellsecp256k1_v0_1_0_fe x = *x_in, u = *u_in, g, v, s, m, r, q; 190 int ret; 191 192 haskellsecp256k1_v0_1_0_fe_normalize_weak(&x); 193 haskellsecp256k1_v0_1_0_fe_normalize_weak(&u); 194 195 VERIFY_CHECK(c >= 0 && c < 8); 196 VERIFY_CHECK(haskellsecp256k1_v0_1_0_ge_x_on_curve_var(&x)); 197 198 if (!(c & 2)) { 199 /* c is in {0, 1, 4, 5}. In this case we look for an inverse under the x1 (if c=0 or 200 * c=4) formula, or x2 (if c=1 or c=5) formula. */ 201 202 /* If -u-x is a valid X coordinate, fail. This would yield an encoding that roundtrips 203 * back under the x3 formula instead (which has priority over x1 and x2, so the decoding 204 * would not match x). */ 205 m = x; /* m = x */ 206 haskellsecp256k1_v0_1_0_fe_add(&m, &u); /* m = u+x */ 207 haskellsecp256k1_v0_1_0_fe_negate(&m, &m, 2); /* m = -u-x */ 208 /* Test if (-u-x) is a valid X coordinate. If so, fail. */ 209 if (haskellsecp256k1_v0_1_0_ge_x_on_curve_var(&m)) return 0; 210 211 /* Let s = -(u^3 + 7)/(u^2 + u*x + x^2) [first part] */ 212 haskellsecp256k1_v0_1_0_fe_sqr(&s, &m); /* s = (u+x)^2 */ 213 haskellsecp256k1_v0_1_0_fe_negate(&s, &s, 1); /* s = -(u+x)^2 */ 214 haskellsecp256k1_v0_1_0_fe_mul(&m, &u, &x); /* m = u*x */ 215 haskellsecp256k1_v0_1_0_fe_add(&s, &m); /* s = -(u^2 + u*x + x^2) */ 216 217 /* Note that at this point, s = 0 is impossible. If it were the case: 218 * s = -(u^2 + u*x + x^2) = 0 219 * => u^2 + u*x + x^2 = 0 220 * => (u + 2*x) * (u^2 + u*x + x^2) = 0 221 * => 2*x^3 + 3*x^2*u + 3*x*u^2 + u^3 = 0 222 * => (x + u)^3 + x^3 = 0 223 * => x^3 = -(x + u)^3 224 * => x^3 + B = (-u - x)^3 + B 225 * 226 * However, we know x^3 + B is square (because x is on the curve) and 227 * that (-u-x)^3 + B is not square (the haskellsecp256k1_v0_1_0_ge_x_on_curve_var(&m) 228 * test above would have failed). This is a contradiction, and thus the 229 * assumption s=0 is false. */ 230 VERIFY_CHECK(!haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(&s)); 231 232 /* If s is not square, fail. We have not fully computed s yet, but s is square iff 233 * -(u^3+7)*(u^2+u*x+x^2) is square (because a/b is square iff a*b is square and b is 234 * nonzero). */ 235 haskellsecp256k1_v0_1_0_fe_sqr(&g, &u); /* g = u^2 */ 236 haskellsecp256k1_v0_1_0_fe_mul(&g, &g, &u); /* g = u^3 */ 237 haskellsecp256k1_v0_1_0_fe_add_int(&g, SECP256K1_B); /* g = u^3+7 */ 238 haskellsecp256k1_v0_1_0_fe_mul(&m, &s, &g); /* m = -(u^3 + 7)*(u^2 + u*x + x^2) */ 239 if (!haskellsecp256k1_v0_1_0_fe_is_square_var(&m)) return 0; 240 241 /* Let s = -(u^3 + 7)/(u^2 + u*x + x^2) [second part] */ 242 haskellsecp256k1_v0_1_0_fe_inv_var(&s, &s); /* s = -1/(u^2 + u*x + x^2) [no div by 0] */ 243 haskellsecp256k1_v0_1_0_fe_mul(&s, &s, &g); /* s = -(u^3 + 7)/(u^2 + u*x + x^2) */ 244 245 /* Let v = x. */ 246 v = x; 247 } else { 248 /* c is in {2, 3, 6, 7}. In this case we look for an inverse under the x3 formula. */ 249 250 /* Let s = x-u. */ 251 haskellsecp256k1_v0_1_0_fe_negate(&m, &u, 1); /* m = -u */ 252 s = m; /* s = -u */ 253 haskellsecp256k1_v0_1_0_fe_add(&s, &x); /* s = x-u */ 254 255 /* If s is not square, fail. */ 256 if (!haskellsecp256k1_v0_1_0_fe_is_square_var(&s)) return 0; 257 258 /* Let r = sqrt(-s*(4*(u^3+7)+3*u^2*s)); fail if it doesn't exist. */ 259 haskellsecp256k1_v0_1_0_fe_sqr(&g, &u); /* g = u^2 */ 260 haskellsecp256k1_v0_1_0_fe_mul(&q, &s, &g); /* q = s*u^2 */ 261 haskellsecp256k1_v0_1_0_fe_mul_int(&q, 3); /* q = 3*s*u^2 */ 262 haskellsecp256k1_v0_1_0_fe_mul(&g, &g, &u); /* g = u^3 */ 263 haskellsecp256k1_v0_1_0_fe_mul_int(&g, 4); /* g = 4*u^3 */ 264 haskellsecp256k1_v0_1_0_fe_add_int(&g, 4 * SECP256K1_B); /* g = 4*(u^3+7) */ 265 haskellsecp256k1_v0_1_0_fe_add(&q, &g); /* q = 4*(u^3+7)+3*s*u^2 */ 266 haskellsecp256k1_v0_1_0_fe_mul(&q, &q, &s); /* q = s*(4*(u^3+7)+3*u^2*s) */ 267 haskellsecp256k1_v0_1_0_fe_negate(&q, &q, 1); /* q = -s*(4*(u^3+7)+3*u^2*s) */ 268 if (!haskellsecp256k1_v0_1_0_fe_is_square_var(&q)) return 0; 269 ret = haskellsecp256k1_v0_1_0_fe_sqrt(&r, &q); /* r = sqrt(-s*(4*(u^3+7)+3*u^2*s)) */ 270 #ifdef VERIFY 271 VERIFY_CHECK(ret); 272 #else 273 (void)ret; 274 #endif 275 276 /* If (c & 1) = 1 and r = 0, fail. */ 277 if (EXPECT((c & 1) && haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(&r), 0)) return 0; 278 279 /* If s = 0, fail. */ 280 if (EXPECT(haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(&s), 0)) return 0; 281 282 /* Let v = (r/s-u)/2. */ 283 haskellsecp256k1_v0_1_0_fe_inv_var(&v, &s); /* v = 1/s [no div by 0] */ 284 haskellsecp256k1_v0_1_0_fe_mul(&v, &v, &r); /* v = r/s */ 285 haskellsecp256k1_v0_1_0_fe_add(&v, &m); /* v = r/s-u */ 286 haskellsecp256k1_v0_1_0_fe_half(&v); /* v = (r/s-u)/2 */ 287 } 288 289 /* Let w = sqrt(s). */ 290 ret = haskellsecp256k1_v0_1_0_fe_sqrt(&m, &s); /* m = sqrt(s) = w */ 291 VERIFY_CHECK(ret); 292 293 /* Return logic. */ 294 if ((c & 5) == 0 || (c & 5) == 5) { 295 haskellsecp256k1_v0_1_0_fe_negate(&m, &m, 1); /* m = -w */ 296 } 297 /* Now m = {-w if c&5=0 or c&5=5; w otherwise}. */ 298 haskellsecp256k1_v0_1_0_fe_mul(&u, &u, c&1 ? &haskellsecp256k1_v0_1_0_ellswift_c4 : &haskellsecp256k1_v0_1_0_ellswift_c3); 299 /* u = {c4 if c&1=1; c3 otherwise}*u */ 300 haskellsecp256k1_v0_1_0_fe_add(&u, &v); /* u = {c4 if c&1=1; c3 otherwise}*u + v */ 301 haskellsecp256k1_v0_1_0_fe_mul(t, &m, &u); 302 return 1; 303 } 304 305 /** Use SHA256 as a PRNG, returning SHA256(hasher || cnt). 306 * 307 * hasher is a SHA256 object to which an incrementing 4-byte counter is written to generate randomness. 308 * Writing 13 bytes (4 bytes for counter, plus 9 bytes for the SHA256 padding) cannot cross a 309 * 64-byte block size boundary (to make sure it only triggers a single SHA256 compression). */ 310 static void haskellsecp256k1_v0_1_0_ellswift_prng(unsigned char* out32, const haskellsecp256k1_v0_1_0_sha256 *hasher, uint32_t cnt) { 311 haskellsecp256k1_v0_1_0_sha256 hash = *hasher; 312 unsigned char buf4[4]; 313 #ifdef VERIFY 314 size_t blocks = hash.bytes >> 6; 315 #endif 316 buf4[0] = cnt; 317 buf4[1] = cnt >> 8; 318 buf4[2] = cnt >> 16; 319 buf4[3] = cnt >> 24; 320 haskellsecp256k1_v0_1_0_sha256_write(&hash, buf4, 4); 321 haskellsecp256k1_v0_1_0_sha256_finalize(&hash, out32); 322 323 /* Writing and finalizing together should trigger exactly one SHA256 compression. */ 324 VERIFY_CHECK(((hash.bytes) >> 6) == (blocks + 1)); 325 } 326 327 /** Find an ElligatorSwift encoding (u, t) for X coordinate x, and random Y coordinate. 328 * 329 * u32 is the 32-byte big endian encoding of u; t is the output field element t that still 330 * needs encoding. 331 * 332 * hasher is a hasher in the haskellsecp256k1_v0_1_0_ellswift_prng sense, with the same restrictions. */ 333 static void haskellsecp256k1_v0_1_0_ellswift_xelligatorswift_var(unsigned char *u32, haskellsecp256k1_v0_1_0_fe *t, const haskellsecp256k1_v0_1_0_fe *x, const haskellsecp256k1_v0_1_0_sha256 *hasher) { 334 /* Pool of 3-bit branch values. */ 335 unsigned char branch_hash[32]; 336 /* Number of 3-bit values in branch_hash left. */ 337 int branches_left = 0; 338 /* Field elements u and branch values are extracted from RNG based on hasher for consecutive 339 * values of cnt. cnt==0 is first used to populate a pool of 64 4-bit branch values. The 64 340 * cnt values that follow are used to generate field elements u. cnt==65 (and multiples 341 * thereof) are used to repopulate the pool and start over, if that were ever necessary. 342 * On average, 4 iterations are needed. */ 343 uint32_t cnt = 0; 344 while (1) { 345 int branch; 346 haskellsecp256k1_v0_1_0_fe u; 347 /* If the pool of branch values is empty, populate it. */ 348 if (branches_left == 0) { 349 haskellsecp256k1_v0_1_0_ellswift_prng(branch_hash, hasher, cnt++); 350 branches_left = 64; 351 } 352 /* Take a 3-bit branch value from the branch pool (top bit is discarded). */ 353 --branches_left; 354 branch = (branch_hash[branches_left >> 1] >> ((branches_left & 1) << 2)) & 7; 355 /* Compute a new u value by hashing. */ 356 haskellsecp256k1_v0_1_0_ellswift_prng(u32, hasher, cnt++); 357 /* overflow is not a problem (we prefer uniform u32 over uniform u). */ 358 haskellsecp256k1_v0_1_0_fe_set_b32_mod(&u, u32); 359 /* Since u is the output of a hash, it should practically never be 0. We could apply the 360 * u=0 to u=1 correction here too to deal with that case still, but it's such a low 361 * probability event that we do not bother. */ 362 VERIFY_CHECK(!haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(&u)); 363 364 /* Find a remainder t, and return it if found. */ 365 if (EXPECT(haskellsecp256k1_v0_1_0_ellswift_xswiftec_inv_var(t, x, &u, branch), 0)) break; 366 } 367 } 368 369 /** Find an ElligatorSwift encoding (u, t) for point P. 370 * 371 * This is similar haskellsecp256k1_v0_1_0_ellswift_xelligatorswift_var, except it takes a full group element p 372 * as input, and returns an encoding that matches the provided Y coordinate rather than a random 373 * one. 374 */ 375 static void haskellsecp256k1_v0_1_0_ellswift_elligatorswift_var(unsigned char *u32, haskellsecp256k1_v0_1_0_fe *t, const haskellsecp256k1_v0_1_0_ge *p, const haskellsecp256k1_v0_1_0_sha256 *hasher) { 376 haskellsecp256k1_v0_1_0_ellswift_xelligatorswift_var(u32, t, &p->x, hasher); 377 haskellsecp256k1_v0_1_0_fe_normalize_var(t); 378 if (haskellsecp256k1_v0_1_0_fe_is_odd(t) != haskellsecp256k1_v0_1_0_fe_is_odd(&p->y)) { 379 haskellsecp256k1_v0_1_0_fe_negate(t, t, 1); 380 haskellsecp256k1_v0_1_0_fe_normalize_var(t); 381 } 382 } 383 384 /** Set hash state to the BIP340 tagged hash midstate for "haskellsecp256k1_v0_1_0_ellswift_encode". */ 385 static void haskellsecp256k1_v0_1_0_ellswift_sha256_init_encode(haskellsecp256k1_v0_1_0_sha256* hash) { 386 haskellsecp256k1_v0_1_0_sha256_initialize(hash); 387 hash->s[0] = 0xd1a6524bul; 388 hash->s[1] = 0x028594b3ul; 389 hash->s[2] = 0x96e42f4eul; 390 hash->s[3] = 0x1037a177ul; 391 hash->s[4] = 0x1b8fcb8bul; 392 hash->s[5] = 0x56023885ul; 393 hash->s[6] = 0x2560ede1ul; 394 hash->s[7] = 0xd626b715ul; 395 396 hash->bytes = 64; 397 } 398 399 int haskellsecp256k1_v0_1_0_ellswift_encode(const haskellsecp256k1_v0_1_0_context *ctx, unsigned char *ell64, const haskellsecp256k1_v0_1_0_pubkey *pubkey, const unsigned char *rnd32) { 400 haskellsecp256k1_v0_1_0_ge p; 401 VERIFY_CHECK(ctx != NULL); 402 ARG_CHECK(ell64 != NULL); 403 ARG_CHECK(pubkey != NULL); 404 ARG_CHECK(rnd32 != NULL); 405 406 if (haskellsecp256k1_v0_1_0_pubkey_load(ctx, &p, pubkey)) { 407 haskellsecp256k1_v0_1_0_fe t; 408 unsigned char p64[64] = {0}; 409 size_t ser_size; 410 int ser_ret; 411 haskellsecp256k1_v0_1_0_sha256 hash; 412 413 /* Set up hasher state; the used RNG is H(pubkey || "\x00"*31 || rnd32 || cnt++), using 414 * BIP340 tagged hash with tag "haskellsecp256k1_v0_1_0_ellswift_encode". */ 415 haskellsecp256k1_v0_1_0_ellswift_sha256_init_encode(&hash); 416 ser_ret = haskellsecp256k1_v0_1_0_eckey_pubkey_serialize(&p, p64, &ser_size, 1); 417 #ifdef VERIFY 418 VERIFY_CHECK(ser_ret && ser_size == 33); 419 #else 420 (void)ser_ret; 421 #endif 422 haskellsecp256k1_v0_1_0_sha256_write(&hash, p64, sizeof(p64)); 423 haskellsecp256k1_v0_1_0_sha256_write(&hash, rnd32, 32); 424 425 /* Compute ElligatorSwift encoding and construct output. */ 426 haskellsecp256k1_v0_1_0_ellswift_elligatorswift_var(ell64, &t, &p, &hash); /* puts u in ell64[0..32] */ 427 haskellsecp256k1_v0_1_0_fe_get_b32(ell64 + 32, &t); /* puts t in ell64[32..64] */ 428 return 1; 429 } 430 /* Only reached in case the provided pubkey is invalid. */ 431 memset(ell64, 0, 64); 432 return 0; 433 } 434 435 /** Set hash state to the BIP340 tagged hash midstate for "haskellsecp256k1_v0_1_0_ellswift_create". */ 436 static void haskellsecp256k1_v0_1_0_ellswift_sha256_init_create(haskellsecp256k1_v0_1_0_sha256* hash) { 437 haskellsecp256k1_v0_1_0_sha256_initialize(hash); 438 hash->s[0] = 0xd29e1bf5ul; 439 hash->s[1] = 0xf7025f42ul; 440 hash->s[2] = 0x9b024773ul; 441 hash->s[3] = 0x094cb7d5ul; 442 hash->s[4] = 0xe59ed789ul; 443 hash->s[5] = 0x03bc9786ul; 444 hash->s[6] = 0x68335b35ul; 445 hash->s[7] = 0x4e363b53ul; 446 447 hash->bytes = 64; 448 } 449 450 int haskellsecp256k1_v0_1_0_ellswift_create(const haskellsecp256k1_v0_1_0_context *ctx, unsigned char *ell64, const unsigned char *seckey32, const unsigned char *auxrnd32) { 451 haskellsecp256k1_v0_1_0_ge p; 452 haskellsecp256k1_v0_1_0_fe t; 453 haskellsecp256k1_v0_1_0_sha256 hash; 454 haskellsecp256k1_v0_1_0_scalar seckey_scalar; 455 int ret; 456 static const unsigned char zero32[32] = {0}; 457 458 /* Sanity check inputs. */ 459 VERIFY_CHECK(ctx != NULL); 460 ARG_CHECK(ell64 != NULL); 461 memset(ell64, 0, 64); 462 ARG_CHECK(haskellsecp256k1_v0_1_0_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx)); 463 ARG_CHECK(seckey32 != NULL); 464 465 /* Compute (affine) public key */ 466 ret = haskellsecp256k1_v0_1_0_ec_pubkey_create_helper(&ctx->ecmult_gen_ctx, &seckey_scalar, &p, seckey32); 467 haskellsecp256k1_v0_1_0_declassify(ctx, &p, sizeof(p)); /* not constant time in produced pubkey */ 468 haskellsecp256k1_v0_1_0_fe_normalize_var(&p.x); 469 haskellsecp256k1_v0_1_0_fe_normalize_var(&p.y); 470 471 /* Set up hasher state. The used RNG is H(privkey || "\x00"*32 [|| auxrnd32] || cnt++), 472 * using BIP340 tagged hash with tag "haskellsecp256k1_v0_1_0_ellswift_create". */ 473 haskellsecp256k1_v0_1_0_ellswift_sha256_init_create(&hash); 474 haskellsecp256k1_v0_1_0_sha256_write(&hash, seckey32, 32); 475 haskellsecp256k1_v0_1_0_sha256_write(&hash, zero32, sizeof(zero32)); 476 haskellsecp256k1_v0_1_0_declassify(ctx, &hash, sizeof(hash)); /* private key is hashed now */ 477 if (auxrnd32) haskellsecp256k1_v0_1_0_sha256_write(&hash, auxrnd32, 32); 478 479 /* Compute ElligatorSwift encoding and construct output. */ 480 haskellsecp256k1_v0_1_0_ellswift_elligatorswift_var(ell64, &t, &p, &hash); /* puts u in ell64[0..32] */ 481 haskellsecp256k1_v0_1_0_fe_get_b32(ell64 + 32, &t); /* puts t in ell64[32..64] */ 482 483 haskellsecp256k1_v0_1_0_memczero(ell64, 64, !ret); 484 haskellsecp256k1_v0_1_0_scalar_clear(&seckey_scalar); 485 486 return ret; 487 } 488 489 int haskellsecp256k1_v0_1_0_ellswift_decode(const haskellsecp256k1_v0_1_0_context *ctx, haskellsecp256k1_v0_1_0_pubkey *pubkey, const unsigned char *ell64) { 490 haskellsecp256k1_v0_1_0_fe u, t; 491 haskellsecp256k1_v0_1_0_ge p; 492 VERIFY_CHECK(ctx != NULL); 493 ARG_CHECK(pubkey != NULL); 494 ARG_CHECK(ell64 != NULL); 495 496 haskellsecp256k1_v0_1_0_fe_set_b32_mod(&u, ell64); 497 haskellsecp256k1_v0_1_0_fe_set_b32_mod(&t, ell64 + 32); 498 haskellsecp256k1_v0_1_0_fe_normalize_var(&t); 499 haskellsecp256k1_v0_1_0_ellswift_swiftec_var(&p, &u, &t); 500 haskellsecp256k1_v0_1_0_pubkey_save(pubkey, &p); 501 return 1; 502 } 503 504 static int ellswift_xdh_hash_function_prefix(unsigned char *output, const unsigned char *x32, const unsigned char *ell_a64, const unsigned char *ell_b64, void *data) { 505 haskellsecp256k1_v0_1_0_sha256 sha; 506 507 haskellsecp256k1_v0_1_0_sha256_initialize(&sha); 508 haskellsecp256k1_v0_1_0_sha256_write(&sha, data, 64); 509 haskellsecp256k1_v0_1_0_sha256_write(&sha, ell_a64, 64); 510 haskellsecp256k1_v0_1_0_sha256_write(&sha, ell_b64, 64); 511 haskellsecp256k1_v0_1_0_sha256_write(&sha, x32, 32); 512 haskellsecp256k1_v0_1_0_sha256_finalize(&sha, output); 513 514 return 1; 515 } 516 517 /** Set hash state to the BIP340 tagged hash midstate for "bip324_ellswift_xonly_ecdh". */ 518 static void haskellsecp256k1_v0_1_0_ellswift_sha256_init_bip324(haskellsecp256k1_v0_1_0_sha256* hash) { 519 haskellsecp256k1_v0_1_0_sha256_initialize(hash); 520 hash->s[0] = 0x8c12d730ul; 521 hash->s[1] = 0x827bd392ul; 522 hash->s[2] = 0x9e4fb2eeul; 523 hash->s[3] = 0x207b373eul; 524 hash->s[4] = 0x2292bd7aul; 525 hash->s[5] = 0xaa5441bcul; 526 hash->s[6] = 0x15c3779ful; 527 hash->s[7] = 0xcfb52549ul; 528 529 hash->bytes = 64; 530 } 531 532 static int ellswift_xdh_hash_function_bip324(unsigned char* output, const unsigned char *x32, const unsigned char *ell_a64, const unsigned char *ell_b64, void *data) { 533 haskellsecp256k1_v0_1_0_sha256 sha; 534 535 (void)data; 536 537 haskellsecp256k1_v0_1_0_ellswift_sha256_init_bip324(&sha); 538 haskellsecp256k1_v0_1_0_sha256_write(&sha, ell_a64, 64); 539 haskellsecp256k1_v0_1_0_sha256_write(&sha, ell_b64, 64); 540 haskellsecp256k1_v0_1_0_sha256_write(&sha, x32, 32); 541 haskellsecp256k1_v0_1_0_sha256_finalize(&sha, output); 542 543 return 1; 544 } 545 546 const haskellsecp256k1_v0_1_0_ellswift_xdh_hash_function haskellsecp256k1_v0_1_0_ellswift_xdh_hash_function_prefix = ellswift_xdh_hash_function_prefix; 547 const haskellsecp256k1_v0_1_0_ellswift_xdh_hash_function haskellsecp256k1_v0_1_0_ellswift_xdh_hash_function_bip324 = ellswift_xdh_hash_function_bip324; 548 549 int haskellsecp256k1_v0_1_0_ellswift_xdh(const haskellsecp256k1_v0_1_0_context *ctx, unsigned char *output, const unsigned char *ell_a64, const unsigned char *ell_b64, const unsigned char *seckey32, int party, haskellsecp256k1_v0_1_0_ellswift_xdh_hash_function hashfp, void *data) { 550 int ret = 0; 551 int overflow; 552 haskellsecp256k1_v0_1_0_scalar s; 553 haskellsecp256k1_v0_1_0_fe xn, xd, px, u, t; 554 unsigned char sx[32]; 555 const unsigned char* theirs64; 556 557 VERIFY_CHECK(ctx != NULL); 558 ARG_CHECK(output != NULL); 559 ARG_CHECK(ell_a64 != NULL); 560 ARG_CHECK(ell_b64 != NULL); 561 ARG_CHECK(seckey32 != NULL); 562 ARG_CHECK(hashfp != NULL); 563 564 /* Load remote public key (as fraction). */ 565 theirs64 = party ? ell_a64 : ell_b64; 566 haskellsecp256k1_v0_1_0_fe_set_b32_mod(&u, theirs64); 567 haskellsecp256k1_v0_1_0_fe_set_b32_mod(&t, theirs64 + 32); 568 haskellsecp256k1_v0_1_0_ellswift_xswiftec_frac_var(&xn, &xd, &u, &t); 569 570 /* Load private key (using one if invalid). */ 571 haskellsecp256k1_v0_1_0_scalar_set_b32(&s, seckey32, &overflow); 572 overflow = haskellsecp256k1_v0_1_0_scalar_is_zero(&s); 573 haskellsecp256k1_v0_1_0_scalar_cmov(&s, &haskellsecp256k1_v0_1_0_scalar_one, overflow); 574 575 /* Compute shared X coordinate. */ 576 haskellsecp256k1_v0_1_0_ecmult_const_xonly(&px, &xn, &xd, &s, 1); 577 haskellsecp256k1_v0_1_0_fe_normalize(&px); 578 haskellsecp256k1_v0_1_0_fe_get_b32(sx, &px); 579 580 /* Invoke hasher */ 581 ret = hashfp(output, sx, ell_a64, ell_b64, data); 582 583 memset(sx, 0, 32); 584 haskellsecp256k1_v0_1_0_fe_clear(&px); 585 haskellsecp256k1_v0_1_0_scalar_clear(&s); 586 587 return !!ret & !overflow; 588 } 589 590 #endif