group_impl.h (38088B)
1 /*********************************************************************** 2 * Copyright (c) 2013, 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_GROUP_IMPL_H 8 #define SECP256K1_GROUP_IMPL_H 9 10 #include "field.h" 11 #include "group.h" 12 #include "util.h" 13 14 /* Begin of section generated by sage/gen_exhaustive_groups.sage. */ 15 #define SECP256K1_G_ORDER_7 SECP256K1_GE_CONST(\ 16 0x66625d13, 0x317ffe44, 0x63d32cff, 0x1ca02b9b,\ 17 0xe5c6d070, 0x50b4b05e, 0x81cc30db, 0xf5166f0a,\ 18 0x1e60e897, 0xa7c00c7c, 0x2df53eb6, 0x98274ff4,\ 19 0x64252f42, 0x8ca44e17, 0x3b25418c, 0xff4ab0cf\ 20 ) 21 #define SECP256K1_G_ORDER_13 SECP256K1_GE_CONST(\ 22 0xa2482ff8, 0x4bf34edf, 0xa51262fd, 0xe57921db,\ 23 0xe0dd2cb7, 0xa5914790, 0xbc71631f, 0xc09704fb,\ 24 0x942536cb, 0xa3e49492, 0x3a701cc3, 0xee3e443f,\ 25 0xdf182aa9, 0x15b8aa6a, 0x166d3b19, 0xba84b045\ 26 ) 27 #define SECP256K1_G_ORDER_199 SECP256K1_GE_CONST(\ 28 0x7fb07b5c, 0xd07c3bda, 0x553902e2, 0x7a87ea2c,\ 29 0x35108a7f, 0x051f41e5, 0xb76abad5, 0x1f2703ad,\ 30 0x0a251539, 0x5b4c4438, 0x952a634f, 0xac10dd4d,\ 31 0x6d6f4745, 0x98990c27, 0x3a4f3116, 0xd32ff969\ 32 ) 33 /** Generator for secp256k1, value 'g' defined in 34 * "Standards for Efficient Cryptography" (SEC2) 2.7.1. 35 */ 36 #define SECP256K1_G SECP256K1_GE_CONST(\ 37 0x79be667e, 0xf9dcbbac, 0x55a06295, 0xce870b07,\ 38 0x029bfcdb, 0x2dce28d9, 0x59f2815b, 0x16f81798,\ 39 0x483ada77, 0x26a3c465, 0x5da4fbfc, 0x0e1108a8,\ 40 0xfd17b448, 0xa6855419, 0x9c47d08f, 0xfb10d4b8\ 41 ) 42 /* These exhaustive group test orders and generators are chosen such that: 43 * - The field size is equal to that of secp256k1, so field code is the same. 44 * - The curve equation is of the form y^2=x^3+B for some small constant B. 45 * - The subgroup has a generator 2*P, where P.x is as small as possible. 46 * - The subgroup has size less than 1000 to permit exhaustive testing. 47 * - The subgroup admits an endomorphism of the form lambda*(x,y) == (beta*x,y). 48 */ 49 #if defined(EXHAUSTIVE_TEST_ORDER) 50 # if EXHAUSTIVE_TEST_ORDER == 7 51 52 static const haskellsecp256k1_v0_1_0_ge haskellsecp256k1_v0_1_0_ge_const_g = SECP256K1_G_ORDER_7; 53 #define SECP256K1_B 6 54 55 # elif EXHAUSTIVE_TEST_ORDER == 13 56 57 static const haskellsecp256k1_v0_1_0_ge haskellsecp256k1_v0_1_0_ge_const_g = SECP256K1_G_ORDER_13; 58 #define SECP256K1_B 2 59 60 # elif EXHAUSTIVE_TEST_ORDER == 199 61 62 static const haskellsecp256k1_v0_1_0_ge haskellsecp256k1_v0_1_0_ge_const_g = SECP256K1_G_ORDER_199; 63 #define SECP256K1_B 4 64 65 # else 66 # error No known generator for the specified exhaustive test group order. 67 # endif 68 #else 69 70 static const haskellsecp256k1_v0_1_0_ge haskellsecp256k1_v0_1_0_ge_const_g = SECP256K1_G; 71 #define SECP256K1_B 7 72 73 #endif 74 /* End of section generated by sage/gen_exhaustive_groups.sage. */ 75 76 static void haskellsecp256k1_v0_1_0_ge_verify(const haskellsecp256k1_v0_1_0_ge *a) { 77 SECP256K1_FE_VERIFY(&a->x); 78 SECP256K1_FE_VERIFY(&a->y); 79 SECP256K1_FE_VERIFY_MAGNITUDE(&a->x, SECP256K1_GE_X_MAGNITUDE_MAX); 80 SECP256K1_FE_VERIFY_MAGNITUDE(&a->y, SECP256K1_GE_Y_MAGNITUDE_MAX); 81 VERIFY_CHECK(a->infinity == 0 || a->infinity == 1); 82 (void)a; 83 } 84 85 static void haskellsecp256k1_v0_1_0_gej_verify(const haskellsecp256k1_v0_1_0_gej *a) { 86 SECP256K1_FE_VERIFY(&a->x); 87 SECP256K1_FE_VERIFY(&a->y); 88 SECP256K1_FE_VERIFY(&a->z); 89 SECP256K1_FE_VERIFY_MAGNITUDE(&a->x, SECP256K1_GEJ_X_MAGNITUDE_MAX); 90 SECP256K1_FE_VERIFY_MAGNITUDE(&a->y, SECP256K1_GEJ_Y_MAGNITUDE_MAX); 91 SECP256K1_FE_VERIFY_MAGNITUDE(&a->z, SECP256K1_GEJ_Z_MAGNITUDE_MAX); 92 VERIFY_CHECK(a->infinity == 0 || a->infinity == 1); 93 (void)a; 94 } 95 96 /* Set r to the affine coordinates of Jacobian point (a.x, a.y, 1/zi). */ 97 static void haskellsecp256k1_v0_1_0_ge_set_gej_zinv(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_fe *zi) { 98 haskellsecp256k1_v0_1_0_fe zi2; 99 haskellsecp256k1_v0_1_0_fe zi3; 100 SECP256K1_GEJ_VERIFY(a); 101 SECP256K1_FE_VERIFY(zi); 102 VERIFY_CHECK(!a->infinity); 103 104 haskellsecp256k1_v0_1_0_fe_sqr(&zi2, zi); 105 haskellsecp256k1_v0_1_0_fe_mul(&zi3, &zi2, zi); 106 haskellsecp256k1_v0_1_0_fe_mul(&r->x, &a->x, &zi2); 107 haskellsecp256k1_v0_1_0_fe_mul(&r->y, &a->y, &zi3); 108 r->infinity = a->infinity; 109 110 SECP256K1_GE_VERIFY(r); 111 } 112 113 /* Set r to the affine coordinates of Jacobian point (a.x, a.y, 1/zi). */ 114 static void haskellsecp256k1_v0_1_0_ge_set_ge_zinv(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_ge *a, const haskellsecp256k1_v0_1_0_fe *zi) { 115 haskellsecp256k1_v0_1_0_fe zi2; 116 haskellsecp256k1_v0_1_0_fe zi3; 117 SECP256K1_GE_VERIFY(a); 118 SECP256K1_FE_VERIFY(zi); 119 VERIFY_CHECK(!a->infinity); 120 121 haskellsecp256k1_v0_1_0_fe_sqr(&zi2, zi); 122 haskellsecp256k1_v0_1_0_fe_mul(&zi3, &zi2, zi); 123 haskellsecp256k1_v0_1_0_fe_mul(&r->x, &a->x, &zi2); 124 haskellsecp256k1_v0_1_0_fe_mul(&r->y, &a->y, &zi3); 125 r->infinity = a->infinity; 126 127 SECP256K1_GE_VERIFY(r); 128 } 129 130 static void haskellsecp256k1_v0_1_0_ge_set_xy(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_fe *x, const haskellsecp256k1_v0_1_0_fe *y) { 131 SECP256K1_FE_VERIFY(x); 132 SECP256K1_FE_VERIFY(y); 133 134 r->infinity = 0; 135 r->x = *x; 136 r->y = *y; 137 138 SECP256K1_GE_VERIFY(r); 139 } 140 141 static int haskellsecp256k1_v0_1_0_ge_is_infinity(const haskellsecp256k1_v0_1_0_ge *a) { 142 SECP256K1_GE_VERIFY(a); 143 144 return a->infinity; 145 } 146 147 static void haskellsecp256k1_v0_1_0_ge_neg(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_ge *a) { 148 SECP256K1_GE_VERIFY(a); 149 150 *r = *a; 151 haskellsecp256k1_v0_1_0_fe_normalize_weak(&r->y); 152 haskellsecp256k1_v0_1_0_fe_negate(&r->y, &r->y, 1); 153 154 SECP256K1_GE_VERIFY(r); 155 } 156 157 static void haskellsecp256k1_v0_1_0_ge_set_gej(haskellsecp256k1_v0_1_0_ge *r, haskellsecp256k1_v0_1_0_gej *a) { 158 haskellsecp256k1_v0_1_0_fe z2, z3; 159 SECP256K1_GEJ_VERIFY(a); 160 161 r->infinity = a->infinity; 162 haskellsecp256k1_v0_1_0_fe_inv(&a->z, &a->z); 163 haskellsecp256k1_v0_1_0_fe_sqr(&z2, &a->z); 164 haskellsecp256k1_v0_1_0_fe_mul(&z3, &a->z, &z2); 165 haskellsecp256k1_v0_1_0_fe_mul(&a->x, &a->x, &z2); 166 haskellsecp256k1_v0_1_0_fe_mul(&a->y, &a->y, &z3); 167 haskellsecp256k1_v0_1_0_fe_set_int(&a->z, 1); 168 r->x = a->x; 169 r->y = a->y; 170 171 SECP256K1_GEJ_VERIFY(a); 172 SECP256K1_GE_VERIFY(r); 173 } 174 175 static void haskellsecp256k1_v0_1_0_ge_set_gej_var(haskellsecp256k1_v0_1_0_ge *r, haskellsecp256k1_v0_1_0_gej *a) { 176 haskellsecp256k1_v0_1_0_fe z2, z3; 177 SECP256K1_GEJ_VERIFY(a); 178 179 if (haskellsecp256k1_v0_1_0_gej_is_infinity(a)) { 180 haskellsecp256k1_v0_1_0_ge_set_infinity(r); 181 return; 182 } 183 r->infinity = 0; 184 haskellsecp256k1_v0_1_0_fe_inv_var(&a->z, &a->z); 185 haskellsecp256k1_v0_1_0_fe_sqr(&z2, &a->z); 186 haskellsecp256k1_v0_1_0_fe_mul(&z3, &a->z, &z2); 187 haskellsecp256k1_v0_1_0_fe_mul(&a->x, &a->x, &z2); 188 haskellsecp256k1_v0_1_0_fe_mul(&a->y, &a->y, &z3); 189 haskellsecp256k1_v0_1_0_fe_set_int(&a->z, 1); 190 haskellsecp256k1_v0_1_0_ge_set_xy(r, &a->x, &a->y); 191 192 SECP256K1_GEJ_VERIFY(a); 193 SECP256K1_GE_VERIFY(r); 194 } 195 196 static void haskellsecp256k1_v0_1_0_ge_set_all_gej_var(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_gej *a, size_t len) { 197 haskellsecp256k1_v0_1_0_fe u; 198 size_t i; 199 size_t last_i = SIZE_MAX; 200 #ifdef VERIFY 201 for (i = 0; i < len; i++) { 202 SECP256K1_GEJ_VERIFY(&a[i]); 203 } 204 #endif 205 206 for (i = 0; i < len; i++) { 207 if (a[i].infinity) { 208 haskellsecp256k1_v0_1_0_ge_set_infinity(&r[i]); 209 } else { 210 /* Use destination's x coordinates as scratch space */ 211 if (last_i == SIZE_MAX) { 212 r[i].x = a[i].z; 213 } else { 214 haskellsecp256k1_v0_1_0_fe_mul(&r[i].x, &r[last_i].x, &a[i].z); 215 } 216 last_i = i; 217 } 218 } 219 if (last_i == SIZE_MAX) { 220 return; 221 } 222 haskellsecp256k1_v0_1_0_fe_inv_var(&u, &r[last_i].x); 223 224 i = last_i; 225 while (i > 0) { 226 i--; 227 if (!a[i].infinity) { 228 haskellsecp256k1_v0_1_0_fe_mul(&r[last_i].x, &r[i].x, &u); 229 haskellsecp256k1_v0_1_0_fe_mul(&u, &u, &a[last_i].z); 230 last_i = i; 231 } 232 } 233 VERIFY_CHECK(!a[last_i].infinity); 234 r[last_i].x = u; 235 236 for (i = 0; i < len; i++) { 237 if (!a[i].infinity) { 238 haskellsecp256k1_v0_1_0_ge_set_gej_zinv(&r[i], &a[i], &r[i].x); 239 } 240 } 241 242 #ifdef VERIFY 243 for (i = 0; i < len; i++) { 244 SECP256K1_GE_VERIFY(&r[i]); 245 } 246 #endif 247 } 248 249 static void haskellsecp256k1_v0_1_0_ge_table_set_globalz(size_t len, haskellsecp256k1_v0_1_0_ge *a, const haskellsecp256k1_v0_1_0_fe *zr) { 250 size_t i; 251 haskellsecp256k1_v0_1_0_fe zs; 252 #ifdef VERIFY 253 for (i = 0; i < len; i++) { 254 SECP256K1_GE_VERIFY(&a[i]); 255 SECP256K1_FE_VERIFY(&zr[i]); 256 } 257 #endif 258 259 if (len > 0) { 260 i = len - 1; 261 /* Ensure all y values are in weak normal form for fast negation of points */ 262 haskellsecp256k1_v0_1_0_fe_normalize_weak(&a[i].y); 263 zs = zr[i]; 264 265 /* Work our way backwards, using the z-ratios to scale the x/y values. */ 266 while (i > 0) { 267 if (i != len - 1) { 268 haskellsecp256k1_v0_1_0_fe_mul(&zs, &zs, &zr[i]); 269 } 270 i--; 271 haskellsecp256k1_v0_1_0_ge_set_ge_zinv(&a[i], &a[i], &zs); 272 } 273 } 274 275 #ifdef VERIFY 276 for (i = 0; i < len; i++) { 277 SECP256K1_GE_VERIFY(&a[i]); 278 } 279 #endif 280 } 281 282 static void haskellsecp256k1_v0_1_0_gej_set_infinity(haskellsecp256k1_v0_1_0_gej *r) { 283 r->infinity = 1; 284 haskellsecp256k1_v0_1_0_fe_clear(&r->x); 285 haskellsecp256k1_v0_1_0_fe_clear(&r->y); 286 haskellsecp256k1_v0_1_0_fe_clear(&r->z); 287 288 SECP256K1_GEJ_VERIFY(r); 289 } 290 291 static void haskellsecp256k1_v0_1_0_ge_set_infinity(haskellsecp256k1_v0_1_0_ge *r) { 292 r->infinity = 1; 293 haskellsecp256k1_v0_1_0_fe_clear(&r->x); 294 haskellsecp256k1_v0_1_0_fe_clear(&r->y); 295 296 SECP256K1_GE_VERIFY(r); 297 } 298 299 static void haskellsecp256k1_v0_1_0_gej_clear(haskellsecp256k1_v0_1_0_gej *r) { 300 r->infinity = 0; 301 haskellsecp256k1_v0_1_0_fe_clear(&r->x); 302 haskellsecp256k1_v0_1_0_fe_clear(&r->y); 303 haskellsecp256k1_v0_1_0_fe_clear(&r->z); 304 305 SECP256K1_GEJ_VERIFY(r); 306 } 307 308 static void haskellsecp256k1_v0_1_0_ge_clear(haskellsecp256k1_v0_1_0_ge *r) { 309 r->infinity = 0; 310 haskellsecp256k1_v0_1_0_fe_clear(&r->x); 311 haskellsecp256k1_v0_1_0_fe_clear(&r->y); 312 313 SECP256K1_GE_VERIFY(r); 314 } 315 316 static int haskellsecp256k1_v0_1_0_ge_set_xo_var(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_fe *x, int odd) { 317 haskellsecp256k1_v0_1_0_fe x2, x3; 318 int ret; 319 SECP256K1_FE_VERIFY(x); 320 321 r->x = *x; 322 haskellsecp256k1_v0_1_0_fe_sqr(&x2, x); 323 haskellsecp256k1_v0_1_0_fe_mul(&x3, x, &x2); 324 r->infinity = 0; 325 haskellsecp256k1_v0_1_0_fe_add_int(&x3, SECP256K1_B); 326 ret = haskellsecp256k1_v0_1_0_fe_sqrt(&r->y, &x3); 327 haskellsecp256k1_v0_1_0_fe_normalize_var(&r->y); 328 if (haskellsecp256k1_v0_1_0_fe_is_odd(&r->y) != odd) { 329 haskellsecp256k1_v0_1_0_fe_negate(&r->y, &r->y, 1); 330 } 331 332 SECP256K1_GE_VERIFY(r); 333 return ret; 334 } 335 336 static void haskellsecp256k1_v0_1_0_gej_set_ge(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_ge *a) { 337 SECP256K1_GE_VERIFY(a); 338 339 r->infinity = a->infinity; 340 r->x = a->x; 341 r->y = a->y; 342 haskellsecp256k1_v0_1_0_fe_set_int(&r->z, 1); 343 344 SECP256K1_GEJ_VERIFY(r); 345 } 346 347 static int haskellsecp256k1_v0_1_0_gej_eq_var(const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_gej *b) { 348 haskellsecp256k1_v0_1_0_gej tmp; 349 SECP256K1_GEJ_VERIFY(b); 350 SECP256K1_GEJ_VERIFY(a); 351 352 haskellsecp256k1_v0_1_0_gej_neg(&tmp, a); 353 haskellsecp256k1_v0_1_0_gej_add_var(&tmp, &tmp, b, NULL); 354 return haskellsecp256k1_v0_1_0_gej_is_infinity(&tmp); 355 } 356 357 static int haskellsecp256k1_v0_1_0_gej_eq_ge_var(const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_ge *b) { 358 haskellsecp256k1_v0_1_0_gej tmp; 359 SECP256K1_GEJ_VERIFY(a); 360 SECP256K1_GE_VERIFY(b); 361 362 haskellsecp256k1_v0_1_0_gej_neg(&tmp, a); 363 haskellsecp256k1_v0_1_0_gej_add_ge_var(&tmp, &tmp, b, NULL); 364 return haskellsecp256k1_v0_1_0_gej_is_infinity(&tmp); 365 } 366 367 static int haskellsecp256k1_v0_1_0_ge_eq_var(const haskellsecp256k1_v0_1_0_ge *a, const haskellsecp256k1_v0_1_0_ge *b) { 368 haskellsecp256k1_v0_1_0_fe tmp; 369 SECP256K1_GE_VERIFY(a); 370 SECP256K1_GE_VERIFY(b); 371 372 if (a->infinity != b->infinity) return 0; 373 if (a->infinity) return 1; 374 375 tmp = a->x; 376 haskellsecp256k1_v0_1_0_fe_normalize_weak(&tmp); 377 if (!haskellsecp256k1_v0_1_0_fe_equal(&tmp, &b->x)) return 0; 378 379 tmp = a->y; 380 haskellsecp256k1_v0_1_0_fe_normalize_weak(&tmp); 381 if (!haskellsecp256k1_v0_1_0_fe_equal(&tmp, &b->y)) return 0; 382 383 return 1; 384 } 385 386 static int haskellsecp256k1_v0_1_0_gej_eq_x_var(const haskellsecp256k1_v0_1_0_fe *x, const haskellsecp256k1_v0_1_0_gej *a) { 387 haskellsecp256k1_v0_1_0_fe r; 388 SECP256K1_FE_VERIFY(x); 389 SECP256K1_GEJ_VERIFY(a); 390 VERIFY_CHECK(!a->infinity); 391 392 haskellsecp256k1_v0_1_0_fe_sqr(&r, &a->z); haskellsecp256k1_v0_1_0_fe_mul(&r, &r, x); 393 return haskellsecp256k1_v0_1_0_fe_equal(&r, &a->x); 394 } 395 396 static void haskellsecp256k1_v0_1_0_gej_neg(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a) { 397 SECP256K1_GEJ_VERIFY(a); 398 399 r->infinity = a->infinity; 400 r->x = a->x; 401 r->y = a->y; 402 r->z = a->z; 403 haskellsecp256k1_v0_1_0_fe_normalize_weak(&r->y); 404 haskellsecp256k1_v0_1_0_fe_negate(&r->y, &r->y, 1); 405 406 SECP256K1_GEJ_VERIFY(r); 407 } 408 409 static int haskellsecp256k1_v0_1_0_gej_is_infinity(const haskellsecp256k1_v0_1_0_gej *a) { 410 SECP256K1_GEJ_VERIFY(a); 411 412 return a->infinity; 413 } 414 415 static int haskellsecp256k1_v0_1_0_ge_is_valid_var(const haskellsecp256k1_v0_1_0_ge *a) { 416 haskellsecp256k1_v0_1_0_fe y2, x3; 417 SECP256K1_GE_VERIFY(a); 418 419 if (a->infinity) { 420 return 0; 421 } 422 /* y^2 = x^3 + 7 */ 423 haskellsecp256k1_v0_1_0_fe_sqr(&y2, &a->y); 424 haskellsecp256k1_v0_1_0_fe_sqr(&x3, &a->x); haskellsecp256k1_v0_1_0_fe_mul(&x3, &x3, &a->x); 425 haskellsecp256k1_v0_1_0_fe_add_int(&x3, SECP256K1_B); 426 return haskellsecp256k1_v0_1_0_fe_equal(&y2, &x3); 427 } 428 429 static SECP256K1_INLINE void haskellsecp256k1_v0_1_0_gej_double(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a) { 430 /* Operations: 3 mul, 4 sqr, 8 add/half/mul_int/negate */ 431 haskellsecp256k1_v0_1_0_fe l, s, t; 432 SECP256K1_GEJ_VERIFY(a); 433 434 r->infinity = a->infinity; 435 436 /* Formula used: 437 * L = (3/2) * X1^2 438 * S = Y1^2 439 * T = -X1*S 440 * X3 = L^2 + 2*T 441 * Y3 = -(L*(X3 + T) + S^2) 442 * Z3 = Y1*Z1 443 */ 444 445 haskellsecp256k1_v0_1_0_fe_mul(&r->z, &a->z, &a->y); /* Z3 = Y1*Z1 (1) */ 446 haskellsecp256k1_v0_1_0_fe_sqr(&s, &a->y); /* S = Y1^2 (1) */ 447 haskellsecp256k1_v0_1_0_fe_sqr(&l, &a->x); /* L = X1^2 (1) */ 448 haskellsecp256k1_v0_1_0_fe_mul_int(&l, 3); /* L = 3*X1^2 (3) */ 449 haskellsecp256k1_v0_1_0_fe_half(&l); /* L = 3/2*X1^2 (2) */ 450 haskellsecp256k1_v0_1_0_fe_negate(&t, &s, 1); /* T = -S (2) */ 451 haskellsecp256k1_v0_1_0_fe_mul(&t, &t, &a->x); /* T = -X1*S (1) */ 452 haskellsecp256k1_v0_1_0_fe_sqr(&r->x, &l); /* X3 = L^2 (1) */ 453 haskellsecp256k1_v0_1_0_fe_add(&r->x, &t); /* X3 = L^2 + T (2) */ 454 haskellsecp256k1_v0_1_0_fe_add(&r->x, &t); /* X3 = L^2 + 2*T (3) */ 455 haskellsecp256k1_v0_1_0_fe_sqr(&s, &s); /* S' = S^2 (1) */ 456 haskellsecp256k1_v0_1_0_fe_add(&t, &r->x); /* T' = X3 + T (4) */ 457 haskellsecp256k1_v0_1_0_fe_mul(&r->y, &t, &l); /* Y3 = L*(X3 + T) (1) */ 458 haskellsecp256k1_v0_1_0_fe_add(&r->y, &s); /* Y3 = L*(X3 + T) + S^2 (2) */ 459 haskellsecp256k1_v0_1_0_fe_negate(&r->y, &r->y, 2); /* Y3 = -(L*(X3 + T) + S^2) (3) */ 460 461 SECP256K1_GEJ_VERIFY(r); 462 } 463 464 static void haskellsecp256k1_v0_1_0_gej_double_var(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a, haskellsecp256k1_v0_1_0_fe *rzr) { 465 SECP256K1_GEJ_VERIFY(a); 466 467 /** For secp256k1, 2Q is infinity if and only if Q is infinity. This is because if 2Q = infinity, 468 * Q must equal -Q, or that Q.y == -(Q.y), or Q.y is 0. For a point on y^2 = x^3 + 7 to have 469 * y=0, x^3 must be -7 mod p. However, -7 has no cube root mod p. 470 * 471 * Having said this, if this function receives a point on a sextic twist, e.g. by 472 * a fault attack, it is possible for y to be 0. This happens for y^2 = x^3 + 6, 473 * since -6 does have a cube root mod p. For this point, this function will not set 474 * the infinity flag even though the point doubles to infinity, and the result 475 * point will be gibberish (z = 0 but infinity = 0). 476 */ 477 if (a->infinity) { 478 haskellsecp256k1_v0_1_0_gej_set_infinity(r); 479 if (rzr != NULL) { 480 haskellsecp256k1_v0_1_0_fe_set_int(rzr, 1); 481 } 482 return; 483 } 484 485 if (rzr != NULL) { 486 *rzr = a->y; 487 haskellsecp256k1_v0_1_0_fe_normalize_weak(rzr); 488 } 489 490 haskellsecp256k1_v0_1_0_gej_double(r, a); 491 492 SECP256K1_GEJ_VERIFY(r); 493 } 494 495 static void haskellsecp256k1_v0_1_0_gej_add_var(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_gej *b, haskellsecp256k1_v0_1_0_fe *rzr) { 496 /* 12 mul, 4 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */ 497 haskellsecp256k1_v0_1_0_fe z22, z12, u1, u2, s1, s2, h, i, h2, h3, t; 498 SECP256K1_GEJ_VERIFY(a); 499 SECP256K1_GEJ_VERIFY(b); 500 501 if (a->infinity) { 502 VERIFY_CHECK(rzr == NULL); 503 *r = *b; 504 return; 505 } 506 if (b->infinity) { 507 if (rzr != NULL) { 508 haskellsecp256k1_v0_1_0_fe_set_int(rzr, 1); 509 } 510 *r = *a; 511 return; 512 } 513 514 haskellsecp256k1_v0_1_0_fe_sqr(&z22, &b->z); 515 haskellsecp256k1_v0_1_0_fe_sqr(&z12, &a->z); 516 haskellsecp256k1_v0_1_0_fe_mul(&u1, &a->x, &z22); 517 haskellsecp256k1_v0_1_0_fe_mul(&u2, &b->x, &z12); 518 haskellsecp256k1_v0_1_0_fe_mul(&s1, &a->y, &z22); haskellsecp256k1_v0_1_0_fe_mul(&s1, &s1, &b->z); 519 haskellsecp256k1_v0_1_0_fe_mul(&s2, &b->y, &z12); haskellsecp256k1_v0_1_0_fe_mul(&s2, &s2, &a->z); 520 haskellsecp256k1_v0_1_0_fe_negate(&h, &u1, 1); haskellsecp256k1_v0_1_0_fe_add(&h, &u2); 521 haskellsecp256k1_v0_1_0_fe_negate(&i, &s2, 1); haskellsecp256k1_v0_1_0_fe_add(&i, &s1); 522 if (haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(&h)) { 523 if (haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(&i)) { 524 haskellsecp256k1_v0_1_0_gej_double_var(r, a, rzr); 525 } else { 526 if (rzr != NULL) { 527 haskellsecp256k1_v0_1_0_fe_set_int(rzr, 0); 528 } 529 haskellsecp256k1_v0_1_0_gej_set_infinity(r); 530 } 531 return; 532 } 533 534 r->infinity = 0; 535 haskellsecp256k1_v0_1_0_fe_mul(&t, &h, &b->z); 536 if (rzr != NULL) { 537 *rzr = t; 538 } 539 haskellsecp256k1_v0_1_0_fe_mul(&r->z, &a->z, &t); 540 541 haskellsecp256k1_v0_1_0_fe_sqr(&h2, &h); 542 haskellsecp256k1_v0_1_0_fe_negate(&h2, &h2, 1); 543 haskellsecp256k1_v0_1_0_fe_mul(&h3, &h2, &h); 544 haskellsecp256k1_v0_1_0_fe_mul(&t, &u1, &h2); 545 546 haskellsecp256k1_v0_1_0_fe_sqr(&r->x, &i); 547 haskellsecp256k1_v0_1_0_fe_add(&r->x, &h3); 548 haskellsecp256k1_v0_1_0_fe_add(&r->x, &t); 549 haskellsecp256k1_v0_1_0_fe_add(&r->x, &t); 550 551 haskellsecp256k1_v0_1_0_fe_add(&t, &r->x); 552 haskellsecp256k1_v0_1_0_fe_mul(&r->y, &t, &i); 553 haskellsecp256k1_v0_1_0_fe_mul(&h3, &h3, &s1); 554 haskellsecp256k1_v0_1_0_fe_add(&r->y, &h3); 555 556 SECP256K1_GEJ_VERIFY(r); 557 } 558 559 static void haskellsecp256k1_v0_1_0_gej_add_ge_var(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_ge *b, haskellsecp256k1_v0_1_0_fe *rzr) { 560 /* Operations: 8 mul, 3 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */ 561 haskellsecp256k1_v0_1_0_fe z12, u1, u2, s1, s2, h, i, h2, h3, t; 562 SECP256K1_GEJ_VERIFY(a); 563 SECP256K1_GE_VERIFY(b); 564 565 if (a->infinity) { 566 VERIFY_CHECK(rzr == NULL); 567 haskellsecp256k1_v0_1_0_gej_set_ge(r, b); 568 return; 569 } 570 if (b->infinity) { 571 if (rzr != NULL) { 572 haskellsecp256k1_v0_1_0_fe_set_int(rzr, 1); 573 } 574 *r = *a; 575 return; 576 } 577 578 haskellsecp256k1_v0_1_0_fe_sqr(&z12, &a->z); 579 u1 = a->x; 580 haskellsecp256k1_v0_1_0_fe_mul(&u2, &b->x, &z12); 581 s1 = a->y; 582 haskellsecp256k1_v0_1_0_fe_mul(&s2, &b->y, &z12); haskellsecp256k1_v0_1_0_fe_mul(&s2, &s2, &a->z); 583 haskellsecp256k1_v0_1_0_fe_negate(&h, &u1, SECP256K1_GEJ_X_MAGNITUDE_MAX); haskellsecp256k1_v0_1_0_fe_add(&h, &u2); 584 haskellsecp256k1_v0_1_0_fe_negate(&i, &s2, 1); haskellsecp256k1_v0_1_0_fe_add(&i, &s1); 585 if (haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(&h)) { 586 if (haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(&i)) { 587 haskellsecp256k1_v0_1_0_gej_double_var(r, a, rzr); 588 } else { 589 if (rzr != NULL) { 590 haskellsecp256k1_v0_1_0_fe_set_int(rzr, 0); 591 } 592 haskellsecp256k1_v0_1_0_gej_set_infinity(r); 593 } 594 return; 595 } 596 597 r->infinity = 0; 598 if (rzr != NULL) { 599 *rzr = h; 600 } 601 haskellsecp256k1_v0_1_0_fe_mul(&r->z, &a->z, &h); 602 603 haskellsecp256k1_v0_1_0_fe_sqr(&h2, &h); 604 haskellsecp256k1_v0_1_0_fe_negate(&h2, &h2, 1); 605 haskellsecp256k1_v0_1_0_fe_mul(&h3, &h2, &h); 606 haskellsecp256k1_v0_1_0_fe_mul(&t, &u1, &h2); 607 608 haskellsecp256k1_v0_1_0_fe_sqr(&r->x, &i); 609 haskellsecp256k1_v0_1_0_fe_add(&r->x, &h3); 610 haskellsecp256k1_v0_1_0_fe_add(&r->x, &t); 611 haskellsecp256k1_v0_1_0_fe_add(&r->x, &t); 612 613 haskellsecp256k1_v0_1_0_fe_add(&t, &r->x); 614 haskellsecp256k1_v0_1_0_fe_mul(&r->y, &t, &i); 615 haskellsecp256k1_v0_1_0_fe_mul(&h3, &h3, &s1); 616 haskellsecp256k1_v0_1_0_fe_add(&r->y, &h3); 617 618 SECP256K1_GEJ_VERIFY(r); 619 if (rzr != NULL) SECP256K1_FE_VERIFY(rzr); 620 } 621 622 static void haskellsecp256k1_v0_1_0_gej_add_zinv_var(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_ge *b, const haskellsecp256k1_v0_1_0_fe *bzinv) { 623 /* Operations: 9 mul, 3 sqr, 11 add/negate/normalizes_to_zero (ignoring special cases) */ 624 haskellsecp256k1_v0_1_0_fe az, z12, u1, u2, s1, s2, h, i, h2, h3, t; 625 SECP256K1_GEJ_VERIFY(a); 626 SECP256K1_GE_VERIFY(b); 627 SECP256K1_FE_VERIFY(bzinv); 628 629 if (a->infinity) { 630 haskellsecp256k1_v0_1_0_fe bzinv2, bzinv3; 631 r->infinity = b->infinity; 632 haskellsecp256k1_v0_1_0_fe_sqr(&bzinv2, bzinv); 633 haskellsecp256k1_v0_1_0_fe_mul(&bzinv3, &bzinv2, bzinv); 634 haskellsecp256k1_v0_1_0_fe_mul(&r->x, &b->x, &bzinv2); 635 haskellsecp256k1_v0_1_0_fe_mul(&r->y, &b->y, &bzinv3); 636 haskellsecp256k1_v0_1_0_fe_set_int(&r->z, 1); 637 SECP256K1_GEJ_VERIFY(r); 638 return; 639 } 640 if (b->infinity) { 641 *r = *a; 642 return; 643 } 644 645 /** We need to calculate (rx,ry,rz) = (ax,ay,az) + (bx,by,1/bzinv). Due to 646 * secp256k1's isomorphism we can multiply the Z coordinates on both sides 647 * by bzinv, and get: (rx,ry,rz*bzinv) = (ax,ay,az*bzinv) + (bx,by,1). 648 * This means that (rx,ry,rz) can be calculated as 649 * (ax,ay,az*bzinv) + (bx,by,1), when not applying the bzinv factor to rz. 650 * The variable az below holds the modified Z coordinate for a, which is used 651 * for the computation of rx and ry, but not for rz. 652 */ 653 haskellsecp256k1_v0_1_0_fe_mul(&az, &a->z, bzinv); 654 655 haskellsecp256k1_v0_1_0_fe_sqr(&z12, &az); 656 u1 = a->x; 657 haskellsecp256k1_v0_1_0_fe_mul(&u2, &b->x, &z12); 658 s1 = a->y; 659 haskellsecp256k1_v0_1_0_fe_mul(&s2, &b->y, &z12); haskellsecp256k1_v0_1_0_fe_mul(&s2, &s2, &az); 660 haskellsecp256k1_v0_1_0_fe_negate(&h, &u1, SECP256K1_GEJ_X_MAGNITUDE_MAX); haskellsecp256k1_v0_1_0_fe_add(&h, &u2); 661 haskellsecp256k1_v0_1_0_fe_negate(&i, &s2, 1); haskellsecp256k1_v0_1_0_fe_add(&i, &s1); 662 if (haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(&h)) { 663 if (haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(&i)) { 664 haskellsecp256k1_v0_1_0_gej_double_var(r, a, NULL); 665 } else { 666 haskellsecp256k1_v0_1_0_gej_set_infinity(r); 667 } 668 return; 669 } 670 671 r->infinity = 0; 672 haskellsecp256k1_v0_1_0_fe_mul(&r->z, &a->z, &h); 673 674 haskellsecp256k1_v0_1_0_fe_sqr(&h2, &h); 675 haskellsecp256k1_v0_1_0_fe_negate(&h2, &h2, 1); 676 haskellsecp256k1_v0_1_0_fe_mul(&h3, &h2, &h); 677 haskellsecp256k1_v0_1_0_fe_mul(&t, &u1, &h2); 678 679 haskellsecp256k1_v0_1_0_fe_sqr(&r->x, &i); 680 haskellsecp256k1_v0_1_0_fe_add(&r->x, &h3); 681 haskellsecp256k1_v0_1_0_fe_add(&r->x, &t); 682 haskellsecp256k1_v0_1_0_fe_add(&r->x, &t); 683 684 haskellsecp256k1_v0_1_0_fe_add(&t, &r->x); 685 haskellsecp256k1_v0_1_0_fe_mul(&r->y, &t, &i); 686 haskellsecp256k1_v0_1_0_fe_mul(&h3, &h3, &s1); 687 haskellsecp256k1_v0_1_0_fe_add(&r->y, &h3); 688 689 SECP256K1_GEJ_VERIFY(r); 690 } 691 692 693 static void haskellsecp256k1_v0_1_0_gej_add_ge(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a, const haskellsecp256k1_v0_1_0_ge *b) { 694 /* Operations: 7 mul, 5 sqr, 21 add/cmov/half/mul_int/negate/normalizes_to_zero */ 695 haskellsecp256k1_v0_1_0_fe zz, u1, u2, s1, s2, t, tt, m, n, q, rr; 696 haskellsecp256k1_v0_1_0_fe m_alt, rr_alt; 697 int degenerate; 698 SECP256K1_GEJ_VERIFY(a); 699 SECP256K1_GE_VERIFY(b); 700 VERIFY_CHECK(!b->infinity); 701 702 /* In: 703 * Eric Brier and Marc Joye, Weierstrass Elliptic Curves and Side-Channel Attacks. 704 * In D. Naccache and P. Paillier, Eds., Public Key Cryptography, vol. 2274 of Lecture Notes in Computer Science, pages 335-345. Springer-Verlag, 2002. 705 * we find as solution for a unified addition/doubling formula: 706 * lambda = ((x1 + x2)^2 - x1 * x2 + a) / (y1 + y2), with a = 0 for secp256k1's curve equation. 707 * x3 = lambda^2 - (x1 + x2) 708 * 2*y3 = lambda * (x1 + x2 - 2 * x3) - (y1 + y2). 709 * 710 * Substituting x_i = Xi / Zi^2 and yi = Yi / Zi^3, for i=1,2,3, gives: 711 * U1 = X1*Z2^2, U2 = X2*Z1^2 712 * S1 = Y1*Z2^3, S2 = Y2*Z1^3 713 * Z = Z1*Z2 714 * T = U1+U2 715 * M = S1+S2 716 * Q = -T*M^2 717 * R = T^2-U1*U2 718 * X3 = R^2+Q 719 * Y3 = -(R*(2*X3+Q)+M^4)/2 720 * Z3 = M*Z 721 * (Note that the paper uses xi = Xi / Zi and yi = Yi / Zi instead.) 722 * 723 * This formula has the benefit of being the same for both addition 724 * of distinct points and doubling. However, it breaks down in the 725 * case that either point is infinity, or that y1 = -y2. We handle 726 * these cases in the following ways: 727 * 728 * - If b is infinity we simply bail by means of a VERIFY_CHECK. 729 * 730 * - If a is infinity, we detect this, and at the end of the 731 * computation replace the result (which will be meaningless, 732 * but we compute to be constant-time) with b.x : b.y : 1. 733 * 734 * - If a = -b, we have y1 = -y2, which is a degenerate case. 735 * But here the answer is infinity, so we simply set the 736 * infinity flag of the result, overriding the computed values 737 * without even needing to cmov. 738 * 739 * - If y1 = -y2 but x1 != x2, which does occur thanks to certain 740 * properties of our curve (specifically, 1 has nontrivial cube 741 * roots in our field, and the curve equation has no x coefficient) 742 * then the answer is not infinity but also not given by the above 743 * equation. In this case, we cmov in place an alternate expression 744 * for lambda. Specifically (y1 - y2)/(x1 - x2). Where both these 745 * expressions for lambda are defined, they are equal, and can be 746 * obtained from each other by multiplication by (y1 + y2)/(y1 + y2) 747 * then substitution of x^3 + 7 for y^2 (using the curve equation). 748 * For all pairs of nonzero points (a, b) at least one is defined, 749 * so this covers everything. 750 */ 751 752 haskellsecp256k1_v0_1_0_fe_sqr(&zz, &a->z); /* z = Z1^2 */ 753 u1 = a->x; /* u1 = U1 = X1*Z2^2 (GEJ_X_M) */ 754 haskellsecp256k1_v0_1_0_fe_mul(&u2, &b->x, &zz); /* u2 = U2 = X2*Z1^2 (1) */ 755 s1 = a->y; /* s1 = S1 = Y1*Z2^3 (GEJ_Y_M) */ 756 haskellsecp256k1_v0_1_0_fe_mul(&s2, &b->y, &zz); /* s2 = Y2*Z1^2 (1) */ 757 haskellsecp256k1_v0_1_0_fe_mul(&s2, &s2, &a->z); /* s2 = S2 = Y2*Z1^3 (1) */ 758 t = u1; haskellsecp256k1_v0_1_0_fe_add(&t, &u2); /* t = T = U1+U2 (GEJ_X_M+1) */ 759 m = s1; haskellsecp256k1_v0_1_0_fe_add(&m, &s2); /* m = M = S1+S2 (GEJ_Y_M+1) */ 760 haskellsecp256k1_v0_1_0_fe_sqr(&rr, &t); /* rr = T^2 (1) */ 761 haskellsecp256k1_v0_1_0_fe_negate(&m_alt, &u2, 1); /* Malt = -X2*Z1^2 (2) */ 762 haskellsecp256k1_v0_1_0_fe_mul(&tt, &u1, &m_alt); /* tt = -U1*U2 (1) */ 763 haskellsecp256k1_v0_1_0_fe_add(&rr, &tt); /* rr = R = T^2-U1*U2 (2) */ 764 /* If lambda = R/M = R/0 we have a problem (except in the "trivial" 765 * case that Z = z1z2 = 0, and this is special-cased later on). */ 766 degenerate = haskellsecp256k1_v0_1_0_fe_normalizes_to_zero(&m); 767 /* This only occurs when y1 == -y2 and x1^3 == x2^3, but x1 != x2. 768 * This means either x1 == beta*x2 or beta*x1 == x2, where beta is 769 * a nontrivial cube root of one. In either case, an alternate 770 * non-indeterminate expression for lambda is (y1 - y2)/(x1 - x2), 771 * so we set R/M equal to this. */ 772 rr_alt = s1; 773 haskellsecp256k1_v0_1_0_fe_mul_int(&rr_alt, 2); /* rr_alt = Y1*Z2^3 - Y2*Z1^3 (GEJ_Y_M*2) */ 774 haskellsecp256k1_v0_1_0_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2 - X2*Z1^2 (GEJ_X_M+2) */ 775 776 haskellsecp256k1_v0_1_0_fe_cmov(&rr_alt, &rr, !degenerate); /* rr_alt (GEJ_Y_M*2) */ 777 haskellsecp256k1_v0_1_0_fe_cmov(&m_alt, &m, !degenerate); /* m_alt (GEJ_X_M+2) */ 778 /* Now Ralt / Malt = lambda and is guaranteed not to be Ralt / 0. 779 * From here on out Ralt and Malt represent the numerator 780 * and denominator of lambda; R and M represent the explicit 781 * expressions x1^2 + x2^2 + x1x2 and y1 + y2. */ 782 haskellsecp256k1_v0_1_0_fe_sqr(&n, &m_alt); /* n = Malt^2 (1) */ 783 haskellsecp256k1_v0_1_0_fe_negate(&q, &t, 784 SECP256K1_GEJ_X_MAGNITUDE_MAX + 1); /* q = -T (GEJ_X_M+2) */ 785 haskellsecp256k1_v0_1_0_fe_mul(&q, &q, &n); /* q = Q = -T*Malt^2 (1) */ 786 /* These two lines use the observation that either M == Malt or M == 0, 787 * so M^3 * Malt is either Malt^4 (which is computed by squaring), or 788 * zero (which is "computed" by cmov). So the cost is one squaring 789 * versus two multiplications. */ 790 haskellsecp256k1_v0_1_0_fe_sqr(&n, &n); /* n = Malt^4 (1) */ 791 haskellsecp256k1_v0_1_0_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (GEJ_Y_M+1) */ 792 haskellsecp256k1_v0_1_0_fe_sqr(&t, &rr_alt); /* t = Ralt^2 (1) */ 793 haskellsecp256k1_v0_1_0_fe_mul(&r->z, &a->z, &m_alt); /* r->z = Z3 = Malt*Z (1) */ 794 haskellsecp256k1_v0_1_0_fe_add(&t, &q); /* t = Ralt^2 + Q (2) */ 795 r->x = t; /* r->x = X3 = Ralt^2 + Q (2) */ 796 haskellsecp256k1_v0_1_0_fe_mul_int(&t, 2); /* t = 2*X3 (4) */ 797 haskellsecp256k1_v0_1_0_fe_add(&t, &q); /* t = 2*X3 + Q (5) */ 798 haskellsecp256k1_v0_1_0_fe_mul(&t, &t, &rr_alt); /* t = Ralt*(2*X3 + Q) (1) */ 799 haskellsecp256k1_v0_1_0_fe_add(&t, &n); /* t = Ralt*(2*X3 + Q) + M^3*Malt (GEJ_Y_M+2) */ 800 haskellsecp256k1_v0_1_0_fe_negate(&r->y, &t, 801 SECP256K1_GEJ_Y_MAGNITUDE_MAX + 2); /* r->y = -(Ralt*(2*X3 + Q) + M^3*Malt) (GEJ_Y_M+3) */ 802 haskellsecp256k1_v0_1_0_fe_half(&r->y); /* r->y = Y3 = -(Ralt*(2*X3 + Q) + M^3*Malt)/2 ((GEJ_Y_M+3)/2 + 1) */ 803 804 /* In case a->infinity == 1, replace r with (b->x, b->y, 1). */ 805 haskellsecp256k1_v0_1_0_fe_cmov(&r->x, &b->x, a->infinity); 806 haskellsecp256k1_v0_1_0_fe_cmov(&r->y, &b->y, a->infinity); 807 haskellsecp256k1_v0_1_0_fe_cmov(&r->z, &haskellsecp256k1_v0_1_0_fe_one, a->infinity); 808 809 /* Set r->infinity if r->z is 0. 810 * 811 * If a->infinity is set, then r->infinity = (r->z == 0) = (1 == 0) = false, 812 * which is correct because the function assumes that b is not infinity. 813 * 814 * Now assume !a->infinity. This implies Z = Z1 != 0. 815 * 816 * Case y1 = -y2: 817 * In this case we could have a = -b, namely if x1 = x2. 818 * We have degenerate = true, r->z = (x1 - x2) * Z. 819 * Then r->infinity = ((x1 - x2)Z == 0) = (x1 == x2) = (a == -b). 820 * 821 * Case y1 != -y2: 822 * In this case, we can't have a = -b. 823 * We have degenerate = false, r->z = (y1 + y2) * Z. 824 * Then r->infinity = ((y1 + y2)Z == 0) = (y1 == -y2) = false. */ 825 r->infinity = haskellsecp256k1_v0_1_0_fe_normalizes_to_zero(&r->z); 826 827 SECP256K1_GEJ_VERIFY(r); 828 } 829 830 static void haskellsecp256k1_v0_1_0_gej_rescale(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_fe *s) { 831 /* Operations: 4 mul, 1 sqr */ 832 haskellsecp256k1_v0_1_0_fe zz; 833 SECP256K1_GEJ_VERIFY(r); 834 SECP256K1_FE_VERIFY(s); 835 VERIFY_CHECK(!haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(s)); 836 837 haskellsecp256k1_v0_1_0_fe_sqr(&zz, s); 838 haskellsecp256k1_v0_1_0_fe_mul(&r->x, &r->x, &zz); /* r->x *= s^2 */ 839 haskellsecp256k1_v0_1_0_fe_mul(&r->y, &r->y, &zz); 840 haskellsecp256k1_v0_1_0_fe_mul(&r->y, &r->y, s); /* r->y *= s^3 */ 841 haskellsecp256k1_v0_1_0_fe_mul(&r->z, &r->z, s); /* r->z *= s */ 842 843 SECP256K1_GEJ_VERIFY(r); 844 } 845 846 static void haskellsecp256k1_v0_1_0_ge_to_storage(haskellsecp256k1_v0_1_0_ge_storage *r, const haskellsecp256k1_v0_1_0_ge *a) { 847 haskellsecp256k1_v0_1_0_fe x, y; 848 SECP256K1_GE_VERIFY(a); 849 VERIFY_CHECK(!a->infinity); 850 851 x = a->x; 852 haskellsecp256k1_v0_1_0_fe_normalize(&x); 853 y = a->y; 854 haskellsecp256k1_v0_1_0_fe_normalize(&y); 855 haskellsecp256k1_v0_1_0_fe_to_storage(&r->x, &x); 856 haskellsecp256k1_v0_1_0_fe_to_storage(&r->y, &y); 857 } 858 859 static void haskellsecp256k1_v0_1_0_ge_from_storage(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_ge_storage *a) { 860 haskellsecp256k1_v0_1_0_fe_from_storage(&r->x, &a->x); 861 haskellsecp256k1_v0_1_0_fe_from_storage(&r->y, &a->y); 862 r->infinity = 0; 863 864 SECP256K1_GE_VERIFY(r); 865 } 866 867 static SECP256K1_INLINE void haskellsecp256k1_v0_1_0_gej_cmov(haskellsecp256k1_v0_1_0_gej *r, const haskellsecp256k1_v0_1_0_gej *a, int flag) { 868 SECP256K1_GEJ_VERIFY(r); 869 SECP256K1_GEJ_VERIFY(a); 870 871 haskellsecp256k1_v0_1_0_fe_cmov(&r->x, &a->x, flag); 872 haskellsecp256k1_v0_1_0_fe_cmov(&r->y, &a->y, flag); 873 haskellsecp256k1_v0_1_0_fe_cmov(&r->z, &a->z, flag); 874 r->infinity ^= (r->infinity ^ a->infinity) & flag; 875 876 SECP256K1_GEJ_VERIFY(r); 877 } 878 879 static SECP256K1_INLINE void haskellsecp256k1_v0_1_0_ge_storage_cmov(haskellsecp256k1_v0_1_0_ge_storage *r, const haskellsecp256k1_v0_1_0_ge_storage *a, int flag) { 880 haskellsecp256k1_v0_1_0_fe_storage_cmov(&r->x, &a->x, flag); 881 haskellsecp256k1_v0_1_0_fe_storage_cmov(&r->y, &a->y, flag); 882 } 883 884 static void haskellsecp256k1_v0_1_0_ge_mul_lambda(haskellsecp256k1_v0_1_0_ge *r, const haskellsecp256k1_v0_1_0_ge *a) { 885 SECP256K1_GE_VERIFY(a); 886 887 *r = *a; 888 haskellsecp256k1_v0_1_0_fe_mul(&r->x, &r->x, &haskellsecp256k1_v0_1_0_const_beta); 889 890 SECP256K1_GE_VERIFY(r); 891 } 892 893 static int haskellsecp256k1_v0_1_0_ge_is_in_correct_subgroup(const haskellsecp256k1_v0_1_0_ge* ge) { 894 #ifdef EXHAUSTIVE_TEST_ORDER 895 haskellsecp256k1_v0_1_0_gej out; 896 int i; 897 SECP256K1_GE_VERIFY(ge); 898 899 /* A very simple EC multiplication ladder that avoids a dependency on ecmult. */ 900 haskellsecp256k1_v0_1_0_gej_set_infinity(&out); 901 for (i = 0; i < 32; ++i) { 902 haskellsecp256k1_v0_1_0_gej_double_var(&out, &out, NULL); 903 if ((((uint32_t)EXHAUSTIVE_TEST_ORDER) >> (31 - i)) & 1) { 904 haskellsecp256k1_v0_1_0_gej_add_ge_var(&out, &out, ge, NULL); 905 } 906 } 907 return haskellsecp256k1_v0_1_0_gej_is_infinity(&out); 908 #else 909 SECP256K1_GE_VERIFY(ge); 910 911 (void)ge; 912 /* The real secp256k1 group has cofactor 1, so the subgroup is the entire curve. */ 913 return 1; 914 #endif 915 } 916 917 static int haskellsecp256k1_v0_1_0_ge_x_on_curve_var(const haskellsecp256k1_v0_1_0_fe *x) { 918 haskellsecp256k1_v0_1_0_fe c; 919 haskellsecp256k1_v0_1_0_fe_sqr(&c, x); 920 haskellsecp256k1_v0_1_0_fe_mul(&c, &c, x); 921 haskellsecp256k1_v0_1_0_fe_add_int(&c, SECP256K1_B); 922 return haskellsecp256k1_v0_1_0_fe_is_square_var(&c); 923 } 924 925 static int haskellsecp256k1_v0_1_0_ge_x_frac_on_curve_var(const haskellsecp256k1_v0_1_0_fe *xn, const haskellsecp256k1_v0_1_0_fe *xd) { 926 /* We want to determine whether (xn/xd) is on the curve. 927 * 928 * (xn/xd)^3 + 7 is square <=> xd*xn^3 + 7*xd^4 is square (multiplying by xd^4, a square). 929 */ 930 haskellsecp256k1_v0_1_0_fe r, t; 931 VERIFY_CHECK(!haskellsecp256k1_v0_1_0_fe_normalizes_to_zero_var(xd)); 932 933 haskellsecp256k1_v0_1_0_fe_mul(&r, xd, xn); /* r = xd*xn */ 934 haskellsecp256k1_v0_1_0_fe_sqr(&t, xn); /* t = xn^2 */ 935 haskellsecp256k1_v0_1_0_fe_mul(&r, &r, &t); /* r = xd*xn^3 */ 936 haskellsecp256k1_v0_1_0_fe_sqr(&t, xd); /* t = xd^2 */ 937 haskellsecp256k1_v0_1_0_fe_sqr(&t, &t); /* t = xd^4 */ 938 VERIFY_CHECK(SECP256K1_B <= 31); 939 haskellsecp256k1_v0_1_0_fe_mul_int(&t, SECP256K1_B); /* t = 7*xd^4 */ 940 haskellsecp256k1_v0_1_0_fe_add(&r, &t); /* r = xd*xn^3 + 7*xd^4 */ 941 return haskellsecp256k1_v0_1_0_fe_is_square_var(&r); 942 } 943 944 #endif /* SECP256K1_GROUP_IMPL_H */