| 1 |
/* Copyright (c) 2014, Intel Corporation. |
| 2 |
* |
| 3 |
* Permission to use, copy, modify, and/or distribute this software for any |
| 4 |
* purpose with or without fee is hereby granted, provided that the above |
| 5 |
* copyright notice and this permission notice appear in all copies. |
| 6 |
* |
| 7 |
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES |
| 8 |
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF |
| 9 |
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY |
| 10 |
* SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
| 11 |
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION |
| 12 |
* OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN |
| 13 |
* CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ |
| 14 |
|
| 15 |
/* Developers and authors: |
| 16 |
* Shay Gueron (1, 2), and Vlad Krasnov (1) |
| 17 |
* (1) Intel Corporation, Israel Development Center |
| 18 |
* (2) University of Haifa |
| 19 |
* Reference: |
| 20 |
* S.Gueron and V.Krasnov, "Fast Prime Field Elliptic Curve Cryptography with |
| 21 |
* 256 Bit Primes" */ |
| 22 |
|
| 23 |
#include <openssl/ec.h> |
| 24 |
|
| 25 |
#include <assert.h> |
| 26 |
#include <stdint.h> |
| 27 |
#include <string.h> |
| 28 |
|
| 29 |
#include <openssl/bn.h> |
| 30 |
#include <openssl/crypto.h> |
| 31 |
#include <openssl/err.h> |
| 32 |
|
| 33 |
#include "../bn/internal.h" |
| 34 |
#include "../ec/internal.h" |
| 35 |
#include "../internal.h" |
| 36 |
|
| 37 |
|
| 38 |
#if !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64) && \ |
| 39 |
!defined(OPENSSL_SMALL) |
| 40 |
|
| 41 |
|
| 42 |
#define P256_LIMBS (256 / BN_BITS2) |
| 43 |
|
| 44 |
typedef struct { |
| 45 |
BN_ULONG X[P256_LIMBS]; |
| 46 |
BN_ULONG Y[P256_LIMBS]; |
| 47 |
BN_ULONG Z[P256_LIMBS]; |
| 48 |
} P256_POINT; |
| 49 |
|
| 50 |
typedef struct { |
| 51 |
BN_ULONG X[P256_LIMBS]; |
| 52 |
BN_ULONG Y[P256_LIMBS]; |
| 53 |
} P256_POINT_AFFINE; |
| 54 |
|
| 55 |
typedef P256_POINT_AFFINE PRECOMP256_ROW[64]; |
| 56 |
|
| 57 |
/* Functions implemented in assembly */ |
| 58 |
|
| 59 |
/* Modular neg: res = -a mod P */ |
| 60 |
void ecp_nistz256_neg(BN_ULONG res[P256_LIMBS], const BN_ULONG a[P256_LIMBS]); |
| 61 |
/* Montgomery mul: res = a*b*2^-256 mod P */ |
| 62 |
void ecp_nistz256_mul_mont(BN_ULONG res[P256_LIMBS], |
| 63 |
const BN_ULONG a[P256_LIMBS], |
| 64 |
const BN_ULONG b[P256_LIMBS]); |
| 65 |
/* Montgomery sqr: res = a*a*2^-256 mod P */ |
| 66 |
void ecp_nistz256_sqr_mont(BN_ULONG res[P256_LIMBS], |
| 67 |
const BN_ULONG a[P256_LIMBS]); |
| 68 |
/* Convert a number from Montgomery domain, by multiplying with 1 */ |
| 69 |
void ecp_nistz256_from_mont(BN_ULONG res[P256_LIMBS], |
| 70 |
const BN_ULONG in[P256_LIMBS]); |
| 71 |
/* Functions that perform constant time access to the precomputed tables */ |
| 72 |
void ecp_nistz256_select_w5(P256_POINT *val, const P256_POINT *in_t, int index); |
| 73 |
void ecp_nistz256_select_w7(P256_POINT_AFFINE *val, |
| 74 |
const P256_POINT_AFFINE *in_t, int index); |
| 75 |
|
| 76 |
/* One converted into the Montgomery domain */ |
| 77 |
static const BN_ULONG ONE[P256_LIMBS] = { |
| 78 |
TOBN(0x00000000, 0x00000001), TOBN(0xffffffff, 0x00000000), |
| 79 |
TOBN(0xffffffff, 0xffffffff), TOBN(0x00000000, 0xfffffffe), |
| 80 |
}; |
| 81 |
|
| 82 |
/* Precomputed tables for the default generator */ |
| 83 |
#include "p256-x86_64-table.h" |
| 84 |
|
| 85 |
/* Recode window to a signed digit, see ecp_nistputil.c for details */ |
| 86 |
static unsigned booth_recode_w5(unsigned in) { |
| 87 |
unsigned s, d; |
| 88 |
|
| 89 |
s = ~((in >> 5) - 1); |
| 90 |
d = (1 << 6) - in - 1; |
| 91 |
d = (d & s) | (in & ~s); |
| 92 |
d = (d >> 1) + (d & 1); |
| 93 |
|
| 94 |
return (d << 1) + (s & 1); |
| 95 |
} |
| 96 |
|
| 97 |
static unsigned booth_recode_w7(unsigned in) { |
| 98 |
unsigned s, d; |
| 99 |
|
| 100 |
s = ~((in >> 7) - 1); |
| 101 |
d = (1 << 8) - in - 1; |
| 102 |
d = (d & s) | (in & ~s); |
| 103 |
d = (d >> 1) + (d & 1); |
| 104 |
|
| 105 |
return (d << 1) + (s & 1); |
| 106 |
} |
| 107 |
|
| 108 |
static void copy_conditional(BN_ULONG dst[P256_LIMBS], |
| 109 |
const BN_ULONG src[P256_LIMBS], BN_ULONG move) { |
| 110 |
BN_ULONG mask1 = ((BN_ULONG)0) - move; |
| 111 |
BN_ULONG mask2 = ~mask1; |
| 112 |
|
| 113 |
dst[0] = (src[0] & mask1) ^ (dst[0] & mask2); |
| 114 |
dst[1] = (src[1] & mask1) ^ (dst[1] & mask2); |
| 115 |
dst[2] = (src[2] & mask1) ^ (dst[2] & mask2); |
| 116 |
dst[3] = (src[3] & mask1) ^ (dst[3] & mask2); |
| 117 |
if (P256_LIMBS == 8) { |
| 118 |
dst[4] = (src[4] & mask1) ^ (dst[4] & mask2); |
| 119 |
dst[5] = (src[5] & mask1) ^ (dst[5] & mask2); |
| 120 |
dst[6] = (src[6] & mask1) ^ (dst[6] & mask2); |
| 121 |
dst[7] = (src[7] & mask1) ^ (dst[7] & mask2); |
| 122 |
} |
| 123 |
} |
| 124 |
|
| 125 |
void ecp_nistz256_point_double(P256_POINT *r, const P256_POINT *a); |
| 126 |
void ecp_nistz256_point_add(P256_POINT *r, const P256_POINT *a, |
| 127 |
const P256_POINT *b); |
| 128 |
void ecp_nistz256_point_add_affine(P256_POINT *r, const P256_POINT *a, |
| 129 |
const P256_POINT_AFFINE *b); |
| 130 |
|
| 131 |
/* r = in^-1 mod p */ |
| 132 |
static void ecp_nistz256_mod_inverse(BN_ULONG r[P256_LIMBS], |
| 133 |
const BN_ULONG in[P256_LIMBS]) { |
| 134 |
/* The poly is ffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff |
| 135 |
ffffffff |
| 136 |
We use FLT and used poly-2 as exponent */ |
| 137 |
BN_ULONG p2[P256_LIMBS]; |
| 138 |
BN_ULONG p4[P256_LIMBS]; |
| 139 |
BN_ULONG p8[P256_LIMBS]; |
| 140 |
BN_ULONG p16[P256_LIMBS]; |
| 141 |
BN_ULONG p32[P256_LIMBS]; |
| 142 |
BN_ULONG res[P256_LIMBS]; |
| 143 |
int i; |
| 144 |
|
| 145 |
ecp_nistz256_sqr_mont(res, in); |
| 146 |
ecp_nistz256_mul_mont(p2, res, in); /* 3*p */ |
| 147 |
|
| 148 |
ecp_nistz256_sqr_mont(res, p2); |
| 149 |
ecp_nistz256_sqr_mont(res, res); |
| 150 |
ecp_nistz256_mul_mont(p4, res, p2); /* f*p */ |
| 151 |
|
| 152 |
ecp_nistz256_sqr_mont(res, p4); |
| 153 |
ecp_nistz256_sqr_mont(res, res); |
| 154 |
ecp_nistz256_sqr_mont(res, res); |
| 155 |
ecp_nistz256_sqr_mont(res, res); |
| 156 |
ecp_nistz256_mul_mont(p8, res, p4); /* ff*p */ |
| 157 |
|
| 158 |
ecp_nistz256_sqr_mont(res, p8); |
| 159 |
for (i = 0; i < 7; i++) { |
| 160 |
ecp_nistz256_sqr_mont(res, res); |
| 161 |
} |
| 162 |
ecp_nistz256_mul_mont(p16, res, p8); /* ffff*p */ |
| 163 |
|
| 164 |
ecp_nistz256_sqr_mont(res, p16); |
| 165 |
for (i = 0; i < 15; i++) { |
| 166 |
ecp_nistz256_sqr_mont(res, res); |
| 167 |
} |
| 168 |
ecp_nistz256_mul_mont(p32, res, p16); /* ffffffff*p */ |
| 169 |
|
| 170 |
ecp_nistz256_sqr_mont(res, p32); |
| 171 |
for (i = 0; i < 31; i++) { |
| 172 |
ecp_nistz256_sqr_mont(res, res); |
| 173 |
} |
| 174 |
ecp_nistz256_mul_mont(res, res, in); |
| 175 |
|
| 176 |
for (i = 0; i < 32 * 4; i++) { |
| 177 |
ecp_nistz256_sqr_mont(res, res); |
| 178 |
} |
| 179 |
ecp_nistz256_mul_mont(res, res, p32); |
| 180 |
|
| 181 |
for (i = 0; i < 32; i++) { |
| 182 |
ecp_nistz256_sqr_mont(res, res); |
| 183 |
} |
| 184 |
ecp_nistz256_mul_mont(res, res, p32); |
| 185 |
|
| 186 |
for (i = 0; i < 16; i++) { |
| 187 |
ecp_nistz256_sqr_mont(res, res); |
| 188 |
} |
| 189 |
ecp_nistz256_mul_mont(res, res, p16); |
| 190 |
|
| 191 |
for (i = 0; i < 8; i++) { |
| 192 |
ecp_nistz256_sqr_mont(res, res); |
| 193 |
} |
| 194 |
ecp_nistz256_mul_mont(res, res, p8); |
| 195 |
|
| 196 |
ecp_nistz256_sqr_mont(res, res); |
| 197 |
ecp_nistz256_sqr_mont(res, res); |
| 198 |
ecp_nistz256_sqr_mont(res, res); |
| 199 |
ecp_nistz256_sqr_mont(res, res); |
| 200 |
ecp_nistz256_mul_mont(res, res, p4); |
| 201 |
|
| 202 |
ecp_nistz256_sqr_mont(res, res); |
| 203 |
ecp_nistz256_sqr_mont(res, res); |
| 204 |
ecp_nistz256_mul_mont(res, res, p2); |
| 205 |
|
| 206 |
ecp_nistz256_sqr_mont(res, res); |
| 207 |
ecp_nistz256_sqr_mont(res, res); |
| 208 |
ecp_nistz256_mul_mont(r, res, in); |
| 209 |
} |
| 210 |
|
| 211 |
/* ecp_nistz256_bignum_to_field_elem copies the contents of |in| to |out| and |
| 212 |
* returns one if it fits. Otherwise it returns zero. */ |
| 213 |
static int ecp_nistz256_bignum_to_field_elem(BN_ULONG out[P256_LIMBS], |
| 214 |
const BIGNUM *in) { |
| 215 |
if (in->top > P256_LIMBS) { |
| 216 |
return 0; |
| 217 |
} |
| 218 |
|
| 219 |
memset(out, 0, sizeof(BN_ULONG) * P256_LIMBS); |
| 220 |
memcpy(out, in->d, sizeof(BN_ULONG) * in->top); |
| 221 |
return 1; |
| 222 |
} |
| 223 |
|
| 224 |
/* r = p * p_scalar */ |
| 225 |
static int ecp_nistz256_windowed_mul(const EC_GROUP *group, P256_POINT *r, |
| 226 |
const EC_POINT *p, const BIGNUM *p_scalar, |
| 227 |
BN_CTX *ctx) { |
| 228 |
assert(p != NULL); |
| 229 |
assert(p_scalar != NULL); |
| 230 |
|
| 231 |
static const unsigned kWindowSize = 5; |
| 232 |
static const unsigned kMask = (1 << (5 /* kWindowSize */ + 1)) - 1; |
| 233 |
|
| 234 |
/* A |P256_POINT| is (3 * 32) = 96 bytes, and the 64-byte alignment should |
| 235 |
* add no more than 63 bytes of overhead. Thus, |table| should require |
| 236 |
* ~1599 ((96 * 16) + 63) bytes of stack space. */ |
| 237 |
alignas(64) P256_POINT table[16]; |
| 238 |
uint8_t p_str[33]; |
| 239 |
|
| 240 |
|
| 241 |
int ret = 0; |
| 242 |
BN_CTX *new_ctx = NULL; |
| 243 |
int ctx_started = 0; |
| 244 |
|
| 245 |
if (BN_num_bits(p_scalar) > 256 || BN_is_negative(p_scalar)) { |
| 246 |
if (ctx == NULL) { |
| 247 |
new_ctx = BN_CTX_new(); |
| 248 |
if (new_ctx == NULL) { |
| 249 |
OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE); |
| 250 |
goto err; |
| 251 |
} |
| 252 |
ctx = new_ctx; |
| 253 |
} |
| 254 |
BN_CTX_start(ctx); |
| 255 |
ctx_started = 1; |
| 256 |
BIGNUM *mod = BN_CTX_get(ctx); |
| 257 |
if (mod == NULL) { |
| 258 |
OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE); |
| 259 |
goto err; |
| 260 |
} |
| 261 |
if (!BN_nnmod(mod, p_scalar, &group->order, ctx)) { |
| 262 |
OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); |
| 263 |
goto err; |
| 264 |
} |
| 265 |
p_scalar = mod; |
| 266 |
} |
| 267 |
|
| 268 |
int j; |
| 269 |
for (j = 0; j < p_scalar->top * BN_BYTES; j += BN_BYTES) { |
| 270 |
BN_ULONG d = p_scalar->d[j / BN_BYTES]; |
| 271 |
|
| 272 |
p_str[j + 0] = d & 0xff; |
| 273 |
p_str[j + 1] = (d >> 8) & 0xff; |
| 274 |
p_str[j + 2] = (d >> 16) & 0xff; |
| 275 |
p_str[j + 3] = (d >>= 24) & 0xff; |
| 276 |
if (BN_BYTES == 8) { |
| 277 |
d >>= 8; |
| 278 |
p_str[j + 4] = d & 0xff; |
| 279 |
p_str[j + 5] = (d >> 8) & 0xff; |
| 280 |
p_str[j + 6] = (d >> 16) & 0xff; |
| 281 |
p_str[j + 7] = (d >> 24) & 0xff; |
| 282 |
} |
| 283 |
} |
| 284 |
|
| 285 |
for (; j < 33; j++) { |
| 286 |
p_str[j] = 0; |
| 287 |
} |
| 288 |
|
| 289 |
/* table[0] is implicitly (0,0,0) (the point at infinity), therefore it is |
| 290 |
* not stored. All other values are actually stored with an offset of -1 in |
| 291 |
* table. */ |
| 292 |
P256_POINT *row = table; |
| 293 |
|
| 294 |
if (!ecp_nistz256_bignum_to_field_elem(row[1 - 1].X, &p->X) || |
| 295 |
!ecp_nistz256_bignum_to_field_elem(row[1 - 1].Y, &p->Y) || |
| 296 |
!ecp_nistz256_bignum_to_field_elem(row[1 - 1].Z, &p->Z)) { |
| 297 |
OPENSSL_PUT_ERROR(EC, EC_R_COORDINATES_OUT_OF_RANGE); |
| 298 |
goto err; |
| 299 |
} |
| 300 |
|
| 301 |
ecp_nistz256_point_double(&row[2 - 1], &row[1 - 1]); |
| 302 |
ecp_nistz256_point_add(&row[3 - 1], &row[2 - 1], &row[1 - 1]); |
| 303 |
ecp_nistz256_point_double(&row[4 - 1], &row[2 - 1]); |
| 304 |
ecp_nistz256_point_double(&row[6 - 1], &row[3 - 1]); |
| 305 |
ecp_nistz256_point_double(&row[8 - 1], &row[4 - 1]); |
| 306 |
ecp_nistz256_point_double(&row[12 - 1], &row[6 - 1]); |
| 307 |
ecp_nistz256_point_add(&row[5 - 1], &row[4 - 1], &row[1 - 1]); |
| 308 |
ecp_nistz256_point_add(&row[7 - 1], &row[6 - 1], &row[1 - 1]); |
| 309 |
ecp_nistz256_point_add(&row[9 - 1], &row[8 - 1], &row[1 - 1]); |
| 310 |
ecp_nistz256_point_add(&row[13 - 1], &row[12 - 1], &row[1 - 1]); |
| 311 |
ecp_nistz256_point_double(&row[14 - 1], &row[7 - 1]); |
| 312 |
ecp_nistz256_point_double(&row[10 - 1], &row[5 - 1]); |
| 313 |
ecp_nistz256_point_add(&row[15 - 1], &row[14 - 1], &row[1 - 1]); |
| 314 |
ecp_nistz256_point_add(&row[11 - 1], &row[10 - 1], &row[1 - 1]); |
| 315 |
ecp_nistz256_point_add(&row[16 - 1], &row[15 - 1], &row[1 - 1]); |
| 316 |
|
| 317 |
BN_ULONG tmp[P256_LIMBS]; |
| 318 |
alignas(32) P256_POINT h; |
| 319 |
unsigned index = 255; |
| 320 |
unsigned wvalue = p_str[(index - 1) / 8]; |
| 321 |
wvalue = (wvalue >> ((index - 1) % 8)) & kMask; |
| 322 |
|
| 323 |
ecp_nistz256_select_w5(r, table, booth_recode_w5(wvalue) >> 1); |
| 324 |
|
| 325 |
while (index >= 5) { |
| 326 |
if (index != 255) { |
| 327 |
unsigned off = (index - 1) / 8; |
| 328 |
|
| 329 |
wvalue = p_str[off] | p_str[off + 1] << 8; |
| 330 |
wvalue = (wvalue >> ((index - 1) % 8)) & kMask; |
| 331 |
|
| 332 |
wvalue = booth_recode_w5(wvalue); |
| 333 |
|
| 334 |
ecp_nistz256_select_w5(&h, table, wvalue >> 1); |
| 335 |
|
| 336 |
ecp_nistz256_neg(tmp, h.Y); |
| 337 |
copy_conditional(h.Y, tmp, (wvalue & 1)); |
| 338 |
|
| 339 |
ecp_nistz256_point_add(r, r, &h); |
| 340 |
} |
| 341 |
|
| 342 |
index -= kWindowSize; |
| 343 |
|
| 344 |
ecp_nistz256_point_double(r, r); |
| 345 |
ecp_nistz256_point_double(r, r); |
| 346 |
ecp_nistz256_point_double(r, r); |
| 347 |
ecp_nistz256_point_double(r, r); |
| 348 |
ecp_nistz256_point_double(r, r); |
| 349 |
} |
| 350 |
|
| 351 |
/* Final window */ |
| 352 |
wvalue = p_str[0]; |
| 353 |
wvalue = (wvalue << 1) & kMask; |
| 354 |
|
| 355 |
wvalue = booth_recode_w5(wvalue); |
| 356 |
|
| 357 |
ecp_nistz256_select_w5(&h, table, wvalue >> 1); |
| 358 |
|
| 359 |
ecp_nistz256_neg(tmp, h.Y); |
| 360 |
copy_conditional(h.Y, tmp, wvalue & 1); |
| 361 |
|
| 362 |
ecp_nistz256_point_add(r, r, &h); |
| 363 |
|
| 364 |
ret = 1; |
| 365 |
|
| 366 |
err: |
| 367 |
if (ctx_started) { |
| 368 |
BN_CTX_end(ctx); |
| 369 |
} |
| 370 |
BN_CTX_free(new_ctx); |
| 371 |
return ret; |
| 372 |
} |
| 373 |
|
| 374 |
static int ecp_nistz256_points_mul( |
| 375 |
const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar, |
| 376 |
const EC_POINT *p_, const BIGNUM *p_scalar, BN_CTX *ctx) { |
| 377 |
assert((p_ != NULL) == (p_scalar != NULL)); |
| 378 |
|
| 379 |
static const unsigned kWindowSize = 7; |
| 380 |
static const unsigned kMask = (1 << (7 /* kWindowSize */ + 1)) - 1; |
| 381 |
|
| 382 |
alignas(32) union { |
| 383 |
P256_POINT p; |
| 384 |
P256_POINT_AFFINE a; |
| 385 |
} t, p; |
| 386 |
|
| 387 |
int ret = 0; |
| 388 |
BN_CTX *new_ctx = NULL; |
| 389 |
int ctx_started = 0; |
| 390 |
|
| 391 |
if (g_scalar != NULL) { |
| 392 |
if (BN_num_bits(g_scalar) > 256 || BN_is_negative(g_scalar)) { |
| 393 |
if (ctx == NULL) { |
| 394 |
new_ctx = BN_CTX_new(); |
| 395 |
if (new_ctx == NULL) { |
| 396 |
goto err; |
| 397 |
} |
| 398 |
ctx = new_ctx; |
| 399 |
} |
| 400 |
BN_CTX_start(ctx); |
| 401 |
ctx_started = 1; |
| 402 |
BIGNUM *tmp_scalar = BN_CTX_get(ctx); |
| 403 |
if (tmp_scalar == NULL) { |
| 404 |
goto err; |
| 405 |
} |
| 406 |
|
| 407 |
if (!BN_nnmod(tmp_scalar, g_scalar, &group->order, ctx)) { |
| 408 |
OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); |
| 409 |
goto err; |
| 410 |
} |
| 411 |
g_scalar = tmp_scalar; |
| 412 |
} |
| 413 |
|
| 414 |
uint8_t p_str[33] = {0}; |
| 415 |
int i; |
| 416 |
for (i = 0; i < g_scalar->top * BN_BYTES; i += BN_BYTES) { |
| 417 |
BN_ULONG d = g_scalar->d[i / BN_BYTES]; |
| 418 |
|
| 419 |
p_str[i + 0] = d & 0xff; |
| 420 |
p_str[i + 1] = (d >> 8) & 0xff; |
| 421 |
p_str[i + 2] = (d >> 16) & 0xff; |
| 422 |
p_str[i + 3] = (d >>= 24) & 0xff; |
| 423 |
if (BN_BYTES == 8) { |
| 424 |
d >>= 8; |
| 425 |
p_str[i + 4] = d & 0xff; |
| 426 |
p_str[i + 5] = (d >> 8) & 0xff; |
| 427 |
p_str[i + 6] = (d >> 16) & 0xff; |
| 428 |
p_str[i + 7] = (d >> 24) & 0xff; |
| 429 |
} |
| 430 |
} |
| 431 |
|
| 432 |
for (; i < (int) sizeof(p_str); i++) { |
| 433 |
p_str[i] = 0; |
| 434 |
} |
| 435 |
|
| 436 |
/* First window */ |
| 437 |
unsigned wvalue = (p_str[0] << 1) & kMask; |
| 438 |
unsigned index = kWindowSize; |
| 439 |
|
| 440 |
wvalue = booth_recode_w7(wvalue); |
| 441 |
|
| 442 |
const PRECOMP256_ROW *const precomputed_table = |
| 443 |
(const PRECOMP256_ROW *)ecp_nistz256_precomputed; |
| 444 |
ecp_nistz256_select_w7(&p.a, precomputed_table[0], wvalue >> 1); |
| 445 |
|
| 446 |
ecp_nistz256_neg(p.p.Z, p.p.Y); |
| 447 |
copy_conditional(p.p.Y, p.p.Z, wvalue & 1); |
| 448 |
|
| 449 |
memcpy(p.p.Z, ONE, sizeof(ONE)); |
| 450 |
|
| 451 |
for (i = 1; i < 37; i++) { |
| 452 |
unsigned off = (index - 1) / 8; |
| 453 |
wvalue = p_str[off] | p_str[off + 1] << 8; |
| 454 |
wvalue = (wvalue >> ((index - 1) % 8)) & kMask; |
| 455 |
index += kWindowSize; |
| 456 |
|
| 457 |
wvalue = booth_recode_w7(wvalue); |
| 458 |
|
| 459 |
ecp_nistz256_select_w7(&t.a, precomputed_table[i], wvalue >> 1); |
| 460 |
|
| 461 |
ecp_nistz256_neg(t.p.Z, t.a.Y); |
| 462 |
copy_conditional(t.a.Y, t.p.Z, wvalue & 1); |
| 463 |
|
| 464 |
ecp_nistz256_point_add_affine(&p.p, &p.p, &t.a); |
| 465 |
} |
| 466 |
} |
| 467 |
|
| 468 |
const int p_is_infinity = g_scalar == NULL; |
| 469 |
if (p_scalar != NULL) { |
| 470 |
P256_POINT *out = &t.p; |
| 471 |
if (p_is_infinity) { |
| 472 |
out = &p.p; |
| 473 |
} |
| 474 |
|
| 475 |
if (!ecp_nistz256_windowed_mul(group, out, p_, p_scalar, ctx)) { |
| 476 |
goto err; |
| 477 |
} |
| 478 |
|
| 479 |
if (!p_is_infinity) { |
| 480 |
ecp_nistz256_point_add(&p.p, &p.p, out); |
| 481 |
} |
| 482 |
} |
| 483 |
|
| 484 |
/* Not constant-time, but we're only operating on the public output. */ |
| 485 |
if (!bn_set_words(&r->X, p.p.X, P256_LIMBS) || |
| 486 |
!bn_set_words(&r->Y, p.p.Y, P256_LIMBS) || |
| 487 |
!bn_set_words(&r->Z, p.p.Z, P256_LIMBS)) { |
| 488 |
return 0; |
| 489 |
} |
| 490 |
|
| 491 |
ret = 1; |
| 492 |
|
| 493 |
err: |
| 494 |
if (ctx_started) { |
| 495 |
BN_CTX_end(ctx); |
| 496 |
} |
| 497 |
BN_CTX_free(new_ctx); |
| 498 |
return ret; |
| 499 |
} |
| 500 |
|
| 501 |
static int ecp_nistz256_get_affine(const EC_GROUP *group, const EC_POINT *point, |
| 502 |
BIGNUM *x, BIGNUM *y, BN_CTX *ctx) { |
| 503 |
BN_ULONG z_inv2[P256_LIMBS]; |
| 504 |
BN_ULONG z_inv3[P256_LIMBS]; |
| 505 |
BN_ULONG point_x[P256_LIMBS], point_y[P256_LIMBS], point_z[P256_LIMBS]; |
| 506 |
|
| 507 |
if (EC_POINT_is_at_infinity(group, point)) { |
| 508 |
OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY); |
| 509 |
return 0; |
| 510 |
} |
| 511 |
|
| 512 |
if (!ecp_nistz256_bignum_to_field_elem(point_x, &point->X) || |
| 513 |
!ecp_nistz256_bignum_to_field_elem(point_y, &point->Y) || |
| 514 |
!ecp_nistz256_bignum_to_field_elem(point_z, &point->Z)) { |
| 515 |
OPENSSL_PUT_ERROR(EC, EC_R_COORDINATES_OUT_OF_RANGE); |
| 516 |
return 0; |
| 517 |
} |
| 518 |
|
| 519 |
ecp_nistz256_mod_inverse(z_inv3, point_z); |
| 520 |
ecp_nistz256_sqr_mont(z_inv2, z_inv3); |
| 521 |
|
| 522 |
/* Instead of using |ecp_nistz256_from_mont| to convert the |x| coordinate |
| 523 |
* and then calling |ecp_nistz256_from_mont| again to convert the |y| |
| 524 |
* coordinate below, convert the common factor |z_inv2| once now, saving one |
| 525 |
* reduction. */ |
| 526 |
ecp_nistz256_from_mont(z_inv2, z_inv2); |
| 527 |
|
| 528 |
if (x != NULL) { |
| 529 |
if (bn_wexpand(x, P256_LIMBS) == NULL) { |
| 530 |
OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE); |
| 531 |
return 0; |
| 532 |
} |
| 533 |
x->top = P256_LIMBS; |
| 534 |
x->neg = 0; |
| 535 |
ecp_nistz256_mul_mont(x->d, z_inv2, point_x); |
| 536 |
bn_correct_top(x); |
| 537 |
} |
| 538 |
|
| 539 |
if (y != NULL) { |
| 540 |
ecp_nistz256_mul_mont(z_inv3, z_inv3, z_inv2); |
| 541 |
if (bn_wexpand(y, P256_LIMBS) == NULL) { |
| 542 |
OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE); |
| 543 |
return 0; |
| 544 |
} |
| 545 |
y->top = P256_LIMBS; |
| 546 |
y->neg = 0; |
| 547 |
ecp_nistz256_mul_mont(y->d, z_inv3, point_y); |
| 548 |
bn_correct_top(y); |
| 549 |
} |
| 550 |
|
| 551 |
return 1; |
| 552 |
} |
| 553 |
|
| 554 |
const EC_METHOD *EC_GFp_nistz256_method(void) { |
| 555 |
static const EC_METHOD ret = { |
| 556 |
ec_GFp_mont_group_init, |
| 557 |
ec_GFp_mont_group_finish, |
| 558 |
ec_GFp_mont_group_copy, |
| 559 |
ec_GFp_mont_group_set_curve, |
| 560 |
ecp_nistz256_get_affine, |
| 561 |
ecp_nistz256_points_mul, |
| 562 |
0 /* check_pub_key_order */, |
| 563 |
ec_GFp_mont_field_mul, |
| 564 |
ec_GFp_mont_field_sqr, |
| 565 |
ec_GFp_mont_field_encode, |
| 566 |
ec_GFp_mont_field_decode, |
| 567 |
}; |
| 568 |
|
| 569 |
return &ret; |
| 570 |
} |
| 571 |
|
| 572 |
#endif /* !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64) && \ |
| 573 |
!defined(OPENSSL_SMALL) */ |