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/crypto.h> 27#include <openssl/err.h> 28 29#include "../../internal.h" 30#include "../bn/internal.h" 31#include "../delocate.h" 32#include "internal.h" 33#include "p256-nistz.h" 34 35#if !defined(OPENSSL_NO_ASM) && \ 36 (defined(OPENSSL_X86_64) || defined(OPENSSL_AARCH64)) && \ 37 !defined(OPENSSL_SMALL) 38 39typedef P256_POINT_AFFINE PRECOMP256_ROW[64]; 40 41// One converted into the Montgomery domain 42static const BN_ULONG ONE_MONT[P256_LIMBS] = { 43 TOBN(0x00000000, 0x00000001), 44 TOBN(0xffffffff, 0x00000000), 45 TOBN(0xffffffff, 0xffffffff), 46 TOBN(0x00000000, 0xfffffffe), 47}; 48 49// Precomputed tables for the default generator 50#include "p256-nistz-table.h" 51 52// Recode window to a signed digit, see |ec_GFp_nistp_recode_scalar_bits| in 53// util.c for details 54static crypto_word_t booth_recode_w5(crypto_word_t in) { 55 crypto_word_t s, d; 56 57 s = ~((in >> 5) - 1); 58 d = (1 << 6) - in - 1; 59 d = (d & s) | (in & ~s); 60 d = (d >> 1) + (d & 1); 61 62 return (d << 1) + (s & 1); 63} 64 65static crypto_word_t booth_recode_w7(crypto_word_t in) { 66 crypto_word_t s, d; 67 68 s = ~((in >> 7) - 1); 69 d = (1 << 8) - in - 1; 70 d = (d & s) | (in & ~s); 71 d = (d >> 1) + (d & 1); 72 73 return (d << 1) + (s & 1); 74} 75 76// copy_conditional copies |src| to |dst| if |move| is one and leaves it as-is 77// if |move| is zero. 78// 79// WARNING: this breaks the usual convention of constant-time functions 80// returning masks. 81static void copy_conditional(BN_ULONG dst[P256_LIMBS], 82 const BN_ULONG src[P256_LIMBS], BN_ULONG move) { 83 BN_ULONG mask1 = ((BN_ULONG)0) - move; 84 BN_ULONG mask2 = ~mask1; 85 86 dst[0] = (src[0] & mask1) ^ (dst[0] & mask2); 87 dst[1] = (src[1] & mask1) ^ (dst[1] & mask2); 88 dst[2] = (src[2] & mask1) ^ (dst[2] & mask2); 89 dst[3] = (src[3] & mask1) ^ (dst[3] & mask2); 90 if (P256_LIMBS == 8) { 91 dst[4] = (src[4] & mask1) ^ (dst[4] & mask2); 92 dst[5] = (src[5] & mask1) ^ (dst[5] & mask2); 93 dst[6] = (src[6] & mask1) ^ (dst[6] & mask2); 94 dst[7] = (src[7] & mask1) ^ (dst[7] & mask2); 95 } 96} 97 98// is_not_zero returns one iff in != 0 and zero otherwise. 99// 100// WARNING: this breaks the usual convention of constant-time functions 101// returning masks. 102// 103// (define-fun is_not_zero ((in (_ BitVec 64))) (_ BitVec 64) 104// (bvlshr (bvor in (bvsub #x0000000000000000 in)) #x000000000000003f) 105// ) 106// 107// (declare-fun x () (_ BitVec 64)) 108// 109// (assert (and (= x #x0000000000000000) (= (is_not_zero x) 110// #x0000000000000001))) (check-sat) 111// 112// (assert (and (not (= x #x0000000000000000)) (= (is_not_zero x) 113// #x0000000000000000))) (check-sat) 114// 115static BN_ULONG is_not_zero(BN_ULONG in) { 116 in |= (0 - in); 117 in >>= BN_BITS2 - 1; 118 return in; 119} 120 121#if defined(OPENSSL_X86_64) 122// Dispatch between CPU variations. The "_adx" suffixed functions use MULX in 123// addition to ADCX/ADOX. MULX is part of BMI2, not ADX, so we must check both 124// capabilities. 125static void ecp_nistz256_mul_mont(BN_ULONG res[P256_LIMBS], 126 const BN_ULONG a[P256_LIMBS], 127 const BN_ULONG b[P256_LIMBS]) { 128 if (CRYPTO_is_BMI2_capable() && CRYPTO_is_ADX_capable()) { 129 ecp_nistz256_mul_mont_adx(res, a, b); 130 } else { 131 ecp_nistz256_mul_mont_nohw(res, a, b); 132 } 133} 134 135static void ecp_nistz256_sqr_mont(BN_ULONG res[P256_LIMBS], 136 const BN_ULONG a[P256_LIMBS]) { 137 if (CRYPTO_is_BMI2_capable() && CRYPTO_is_ADX_capable()) { 138 ecp_nistz256_sqr_mont_adx(res, a); 139 } else { 140 ecp_nistz256_sqr_mont_nohw(res, a); 141 } 142} 143 144static void ecp_nistz256_ord_mul_mont(BN_ULONG res[P256_LIMBS], 145 const BN_ULONG a[P256_LIMBS], 146 const BN_ULONG b[P256_LIMBS]) { 147 if (CRYPTO_is_BMI2_capable() && CRYPTO_is_ADX_capable()) { 148 ecp_nistz256_ord_mul_mont_adx(res, a, b); 149 } else { 150 ecp_nistz256_ord_mul_mont_nohw(res, a, b); 151 } 152} 153 154static void ecp_nistz256_ord_sqr_mont(BN_ULONG res[P256_LIMBS], 155 const BN_ULONG a[P256_LIMBS], 156 BN_ULONG rep) { 157 if (CRYPTO_is_BMI2_capable() && CRYPTO_is_ADX_capable()) { 158 ecp_nistz256_ord_sqr_mont_adx(res, a, rep); 159 } else { 160 ecp_nistz256_ord_sqr_mont_nohw(res, a, rep); 161 } 162} 163 164static void ecp_nistz256_select_w5(P256_POINT *val, const P256_POINT in_t[16], 165 int index) { 166 if (CRYPTO_is_AVX2_capable()) { 167 ecp_nistz256_select_w5_avx2(val, in_t, index); 168 } else { 169 ecp_nistz256_select_w5_nohw(val, in_t, index); 170 } 171} 172 173static void ecp_nistz256_select_w7(P256_POINT_AFFINE *val, 174 const P256_POINT_AFFINE in_t[64], 175 int index) { 176 if (CRYPTO_is_AVX2_capable()) { 177 ecp_nistz256_select_w7_avx2(val, in_t, index); 178 } else { 179 ecp_nistz256_select_w7_nohw(val, in_t, index); 180 } 181} 182 183static void ecp_nistz256_point_double(P256_POINT *r, const P256_POINT *a) { 184 if (CRYPTO_is_BMI2_capable() && CRYPTO_is_ADX_capable()) { 185 ecp_nistz256_point_double_adx(r, a); 186 } else { 187 ecp_nistz256_point_double_nohw(r, a); 188 } 189} 190 191static void ecp_nistz256_point_add(P256_POINT *r, const P256_POINT *a, 192 const P256_POINT *b) { 193 if (CRYPTO_is_BMI2_capable() && CRYPTO_is_ADX_capable()) { 194 ecp_nistz256_point_add_adx(r, a, b); 195 } else { 196 ecp_nistz256_point_add_nohw(r, a, b); 197 } 198} 199 200static void ecp_nistz256_point_add_affine(P256_POINT *r, const P256_POINT *a, 201 const P256_POINT_AFFINE *b) { 202 if (CRYPTO_is_BMI2_capable() && CRYPTO_is_ADX_capable()) { 203 ecp_nistz256_point_add_affine_adx(r, a, b); 204 } else { 205 ecp_nistz256_point_add_affine_nohw(r, a, b); 206 } 207} 208#endif // OPENSSL_X86_64 209 210// ecp_nistz256_from_mont sets |res| to |in|, converted from Montgomery domain 211// by multiplying with 1. 212static void ecp_nistz256_from_mont(BN_ULONG res[P256_LIMBS], 213 const BN_ULONG in[P256_LIMBS]) { 214 static const BN_ULONG ONE[P256_LIMBS] = {1}; 215 ecp_nistz256_mul_mont(res, in, ONE); 216} 217 218// ecp_nistz256_mod_inverse_sqr_mont sets |r| to (|in| * 2^-256)^-2 * 2^256 mod 219// p. That is, |r| is the modular inverse square of |in| for input and output in 220// the Montgomery domain. 221static void ecp_nistz256_mod_inverse_sqr_mont(BN_ULONG r[P256_LIMBS], 222 const BN_ULONG in[P256_LIMBS]) { 223 // This implements the addition chain described in 224 // https://briansmith.org/ecc-inversion-addition-chains-01#p256_field_inversion 225 BN_ULONG x2[P256_LIMBS], x3[P256_LIMBS], x6[P256_LIMBS], x12[P256_LIMBS], 226 x15[P256_LIMBS], x30[P256_LIMBS], x32[P256_LIMBS]; 227 ecp_nistz256_sqr_mont(x2, in); // 2^2 - 2^1 228 ecp_nistz256_mul_mont(x2, x2, in); // 2^2 - 2^0 229 230 ecp_nistz256_sqr_mont(x3, x2); // 2^3 - 2^1 231 ecp_nistz256_mul_mont(x3, x3, in); // 2^3 - 2^0 232 233 ecp_nistz256_sqr_mont(x6, x3); 234 for (int i = 1; i < 3; i++) { 235 ecp_nistz256_sqr_mont(x6, x6); 236 } // 2^6 - 2^3 237 ecp_nistz256_mul_mont(x6, x6, x3); // 2^6 - 2^0 238 239 ecp_nistz256_sqr_mont(x12, x6); 240 for (int i = 1; i < 6; i++) { 241 ecp_nistz256_sqr_mont(x12, x12); 242 } // 2^12 - 2^6 243 ecp_nistz256_mul_mont(x12, x12, x6); // 2^12 - 2^0 244 245 ecp_nistz256_sqr_mont(x15, x12); 246 for (int i = 1; i < 3; i++) { 247 ecp_nistz256_sqr_mont(x15, x15); 248 } // 2^15 - 2^3 249 ecp_nistz256_mul_mont(x15, x15, x3); // 2^15 - 2^0 250 251 ecp_nistz256_sqr_mont(x30, x15); 252 for (int i = 1; i < 15; i++) { 253 ecp_nistz256_sqr_mont(x30, x30); 254 } // 2^30 - 2^15 255 ecp_nistz256_mul_mont(x30, x30, x15); // 2^30 - 2^0 256 257 ecp_nistz256_sqr_mont(x32, x30); 258 ecp_nistz256_sqr_mont(x32, x32); // 2^32 - 2^2 259 ecp_nistz256_mul_mont(x32, x32, x2); // 2^32 - 2^0 260 261 BN_ULONG ret[P256_LIMBS]; 262 ecp_nistz256_sqr_mont(ret, x32); 263 for (int i = 1; i < 31 + 1; i++) { 264 ecp_nistz256_sqr_mont(ret, ret); 265 } // 2^64 - 2^32 266 ecp_nistz256_mul_mont(ret, ret, in); // 2^64 - 2^32 + 2^0 267 268 for (int i = 0; i < 96 + 32; i++) { 269 ecp_nistz256_sqr_mont(ret, ret); 270 } // 2^192 - 2^160 + 2^128 271 ecp_nistz256_mul_mont(ret, ret, x32); // 2^192 - 2^160 + 2^128 + 2^32 - 2^0 272 273 for (int i = 0; i < 32; i++) { 274 ecp_nistz256_sqr_mont(ret, ret); 275 } // 2^224 - 2^192 + 2^160 + 2^64 - 2^32 276 ecp_nistz256_mul_mont(ret, ret, x32); // 2^224 - 2^192 + 2^160 + 2^64 - 2^0 277 278 for (int i = 0; i < 30; i++) { 279 ecp_nistz256_sqr_mont(ret, ret); 280 } // 2^254 - 2^222 + 2^190 + 2^94 - 2^30 281 ecp_nistz256_mul_mont(ret, ret, x30); // 2^254 - 2^222 + 2^190 + 2^94 - 2^0 282 283 ecp_nistz256_sqr_mont(ret, ret); 284 ecp_nistz256_sqr_mont(r, ret); // 2^256 - 2^224 + 2^192 + 2^96 - 2^2 285} 286 287// r = p * p_scalar 288static void ecp_nistz256_windowed_mul(const EC_GROUP *group, P256_POINT *r, 289 const EC_JACOBIAN *p, 290 const EC_SCALAR *p_scalar) { 291 assert(p != NULL); 292 assert(p_scalar != NULL); 293 assert(group->field.N.width == P256_LIMBS); 294 295 static const size_t kWindowSize = 5; 296 static const crypto_word_t kMask = (1 << (5 /* kWindowSize */ + 1)) - 1; 297 298 // A |P256_POINT| is (3 * 32) = 96 bytes, and the 64-byte alignment should 299 // add no more than 63 bytes of overhead. Thus, |table| should require 300 // ~1599 ((96 * 16) + 63) bytes of stack space. 301 alignas(64) P256_POINT table[16]; 302 uint8_t p_str[33]; 303 OPENSSL_memcpy(p_str, p_scalar->words, 32); 304 p_str[32] = 0; 305 306 // table[0] is implicitly (0,0,0) (the point at infinity), therefore it is 307 // not stored. All other values are actually stored with an offset of -1 in 308 // table. 309 P256_POINT *row = table; 310 assert(group->field.N.width == P256_LIMBS); 311 OPENSSL_memcpy(row[1 - 1].X, p->X.words, P256_LIMBS * sizeof(BN_ULONG)); 312 OPENSSL_memcpy(row[1 - 1].Y, p->Y.words, P256_LIMBS * sizeof(BN_ULONG)); 313 OPENSSL_memcpy(row[1 - 1].Z, p->Z.words, P256_LIMBS * sizeof(BN_ULONG)); 314 315 ecp_nistz256_point_double(&row[2 - 1], &row[1 - 1]); 316 ecp_nistz256_point_add(&row[3 - 1], &row[2 - 1], &row[1 - 1]); 317 ecp_nistz256_point_double(&row[4 - 1], &row[2 - 1]); 318 ecp_nistz256_point_double(&row[6 - 1], &row[3 - 1]); 319 ecp_nistz256_point_double(&row[8 - 1], &row[4 - 1]); 320 ecp_nistz256_point_double(&row[12 - 1], &row[6 - 1]); 321 ecp_nistz256_point_add(&row[5 - 1], &row[4 - 1], &row[1 - 1]); 322 ecp_nistz256_point_add(&row[7 - 1], &row[6 - 1], &row[1 - 1]); 323 ecp_nistz256_point_add(&row[9 - 1], &row[8 - 1], &row[1 - 1]); 324 ecp_nistz256_point_add(&row[13 - 1], &row[12 - 1], &row[1 - 1]); 325 ecp_nistz256_point_double(&row[14 - 1], &row[7 - 1]); 326 ecp_nistz256_point_double(&row[10 - 1], &row[5 - 1]); 327 ecp_nistz256_point_add(&row[15 - 1], &row[14 - 1], &row[1 - 1]); 328 ecp_nistz256_point_add(&row[11 - 1], &row[10 - 1], &row[1 - 1]); 329 ecp_nistz256_point_double(&row[16 - 1], &row[8 - 1]); 330 331 BN_ULONG tmp[P256_LIMBS]; 332 alignas(32) P256_POINT h; 333 size_t index = 255; 334 crypto_word_t wvalue = p_str[(index - 1) / 8]; 335 wvalue = (wvalue >> ((index - 1) % 8)) & kMask; 336 337 ecp_nistz256_select_w5(r, table, booth_recode_w5(wvalue) >> 1); 338 339 while (index >= 5) { 340 if (index != 255) { 341 size_t off = (index - 1) / 8; 342 343 wvalue = (crypto_word_t)p_str[off] | (crypto_word_t)p_str[off + 1] << 8; 344 wvalue = (wvalue >> ((index - 1) % 8)) & kMask; 345 346 wvalue = booth_recode_w5(wvalue); 347 348 ecp_nistz256_select_w5(&h, table, wvalue >> 1); 349 350 ecp_nistz256_neg(tmp, h.Y); 351 copy_conditional(h.Y, tmp, (wvalue & 1)); 352 353 ecp_nistz256_point_add(r, r, &h); 354 } 355 356 index -= kWindowSize; 357 358 ecp_nistz256_point_double(r, r); 359 ecp_nistz256_point_double(r, r); 360 ecp_nistz256_point_double(r, r); 361 ecp_nistz256_point_double(r, r); 362 ecp_nistz256_point_double(r, r); 363 } 364 365 // Final window 366 wvalue = p_str[0]; 367 wvalue = (wvalue << 1) & kMask; 368 369 wvalue = booth_recode_w5(wvalue); 370 371 ecp_nistz256_select_w5(&h, table, wvalue >> 1); 372 373 ecp_nistz256_neg(tmp, h.Y); 374 copy_conditional(h.Y, tmp, wvalue & 1); 375 376 ecp_nistz256_point_add(r, r, &h); 377} 378 379static crypto_word_t calc_first_wvalue(size_t *index, const uint8_t p_str[33]) { 380 static const size_t kWindowSize = 7; 381 static const crypto_word_t kMask = (1 << (7 /* kWindowSize */ + 1)) - 1; 382 *index = kWindowSize; 383 384 crypto_word_t wvalue = (p_str[0] << 1) & kMask; 385 return booth_recode_w7(wvalue); 386} 387 388static crypto_word_t calc_wvalue(size_t *index, const uint8_t p_str[33]) { 389 static const size_t kWindowSize = 7; 390 static const crypto_word_t kMask = (1 << (7 /* kWindowSize */ + 1)) - 1; 391 392 const size_t off = (*index - 1) / 8; 393 crypto_word_t wvalue = 394 (crypto_word_t)p_str[off] | (crypto_word_t)p_str[off + 1] << 8; 395 wvalue = (wvalue >> ((*index - 1) % 8)) & kMask; 396 *index += kWindowSize; 397 398 return booth_recode_w7(wvalue); 399} 400 401static void ecp_nistz256_point_mul(const EC_GROUP *group, EC_JACOBIAN *r, 402 const EC_JACOBIAN *p, 403 const EC_SCALAR *scalar) { 404 alignas(32) P256_POINT out; 405 ecp_nistz256_windowed_mul(group, &out, p, scalar); 406 407 assert(group->field.N.width == P256_LIMBS); 408 OPENSSL_memcpy(r->X.words, out.X, P256_LIMBS * sizeof(BN_ULONG)); 409 OPENSSL_memcpy(r->Y.words, out.Y, P256_LIMBS * sizeof(BN_ULONG)); 410 OPENSSL_memcpy(r->Z.words, out.Z, P256_LIMBS * sizeof(BN_ULONG)); 411} 412 413static void ecp_nistz256_point_mul_base(const EC_GROUP *group, EC_JACOBIAN *r, 414 const EC_SCALAR *scalar) { 415 uint8_t p_str[33]; 416 OPENSSL_memcpy(p_str, scalar->words, 32); 417 p_str[32] = 0; 418 419 // First window 420 size_t index = 0; 421 crypto_word_t wvalue = calc_first_wvalue(&index, p_str); 422 423 alignas(32) P256_POINT_AFFINE t; 424 alignas(32) P256_POINT p; 425 ecp_nistz256_select_w7(&t, ecp_nistz256_precomputed[0], wvalue >> 1); 426 ecp_nistz256_neg(p.Z, t.Y); 427 copy_conditional(t.Y, p.Z, wvalue & 1); 428 429 // Convert |t| from affine to Jacobian coordinates. We set Z to zero if |t| 430 // is infinity and |ONE_MONT| otherwise. |t| was computed from the table, so 431 // it is infinity iff |wvalue >> 1| is zero. 432 OPENSSL_memcpy(p.X, t.X, sizeof(p.X)); 433 OPENSSL_memcpy(p.Y, t.Y, sizeof(p.Y)); 434 OPENSSL_memset(p.Z, 0, sizeof(p.Z)); 435 copy_conditional(p.Z, ONE_MONT, is_not_zero(wvalue >> 1)); 436 437 for (int i = 1; i < 37; i++) { 438 wvalue = calc_wvalue(&index, p_str); 439 440 ecp_nistz256_select_w7(&t, ecp_nistz256_precomputed[i], wvalue >> 1); 441 442 alignas(32) BN_ULONG neg_Y[P256_LIMBS]; 443 ecp_nistz256_neg(neg_Y, t.Y); 444 copy_conditional(t.Y, neg_Y, wvalue & 1); 445 446 // Note |ecp_nistz256_point_add_affine| does not work if |p| and |t| are the 447 // same non-infinity point. 448 ecp_nistz256_point_add_affine(&p, &p, &t); 449 } 450 451 assert(group->field.N.width == P256_LIMBS); 452 OPENSSL_memcpy(r->X.words, p.X, P256_LIMBS * sizeof(BN_ULONG)); 453 OPENSSL_memcpy(r->Y.words, p.Y, P256_LIMBS * sizeof(BN_ULONG)); 454 OPENSSL_memcpy(r->Z.words, p.Z, P256_LIMBS * sizeof(BN_ULONG)); 455} 456 457static void ecp_nistz256_points_mul_public(const EC_GROUP *group, 458 EC_JACOBIAN *r, 459 const EC_SCALAR *g_scalar, 460 const EC_JACOBIAN *p_, 461 const EC_SCALAR *p_scalar) { 462 assert(p_ != NULL && p_scalar != NULL && g_scalar != NULL); 463 464 alignas(32) P256_POINT p; 465 uint8_t p_str[33]; 466 OPENSSL_memcpy(p_str, g_scalar->words, 32); 467 p_str[32] = 0; 468 469 // First window 470 size_t index = 0; 471 size_t wvalue = calc_first_wvalue(&index, p_str); 472 473 // Convert |p| from affine to Jacobian coordinates. We set Z to zero if |p| 474 // is infinity and |ONE_MONT| otherwise. |p| was computed from the table, so 475 // it is infinity iff |wvalue >> 1| is zero. 476 if ((wvalue >> 1) != 0) { 477 OPENSSL_memcpy(p.X, &ecp_nistz256_precomputed[0][(wvalue >> 1) - 1].X, 478 sizeof(p.X)); 479 OPENSSL_memcpy(p.Y, &ecp_nistz256_precomputed[0][(wvalue >> 1) - 1].Y, 480 sizeof(p.Y)); 481 OPENSSL_memcpy(p.Z, ONE_MONT, sizeof(p.Z)); 482 } else { 483 OPENSSL_memset(p.X, 0, sizeof(p.X)); 484 OPENSSL_memset(p.Y, 0, sizeof(p.Y)); 485 OPENSSL_memset(p.Z, 0, sizeof(p.Z)); 486 } 487 488 if ((wvalue & 1) == 1) { 489 ecp_nistz256_neg(p.Y, p.Y); 490 } 491 492 for (int i = 1; i < 37; i++) { 493 wvalue = calc_wvalue(&index, p_str); 494 if ((wvalue >> 1) == 0) { 495 continue; 496 } 497 498 alignas(32) P256_POINT_AFFINE t; 499 OPENSSL_memcpy(&t, &ecp_nistz256_precomputed[i][(wvalue >> 1) - 1], 500 sizeof(t)); 501 if ((wvalue & 1) == 1) { 502 ecp_nistz256_neg(t.Y, t.Y); 503 } 504 505 // Note |ecp_nistz256_point_add_affine| does not work if |p| and |t| are 506 // the same non-infinity point, so it is important that we compute the 507 // |g_scalar| term before the |p_scalar| term. 508 ecp_nistz256_point_add_affine(&p, &p, &t); 509 } 510 511 alignas(32) P256_POINT tmp; 512 ecp_nistz256_windowed_mul(group, &tmp, p_, p_scalar); 513 ecp_nistz256_point_add(&p, &p, &tmp); 514 515 assert(group->field.N.width == P256_LIMBS); 516 OPENSSL_memcpy(r->X.words, p.X, P256_LIMBS * sizeof(BN_ULONG)); 517 OPENSSL_memcpy(r->Y.words, p.Y, P256_LIMBS * sizeof(BN_ULONG)); 518 OPENSSL_memcpy(r->Z.words, p.Z, P256_LIMBS * sizeof(BN_ULONG)); 519} 520 521static int ecp_nistz256_get_affine(const EC_GROUP *group, 522 const EC_JACOBIAN *point, EC_FELEM *x, 523 EC_FELEM *y) { 524 if (constant_time_declassify_int( 525 ec_GFp_simple_is_at_infinity(group, point))) { 526 OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY); 527 return 0; 528 } 529 530 BN_ULONG z_inv2[P256_LIMBS]; 531 assert(group->field.N.width == P256_LIMBS); 532 ecp_nistz256_mod_inverse_sqr_mont(z_inv2, point->Z.words); 533 534 if (x != NULL) { 535 ecp_nistz256_mul_mont(x->words, z_inv2, point->X.words); 536 } 537 538 if (y != NULL) { 539 ecp_nistz256_sqr_mont(z_inv2, z_inv2); // z^-4 540 ecp_nistz256_mul_mont(y->words, point->Y.words, point->Z.words); // y * z 541 ecp_nistz256_mul_mont(y->words, y->words, z_inv2); // y * z^-3 542 } 543 544 return 1; 545} 546 547static void ecp_nistz256_add(const EC_GROUP *group, EC_JACOBIAN *r, 548 const EC_JACOBIAN *a_, const EC_JACOBIAN *b_) { 549 P256_POINT a, b; 550 OPENSSL_memcpy(a.X, a_->X.words, P256_LIMBS * sizeof(BN_ULONG)); 551 OPENSSL_memcpy(a.Y, a_->Y.words, P256_LIMBS * sizeof(BN_ULONG)); 552 OPENSSL_memcpy(a.Z, a_->Z.words, P256_LIMBS * sizeof(BN_ULONG)); 553 OPENSSL_memcpy(b.X, b_->X.words, P256_LIMBS * sizeof(BN_ULONG)); 554 OPENSSL_memcpy(b.Y, b_->Y.words, P256_LIMBS * sizeof(BN_ULONG)); 555 OPENSSL_memcpy(b.Z, b_->Z.words, P256_LIMBS * sizeof(BN_ULONG)); 556 ecp_nistz256_point_add(&a, &a, &b); 557 OPENSSL_memcpy(r->X.words, a.X, P256_LIMBS * sizeof(BN_ULONG)); 558 OPENSSL_memcpy(r->Y.words, a.Y, P256_LIMBS * sizeof(BN_ULONG)); 559 OPENSSL_memcpy(r->Z.words, a.Z, P256_LIMBS * sizeof(BN_ULONG)); 560} 561 562static void ecp_nistz256_dbl(const EC_GROUP *group, EC_JACOBIAN *r, 563 const EC_JACOBIAN *a_) { 564 P256_POINT a; 565 OPENSSL_memcpy(a.X, a_->X.words, P256_LIMBS * sizeof(BN_ULONG)); 566 OPENSSL_memcpy(a.Y, a_->Y.words, P256_LIMBS * sizeof(BN_ULONG)); 567 OPENSSL_memcpy(a.Z, a_->Z.words, P256_LIMBS * sizeof(BN_ULONG)); 568 ecp_nistz256_point_double(&a, &a); 569 OPENSSL_memcpy(r->X.words, a.X, P256_LIMBS * sizeof(BN_ULONG)); 570 OPENSSL_memcpy(r->Y.words, a.Y, P256_LIMBS * sizeof(BN_ULONG)); 571 OPENSSL_memcpy(r->Z.words, a.Z, P256_LIMBS * sizeof(BN_ULONG)); 572} 573 574static void ecp_nistz256_inv0_mod_ord(const EC_GROUP *group, EC_SCALAR *out, 575 const EC_SCALAR *in) { 576 // table[i] stores a power of |in| corresponding to the matching enum value. 577 enum { 578 // The following indices specify the power in binary. 579 i_1 = 0, 580 i_10, 581 i_11, 582 i_101, 583 i_111, 584 i_1010, 585 i_1111, 586 i_10101, 587 i_101010, 588 i_101111, 589 // The following indices specify 2^N-1, or N ones in a row. 590 i_x6, 591 i_x8, 592 i_x16, 593 i_x32 594 }; 595 BN_ULONG table[15][P256_LIMBS]; 596 597 // https://briansmith.org/ecc-inversion-addition-chains-01#p256_scalar_inversion 598 // 599 // Even though this code path spares 12 squarings, 4.5%, and 13 600 // multiplications, 25%, the overall sign operation is not that much faster, 601 // not more that 2%. Most of the performance of this function comes from the 602 // scalar operations. 603 604 // Pre-calculate powers. 605 OPENSSL_memcpy(table[i_1], in->words, P256_LIMBS * sizeof(BN_ULONG)); 606 607 ecp_nistz256_ord_sqr_mont(table[i_10], table[i_1], 1); 608 609 ecp_nistz256_ord_mul_mont(table[i_11], table[i_1], table[i_10]); 610 611 ecp_nistz256_ord_mul_mont(table[i_101], table[i_11], table[i_10]); 612 613 ecp_nistz256_ord_mul_mont(table[i_111], table[i_101], table[i_10]); 614 615 ecp_nistz256_ord_sqr_mont(table[i_1010], table[i_101], 1); 616 617 ecp_nistz256_ord_mul_mont(table[i_1111], table[i_1010], table[i_101]); 618 619 ecp_nistz256_ord_sqr_mont(table[i_10101], table[i_1010], 1); 620 ecp_nistz256_ord_mul_mont(table[i_10101], table[i_10101], table[i_1]); 621 622 ecp_nistz256_ord_sqr_mont(table[i_101010], table[i_10101], 1); 623 624 ecp_nistz256_ord_mul_mont(table[i_101111], table[i_101010], table[i_101]); 625 626 ecp_nistz256_ord_mul_mont(table[i_x6], table[i_101010], table[i_10101]); 627 628 ecp_nistz256_ord_sqr_mont(table[i_x8], table[i_x6], 2); 629 ecp_nistz256_ord_mul_mont(table[i_x8], table[i_x8], table[i_11]); 630 631 ecp_nistz256_ord_sqr_mont(table[i_x16], table[i_x8], 8); 632 ecp_nistz256_ord_mul_mont(table[i_x16], table[i_x16], table[i_x8]); 633 634 ecp_nistz256_ord_sqr_mont(table[i_x32], table[i_x16], 16); 635 ecp_nistz256_ord_mul_mont(table[i_x32], table[i_x32], table[i_x16]); 636 637 // Compute |in| raised to the order-2. 638 ecp_nistz256_ord_sqr_mont(out->words, table[i_x32], 64); 639 ecp_nistz256_ord_mul_mont(out->words, out->words, table[i_x32]); 640 static const struct { 641 uint8_t p, i; 642 } kChain[27] = {{32, i_x32}, {6, i_101111}, {5, i_111}, {4, i_11}, 643 {5, i_1111}, {5, i_10101}, {4, i_101}, {3, i_101}, 644 {3, i_101}, {5, i_111}, {9, i_101111}, {6, i_1111}, 645 {2, i_1}, {5, i_1}, {6, i_1111}, {5, i_111}, 646 {4, i_111}, {5, i_111}, {5, i_101}, {3, i_11}, 647 {10, i_101111}, {2, i_11}, {5, i_11}, {5, i_11}, 648 {3, i_1}, {7, i_10101}, {6, i_1111}}; 649 for (size_t i = 0; i < OPENSSL_ARRAY_SIZE(kChain); i++) { 650 ecp_nistz256_ord_sqr_mont(out->words, out->words, kChain[i].p); 651 ecp_nistz256_ord_mul_mont(out->words, out->words, table[kChain[i].i]); 652 } 653} 654 655static int ecp_nistz256_scalar_to_montgomery_inv_vartime(const EC_GROUP *group, 656 EC_SCALAR *out, 657 const EC_SCALAR *in) { 658#if defined(OPENSSL_X86_64) 659 if (!CRYPTO_is_AVX_capable()) { 660 // No AVX support; fallback to generic code. 661 return ec_simple_scalar_to_montgomery_inv_vartime(group, out, in); 662 } 663#endif 664 665 assert(group->order.N.width == P256_LIMBS); 666 if (!beeu_mod_inverse_vartime(out->words, in->words, group->order.N.d)) { 667 return 0; 668 } 669 670 // The result should be returned in the Montgomery domain. 671 ec_scalar_to_montgomery(group, out, out); 672 return 1; 673} 674 675static int ecp_nistz256_cmp_x_coordinate(const EC_GROUP *group, 676 const EC_JACOBIAN *p, 677 const EC_SCALAR *r) { 678 if (ec_GFp_simple_is_at_infinity(group, p)) { 679 return 0; 680 } 681 682 assert(group->order.N.width == P256_LIMBS); 683 assert(group->field.N.width == P256_LIMBS); 684 685 // We wish to compare X/Z^2 with r. This is equivalent to comparing X with 686 // r*Z^2. Note that X and Z are represented in Montgomery form, while r is 687 // not. 688 BN_ULONG r_Z2[P256_LIMBS], Z2_mont[P256_LIMBS], X[P256_LIMBS]; 689 ecp_nistz256_mul_mont(Z2_mont, p->Z.words, p->Z.words); 690 ecp_nistz256_mul_mont(r_Z2, r->words, Z2_mont); 691 ecp_nistz256_from_mont(X, p->X.words); 692 693 if (OPENSSL_memcmp(r_Z2, X, sizeof(r_Z2)) == 0) { 694 return 1; 695 } 696 697 // During signing the x coefficient is reduced modulo the group order. 698 // Therefore there is a small possibility, less than 1/2^128, that group_order 699 // < p.x < P. in that case we need not only to compare against |r| but also to 700 // compare against r+group_order. 701 BN_ULONG carry = bn_add_words(r_Z2, r->words, group->order.N.d, P256_LIMBS); 702 if (carry == 0 && bn_less_than_words(r_Z2, group->field.N.d, P256_LIMBS)) { 703 // r + group_order < p, so compare (r + group_order) * Z^2 against X. 704 ecp_nistz256_mul_mont(r_Z2, r_Z2, Z2_mont); 705 if (OPENSSL_memcmp(r_Z2, X, sizeof(r_Z2)) == 0) { 706 return 1; 707 } 708 } 709 710 return 0; 711} 712 713DEFINE_METHOD_FUNCTION(EC_METHOD, EC_GFp_nistz256_method) { 714 out->point_get_affine_coordinates = ecp_nistz256_get_affine; 715 out->add = ecp_nistz256_add; 716 out->dbl = ecp_nistz256_dbl; 717 out->mul = ecp_nistz256_point_mul; 718 out->mul_base = ecp_nistz256_point_mul_base; 719 out->mul_public = ecp_nistz256_points_mul_public; 720 out->felem_mul = ec_GFp_mont_felem_mul; 721 out->felem_sqr = ec_GFp_mont_felem_sqr; 722 out->felem_to_bytes = ec_GFp_mont_felem_to_bytes; 723 out->felem_from_bytes = ec_GFp_mont_felem_from_bytes; 724 out->felem_reduce = ec_GFp_mont_felem_reduce; 725 // TODO(davidben): This should use the specialized field arithmetic 726 // implementation, rather than the generic one. 727 out->felem_exp = ec_GFp_mont_felem_exp; 728 out->scalar_inv0_montgomery = ecp_nistz256_inv0_mod_ord; 729 out->scalar_to_montgomery_inv_vartime = 730 ecp_nistz256_scalar_to_montgomery_inv_vartime; 731 out->cmp_x_coordinate = ecp_nistz256_cmp_x_coordinate; 732} 733 734#endif /* !defined(OPENSSL_NO_ASM) && \ 735 (defined(OPENSSL_X86_64) || defined(OPENSSL_AARCH64)) && \ 736 !defined(OPENSSL_SMALL) */ 737