1 /* Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project. 2 * ==================================================================== 3 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in 14 * the documentation and/or other materials provided with the 15 * distribution. 16 * 17 * 3. All advertising materials mentioning features or use of this 18 * software must display the following acknowledgment: 19 * "This product includes software developed by the OpenSSL Project 20 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 21 * 22 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 23 * endorse or promote products derived from this software without 24 * prior written permission. For written permission, please contact 25 * openssl-core (at) openssl.org. 26 * 27 * 5. Products derived from this software may not be called "OpenSSL" 28 * nor may "OpenSSL" appear in their names without prior written 29 * permission of the OpenSSL Project. 30 * 31 * 6. Redistributions of any form whatsoever must retain the following 32 * acknowledgment: 33 * "This product includes software developed by the OpenSSL Project 34 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 35 * 36 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 37 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 38 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 39 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 42 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 43 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 44 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 45 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 46 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 47 * OF THE POSSIBILITY OF SUCH DAMAGE. 48 * ==================================================================== 49 * 50 * This product includes cryptographic software written by Eric Young 51 * (eay (at) cryptsoft.com). This product includes software written by Tim 52 * Hudson (tjh (at) cryptsoft.com). 53 * 54 */ 55 /* ==================================================================== 56 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 57 * 58 * Portions of the attached software ("Contribution") are developed by 59 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project. 60 * 61 * The Contribution is licensed pursuant to the OpenSSL open source 62 * license provided above. 63 * 64 * The elliptic curve binary polynomial software is originally written by 65 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems 66 * Laboratories. */ 67 68 #include <openssl/ec.h> 69 70 #include <openssl/bn.h> 71 #include <openssl/err.h> 72 #include <openssl/mem.h> 73 74 #include "../bn/internal.h" 75 #include "../delocate.h" 76 #include "internal.h" 77 78 79 int ec_GFp_mont_group_init(EC_GROUP *group) { 80 int ok; 81 82 ok = ec_GFp_simple_group_init(group); 83 group->mont = NULL; 84 return ok; 85 } 86 87 void ec_GFp_mont_group_finish(EC_GROUP *group) { 88 BN_MONT_CTX_free(group->mont); 89 group->mont = NULL; 90 ec_GFp_simple_group_finish(group); 91 } 92 93 int ec_GFp_mont_group_set_curve(EC_GROUP *group, const BIGNUM *p, 94 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { 95 BN_CTX *new_ctx = NULL; 96 int ret = 0; 97 98 BN_MONT_CTX_free(group->mont); 99 group->mont = NULL; 100 101 if (ctx == NULL) { 102 ctx = new_ctx = BN_CTX_new(); 103 if (ctx == NULL) { 104 return 0; 105 } 106 } 107 108 group->mont = BN_MONT_CTX_new_for_modulus(p, ctx); 109 if (group->mont == NULL) { 110 OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB); 111 goto err; 112 } 113 114 ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx); 115 116 if (!ret) { 117 BN_MONT_CTX_free(group->mont); 118 group->mont = NULL; 119 } 120 121 err: 122 BN_CTX_free(new_ctx); 123 return ret; 124 } 125 126 static void ec_GFp_mont_felem_to_montgomery(const EC_GROUP *group, 127 EC_FELEM *out, const EC_FELEM *in) { 128 bn_to_montgomery_small(out->words, in->words, group->field.width, 129 group->mont); 130 } 131 132 static void ec_GFp_mont_felem_from_montgomery(const EC_GROUP *group, 133 EC_FELEM *out, 134 const EC_FELEM *in) { 135 bn_from_montgomery_small(out->words, in->words, group->field.width, 136 group->mont); 137 } 138 139 static void ec_GFp_mont_felem_inv(const EC_GROUP *group, EC_FELEM *out, 140 const EC_FELEM *a) { 141 bn_mod_inverse_prime_mont_small(out->words, a->words, group->field.width, 142 group->mont); 143 } 144 145 void ec_GFp_mont_felem_mul(const EC_GROUP *group, EC_FELEM *r, 146 const EC_FELEM *a, const EC_FELEM *b) { 147 bn_mod_mul_montgomery_small(r->words, a->words, b->words, group->field.width, 148 group->mont); 149 } 150 151 void ec_GFp_mont_felem_sqr(const EC_GROUP *group, EC_FELEM *r, 152 const EC_FELEM *a) { 153 bn_mod_mul_montgomery_small(r->words, a->words, a->words, group->field.width, 154 group->mont); 155 } 156 157 int ec_GFp_mont_bignum_to_felem(const EC_GROUP *group, EC_FELEM *out, 158 const BIGNUM *in) { 159 if (group->mont == NULL) { 160 OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED); 161 return 0; 162 } 163 164 if (!bn_copy_words(out->words, group->field.width, in)) { 165 return 0; 166 } 167 ec_GFp_mont_felem_to_montgomery(group, out, out); 168 return 1; 169 } 170 171 int ec_GFp_mont_felem_to_bignum(const EC_GROUP *group, BIGNUM *out, 172 const EC_FELEM *in) { 173 if (group->mont == NULL) { 174 OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED); 175 return 0; 176 } 177 178 EC_FELEM tmp; 179 ec_GFp_mont_felem_from_montgomery(group, &tmp, in); 180 return bn_set_words(out, tmp.words, group->field.width); 181 } 182 183 static int ec_GFp_mont_point_get_affine_coordinates(const EC_GROUP *group, 184 const EC_RAW_POINT *point, 185 EC_FELEM *x, EC_FELEM *y) { 186 if (ec_GFp_simple_is_at_infinity(group, point)) { 187 OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY); 188 return 0; 189 } 190 191 // Transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3). 192 193 EC_FELEM z1, z2; 194 ec_GFp_mont_felem_inv(group, &z2, &point->Z); 195 ec_GFp_mont_felem_sqr(group, &z1, &z2); 196 197 // Instead of using |ec_GFp_mont_felem_from_montgomery| to convert the |x| 198 // coordinate and then calling |ec_GFp_mont_felem_from_montgomery| again to 199 // convert the |y| coordinate below, convert the common factor |z1| once now, 200 // saving one reduction. 201 ec_GFp_mont_felem_from_montgomery(group, &z1, &z1); 202 203 if (x != NULL) { 204 ec_GFp_mont_felem_mul(group, x, &point->X, &z1); 205 } 206 207 if (y != NULL) { 208 ec_GFp_mont_felem_mul(group, &z1, &z1, &z2); 209 ec_GFp_mont_felem_mul(group, y, &point->Y, &z1); 210 } 211 212 return 1; 213 } 214 215 void ec_GFp_mont_add(const EC_GROUP *group, EC_RAW_POINT *out, 216 const EC_RAW_POINT *a, const EC_RAW_POINT *b) { 217 if (a == b) { 218 ec_GFp_mont_dbl(group, out, a); 219 return; 220 } 221 222 // The method is taken from: 223 // http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-add-2007-bl 224 // 225 // Coq transcription and correctness proof: 226 // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L467> 227 // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L544> 228 EC_FELEM x_out, y_out, z_out; 229 BN_ULONG z1nz = ec_felem_non_zero_mask(group, &a->Z); 230 BN_ULONG z2nz = ec_felem_non_zero_mask(group, &b->Z); 231 232 // z1z1 = z1z1 = z1**2 233 EC_FELEM z1z1; 234 ec_GFp_mont_felem_sqr(group, &z1z1, &a->Z); 235 236 // z2z2 = z2**2 237 EC_FELEM z2z2; 238 ec_GFp_mont_felem_sqr(group, &z2z2, &b->Z); 239 240 // u1 = x1*z2z2 241 EC_FELEM u1; 242 ec_GFp_mont_felem_mul(group, &u1, &a->X, &z2z2); 243 244 // two_z1z2 = (z1 + z2)**2 - (z1z1 + z2z2) = 2z1z2 245 EC_FELEM two_z1z2; 246 ec_felem_add(group, &two_z1z2, &a->Z, &b->Z); 247 ec_GFp_mont_felem_sqr(group, &two_z1z2, &two_z1z2); 248 ec_felem_sub(group, &two_z1z2, &two_z1z2, &z1z1); 249 ec_felem_sub(group, &two_z1z2, &two_z1z2, &z2z2); 250 251 // s1 = y1 * z2**3 252 EC_FELEM s1; 253 ec_GFp_mont_felem_mul(group, &s1, &b->Z, &z2z2); 254 ec_GFp_mont_felem_mul(group, &s1, &s1, &a->Y); 255 256 // u2 = x2*z1z1 257 EC_FELEM u2; 258 ec_GFp_mont_felem_mul(group, &u2, &b->X, &z1z1); 259 260 // h = u2 - u1 261 EC_FELEM h; 262 ec_felem_sub(group, &h, &u2, &u1); 263 264 BN_ULONG xneq = ec_felem_non_zero_mask(group, &h); 265 266 // z_out = two_z1z2 * h 267 ec_GFp_mont_felem_mul(group, &z_out, &h, &two_z1z2); 268 269 // z1z1z1 = z1 * z1z1 270 EC_FELEM z1z1z1; 271 ec_GFp_mont_felem_mul(group, &z1z1z1, &a->Z, &z1z1); 272 273 // s2 = y2 * z1**3 274 EC_FELEM s2; 275 ec_GFp_mont_felem_mul(group, &s2, &b->Y, &z1z1z1); 276 277 // r = (s2 - s1)*2 278 EC_FELEM r; 279 ec_felem_sub(group, &r, &s2, &s1); 280 ec_felem_add(group, &r, &r, &r); 281 282 BN_ULONG yneq = ec_felem_non_zero_mask(group, &r); 283 284 // This case will never occur in the constant-time |ec_GFp_mont_mul|. 285 if (!xneq && !yneq && z1nz && z2nz) { 286 ec_GFp_mont_dbl(group, out, a); 287 return; 288 } 289 290 // I = (2h)**2 291 EC_FELEM i; 292 ec_felem_add(group, &i, &h, &h); 293 ec_GFp_mont_felem_sqr(group, &i, &i); 294 295 // J = h * I 296 EC_FELEM j; 297 ec_GFp_mont_felem_mul(group, &j, &h, &i); 298 299 // V = U1 * I 300 EC_FELEM v; 301 ec_GFp_mont_felem_mul(group, &v, &u1, &i); 302 303 // x_out = r**2 - J - 2V 304 ec_GFp_mont_felem_sqr(group, &x_out, &r); 305 ec_felem_sub(group, &x_out, &x_out, &j); 306 ec_felem_sub(group, &x_out, &x_out, &v); 307 ec_felem_sub(group, &x_out, &x_out, &v); 308 309 // y_out = r(V-x_out) - 2 * s1 * J 310 ec_felem_sub(group, &y_out, &v, &x_out); 311 ec_GFp_mont_felem_mul(group, &y_out, &y_out, &r); 312 EC_FELEM s1j; 313 ec_GFp_mont_felem_mul(group, &s1j, &s1, &j); 314 ec_felem_sub(group, &y_out, &y_out, &s1j); 315 ec_felem_sub(group, &y_out, &y_out, &s1j); 316 317 ec_felem_select(group, &x_out, z1nz, &x_out, &b->X); 318 ec_felem_select(group, &out->X, z2nz, &x_out, &a->X); 319 ec_felem_select(group, &y_out, z1nz, &y_out, &b->Y); 320 ec_felem_select(group, &out->Y, z2nz, &y_out, &a->Y); 321 ec_felem_select(group, &z_out, z1nz, &z_out, &b->Z); 322 ec_felem_select(group, &out->Z, z2nz, &z_out, &a->Z); 323 } 324 325 void ec_GFp_mont_dbl(const EC_GROUP *group, EC_RAW_POINT *r, 326 const EC_RAW_POINT *a) { 327 if (group->a_is_minus3) { 328 // The method is taken from: 329 // http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b 330 // 331 // Coq transcription and correctness proof: 332 // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/Jacobian.v#L93> 333 // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/Jacobian.v#L201> 334 EC_FELEM delta, gamma, beta, ftmp, ftmp2, tmptmp, alpha, fourbeta; 335 // delta = z^2 336 ec_GFp_mont_felem_sqr(group, &delta, &a->Z); 337 // gamma = y^2 338 ec_GFp_mont_felem_sqr(group, &gamma, &a->Y); 339 // beta = x*gamma 340 ec_GFp_mont_felem_mul(group, &beta, &a->X, &gamma); 341 342 // alpha = 3*(x-delta)*(x+delta) 343 ec_felem_sub(group, &ftmp, &a->X, &delta); 344 ec_felem_add(group, &ftmp2, &a->X, &delta); 345 346 ec_felem_add(group, &tmptmp, &ftmp2, &ftmp2); 347 ec_felem_add(group, &ftmp2, &ftmp2, &tmptmp); 348 ec_GFp_mont_felem_mul(group, &alpha, &ftmp, &ftmp2); 349 350 // x' = alpha^2 - 8*beta 351 ec_GFp_mont_felem_sqr(group, &r->X, &alpha); 352 ec_felem_add(group, &fourbeta, &beta, &beta); 353 ec_felem_add(group, &fourbeta, &fourbeta, &fourbeta); 354 ec_felem_add(group, &tmptmp, &fourbeta, &fourbeta); 355 ec_felem_sub(group, &r->X, &r->X, &tmptmp); 356 357 // z' = (y + z)^2 - gamma - delta 358 ec_felem_add(group, &delta, &gamma, &delta); 359 ec_felem_add(group, &ftmp, &a->Y, &a->Z); 360 ec_GFp_mont_felem_sqr(group, &r->Z, &ftmp); 361 ec_felem_sub(group, &r->Z, &r->Z, &delta); 362 363 // y' = alpha*(4*beta - x') - 8*gamma^2 364 ec_felem_sub(group, &r->Y, &fourbeta, &r->X); 365 ec_felem_add(group, &gamma, &gamma, &gamma); 366 ec_GFp_mont_felem_sqr(group, &gamma, &gamma); 367 ec_GFp_mont_felem_mul(group, &r->Y, &alpha, &r->Y); 368 ec_felem_add(group, &gamma, &gamma, &gamma); 369 ec_felem_sub(group, &r->Y, &r->Y, &gamma); 370 } else { 371 // The method is taken from: 372 // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl 373 // 374 // Coq transcription and correctness proof: 375 // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L102> 376 // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L534> 377 EC_FELEM xx, yy, yyyy, zz; 378 ec_GFp_mont_felem_sqr(group, &xx, &a->X); 379 ec_GFp_mont_felem_sqr(group, &yy, &a->Y); 380 ec_GFp_mont_felem_sqr(group, &yyyy, &yy); 381 ec_GFp_mont_felem_sqr(group, &zz, &a->Z); 382 383 // s = 2*((x_in + yy)^2 - xx - yyyy) 384 EC_FELEM s; 385 ec_felem_add(group, &s, &a->X, &yy); 386 ec_GFp_mont_felem_sqr(group, &s, &s); 387 ec_felem_sub(group, &s, &s, &xx); 388 ec_felem_sub(group, &s, &s, &yyyy); 389 ec_felem_add(group, &s, &s, &s); 390 391 // m = 3*xx + a*zz^2 392 EC_FELEM m; 393 ec_GFp_mont_felem_sqr(group, &m, &zz); 394 ec_GFp_mont_felem_mul(group, &m, &group->a, &m); 395 ec_felem_add(group, &m, &m, &xx); 396 ec_felem_add(group, &m, &m, &xx); 397 ec_felem_add(group, &m, &m, &xx); 398 399 // x_out = m^2 - 2*s 400 ec_GFp_mont_felem_sqr(group, &r->X, &m); 401 ec_felem_sub(group, &r->X, &r->X, &s); 402 ec_felem_sub(group, &r->X, &r->X, &s); 403 404 // z_out = (y_in + z_in)^2 - yy - zz 405 ec_felem_add(group, &r->Z, &a->Y, &a->Z); 406 ec_GFp_mont_felem_sqr(group, &r->Z, &r->Z); 407 ec_felem_sub(group, &r->Z, &r->Z, &yy); 408 ec_felem_sub(group, &r->Z, &r->Z, &zz); 409 410 // y_out = m*(s-x_out) - 8*yyyy 411 ec_felem_add(group, &yyyy, &yyyy, &yyyy); 412 ec_felem_add(group, &yyyy, &yyyy, &yyyy); 413 ec_felem_add(group, &yyyy, &yyyy, &yyyy); 414 ec_felem_sub(group, &r->Y, &s, &r->X); 415 ec_GFp_mont_felem_mul(group, &r->Y, &r->Y, &m); 416 ec_felem_sub(group, &r->Y, &r->Y, &yyyy); 417 } 418 } 419 420 static int ec_GFp_mont_cmp_x_coordinate(const EC_GROUP *group, 421 const EC_RAW_POINT *p, 422 const EC_SCALAR *r) { 423 if (!group->field_greater_than_order || 424 group->field.width != group->order.width) { 425 // Do not bother optimizing this case. p > order in all commonly-used 426 // curves. 427 return ec_GFp_simple_cmp_x_coordinate(group, p, r); 428 } 429 430 if (ec_GFp_simple_is_at_infinity(group, p)) { 431 return 0; 432 } 433 434 // We wish to compare X/Z^2 with r. This is equivalent to comparing X with 435 // r*Z^2. Note that X and Z are represented in Montgomery form, while r is 436 // not. 437 EC_FELEM r_Z2, Z2_mont, X; 438 ec_GFp_mont_felem_mul(group, &Z2_mont, &p->Z, &p->Z); 439 // r < order < p, so this is valid. 440 OPENSSL_memcpy(r_Z2.words, r->words, group->field.width * sizeof(BN_ULONG)); 441 ec_GFp_mont_felem_mul(group, &r_Z2, &r_Z2, &Z2_mont); 442 ec_GFp_mont_felem_from_montgomery(group, &X, &p->X); 443 444 if (ec_felem_equal(group, &r_Z2, &X)) { 445 return 1; 446 } 447 448 // During signing the x coefficient is reduced modulo the group order. 449 // Therefore there is a small possibility, less than 1/2^128, that group_order 450 // < p.x < P. in that case we need not only to compare against |r| but also to 451 // compare against r+group_order. 452 if (bn_less_than_words(r->words, group->field_minus_order.words, 453 group->field.width)) { 454 // We can ignore the carry because: r + group_order < p < 2^256. 455 bn_add_words(r_Z2.words, r->words, group->order.d, group->field.width); 456 ec_GFp_mont_felem_mul(group, &r_Z2, &r_Z2, &Z2_mont); 457 if (ec_felem_equal(group, &r_Z2, &X)) { 458 return 1; 459 } 460 } 461 462 return 0; 463 } 464 465 DEFINE_METHOD_FUNCTION(EC_METHOD, EC_GFp_mont_method) { 466 out->group_init = ec_GFp_mont_group_init; 467 out->group_finish = ec_GFp_mont_group_finish; 468 out->group_set_curve = ec_GFp_mont_group_set_curve; 469 out->point_get_affine_coordinates = ec_GFp_mont_point_get_affine_coordinates; 470 out->add = ec_GFp_mont_add; 471 out->dbl = ec_GFp_mont_dbl; 472 out->mul = ec_GFp_mont_mul; 473 out->mul_public = ec_GFp_mont_mul_public; 474 out->felem_mul = ec_GFp_mont_felem_mul; 475 out->felem_sqr = ec_GFp_mont_felem_sqr; 476 out->bignum_to_felem = ec_GFp_mont_bignum_to_felem; 477 out->felem_to_bignum = ec_GFp_mont_felem_to_bignum; 478 out->scalar_inv_montgomery = ec_simple_scalar_inv_montgomery; 479 out->scalar_inv_montgomery_vartime = ec_GFp_simple_mont_inv_mod_ord_vartime; 480 out->cmp_x_coordinate = ec_GFp_mont_cmp_x_coordinate; 481 } 482
