1 /* 2 * Copyright 2014-2016 The OpenSSL Project Authors. All Rights Reserved. 3 * Copyright (c) 2014, Intel Corporation. All Rights Reserved. 4 * 5 * Licensed under the OpenSSL license (the "License"). You may not use 6 * this file except in compliance with the License. You can obtain a copy 7 * in the file LICENSE in the source distribution or at 8 * https://www.openssl.org/source/license.html 9 * 10 * Originally written by Shay Gueron (1, 2), and Vlad Krasnov (1) 11 * (1) Intel Corporation, Israel Development Center, Haifa, Israel 12 * (2) University of Haifa, Israel 13 * 14 * Reference: 15 * S.Gueron and V.Krasnov, "Fast Prime Field Elliptic Curve Cryptography with 16 * 256 Bit Primes" 17 */ 18 19 #include <openssl/ec.h> 20 21 #include <assert.h> 22 #include <stdint.h> 23 #include <string.h> 24 25 #include <openssl/bn.h> 26 #include <openssl/cpu.h> 27 #include <openssl/crypto.h> 28 #include <openssl/err.h> 29 30 #include "../bn/internal.h" 31 #include "../delocate.h" 32 #include "../../internal.h" 33 #include "internal.h" 34 #include "p256-x86_64.h" 35 36 37 #if !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64) && \ 38 !defined(OPENSSL_SMALL) 39 40 typedef P256_POINT_AFFINE PRECOMP256_ROW[64]; 41 42 // One converted into the Montgomery domain 43 static const BN_ULONG ONE[P256_LIMBS] = { 44 TOBN(0x00000000, 0x00000001), TOBN(0xffffffff, 0x00000000), 45 TOBN(0xffffffff, 0xffffffff), TOBN(0x00000000, 0xfffffffe), 46 }; 47 48 // Precomputed tables for the default generator 49 #include "p256-x86_64-table.h" 50 51 // Recode window to a signed digit, see util-64.c for details 52 static unsigned booth_recode_w5(unsigned in) { 53 unsigned s, d; 54 55 s = ~((in >> 5) - 1); 56 d = (1 << 6) - in - 1; 57 d = (d & s) | (in & ~s); 58 d = (d >> 1) + (d & 1); 59 60 return (d << 1) + (s & 1); 61 } 62 63 static unsigned booth_recode_w7(unsigned in) { 64 unsigned s, d; 65 66 s = ~((in >> 7) - 1); 67 d = (1 << 8) - in - 1; 68 d = (d & s) | (in & ~s); 69 d = (d >> 1) + (d & 1); 70 71 return (d << 1) + (s & 1); 72 } 73 74 // copy_conditional copies |src| to |dst| if |move| is one and leaves it as-is 75 // if |move| is zero. 76 // 77 // WARNING: this breaks the usual convention of constant-time functions 78 // returning masks. 79 static void copy_conditional(BN_ULONG dst[P256_LIMBS], 80 const BN_ULONG src[P256_LIMBS], BN_ULONG move) { 81 BN_ULONG mask1 = ((BN_ULONG)0) - move; 82 BN_ULONG mask2 = ~mask1; 83 84 dst[0] = (src[0] & mask1) ^ (dst[0] & mask2); 85 dst[1] = (src[1] & mask1) ^ (dst[1] & mask2); 86 dst[2] = (src[2] & mask1) ^ (dst[2] & mask2); 87 dst[3] = (src[3] & mask1) ^ (dst[3] & mask2); 88 if (P256_LIMBS == 8) { 89 dst[4] = (src[4] & mask1) ^ (dst[4] & mask2); 90 dst[5] = (src[5] & mask1) ^ (dst[5] & mask2); 91 dst[6] = (src[6] & mask1) ^ (dst[6] & mask2); 92 dst[7] = (src[7] & mask1) ^ (dst[7] & mask2); 93 } 94 } 95 96 // is_not_zero returns one iff in != 0 and zero otherwise. 97 // 98 // WARNING: this breaks the usual convention of constant-time functions 99 // returning masks. 100 // 101 // (define-fun is_not_zero ((in (_ BitVec 64))) (_ BitVec 64) 102 // (bvlshr (bvor in (bvsub #x0000000000000000 in)) #x000000000000003f) 103 // ) 104 // 105 // (declare-fun x () (_ BitVec 64)) 106 // 107 // (assert (and (= x #x0000000000000000) (= (is_not_zero x) #x0000000000000001))) 108 // (check-sat) 109 // 110 // (assert (and (not (= x #x0000000000000000)) (= (is_not_zero x) #x0000000000000000))) 111 // (check-sat) 112 // 113 static BN_ULONG is_not_zero(BN_ULONG in) { 114 in |= (0 - in); 115 in >>= BN_BITS2 - 1; 116 return in; 117 } 118 119 // ecp_nistz256_mod_inverse_mont sets |r| to (|in| * 2^-256)^-1 * 2^256 mod p. 120 // That is, |r| is the modular inverse of |in| for input and output in the 121 // Montgomery domain. 122 static void ecp_nistz256_mod_inverse_mont(BN_ULONG r[P256_LIMBS], 123 const BN_ULONG in[P256_LIMBS]) { 124 /* The poly is ffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff 125 ffffffff 126 We use FLT and used poly-2 as exponent */ 127 BN_ULONG p2[P256_LIMBS]; 128 BN_ULONG p4[P256_LIMBS]; 129 BN_ULONG p8[P256_LIMBS]; 130 BN_ULONG p16[P256_LIMBS]; 131 BN_ULONG p32[P256_LIMBS]; 132 BN_ULONG res[P256_LIMBS]; 133 int i; 134 135 ecp_nistz256_sqr_mont(res, in); 136 ecp_nistz256_mul_mont(p2, res, in); // 3*p 137 138 ecp_nistz256_sqr_mont(res, p2); 139 ecp_nistz256_sqr_mont(res, res); 140 ecp_nistz256_mul_mont(p4, res, p2); // f*p 141 142 ecp_nistz256_sqr_mont(res, p4); 143 ecp_nistz256_sqr_mont(res, res); 144 ecp_nistz256_sqr_mont(res, res); 145 ecp_nistz256_sqr_mont(res, res); 146 ecp_nistz256_mul_mont(p8, res, p4); // ff*p 147 148 ecp_nistz256_sqr_mont(res, p8); 149 for (i = 0; i < 7; i++) { 150 ecp_nistz256_sqr_mont(res, res); 151 } 152 ecp_nistz256_mul_mont(p16, res, p8); // ffff*p 153 154 ecp_nistz256_sqr_mont(res, p16); 155 for (i = 0; i < 15; i++) { 156 ecp_nistz256_sqr_mont(res, res); 157 } 158 ecp_nistz256_mul_mont(p32, res, p16); // ffffffff*p 159 160 ecp_nistz256_sqr_mont(res, p32); 161 for (i = 0; i < 31; i++) { 162 ecp_nistz256_sqr_mont(res, res); 163 } 164 ecp_nistz256_mul_mont(res, res, in); 165 166 for (i = 0; i < 32 * 4; i++) { 167 ecp_nistz256_sqr_mont(res, res); 168 } 169 ecp_nistz256_mul_mont(res, res, p32); 170 171 for (i = 0; i < 32; i++) { 172 ecp_nistz256_sqr_mont(res, res); 173 } 174 ecp_nistz256_mul_mont(res, res, p32); 175 176 for (i = 0; i < 16; i++) { 177 ecp_nistz256_sqr_mont(res, res); 178 } 179 ecp_nistz256_mul_mont(res, res, p16); 180 181 for (i = 0; i < 8; i++) { 182 ecp_nistz256_sqr_mont(res, res); 183 } 184 ecp_nistz256_mul_mont(res, res, p8); 185 186 ecp_nistz256_sqr_mont(res, res); 187 ecp_nistz256_sqr_mont(res, res); 188 ecp_nistz256_sqr_mont(res, res); 189 ecp_nistz256_sqr_mont(res, res); 190 ecp_nistz256_mul_mont(res, res, p4); 191 192 ecp_nistz256_sqr_mont(res, res); 193 ecp_nistz256_sqr_mont(res, res); 194 ecp_nistz256_mul_mont(res, res, p2); 195 196 ecp_nistz256_sqr_mont(res, res); 197 ecp_nistz256_sqr_mont(res, res); 198 ecp_nistz256_mul_mont(r, res, in); 199 } 200 201 // r = p * p_scalar 202 static void ecp_nistz256_windowed_mul(const EC_GROUP *group, P256_POINT *r, 203 const EC_RAW_POINT *p, 204 const EC_SCALAR *p_scalar) { 205 assert(p != NULL); 206 assert(p_scalar != NULL); 207 assert(group->field.width == P256_LIMBS); 208 209 static const unsigned kWindowSize = 5; 210 static const unsigned kMask = (1 << (5 /* kWindowSize */ + 1)) - 1; 211 212 // A |P256_POINT| is (3 * 32) = 96 bytes, and the 64-byte alignment should 213 // add no more than 63 bytes of overhead. Thus, |table| should require 214 // ~1599 ((96 * 16) + 63) bytes of stack space. 215 alignas(64) P256_POINT table[16]; 216 uint8_t p_str[33]; 217 OPENSSL_memcpy(p_str, p_scalar->bytes, 32); 218 p_str[32] = 0; 219 220 // table[0] is implicitly (0,0,0) (the point at infinity), therefore it is 221 // not stored. All other values are actually stored with an offset of -1 in 222 // table. 223 P256_POINT *row = table; 224 assert(group->field.width == P256_LIMBS); 225 OPENSSL_memcpy(row[1 - 1].X, p->X.words, P256_LIMBS * sizeof(BN_ULONG)); 226 OPENSSL_memcpy(row[1 - 1].Y, p->Y.words, P256_LIMBS * sizeof(BN_ULONG)); 227 OPENSSL_memcpy(row[1 - 1].Z, p->Z.words, P256_LIMBS * sizeof(BN_ULONG)); 228 229 ecp_nistz256_point_double(&row[2 - 1], &row[1 - 1]); 230 ecp_nistz256_point_add(&row[3 - 1], &row[2 - 1], &row[1 - 1]); 231 ecp_nistz256_point_double(&row[4 - 1], &row[2 - 1]); 232 ecp_nistz256_point_double(&row[6 - 1], &row[3 - 1]); 233 ecp_nistz256_point_double(&row[8 - 1], &row[4 - 1]); 234 ecp_nistz256_point_double(&row[12 - 1], &row[6 - 1]); 235 ecp_nistz256_point_add(&row[5 - 1], &row[4 - 1], &row[1 - 1]); 236 ecp_nistz256_point_add(&row[7 - 1], &row[6 - 1], &row[1 - 1]); 237 ecp_nistz256_point_add(&row[9 - 1], &row[8 - 1], &row[1 - 1]); 238 ecp_nistz256_point_add(&row[13 - 1], &row[12 - 1], &row[1 - 1]); 239 ecp_nistz256_point_double(&row[14 - 1], &row[7 - 1]); 240 ecp_nistz256_point_double(&row[10 - 1], &row[5 - 1]); 241 ecp_nistz256_point_add(&row[15 - 1], &row[14 - 1], &row[1 - 1]); 242 ecp_nistz256_point_add(&row[11 - 1], &row[10 - 1], &row[1 - 1]); 243 ecp_nistz256_point_double(&row[16 - 1], &row[8 - 1]); 244 245 BN_ULONG tmp[P256_LIMBS]; 246 alignas(32) P256_POINT h; 247 unsigned index = 255; 248 unsigned wvalue = p_str[(index - 1) / 8]; 249 wvalue = (wvalue >> ((index - 1) % 8)) & kMask; 250 251 ecp_nistz256_select_w5(r, table, booth_recode_w5(wvalue) >> 1); 252 253 while (index >= 5) { 254 if (index != 255) { 255 unsigned off = (index - 1) / 8; 256 257 wvalue = p_str[off] | p_str[off + 1] << 8; 258 wvalue = (wvalue >> ((index - 1) % 8)) & kMask; 259 260 wvalue = booth_recode_w5(wvalue); 261 262 ecp_nistz256_select_w5(&h, table, wvalue >> 1); 263 264 ecp_nistz256_neg(tmp, h.Y); 265 copy_conditional(h.Y, tmp, (wvalue & 1)); 266 267 ecp_nistz256_point_add(r, r, &h); 268 } 269 270 index -= kWindowSize; 271 272 ecp_nistz256_point_double(r, r); 273 ecp_nistz256_point_double(r, r); 274 ecp_nistz256_point_double(r, r); 275 ecp_nistz256_point_double(r, r); 276 ecp_nistz256_point_double(r, r); 277 } 278 279 // Final window 280 wvalue = p_str[0]; 281 wvalue = (wvalue << 1) & kMask; 282 283 wvalue = booth_recode_w5(wvalue); 284 285 ecp_nistz256_select_w5(&h, table, wvalue >> 1); 286 287 ecp_nistz256_neg(tmp, h.Y); 288 copy_conditional(h.Y, tmp, wvalue & 1); 289 290 ecp_nistz256_point_add(r, r, &h); 291 } 292 293 typedef union { 294 P256_POINT p; 295 P256_POINT_AFFINE a; 296 } p256_point_union_t; 297 298 static unsigned calc_first_wvalue(unsigned *index, const uint8_t p_str[33]) { 299 static const unsigned kWindowSize = 7; 300 static const unsigned kMask = (1 << (7 /* kWindowSize */ + 1)) - 1; 301 *index = kWindowSize; 302 303 unsigned wvalue = (p_str[0] << 1) & kMask; 304 return booth_recode_w7(wvalue); 305 } 306 307 static unsigned calc_wvalue(unsigned *index, const uint8_t p_str[33]) { 308 static const unsigned kWindowSize = 7; 309 static const unsigned kMask = (1 << (7 /* kWindowSize */ + 1)) - 1; 310 311 const unsigned off = (*index - 1) / 8; 312 unsigned wvalue = p_str[off] | p_str[off + 1] << 8; 313 wvalue = (wvalue >> ((*index - 1) % 8)) & kMask; 314 *index += kWindowSize; 315 316 return booth_recode_w7(wvalue); 317 } 318 319 static void mul_p_add_and_store(const EC_GROUP *group, EC_RAW_POINT *r, 320 const EC_SCALAR *g_scalar, 321 const EC_RAW_POINT *p_, 322 const EC_SCALAR *p_scalar, 323 p256_point_union_t *t, p256_point_union_t *p) { 324 const int p_is_infinity = g_scalar == NULL; 325 if (p_scalar != NULL) { 326 P256_POINT *out = &t->p; 327 if (p_is_infinity) { 328 out = &p->p; 329 } 330 331 ecp_nistz256_windowed_mul(group, out, p_, p_scalar); 332 if (!p_is_infinity) { 333 ecp_nistz256_point_add(&p->p, &p->p, out); 334 } 335 } 336 337 assert(group->field.width == P256_LIMBS); 338 OPENSSL_memcpy(r->X.words, p->p.X, P256_LIMBS * sizeof(BN_ULONG)); 339 OPENSSL_memcpy(r->Y.words, p->p.Y, P256_LIMBS * sizeof(BN_ULONG)); 340 OPENSSL_memcpy(r->Z.words, p->p.Z, P256_LIMBS * sizeof(BN_ULONG)); 341 } 342 343 static void ecp_nistz256_points_mul(const EC_GROUP *group, EC_RAW_POINT *r, 344 const EC_SCALAR *g_scalar, 345 const EC_RAW_POINT *p_, 346 const EC_SCALAR *p_scalar) { 347 assert((p_ != NULL) == (p_scalar != NULL)); 348 349 alignas(32) p256_point_union_t t, p; 350 351 if (g_scalar != NULL) { 352 uint8_t p_str[33]; 353 OPENSSL_memcpy(p_str, g_scalar->bytes, 32); 354 p_str[32] = 0; 355 356 // First window 357 unsigned index = 0; 358 unsigned wvalue = calc_first_wvalue(&index, p_str); 359 360 ecp_nistz256_select_w7(&p.a, ecp_nistz256_precomputed[0], wvalue >> 1); 361 362 ecp_nistz256_neg(p.p.Z, p.p.Y); 363 copy_conditional(p.p.Y, p.p.Z, wvalue & 1); 364 365 // Convert |p| from affine to Jacobian coordinates. We set Z to zero if |p| 366 // is infinity and |ONE| otherwise. |p| was computed from the table, so it 367 // is infinity iff |wvalue >> 1| is zero. 368 OPENSSL_memset(p.p.Z, 0, sizeof(p.p.Z)); 369 copy_conditional(p.p.Z, ONE, is_not_zero(wvalue >> 1)); 370 371 for (int i = 1; i < 37; i++) { 372 wvalue = calc_wvalue(&index, p_str); 373 374 ecp_nistz256_select_w7(&t.a, ecp_nistz256_precomputed[i], wvalue >> 1); 375 376 ecp_nistz256_neg(t.p.Z, t.a.Y); 377 copy_conditional(t.a.Y, t.p.Z, wvalue & 1); 378 379 // Note |ecp_nistz256_point_add_affine| does not work if |p.p| and |t.a| 380 // are the same non-infinity point, so it is important that we compute the 381 // |g_scalar| term before the |p_scalar| term. 382 ecp_nistz256_point_add_affine(&p.p, &p.p, &t.a); 383 } 384 } 385 386 mul_p_add_and_store(group, r, g_scalar, p_, p_scalar, &t, &p); 387 } 388 389 static void ecp_nistz256_points_mul_public(const EC_GROUP *group, 390 EC_RAW_POINT *r, 391 const EC_SCALAR *g_scalar, 392 const EC_RAW_POINT *p_, 393 const EC_SCALAR *p_scalar) { 394 assert(p_ != NULL && p_scalar != NULL && g_scalar != NULL); 395 396 alignas(32) p256_point_union_t t, p; 397 uint8_t p_str[33]; 398 OPENSSL_memcpy(p_str, g_scalar->bytes, 32); 399 p_str[32] = 0; 400 401 // First window 402 unsigned index = 0; 403 unsigned wvalue = calc_first_wvalue(&index, p_str); 404 405 // Convert |p| from affine to Jacobian coordinates. We set Z to zero if |p| 406 // is infinity and |ONE| otherwise. |p| was computed from the table, so it 407 // is infinity iff |wvalue >> 1| is zero. 408 if ((wvalue >> 1) != 0) { 409 OPENSSL_memcpy(&p.a, &ecp_nistz256_precomputed[0][(wvalue >> 1) - 1], 410 sizeof(p.a)); 411 OPENSSL_memcpy(&p.p.Z, ONE, sizeof(p.p.Z)); 412 } else { 413 OPENSSL_memset(&p.a, 0, sizeof(p.a)); 414 OPENSSL_memset(p.p.Z, 0, sizeof(p.p.Z)); 415 } 416 417 if ((wvalue & 1) == 1) { 418 ecp_nistz256_neg(p.p.Y, p.p.Y); 419 } 420 421 for (int i = 1; i < 37; i++) { 422 wvalue = calc_wvalue(&index, p_str); 423 424 if ((wvalue >> 1) == 0) { 425 continue; 426 } 427 428 OPENSSL_memcpy(&t.a, &ecp_nistz256_precomputed[i][(wvalue >> 1) - 1], 429 sizeof(p.a)); 430 431 if ((wvalue & 1) == 1) { 432 ecp_nistz256_neg(t.a.Y, t.a.Y); 433 } 434 435 // Note |ecp_nistz256_point_add_affine| does not work if |p.p| and |t.a| 436 // are the same non-infinity point, so it is important that we compute the 437 // |g_scalar| term before the |p_scalar| term. 438 ecp_nistz256_point_add_affine(&p.p, &p.p, &t.a); 439 } 440 441 mul_p_add_and_store(group, r, g_scalar, p_, p_scalar, &t, &p); 442 } 443 444 static int ecp_nistz256_get_affine(const EC_GROUP *group, 445 const EC_RAW_POINT *point, EC_FELEM *x, 446 EC_FELEM *y) { 447 if (ec_GFp_simple_is_at_infinity(group, point)) { 448 OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY); 449 return 0; 450 } 451 452 BN_ULONG z_inv2[P256_LIMBS]; 453 BN_ULONG z_inv3[P256_LIMBS]; 454 assert(group->field.width == P256_LIMBS); 455 ecp_nistz256_mod_inverse_mont(z_inv3, point->Z.words); 456 ecp_nistz256_sqr_mont(z_inv2, z_inv3); 457 458 // Instead of using |ecp_nistz256_from_mont| to convert the |x| coordinate 459 // and then calling |ecp_nistz256_from_mont| again to convert the |y| 460 // coordinate below, convert the common factor |z_inv2| once now, saving one 461 // reduction. 462 ecp_nistz256_from_mont(z_inv2, z_inv2); 463 464 if (x != NULL) { 465 ecp_nistz256_mul_mont(x->words, z_inv2, point->X.words); 466 } 467 468 if (y != NULL) { 469 ecp_nistz256_mul_mont(z_inv3, z_inv3, z_inv2); 470 ecp_nistz256_mul_mont(y->words, z_inv3, point->Y.words); 471 } 472 473 return 1; 474 } 475 476 static void ecp_nistz256_add(const EC_GROUP *group, EC_RAW_POINT *r, 477 const EC_RAW_POINT *a_, const EC_RAW_POINT *b_) { 478 P256_POINT a, b; 479 OPENSSL_memcpy(a.X, a_->X.words, P256_LIMBS * sizeof(BN_ULONG)); 480 OPENSSL_memcpy(a.Y, a_->Y.words, P256_LIMBS * sizeof(BN_ULONG)); 481 OPENSSL_memcpy(a.Z, a_->Z.words, P256_LIMBS * sizeof(BN_ULONG)); 482 OPENSSL_memcpy(b.X, b_->X.words, P256_LIMBS * sizeof(BN_ULONG)); 483 OPENSSL_memcpy(b.Y, b_->Y.words, P256_LIMBS * sizeof(BN_ULONG)); 484 OPENSSL_memcpy(b.Z, b_->Z.words, P256_LIMBS * sizeof(BN_ULONG)); 485 ecp_nistz256_point_add(&a, &a, &b); 486 OPENSSL_memcpy(r->X.words, a.X, P256_LIMBS * sizeof(BN_ULONG)); 487 OPENSSL_memcpy(r->Y.words, a.Y, P256_LIMBS * sizeof(BN_ULONG)); 488 OPENSSL_memcpy(r->Z.words, a.Z, P256_LIMBS * sizeof(BN_ULONG)); 489 } 490 491 static void ecp_nistz256_dbl(const EC_GROUP *group, EC_RAW_POINT *r, 492 const EC_RAW_POINT *a_) { 493 P256_POINT a; 494 OPENSSL_memcpy(a.X, a_->X.words, P256_LIMBS * sizeof(BN_ULONG)); 495 OPENSSL_memcpy(a.Y, a_->Y.words, P256_LIMBS * sizeof(BN_ULONG)); 496 OPENSSL_memcpy(a.Z, a_->Z.words, P256_LIMBS * sizeof(BN_ULONG)); 497 ecp_nistz256_point_double(&a, &a); 498 OPENSSL_memcpy(r->X.words, a.X, P256_LIMBS * sizeof(BN_ULONG)); 499 OPENSSL_memcpy(r->Y.words, a.Y, P256_LIMBS * sizeof(BN_ULONG)); 500 OPENSSL_memcpy(r->Z.words, a.Z, P256_LIMBS * sizeof(BN_ULONG)); 501 } 502 503 static void ecp_nistz256_inv_mod_ord(const EC_GROUP *group, EC_SCALAR *out, 504 const EC_SCALAR *in) { 505 // table[i] stores a power of |in| corresponding to the matching enum value. 506 enum { 507 // The following indices specify the power in binary. 508 i_1 = 0, 509 i_10, 510 i_11, 511 i_101, 512 i_111, 513 i_1010, 514 i_1111, 515 i_10101, 516 i_101010, 517 i_101111, 518 // The following indices specify 2^N-1, or N ones in a row. 519 i_x6, 520 i_x8, 521 i_x16, 522 i_x32 523 }; 524 BN_ULONG table[15][P256_LIMBS]; 525 526 // https://briansmith.org/ecc-inversion-addition-chains-01#p256_scalar_inversion 527 // 528 // Even though this code path spares 12 squarings, 4.5%, and 13 529 // multiplications, 25%, the overall sign operation is not that much faster, 530 // not more that 2%. Most of the performance of this function comes from the 531 // scalar operations. 532 533 // Pre-calculate powers. 534 OPENSSL_memcpy(table[i_1], in->words, P256_LIMBS * sizeof(BN_ULONG)); 535 536 ecp_nistz256_ord_sqr_mont(table[i_10], table[i_1], 1); 537 538 ecp_nistz256_ord_mul_mont(table[i_11], table[i_1], table[i_10]); 539 540 ecp_nistz256_ord_mul_mont(table[i_101], table[i_11], table[i_10]); 541 542 ecp_nistz256_ord_mul_mont(table[i_111], table[i_101], table[i_10]); 543 544 ecp_nistz256_ord_sqr_mont(table[i_1010], table[i_101], 1); 545 546 ecp_nistz256_ord_mul_mont(table[i_1111], table[i_1010], table[i_101]); 547 548 ecp_nistz256_ord_sqr_mont(table[i_10101], table[i_1010], 1); 549 ecp_nistz256_ord_mul_mont(table[i_10101], table[i_10101], table[i_1]); 550 551 ecp_nistz256_ord_sqr_mont(table[i_101010], table[i_10101], 1); 552 553 ecp_nistz256_ord_mul_mont(table[i_101111], table[i_101010], table[i_101]); 554 555 ecp_nistz256_ord_mul_mont(table[i_x6], table[i_101010], table[i_10101]); 556 557 ecp_nistz256_ord_sqr_mont(table[i_x8], table[i_x6], 2); 558 ecp_nistz256_ord_mul_mont(table[i_x8], table[i_x8], table[i_11]); 559 560 ecp_nistz256_ord_sqr_mont(table[i_x16], table[i_x8], 8); 561 ecp_nistz256_ord_mul_mont(table[i_x16], table[i_x16], table[i_x8]); 562 563 ecp_nistz256_ord_sqr_mont(table[i_x32], table[i_x16], 16); 564 ecp_nistz256_ord_mul_mont(table[i_x32], table[i_x32], table[i_x16]); 565 566 // Compute |in| raised to the order-2. 567 ecp_nistz256_ord_sqr_mont(out->words, table[i_x32], 64); 568 ecp_nistz256_ord_mul_mont(out->words, out->words, table[i_x32]); 569 static const struct { 570 uint8_t p, i; 571 } kChain[27] = {{32, i_x32}, {6, i_101111}, {5, i_111}, {4, i_11}, 572 {5, i_1111}, {5, i_10101}, {4, i_101}, {3, i_101}, 573 {3, i_101}, {5, i_111}, {9, i_101111}, {6, i_1111}, 574 {2, i_1}, {5, i_1}, {6, i_1111}, {5, i_111}, 575 {4, i_111}, {5, i_111}, {5, i_101}, {3, i_11}, 576 {10, i_101111}, {2, i_11}, {5, i_11}, {5, i_11}, 577 {3, i_1}, {7, i_10101}, {6, i_1111}}; 578 for (size_t i = 0; i < OPENSSL_ARRAY_SIZE(kChain); i++) { 579 ecp_nistz256_ord_sqr_mont(out->words, out->words, kChain[i].p); 580 ecp_nistz256_ord_mul_mont(out->words, out->words, table[kChain[i].i]); 581 } 582 } 583 584 static int ecp_nistz256_mont_inv_mod_ord_vartime(const EC_GROUP *group, 585 EC_SCALAR *out, 586 const EC_SCALAR *in) { 587 if ((OPENSSL_ia32cap_get()[1] & (1 << 28)) == 0) { 588 // No AVX support; fallback to generic code. 589 return ec_GFp_simple_mont_inv_mod_ord_vartime(group, out, in); 590 } 591 592 assert(group->order.width == P256_LIMBS); 593 if (!beeu_mod_inverse_vartime(out->words, in->words, group->order.d)) { 594 return 0; 595 } 596 597 // The result should be returned in the Montgomery domain. 598 ec_scalar_to_montgomery(group, out, out); 599 return 1; 600 } 601 602 static int ecp_nistz256_cmp_x_coordinate(const EC_GROUP *group, 603 const EC_RAW_POINT *p, 604 const EC_SCALAR *r) { 605 if (ec_GFp_simple_is_at_infinity(group, p)) { 606 return 0; 607 } 608 609 assert(group->order.width == P256_LIMBS); 610 assert(group->field.width == P256_LIMBS); 611 612 // We wish to compare X/Z^2 with r. This is equivalent to comparing X with 613 // r*Z^2. Note that X and Z are represented in Montgomery form, while r is 614 // not. 615 BN_ULONG r_Z2[P256_LIMBS], Z2_mont[P256_LIMBS], X[P256_LIMBS]; 616 ecp_nistz256_mul_mont(Z2_mont, p->Z.words, p->Z.words); 617 ecp_nistz256_mul_mont(r_Z2, r->words, Z2_mont); 618 ecp_nistz256_from_mont(X, p->X.words); 619 620 if (OPENSSL_memcmp(r_Z2, X, sizeof(r_Z2)) == 0) { 621 return 1; 622 } 623 624 // During signing the x coefficient is reduced modulo the group order. 625 // Therefore there is a small possibility, less than 1/2^128, that group_order 626 // < p.x < P. in that case we need not only to compare against |r| but also to 627 // compare against r+group_order. 628 if (bn_less_than_words(r->words, group->field_minus_order.words, 629 P256_LIMBS)) { 630 // We can ignore the carry because: r + group_order < p < 2^256. 631 bn_add_words(r_Z2, r->words, group->order.d, P256_LIMBS); 632 ecp_nistz256_mul_mont(r_Z2, r_Z2, Z2_mont); 633 if (OPENSSL_memcmp(r_Z2, X, sizeof(r_Z2)) == 0) { 634 return 1; 635 } 636 } 637 638 return 0; 639 } 640 641 DEFINE_METHOD_FUNCTION(EC_METHOD, EC_GFp_nistz256_method) { 642 out->group_init = ec_GFp_mont_group_init; 643 out->group_finish = ec_GFp_mont_group_finish; 644 out->group_set_curve = ec_GFp_mont_group_set_curve; 645 out->point_get_affine_coordinates = ecp_nistz256_get_affine; 646 out->add = ecp_nistz256_add; 647 out->dbl = ecp_nistz256_dbl; 648 out->mul = ecp_nistz256_points_mul; 649 out->mul_public = ecp_nistz256_points_mul_public; 650 out->felem_mul = ec_GFp_mont_felem_mul; 651 out->felem_sqr = ec_GFp_mont_felem_sqr; 652 out->bignum_to_felem = ec_GFp_mont_bignum_to_felem; 653 out->felem_to_bignum = ec_GFp_mont_felem_to_bignum; 654 out->scalar_inv_montgomery = ecp_nistz256_inv_mod_ord; 655 out->scalar_inv_montgomery_vartime = ecp_nistz256_mont_inv_mod_ord_vartime; 656 out->cmp_x_coordinate = ecp_nistz256_cmp_x_coordinate; 657 } 658 659 #endif /* !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64) && \ 660 !defined(OPENSSL_SMALL) */ 661
