| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | /*********************************************************************** | ||
| 2 | * Copyright (c) 2022 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_MODULE_ELLSWIFT_MAIN_H | ||
| 8 | #define SECP256K1_MODULE_ELLSWIFT_MAIN_H | ||
| 9 | |||
| 10 | #include "../../../include/secp256k1.h" | ||
| 11 | #include "../../../include/secp256k1_ellswift.h" | ||
| 12 | #include "../../hash.h" | ||
| 13 | |||
| 14 | /** c1 = (sqrt(-3)-1)/2 */ | ||
| 15 | static const secp256k1_fe secp256k1_ellswift_c1 = SECP256K1_FE_CONST(0x851695d4, 0x9a83f8ef, 0x919bb861, 0x53cbcb16, 0x630fb68a, 0xed0a766a, 0x3ec693d6, 0x8e6afa40); | ||
| 16 | /** c2 = (-sqrt(-3)-1)/2 = -(c1+1) */ | ||
| 17 | static const secp256k1_fe secp256k1_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 secp256k1_fe secp256k1_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 secp256k1_fe secp256k1_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 | 243374 | static void secp256k1_ellswift_xswiftec_frac_var(secp256k1_fe *xn, secp256k1_fe *xd, const secp256k1_fe *u, const secp256k1_fe *t) { | |
| 25 | /* The implemented algorithm is the following (all operations in GF(p)): | ||
| 26 | * | ||
| 27 | * - 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 x3. | ||
| 34 | * - If x2=(-X/Y-u)/2 is a valid x coordinare, return x2. | ||
| 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 | * - ... | ||
| 40 | * - Let s=t^2 | ||
| 41 | * - Let g=u^3+7 | ||
| 42 | * - If g+s=0, set t=2*t, s=4*s | ||
| 43 | * - Let X=(g-s)/(2*t) | ||
| 44 | * - Let Y=(X+t)/(c0*u) = (g+s)/(2*c0*t*u) | ||
| 45 | * - If x3=u+4*Y^2 is a valid x coordinate, return x3. | ||
| 46 | * - If x2=(-X/Y-u)/2 is a valid x coordinate, return it. | ||
| 47 | * - Return x1=-(x2+u). | ||
| 48 | * | ||
| 49 | * Now substitute Y^2 = -(g+s)^2/(12*s*u^2) and X/Y = c0*u*(g-s)/(g+s) | ||
| 50 | * | ||
| 51 | * - ... | ||
| 52 | * - If g+s=0, set s=4*s | ||
| 53 | * - If x3=u-(g+s)^2/(3*s*u^2) is a valid x coordinate, return it. | ||
| 54 | * - If x2=(-c0*u*(g-s)/(g+s)-u)/2 is a valid x coordinate, return it. | ||
| 55 | * - Return x1=(c0*u*(g-s)/(g+s)-u)/2. | ||
| 56 | * | ||
| 57 | * Simplifying x2 using 2 additional constants: | ||
| 58 | * | ||
| 59 | * - c1 = (c0-1)/2 = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40 | ||
| 60 | * - c2 = (-c0-1)/2 = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee | ||
| 61 | * - ... | ||
| 62 | * - If x2=u*(c1*s+c2*g)/(g+s) is a valid x coordinate, return it. | ||
| 63 | * - ... | ||
| 64 | * | ||
| 65 | * Writing x3 as a fraction: | ||
| 66 | * | ||
| 67 | * - ... | ||
| 68 | * - If x3=(3*s*u^3-(g+s)^2)/(3*s*u^2) | ||
| 69 | * - ... | ||
| 70 | |||
| 71 | * Overall, we get: | ||
| 72 | * | ||
| 73 | * - c1 = 0x851695d49a83f8ef919bb86153cbcb16630fb68aed0a766a3ec693d68e6afa40 | ||
| 74 | * - c2 = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee | ||
| 75 | * - If u=0, set u=1. | ||
| 76 | * - If t=0, set s=1, else set s=t^2 | ||
| 77 | * - Let g=u^3+7 | ||
| 78 | * - If g+s=0, set s=4*s | ||
| 79 | * - If x3=(3*s*u^3-(g+s)^2)/(3*s*u^2) is a valid x coordinate, return it. | ||
| 80 | * - If x2=u*(c1*s+c2*g)/(g+s) is a valid x coordinate, return it. | ||
| 81 | * - Return x1=-(x2+u) | ||
| 82 | */ | ||
| 83 | secp256k1_fe u1, s, g, p, d, n, l; | ||
| 84 | 243374 | u1 = *u; | |
| 85 |
2/2✓ Branch 1 taken 36 times.
✓ Branch 2 taken 243338 times.
|
243374 | if (EXPECT(secp256k1_fe_normalizes_to_zero_var(&u1), 0)) u1 = secp256k1_fe_one; |
| 86 | 243374 | secp256k1_fe_sqr(&s, t); | |
| 87 |
2/2✓ Branch 1 taken 30 times.
✓ Branch 2 taken 243344 times.
|
243374 | if (EXPECT(secp256k1_fe_normalizes_to_zero_var(t), 0)) s = secp256k1_fe_one; |
| 88 | 243374 | secp256k1_fe_sqr(&l, &u1); /* l = u^2 */ | |
| 89 | 243374 | secp256k1_fe_mul(&g, &l, &u1); /* g = u^3 */ | |
| 90 | 243374 | secp256k1_fe_add_int(&g, SECP256K1_B); /* g = u^3 + 7 */ | |
| 91 | 243374 | p = g; /* p = g */ | |
| 92 | 243374 | secp256k1_fe_add(&p, &s); /* p = g+s */ | |
| 93 |
2/2✓ Branch 1 taken 14 times.
✓ Branch 2 taken 243360 times.
|
243374 | if (EXPECT(secp256k1_fe_normalizes_to_zero_var(&p), 0)) { |
| 94 | 14 | secp256k1_fe_mul_int(&s, 4); /* s = 4*s */ | |
| 95 | /* recompute p = g+s */ | ||
| 96 | 14 | p = g; /* p = g */ | |
| 97 | 14 | secp256k1_fe_add(&p, &s); /* p = g+s */ | |
| 98 | } | ||
| 99 | 243374 | secp256k1_fe_mul(&d, &s, &l); /* d = s*u^2 */ | |
| 100 | 243374 | secp256k1_fe_mul_int(&d, 3); /* d = 3*s*u^2 */ | |
| 101 | 243374 | secp256k1_fe_sqr(&l, &p); /* l = (g+s)^2 */ | |
| 102 | 243374 | secp256k1_fe_negate(&l, &l, 1); /* l = -(g+s)^2 */ | |
| 103 | 243374 | secp256k1_fe_mul(&n, &d, &u1); /* n = 3*s*u^3 */ | |
| 104 | 243374 | secp256k1_fe_add(&n, &l); /* n = 3*s*u^3-(g+s)^2 */ | |
| 105 |
2/2✓ Branch 1 taken 122141 times.
✓ Branch 2 taken 121233 times.
|
243374 | if (secp256k1_ge_x_frac_on_curve_var(&n, &d)) { |
| 106 | /* Return n/d = (3*s*u^3-(g+s)^2)/(3*s*u^2) */ | ||
| 107 | 122141 | *xn = n; | |
| 108 | 122141 | *xd = d; | |
| 109 | 182935 | return; | |
| 110 | } | ||
| 111 | 121233 | *xd = p; | |
| 112 | 121233 | secp256k1_fe_mul(&l, &secp256k1_ellswift_c1, &s); /* l = c1*s */ | |
| 113 | 121233 | secp256k1_fe_mul(&n, &secp256k1_ellswift_c2, &g); /* n = c2*g */ | |
| 114 | 121233 | secp256k1_fe_add(&n, &l); /* n = c1*s+c2*g */ | |
| 115 | 121233 | secp256k1_fe_mul(&n, &n, &u1); /* n = u*(c1*s+c2*g) */ | |
| 116 | /* Possible optimization: in the invocation below, d^2 = (g+s)^2 is computed, | ||
| 117 | * which we already have computed above. This could be deduplicated. */ | ||
| 118 |
2/2✓ Branch 1 taken 60794 times.
✓ Branch 2 taken 60439 times.
|
121233 | if (secp256k1_ge_x_frac_on_curve_var(&n, &p)) { |
| 119 | /* Return n/p = u*(c1*s+c2*g)/(g+s) */ | ||
| 120 | 60794 | *xn = n; | |
| 121 | 60794 | return; | |
| 122 | } | ||
| 123 | 60439 | secp256k1_fe_mul(&l, &p, &u1); /* l = u*(g+s) */ | |
| 124 | 60439 | secp256k1_fe_add(&n, &l); /* n = u*(c1*s+c2*g)+u*g*s */ | |
| 125 | 60439 | secp256k1_fe_negate(xn, &n, 2); /* n = -u*(c1*s+c2*g)+u*g*s */ | |
| 126 | #ifdef VERIFY | ||
| 127 | VERIFY_CHECK(secp256k1_ge_x_frac_on_curve_var(xn, &p)); | ||
| 128 | #endif | ||
| 129 | /* Return n/p = -(u*(c1*s+c2*g)/(g+s)+u) */ | ||
| 130 | } | ||
| 131 | |||
| 132 | /** Decode ElligatorSwift encoding (u, t) to X coordinate. */ | ||
| 133 | 140974 | static void secp256k1_ellswift_xswiftec_var(secp256k1_fe *x, const secp256k1_fe *u, const secp256k1_fe *t) { | |
| 134 | secp256k1_fe xn, xd; | ||
| 135 | 140974 | secp256k1_ellswift_xswiftec_frac_var(&xn, &xd, u, t); | |
| 136 | 140974 | secp256k1_fe_inv_var(&xd, &xd); | |
| 137 | 140974 | secp256k1_fe_mul(x, &xn, &xd); | |
| 138 | 140974 | } | |
| 139 | |||
| 140 | /** Decode ElligatorSwift encoding (u, t) to point P. */ | ||
| 141 | 140876 | static void secp256k1_ellswift_swiftec_var(secp256k1_ge *p, const secp256k1_fe *u, const secp256k1_fe *t) { | |
| 142 | secp256k1_fe x; | ||
| 143 | 140876 | secp256k1_ellswift_xswiftec_var(&x, u, t); | |
| 144 | 140876 | secp256k1_ge_set_xo_var(p, &x, secp256k1_fe_is_odd(t)); | |
| 145 | 140876 | } | |
| 146 | |||
| 147 | /* Try to complete an ElligatorSwift encoding (u, t) for X coordinate x, given u and x. | ||
| 148 | * | ||
| 149 | * There may be up to 8 distinct t values such that (u, t) decodes back to x, but also | ||
| 150 | * fewer, or none at all. Each such partial inverse can be accessed individually using a | ||
| 151 | * distinct input argument c (in range 0-7), and some or all of these may return failure. | ||
| 152 | * The following guarantees exist: | ||
| 153 | * - Given (x, u), no two distinct c values give the same successful result t. | ||
| 154 | * - Every successful result maps back to x through secp256k1_ellswift_xswiftec_var. | ||
| 155 | * - Given (x, u), all t values that map back to x can be reached by combining the | ||
| 156 | * successful results from this function over all c values, with the exception of: | ||
| 157 | * - this function cannot be called with u=0 | ||
| 158 | * - no result with t=0 will be returned | ||
| 159 | * - no result for which u^3 + t^2 + 7 = 0 will be returned. | ||
| 160 | */ | ||
| 161 | 461012 | static int secp256k1_ellswift_xswiftec_inv_var(secp256k1_fe *t, const secp256k1_fe *x_in, const secp256k1_fe *u_in, int c) { | |
| 162 | /* The implemented algorithm is this (all arithmetic, except involving c, is mod p): | ||
| 163 | * | ||
| 164 | * - If (c & 2) = 0: | ||
| 165 | * - If (-x-u) is a valid X coordinate, fail. | ||
| 166 | * - Let s=-(u^3+7)/(u^2+u*x+x^2). | ||
| 167 | * - If s is not square, fail. | ||
| 168 | * - Let v=x. | ||
| 169 | * - If (c & 2) = 2: | ||
| 170 | * - Let s=x-u. | ||
| 171 | * - If s=0, fail. | ||
| 172 | * - If s is not square, fail. | ||
| 173 | * - Let r=sqrt(-s*(4*(u^3+7)+3*u^2*s)); fail if it doesn't exist. | ||
| 174 | * - If (c & 1) = 1 and r = 0, fail. | ||
| 175 | * - Let v=(r/s-u)/2. | ||
| 176 | * - Let w=sqrt(s). | ||
| 177 | * - If (c & 5) = 0: return -w*(c3*u + v) | ||
| 178 | * - If (c & 5) = 1: return w*(c4*u + v) | ||
| 179 | * - If (c & 5) = 4: return w*(c3*u + v) | ||
| 180 | * - If (c & 5) = 5: return -w*(c4*u + v) | ||
| 181 | */ | ||
| 182 | 461012 | secp256k1_fe x = *x_in, u = *u_in, u2, g, v, s, m, r, q; | |
| 183 | |||
| 184 | /* Normalize. */ | ||
| 185 | 461012 | secp256k1_fe_normalize_weak(&x); | |
| 186 | 461012 | secp256k1_fe_normalize_weak(&u); | |
| 187 | |||
| 188 |
2/2✓ Branch 0 taken 230177 times.
✓ Branch 1 taken 230835 times.
|
461012 | if (!(c & 2)) { |
| 189 | /* If -u-x is a valid X coordinate, fail. */ | ||
| 190 | 230177 | m = x; /* m = x */ | |
| 191 | 230177 | secp256k1_fe_add(&m, &u); /* m = u+x */ | |
| 192 | 230177 | secp256k1_fe_negate(&m, &m, 2); /* m = -u-x */ | |
| 193 |
2/2✓ Branch 1 taken 115058 times.
✓ Branch 2 taken 115119 times.
|
230177 | if (secp256k1_ge_x_on_curve_var(&m)) return 0; /* test if -u-x on curve */ |
| 194 | |||
| 195 | /* Let s = -(u^3 + 7)/(u^2 + u*x + x^2) [first part] */ | ||
| 196 | 115119 | secp256k1_fe_sqr(&s, &m); /* s = (u+x)^2 */ | |
| 197 | 115119 | secp256k1_fe_negate(&s, &s, 1); /* s= -(u+x)^2 */ | |
| 198 | 115119 | secp256k1_fe_mul(&m, &u, &x); /* m = u*x */ | |
| 199 | 115119 | secp256k1_fe_add(&s, &m); /* s = -(u^2 + u*x + x^2) */ | |
| 200 | |||
| 201 | /* If s is not square, fail. We have not fully computed s yet, but s is square iff | ||
| 202 | * -(u^3+7)*(u^2+u*x+x^2) is square. */ | ||
| 203 | 115119 | secp256k1_fe_sqr(&g, &u); /* g = u^2 */ | |
| 204 | 115119 | secp256k1_fe_mul(&g, &g, &u); /* g = u^3 */ | |
| 205 | 115119 | secp256k1_fe_add_int(&g, SECP256K1_B); /* g = u^3+7 */ | |
| 206 | 115119 | secp256k1_fe_mul(&m, &s, &g); /* m = -(u^3 + 7)*(u^2 + u*x + x^2) */ | |
| 207 |
2/2✓ Branch 1 taken 57486 times.
✓ Branch 2 taken 57633 times.
|
115119 | if (!secp256k1_fe_is_square_var(&m)) return 0; |
| 208 | |||
| 209 | /* Let s = -(u^3 + 7)/(u^2 + u*x + x^2) [second part] */ | ||
| 210 | 57633 | secp256k1_fe_inv_var(&s, &s); /* s = -1/(u^2 + u*x + x^2) */ | |
| 211 | 57633 | secp256k1_fe_mul(&s, &s, &g); /* s = -(u^3 + 7)/(u^2 + u*x + x^2) */ | |
| 212 | |||
| 213 | /* Let v = x. */ | ||
| 214 | 57633 | v = x; | |
| 215 | } else { | ||
| 216 | /* Let s = x-u. */ | ||
| 217 | 230835 | secp256k1_fe_negate(&m, &u, 1); /* m = -u */ | |
| 218 | 230835 | s = m; /* s = -u */ | |
| 219 | 230835 | secp256k1_fe_add(&s, &x); /* s = x-u */ | |
| 220 | |||
| 221 | /* If s=0, fail. */ | ||
| 222 |
2/2✓ Branch 1 taken 8 times.
✓ Branch 2 taken 230827 times.
|
230835 | if (secp256k1_fe_normalizes_to_zero_var(&s)) return 0; |
| 223 | |||
| 224 | /* If s is not square, fail. */ | ||
| 225 |
2/2✓ Branch 1 taken 115560 times.
✓ Branch 2 taken 115267 times.
|
230827 | if (!secp256k1_fe_is_square_var(&s)) return 0; |
| 226 | |||
| 227 | /* Let r = sqrt(-s*(4*(u^3+7)+3*u^2*s)); fail if it doesn't exist. */ | ||
| 228 | 115267 | secp256k1_fe_sqr(&u2, &u); /* u2 = u^2 */ | |
| 229 | 115267 | secp256k1_fe_mul(&g, &u2, &u); /* g = u^3 */ | |
| 230 | 115267 | secp256k1_fe_add_int(&g, SECP256K1_B); /* g = u^3+7 */ | |
| 231 | 115267 | secp256k1_fe_normalize_weak(&g); | |
| 232 | 115267 | secp256k1_fe_mul_int(&g, 4); /* g = 4*(u^3+7) */ | |
| 233 | 115267 | secp256k1_fe_mul_int(&u2, 3); /* u2 = 3*u^2 */ | |
| 234 | 115267 | secp256k1_fe_mul(&q, &s, &u2); /* q = 3*s*u^2 */ | |
| 235 | 115267 | secp256k1_fe_add(&q, &g); /* q = 4*(u^3+7)+3*s*u^2 */ | |
| 236 | 115267 | secp256k1_fe_mul(&q, &q, &s); /* q = s*(4*(u^3+7)+3*u^2*s) */ | |
| 237 | 115267 | secp256k1_fe_negate(&q, &q, 1); /* q = -s*(4*(u^3+7)+3*u^2*s) */ | |
| 238 |
2/2✓ Branch 1 taken 57596 times.
✓ Branch 2 taken 57671 times.
|
115267 | if (!secp256k1_fe_is_square_var(&q)) return 0; |
| 239 | 57671 | secp256k1_fe_sqrt(&r, &q); /* r = sqrt(-s*(4*(u^3+7)+3*u^2*s)) */ | |
| 240 | |||
| 241 | /* If (c & 1) = 1 and r = 0, fail. */ | ||
| 242 |
4/4✓ Branch 0 taken 29060 times.
✓ Branch 1 taken 28611 times.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 29054 times.
|
57671 | if ((c & 1) && secp256k1_fe_normalizes_to_zero_var(&r)) return 0; |
| 243 | |||
| 244 | /* Let v=(r/s-u)/2. */ | ||
| 245 | 57665 | secp256k1_fe_inv_var(&v, &s); /* v=1/s */ | |
| 246 | 57665 | secp256k1_fe_mul(&v, &v, &r); /* v=r/s */ | |
| 247 | 57665 | secp256k1_fe_add(&v, &m); /* v=r/s-u */ | |
| 248 | 57665 | secp256k1_fe_half(&v); /* v=(r/s-u)/2 */ | |
| 249 | } | ||
| 250 | |||
| 251 | /* Let w=sqrt(s). */ | ||
| 252 | 115298 | secp256k1_fe_sqrt(&m, &s); /* m = sqrt(s) = w */ | |
| 253 | |||
| 254 | /* Return logic. */ | ||
| 255 |
4/4✓ Branch 0 taken 86715 times.
✓ Branch 1 taken 28583 times.
✓ Branch 2 taken 28824 times.
✓ Branch 3 taken 57891 times.
|
115298 | if ((c & 5) == 0 || (c & 5) == 5) { |
| 256 | 57407 | secp256k1_fe_negate(&m, &m, 1); /* m = -w */ | |
| 257 | } | ||
| 258 | /* Now m = {w if c&5=0 or c&5=5; -w otherwise}. */ | ||
| 259 |
2/2✓ Branch 0 taken 57877 times.
✓ Branch 1 taken 57421 times.
|
115298 | secp256k1_fe_mul(&u, &u, c&1 ? &secp256k1_ellswift_c4 : &secp256k1_ellswift_c3); |
| 260 | /* u = {c4 if c&1=1; c3 otherwise}*u */ | ||
| 261 | 115298 | secp256k1_fe_add(&u, &v); /* u = {c4 if c&1=1; c3 otherwise}*u + v */ | |
| 262 | 115298 | secp256k1_fe_mul(t, &m, &u); | |
| 263 | 115298 | return 1; | |
| 264 | } | ||
| 265 | |||
| 266 | /** Find an ElligatorSwift encoding (u, t) for X coordinate x. | ||
| 267 | * | ||
| 268 | * hasher is a SHA256 object which a incrementing 4-byte counter is added to to | ||
| 269 | * generate randomness for the rejection sampling in this function. Its size plus | ||
| 270 | * 4 (for the counter) plus 9 (for the SHA256 padding) must be a multiple of 64 | ||
| 271 | * for efficiency reasons. | ||
| 272 | */ | ||
| 273 | 115200 | static void secp256k1_ellswift_xelligatorswift_var(secp256k1_fe *u, secp256k1_fe *t, const secp256k1_fe *x, const secp256k1_sha256 *hasher) { | |
| 274 | /* Pool of 3-bit branch values. */ | ||
| 275 | unsigned char branch_hash[32]; | ||
| 276 | /* Number of 3-bit values in branch_hash left. */ | ||
| 277 | 115200 | int branches_left = 0; | |
| 278 | /* Field elements u and branch values are extracted from | ||
| 279 | * SHA256(hasher || cnt) for consecutive values of cnt. cnt==0 | ||
| 280 | * is first used to populate a pool of 64 4-bit branch values. The 64 cnt | ||
| 281 | * values that follow are used to generate field elements u. cnt==65 (and | ||
| 282 | * multiples thereof) are used to repopulate the pool and start over, if | ||
| 283 | * that were ever necessary. */ | ||
| 284 | 115200 | uint32_t cnt = 0; | |
| 285 | VERIFY_CHECK((hasher->bytes + 4 + 9) % 64 == 0); | ||
| 286 | 345556 | while (1) { | |
| 287 | int branch; | ||
| 288 | /* If the pool of branch values is empty, populate it. */ | ||
| 289 |
2/2✓ Branch 0 taken 115200 times.
✓ Branch 1 taken 345556 times.
|
460756 | if (branches_left == 0) { |
| 290 | 115200 | secp256k1_sha256 hash = *hasher; | |
| 291 | unsigned char buf4[4]; | ||
| 292 | 115200 | buf4[0] = cnt; | |
| 293 | 115200 | buf4[1] = cnt >> 8; | |
| 294 | 115200 | buf4[2] = cnt >> 16; | |
| 295 | 115200 | buf4[3] = cnt >> 24; | |
| 296 | 115200 | ++cnt; | |
| 297 | 115200 | secp256k1_sha256_write(&hash, buf4, 4); | |
| 298 | 115200 | secp256k1_sha256_finalize(&hash, branch_hash); | |
| 299 | 115200 | branches_left = 64; | |
| 300 | } | ||
| 301 | /* Take a 3-bit branch value from the branch pool (top bit is discarded). */ | ||
| 302 | 460756 | --branches_left; | |
| 303 | 460756 | branch = (branch_hash[branches_left >> 1] >> ((branches_left & 1) << 2)) & 7; | |
| 304 | /* Compute a new u value by hashing. */ | ||
| 305 | { | ||
| 306 | 460756 | secp256k1_sha256 hash = *hasher; | |
| 307 | unsigned char buf4[4]; | ||
| 308 | unsigned char u32[32]; | ||
| 309 | 460756 | buf4[0] = cnt; | |
| 310 | 460756 | buf4[1] = cnt >> 8; | |
| 311 | 460756 | buf4[2] = cnt >> 16; | |
| 312 | 460756 | buf4[3] = cnt >> 24; | |
| 313 | 460756 | ++cnt; | |
| 314 | 460756 | secp256k1_sha256_write(&hash, buf4, 4); | |
| 315 | 460756 | secp256k1_sha256_finalize(&hash, u32); | |
| 316 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 460756 times.
|
460756 | if (!secp256k1_fe_set_b32(u, u32)) continue; |
| 317 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 460756 times.
|
460756 | if (secp256k1_fe_is_zero(u)) continue; |
| 318 | } | ||
| 319 | /* Find a remainder t, and return it if found. */ | ||
| 320 |
2/2✓ Branch 1 taken 115200 times.
✓ Branch 2 taken 345556 times.
|
460756 | if (secp256k1_ellswift_xswiftec_inv_var(t, x, u, branch)) { |
| 321 | 115200 | secp256k1_fe_normalize_var(t); | |
| 322 | 115200 | break; | |
| 323 | } | ||
| 324 | } | ||
| 325 | 115200 | } | |
| 326 | |||
| 327 | /** Find an ElligatorSwift encoding (u, t) for point P. */ | ||
| 328 | 115200 | static void secp256k1_ellswift_elligatorswift_var(secp256k1_fe *u, secp256k1_fe *t, const secp256k1_ge *p, const secp256k1_sha256 *hasher) { | |
| 329 | 115200 | secp256k1_ellswift_xelligatorswift_var(u, t, &p->x, hasher); | |
| 330 |
2/2✓ Branch 2 taken 57597 times.
✓ Branch 3 taken 57603 times.
|
115200 | if (secp256k1_fe_is_odd(t) != secp256k1_fe_is_odd(&p->y)) { |
| 331 | 57597 | secp256k1_fe_negate(t, t, 1); | |
| 332 | 57597 | secp256k1_fe_normalize_var(t); | |
| 333 | } | ||
| 334 | 115200 | } | |
| 335 | |||
| 336 | 64000 | int secp256k1_ellswift_encode(const secp256k1_context *ctx, unsigned char *ell64, const secp256k1_pubkey *pubkey, const unsigned char *rnd32) { | |
| 337 | secp256k1_ge p; | ||
| 338 | VERIFY_CHECK(ctx != NULL); | ||
| 339 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 64000 times.
|
64000 | ARG_CHECK(ell64 != NULL); |
| 340 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 64000 times.
|
64000 | ARG_CHECK(pubkey != NULL); |
| 341 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 64000 times.
|
64000 | ARG_CHECK(rnd32 != NULL); |
| 342 | |||
| 343 |
1/2✓ Branch 1 taken 64000 times.
✗ Branch 2 not taken.
|
64000 | if (secp256k1_pubkey_load(ctx, &p, pubkey)) { |
| 344 | static const unsigned char PREFIX[128 - 9 - 4 - 32 - 33] = "secp256k1_ellswift_encode"; | ||
| 345 | secp256k1_fe u, t; | ||
| 346 | unsigned char p33[33]; | ||
| 347 | secp256k1_sha256 hash; | ||
| 348 | |||
| 349 | /* Set up hasher state */ | ||
| 350 | 64000 | secp256k1_sha256_initialize(&hash); | |
| 351 | 64000 | secp256k1_sha256_write(&hash, PREFIX, sizeof(PREFIX)); | |
| 352 | 64000 | secp256k1_sha256_write(&hash, rnd32, 32); | |
| 353 | 64000 | secp256k1_fe_get_b32(p33, &p.x); | |
| 354 | 64000 | p33[32] = secp256k1_fe_is_odd(&p.y); | |
| 355 | 64000 | secp256k1_sha256_write(&hash, p33, sizeof(p33)); | |
| 356 | VERIFY_CHECK(hash.bytes == 128 - 9 - 4); | ||
| 357 | |||
| 358 | /* Compute ElligatorSwift encoding and construct output. */ | ||
| 359 | 64000 | secp256k1_ellswift_elligatorswift_var(&u, &t, &p, &hash); | |
| 360 | 64000 | secp256k1_fe_get_b32(ell64, &u); | |
| 361 | 64000 | secp256k1_fe_get_b32(ell64 + 32, &t); | |
| 362 | 64000 | return 1; | |
| 363 | } | ||
| 364 | /* Only returned in case the provided pubkey is invalid. */ | ||
| 365 | ✗ | return 0; | |
| 366 | } | ||
| 367 | |||
| 368 | 51200 | int secp256k1_ellswift_create(const secp256k1_context *ctx, unsigned char *ell64, const unsigned char *seckey32, const unsigned char *rnd32) { | |
| 369 | secp256k1_ge p; | ||
| 370 | secp256k1_fe u, t; | ||
| 371 | secp256k1_sha256 hash; | ||
| 372 | secp256k1_scalar seckey_scalar; | ||
| 373 | static const unsigned char PREFIX[32] = "secp256k1_ellswift_create"; | ||
| 374 | static const unsigned char ZERO[32] = {0}; | ||
| 375 | 51200 | int ret = 0; | |
| 376 | |||
| 377 | /* Sanity check inputs. */ | ||
| 378 | VERIFY_CHECK(ctx != NULL); | ||
| 379 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 51200 times.
|
51200 | ARG_CHECK(ell64 != NULL); |
| 380 | 51200 | memset(ell64, 0, 64); | |
| 381 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 51200 times.
|
51200 | ARG_CHECK(secp256k1_ecmult_gen_context_is_built(&ctx->ecmult_gen_ctx)); |
| 382 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 51200 times.
|
51200 | ARG_CHECK(seckey32 != NULL); |
| 383 | |||
| 384 | /* Compute (affine) public key */ | ||
| 385 | 51200 | ret = secp256k1_ec_pubkey_create_helper(&ctx->ecmult_gen_ctx, &seckey_scalar, &p, seckey32); | |
| 386 | 51200 | secp256k1_declassify(ctx, &p, sizeof(p)); /* not constant time in produced pubkey */ | |
| 387 | 51200 | secp256k1_fe_normalize_var(&p.x); | |
| 388 | 51200 | secp256k1_fe_normalize_var(&p.y); | |
| 389 | |||
| 390 | /* Set up hasher state */ | ||
| 391 | 51200 | secp256k1_sha256_initialize(&hash); | |
| 392 | 51200 | secp256k1_sha256_write(&hash, PREFIX, sizeof(PREFIX)); | |
| 393 | 51200 | secp256k1_sha256_write(&hash, seckey32, 32); | |
| 394 |
1/2✓ Branch 0 taken 51200 times.
✗ Branch 1 not taken.
|
51200 | secp256k1_sha256_write(&hash, rnd32 ? rnd32 : ZERO, 32); |
| 395 | 51200 | secp256k1_sha256_write(&hash, ZERO, 32 - 9 - 4); | |
| 396 | 51200 | secp256k1_declassify(ctx, &hash, sizeof(hash)); /* hasher gets to declassify private key */ | |
| 397 | |||
| 398 | /* Compute ElligatorSwift encoding and construct output. */ | ||
| 399 | 51200 | secp256k1_ellswift_elligatorswift_var(&u, &t, &p, &hash); | |
| 400 | 51200 | secp256k1_fe_get_b32(ell64, &u); | |
| 401 | 51200 | secp256k1_fe_get_b32(ell64 + 32, &t); | |
| 402 | |||
| 403 | 51200 | secp256k1_memczero(ell64, 64, !ret); | |
| 404 | 51200 | secp256k1_scalar_clear(&seckey_scalar); | |
| 405 | |||
| 406 | 51200 | return ret; | |
| 407 | } | ||
| 408 | |||
| 409 | 140876 | int secp256k1_ellswift_decode(const secp256k1_context *ctx, secp256k1_pubkey *pubkey, const unsigned char *ell64) { | |
| 410 | secp256k1_fe u, t; | ||
| 411 | secp256k1_ge p; | ||
| 412 | VERIFY_CHECK(ctx != NULL); | ||
| 413 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 140876 times.
|
140876 | ARG_CHECK(pubkey != NULL); |
| 414 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 140876 times.
|
140876 | ARG_CHECK(ell64 != NULL); |
| 415 | |||
| 416 | 140876 | secp256k1_fe_set_b32(&u, ell64); | |
| 417 | 140876 | secp256k1_fe_normalize_var(&u); | |
| 418 | 140876 | secp256k1_fe_set_b32(&t, ell64 + 32); | |
| 419 | 140876 | secp256k1_fe_normalize_var(&t); | |
| 420 | 140876 | secp256k1_ellswift_swiftec_var(&p, &u, &t); | |
| 421 | 140876 | secp256k1_pubkey_save(pubkey, &p); | |
| 422 | 140876 | return 1; | |
| 423 | } | ||
| 424 | |||
| 425 | 51200 | static int ellswift_xdh_hash_function_sha256(unsigned char *output, const unsigned char *x32, const unsigned char *ours64, const unsigned char *theirs64, void *data) { | |
| 426 | secp256k1_sha256 sha; | ||
| 427 | |||
| 428 | (void)data; | ||
| 429 | |||
| 430 | 51200 | secp256k1_sha256_initialize(&sha); | |
| 431 |
2/2✓ Branch 1 taken 25714 times.
✓ Branch 2 taken 25486 times.
|
51200 | if (secp256k1_memcmp_var(ours64, theirs64, 64) <= 0) { |
| 432 | 25714 | secp256k1_sha256_write(&sha, ours64, 64); | |
| 433 | 25714 | secp256k1_sha256_write(&sha, theirs64, 64); | |
| 434 | } else { | ||
| 435 | 25486 | secp256k1_sha256_write(&sha, theirs64, 64); | |
| 436 | 25486 | secp256k1_sha256_write(&sha, ours64, 64); | |
| 437 | } | ||
| 438 | 51200 | secp256k1_sha256_write(&sha, x32, 32); | |
| 439 | 51200 | secp256k1_sha256_finalize(&sha, output); | |
| 440 | |||
| 441 | 51200 | return 1; | |
| 442 | } | ||
| 443 | |||
| 444 | const secp256k1_ellswift_xdh_hash_function secp256k1_ellswift_xdh_hash_function_sha256 = ellswift_xdh_hash_function_sha256; | ||
| 445 | const secp256k1_ellswift_xdh_hash_function secp256k1_ellswift_xdh_hash_function_default = ellswift_xdh_hash_function_sha256; | ||
| 446 | |||
| 447 | 102400 | int secp256k1_ellswift_xdh(const secp256k1_context *ctx, unsigned char *output, const unsigned char *theirs64, const unsigned char *ours64, const unsigned char *seckey32, secp256k1_ellswift_xdh_hash_function hashfp, void *data) { | |
| 448 | 102400 | int ret = 0; | |
| 449 | int overflow; | ||
| 450 | secp256k1_scalar s; | ||
| 451 | secp256k1_fe xn, xd, px, u, t; | ||
| 452 | unsigned char sx[32]; | ||
| 453 | |||
| 454 | VERIFY_CHECK(ctx != NULL); | ||
| 455 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 102400 times.
|
102400 | ARG_CHECK(output != NULL); |
| 456 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 102400 times.
|
102400 | ARG_CHECK(theirs64 != NULL); |
| 457 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 102400 times.
|
102400 | ARG_CHECK(ours64 != NULL); |
| 458 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 102400 times.
|
102400 | ARG_CHECK(seckey32 != NULL); |
| 459 | |||
| 460 |
2/2✓ Branch 0 taken 51200 times.
✓ Branch 1 taken 51200 times.
|
102400 | if (hashfp == NULL) { |
| 461 | 51200 | hashfp = secp256k1_ellswift_xdh_hash_function_default; | |
| 462 | } | ||
| 463 | |||
| 464 | /* Load remote public key (as fraction). */ | ||
| 465 | 102400 | secp256k1_fe_set_b32(&u, theirs64); | |
| 466 | 102400 | secp256k1_fe_normalize_var(&u); | |
| 467 | 102400 | secp256k1_fe_set_b32(&t, theirs64 + 32); | |
| 468 | 102400 | secp256k1_fe_normalize_var(&t); | |
| 469 | 102400 | secp256k1_ellswift_xswiftec_frac_var(&xn, &xd, &u, &t); | |
| 470 | |||
| 471 | /* Load private key (using one if invalid). */ | ||
| 472 | 102400 | secp256k1_scalar_set_b32(&s, seckey32, &overflow); | |
| 473 | 102400 | overflow = secp256k1_scalar_is_zero(&s); | |
| 474 | 102400 | secp256k1_scalar_cmov(&s, &secp256k1_scalar_one, overflow); | |
| 475 | |||
| 476 | /* Compute shared X coordinate. */ | ||
| 477 | 102400 | secp256k1_ecmult_const_xonly(&px, &xn, &xd, &s, 256, 1); | |
| 478 | 102400 | secp256k1_fe_normalize(&px); | |
| 479 | 102400 | secp256k1_fe_get_b32(sx, &px); | |
| 480 | |||
| 481 | /* Invoke hasher */ | ||
| 482 | 102400 | ret = hashfp(output, sx, ours64, theirs64, data); | |
| 483 | |||
| 484 | 102400 | memset(sx, 0, 32); | |
| 485 | 102400 | secp256k1_fe_clear(&px); | |
| 486 | 102400 | secp256k1_scalar_clear(&s); | |
| 487 | |||
| 488 | 102400 | return !!ret & !overflow; | |
| 489 | } | ||
| 490 | |||
| 491 | #endif | ||
| 492 |