1/* 2 * Copyright 2001-2016 The OpenSSL Project Authors. All Rights Reserved. 3 * Copyright (c) 2002, Oracle and/or its affiliates. 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 11#include <openssl/ec.h> 12 13#include <openssl/bn.h> 14#include <openssl/err.h> 15#include <openssl/mem.h> 16 17#include "../bn/internal.h" 18#include "../delocate.h" 19#include "internal.h" 20 21 22static void ec_GFp_mont_felem_to_montgomery(const EC_GROUP *group, 23 EC_FELEM *out, const EC_FELEM *in) { 24 bn_to_montgomery_small(out->words, in->words, group->field.N.width, 25 &group->field); 26} 27 28static void ec_GFp_mont_felem_from_montgomery(const EC_GROUP *group, 29 EC_FELEM *out, 30 const EC_FELEM *in) { 31 bn_from_montgomery_small(out->words, group->field.N.width, in->words, 32 group->field.N.width, &group->field); 33} 34 35static void ec_GFp_mont_felem_inv0(const EC_GROUP *group, EC_FELEM *out, 36 const EC_FELEM *a) { 37 bn_mod_inverse0_prime_mont_small(out->words, a->words, group->field.N.width, 38 &group->field); 39} 40 41void ec_GFp_mont_felem_mul(const EC_GROUP *group, EC_FELEM *r, 42 const EC_FELEM *a, const EC_FELEM *b) { 43 bn_mod_mul_montgomery_small(r->words, a->words, b->words, 44 group->field.N.width, &group->field); 45} 46 47void ec_GFp_mont_felem_sqr(const EC_GROUP *group, EC_FELEM *r, 48 const EC_FELEM *a) { 49 bn_mod_mul_montgomery_small(r->words, a->words, a->words, 50 group->field.N.width, &group->field); 51} 52 53void ec_GFp_mont_felem_to_bytes(const EC_GROUP *group, uint8_t *out, 54 size_t *out_len, const EC_FELEM *in) { 55 EC_FELEM tmp; 56 ec_GFp_mont_felem_from_montgomery(group, &tmp, in); 57 ec_GFp_simple_felem_to_bytes(group, out, out_len, &tmp); 58} 59 60int ec_GFp_mont_felem_from_bytes(const EC_GROUP *group, EC_FELEM *out, 61 const uint8_t *in, size_t len) { 62 if (!ec_GFp_simple_felem_from_bytes(group, out, in, len)) { 63 return 0; 64 } 65 66 ec_GFp_mont_felem_to_montgomery(group, out, out); 67 return 1; 68} 69 70void ec_GFp_mont_felem_reduce(const EC_GROUP *group, EC_FELEM *out, 71 const BN_ULONG *words, size_t num) { 72 // Convert "from" Montgomery form so the value is reduced mod p. 73 bn_from_montgomery_small(out->words, group->field.N.width, words, num, 74 &group->field); 75 // Convert "to" Montgomery form to remove the R^-1 factor added. 76 ec_GFp_mont_felem_to_montgomery(group, out, out); 77 // Convert to Montgomery form to match this implementation's representation. 78 ec_GFp_mont_felem_to_montgomery(group, out, out); 79} 80 81void ec_GFp_mont_felem_exp(const EC_GROUP *group, EC_FELEM *out, 82 const EC_FELEM *a, const BN_ULONG *exp, 83 size_t num_exp) { 84 bn_mod_exp_mont_small(out->words, a->words, group->field.N.width, exp, 85 num_exp, &group->field); 86} 87 88static int ec_GFp_mont_point_get_affine_coordinates(const EC_GROUP *group, 89 const EC_JACOBIAN *point, 90 EC_FELEM *x, EC_FELEM *y) { 91 if (constant_time_declassify_int( 92 ec_GFp_simple_is_at_infinity(group, point))) { 93 OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY); 94 return 0; 95 } 96 97 // Transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3). Note the check above 98 // ensures |point->Z| is non-zero, so the inverse always exists. 99 EC_FELEM z1, z2; 100 ec_GFp_mont_felem_inv0(group, &z2, &point->Z); 101 ec_GFp_mont_felem_sqr(group, &z1, &z2); 102 103 if (x != NULL) { 104 ec_GFp_mont_felem_mul(group, x, &point->X, &z1); 105 } 106 107 if (y != NULL) { 108 ec_GFp_mont_felem_mul(group, &z1, &z1, &z2); 109 ec_GFp_mont_felem_mul(group, y, &point->Y, &z1); 110 } 111 112 return 1; 113} 114 115static int ec_GFp_mont_jacobian_to_affine_batch(const EC_GROUP *group, 116 EC_AFFINE *out, 117 const EC_JACOBIAN *in, 118 size_t num) { 119 if (num == 0) { 120 return 1; 121 } 122 123 // Compute prefix products of all Zs. Use |out[i].X| as scratch space 124 // to store these values. 125 out[0].X = in[0].Z; 126 for (size_t i = 1; i < num; i++) { 127 ec_GFp_mont_felem_mul(group, &out[i].X, &out[i - 1].X, &in[i].Z); 128 } 129 130 // Some input was infinity iff the product of all Zs is zero. 131 if (ec_felem_non_zero_mask(group, &out[num - 1].X) == 0) { 132 OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY); 133 return 0; 134 } 135 136 // Invert the product of all Zs. 137 EC_FELEM zinvprod; 138 ec_GFp_mont_felem_inv0(group, &zinvprod, &out[num - 1].X); 139 for (size_t i = num - 1; i < num; i--) { 140 // Our loop invariant is that |zinvprod| is Z0^-1 * Z1^-1 * ... * Zi^-1. 141 // Recover Zi^-1 by multiplying by the previous product. 142 EC_FELEM zinv, zinv2; 143 if (i == 0) { 144 zinv = zinvprod; 145 } else { 146 ec_GFp_mont_felem_mul(group, &zinv, &zinvprod, &out[i - 1].X); 147 // Maintain the loop invariant for the next iteration. 148 ec_GFp_mont_felem_mul(group, &zinvprod, &zinvprod, &in[i].Z); 149 } 150 151 // Compute affine coordinates: x = X * Z^-2 and y = Y * Z^-3. 152 ec_GFp_mont_felem_sqr(group, &zinv2, &zinv); 153 ec_GFp_mont_felem_mul(group, &out[i].X, &in[i].X, &zinv2); 154 ec_GFp_mont_felem_mul(group, &out[i].Y, &in[i].Y, &zinv2); 155 ec_GFp_mont_felem_mul(group, &out[i].Y, &out[i].Y, &zinv); 156 } 157 158 return 1; 159} 160 161void ec_GFp_mont_add(const EC_GROUP *group, EC_JACOBIAN *out, 162 const EC_JACOBIAN *a, const EC_JACOBIAN *b) { 163 if (a == b) { 164 ec_GFp_mont_dbl(group, out, a); 165 return; 166 } 167 168 // The method is taken from: 169 // http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-add-2007-bl 170 // 171 // Coq transcription and correctness proof: 172 // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L467> 173 // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L544> 174 EC_FELEM x_out, y_out, z_out; 175 BN_ULONG z1nz = ec_felem_non_zero_mask(group, &a->Z); 176 BN_ULONG z2nz = ec_felem_non_zero_mask(group, &b->Z); 177 178 // z1z1 = z1z1 = z1**2 179 EC_FELEM z1z1; 180 ec_GFp_mont_felem_sqr(group, &z1z1, &a->Z); 181 182 // z2z2 = z2**2 183 EC_FELEM z2z2; 184 ec_GFp_mont_felem_sqr(group, &z2z2, &b->Z); 185 186 // u1 = x1*z2z2 187 EC_FELEM u1; 188 ec_GFp_mont_felem_mul(group, &u1, &a->X, &z2z2); 189 190 // two_z1z2 = (z1 + z2)**2 - (z1z1 + z2z2) = 2z1z2 191 EC_FELEM two_z1z2; 192 ec_felem_add(group, &two_z1z2, &a->Z, &b->Z); 193 ec_GFp_mont_felem_sqr(group, &two_z1z2, &two_z1z2); 194 ec_felem_sub(group, &two_z1z2, &two_z1z2, &z1z1); 195 ec_felem_sub(group, &two_z1z2, &two_z1z2, &z2z2); 196 197 // s1 = y1 * z2**3 198 EC_FELEM s1; 199 ec_GFp_mont_felem_mul(group, &s1, &b->Z, &z2z2); 200 ec_GFp_mont_felem_mul(group, &s1, &s1, &a->Y); 201 202 // u2 = x2*z1z1 203 EC_FELEM u2; 204 ec_GFp_mont_felem_mul(group, &u2, &b->X, &z1z1); 205 206 // h = u2 - u1 207 EC_FELEM h; 208 ec_felem_sub(group, &h, &u2, &u1); 209 210 BN_ULONG xneq = ec_felem_non_zero_mask(group, &h); 211 212 // z_out = two_z1z2 * h 213 ec_GFp_mont_felem_mul(group, &z_out, &h, &two_z1z2); 214 215 // z1z1z1 = z1 * z1z1 216 EC_FELEM z1z1z1; 217 ec_GFp_mont_felem_mul(group, &z1z1z1, &a->Z, &z1z1); 218 219 // s2 = y2 * z1**3 220 EC_FELEM s2; 221 ec_GFp_mont_felem_mul(group, &s2, &b->Y, &z1z1z1); 222 223 // r = (s2 - s1)*2 224 EC_FELEM r; 225 ec_felem_sub(group, &r, &s2, &s1); 226 ec_felem_add(group, &r, &r, &r); 227 228 BN_ULONG yneq = ec_felem_non_zero_mask(group, &r); 229 230 // This case will never occur in the constant-time |ec_GFp_mont_mul|. 231 BN_ULONG is_nontrivial_double = ~xneq & ~yneq & z1nz & z2nz; 232 if (constant_time_declassify_w(is_nontrivial_double)) { 233 ec_GFp_mont_dbl(group, out, a); 234 return; 235 } 236 237 // I = (2h)**2 238 EC_FELEM i; 239 ec_felem_add(group, &i, &h, &h); 240 ec_GFp_mont_felem_sqr(group, &i, &i); 241 242 // J = h * I 243 EC_FELEM j; 244 ec_GFp_mont_felem_mul(group, &j, &h, &i); 245 246 // V = U1 * I 247 EC_FELEM v; 248 ec_GFp_mont_felem_mul(group, &v, &u1, &i); 249 250 // x_out = r**2 - J - 2V 251 ec_GFp_mont_felem_sqr(group, &x_out, &r); 252 ec_felem_sub(group, &x_out, &x_out, &j); 253 ec_felem_sub(group, &x_out, &x_out, &v); 254 ec_felem_sub(group, &x_out, &x_out, &v); 255 256 // y_out = r(V-x_out) - 2 * s1 * J 257 ec_felem_sub(group, &y_out, &v, &x_out); 258 ec_GFp_mont_felem_mul(group, &y_out, &y_out, &r); 259 EC_FELEM s1j; 260 ec_GFp_mont_felem_mul(group, &s1j, &s1, &j); 261 ec_felem_sub(group, &y_out, &y_out, &s1j); 262 ec_felem_sub(group, &y_out, &y_out, &s1j); 263 264 ec_felem_select(group, &x_out, z1nz, &x_out, &b->X); 265 ec_felem_select(group, &out->X, z2nz, &x_out, &a->X); 266 ec_felem_select(group, &y_out, z1nz, &y_out, &b->Y); 267 ec_felem_select(group, &out->Y, z2nz, &y_out, &a->Y); 268 ec_felem_select(group, &z_out, z1nz, &z_out, &b->Z); 269 ec_felem_select(group, &out->Z, z2nz, &z_out, &a->Z); 270} 271 272void ec_GFp_mont_dbl(const EC_GROUP *group, EC_JACOBIAN *r, 273 const EC_JACOBIAN *a) { 274 if (group->a_is_minus3) { 275 // The method is taken from: 276 // http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b 277 // 278 // Coq transcription and correctness proof: 279 // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/Jacobian.v#L93> 280 // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/Jacobian.v#L201> 281 EC_FELEM delta, gamma, beta, ftmp, ftmp2, tmptmp, alpha, fourbeta; 282 // delta = z^2 283 ec_GFp_mont_felem_sqr(group, &delta, &a->Z); 284 // gamma = y^2 285 ec_GFp_mont_felem_sqr(group, &gamma, &a->Y); 286 // beta = x*gamma 287 ec_GFp_mont_felem_mul(group, &beta, &a->X, &gamma); 288 289 // alpha = 3*(x-delta)*(x+delta) 290 ec_felem_sub(group, &ftmp, &a->X, &delta); 291 ec_felem_add(group, &ftmp2, &a->X, &delta); 292 293 ec_felem_add(group, &tmptmp, &ftmp2, &ftmp2); 294 ec_felem_add(group, &ftmp2, &ftmp2, &tmptmp); 295 ec_GFp_mont_felem_mul(group, &alpha, &ftmp, &ftmp2); 296 297 // x' = alpha^2 - 8*beta 298 ec_GFp_mont_felem_sqr(group, &r->X, &alpha); 299 ec_felem_add(group, &fourbeta, &beta, &beta); 300 ec_felem_add(group, &fourbeta, &fourbeta, &fourbeta); 301 ec_felem_add(group, &tmptmp, &fourbeta, &fourbeta); 302 ec_felem_sub(group, &r->X, &r->X, &tmptmp); 303 304 // z' = (y + z)^2 - gamma - delta 305 ec_felem_add(group, &delta, &gamma, &delta); 306 ec_felem_add(group, &ftmp, &a->Y, &a->Z); 307 ec_GFp_mont_felem_sqr(group, &r->Z, &ftmp); 308 ec_felem_sub(group, &r->Z, &r->Z, &delta); 309 310 // y' = alpha*(4*beta - x') - 8*gamma^2 311 ec_felem_sub(group, &r->Y, &fourbeta, &r->X); 312 ec_felem_add(group, &gamma, &gamma, &gamma); 313 ec_GFp_mont_felem_sqr(group, &gamma, &gamma); 314 ec_GFp_mont_felem_mul(group, &r->Y, &alpha, &r->Y); 315 ec_felem_add(group, &gamma, &gamma, &gamma); 316 ec_felem_sub(group, &r->Y, &r->Y, &gamma); 317 } else { 318 // The method is taken from: 319 // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl 320 // 321 // Coq transcription and correctness proof: 322 // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L102> 323 // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L534> 324 EC_FELEM xx, yy, yyyy, zz; 325 ec_GFp_mont_felem_sqr(group, &xx, &a->X); 326 ec_GFp_mont_felem_sqr(group, &yy, &a->Y); 327 ec_GFp_mont_felem_sqr(group, &yyyy, &yy); 328 ec_GFp_mont_felem_sqr(group, &zz, &a->Z); 329 330 // s = 2*((x_in + yy)^2 - xx - yyyy) 331 EC_FELEM s; 332 ec_felem_add(group, &s, &a->X, &yy); 333 ec_GFp_mont_felem_sqr(group, &s, &s); 334 ec_felem_sub(group, &s, &s, &xx); 335 ec_felem_sub(group, &s, &s, &yyyy); 336 ec_felem_add(group, &s, &s, &s); 337 338 // m = 3*xx + a*zz^2 339 EC_FELEM m; 340 ec_GFp_mont_felem_sqr(group, &m, &zz); 341 ec_GFp_mont_felem_mul(group, &m, &group->a, &m); 342 ec_felem_add(group, &m, &m, &xx); 343 ec_felem_add(group, &m, &m, &xx); 344 ec_felem_add(group, &m, &m, &xx); 345 346 // x_out = m^2 - 2*s 347 ec_GFp_mont_felem_sqr(group, &r->X, &m); 348 ec_felem_sub(group, &r->X, &r->X, &s); 349 ec_felem_sub(group, &r->X, &r->X, &s); 350 351 // z_out = (y_in + z_in)^2 - yy - zz 352 ec_felem_add(group, &r->Z, &a->Y, &a->Z); 353 ec_GFp_mont_felem_sqr(group, &r->Z, &r->Z); 354 ec_felem_sub(group, &r->Z, &r->Z, &yy); 355 ec_felem_sub(group, &r->Z, &r->Z, &zz); 356 357 // y_out = m*(s-x_out) - 8*yyyy 358 ec_felem_add(group, &yyyy, &yyyy, &yyyy); 359 ec_felem_add(group, &yyyy, &yyyy, &yyyy); 360 ec_felem_add(group, &yyyy, &yyyy, &yyyy); 361 ec_felem_sub(group, &r->Y, &s, &r->X); 362 ec_GFp_mont_felem_mul(group, &r->Y, &r->Y, &m); 363 ec_felem_sub(group, &r->Y, &r->Y, &yyyy); 364 } 365} 366 367static int ec_GFp_mont_cmp_x_coordinate(const EC_GROUP *group, 368 const EC_JACOBIAN *p, 369 const EC_SCALAR *r) { 370 if (!group->field_greater_than_order || 371 group->field.N.width != group->order.N.width) { 372 // Do not bother optimizing this case. p > order in all commonly-used 373 // curves. 374 return ec_GFp_simple_cmp_x_coordinate(group, p, r); 375 } 376 377 if (ec_GFp_simple_is_at_infinity(group, p)) { 378 return 0; 379 } 380 381 // We wish to compare X/Z^2 with r. This is equivalent to comparing X with 382 // r*Z^2. Note that X and Z are represented in Montgomery form, while r is 383 // not. 384 EC_FELEM r_Z2, Z2_mont, X; 385 ec_GFp_mont_felem_mul(group, &Z2_mont, &p->Z, &p->Z); 386 // r < order < p, so this is valid. 387 OPENSSL_memcpy(r_Z2.words, r->words, group->field.N.width * sizeof(BN_ULONG)); 388 ec_GFp_mont_felem_mul(group, &r_Z2, &r_Z2, &Z2_mont); 389 ec_GFp_mont_felem_from_montgomery(group, &X, &p->X); 390 391 if (ec_felem_equal(group, &r_Z2, &X)) { 392 return 1; 393 } 394 395 // During signing the x coefficient is reduced modulo the group order. 396 // Therefore there is a small possibility, less than 1/2^128, that group_order 397 // < p.x < P. in that case we need not only to compare against |r| but also to 398 // compare against r+group_order. 399 BN_ULONG carry = bn_add_words(r_Z2.words, r->words, group->order.N.d, 400 group->field.N.width); 401 if (carry == 0 && 402 bn_less_than_words(r_Z2.words, group->field.N.d, group->field.N.width)) { 403 // r + group_order < p, so compare (r + group_order) * Z^2 against X. 404 ec_GFp_mont_felem_mul(group, &r_Z2, &r_Z2, &Z2_mont); 405 if (ec_felem_equal(group, &r_Z2, &X)) { 406 return 1; 407 } 408 } 409 410 return 0; 411} 412 413DEFINE_METHOD_FUNCTION(EC_METHOD, EC_GFp_mont_method) { 414 out->point_get_affine_coordinates = ec_GFp_mont_point_get_affine_coordinates; 415 out->jacobian_to_affine_batch = ec_GFp_mont_jacobian_to_affine_batch; 416 out->add = ec_GFp_mont_add; 417 out->dbl = ec_GFp_mont_dbl; 418 out->mul = ec_GFp_mont_mul; 419 out->mul_base = ec_GFp_mont_mul_base; 420 out->mul_batch = ec_GFp_mont_mul_batch; 421 out->mul_public_batch = ec_GFp_mont_mul_public_batch; 422 out->init_precomp = ec_GFp_mont_init_precomp; 423 out->mul_precomp = ec_GFp_mont_mul_precomp; 424 out->felem_mul = ec_GFp_mont_felem_mul; 425 out->felem_sqr = ec_GFp_mont_felem_sqr; 426 out->felem_to_bytes = ec_GFp_mont_felem_to_bytes; 427 out->felem_from_bytes = ec_GFp_mont_felem_from_bytes; 428 out->felem_reduce = ec_GFp_mont_felem_reduce; 429 out->felem_exp = ec_GFp_mont_felem_exp; 430 out->scalar_inv0_montgomery = ec_simple_scalar_inv0_montgomery; 431 out->scalar_to_montgomery_inv_vartime = 432 ec_simple_scalar_to_montgomery_inv_vartime; 433 out->cmp_x_coordinate = ec_GFp_mont_cmp_x_coordinate; 434} 435