1 /* $OpenBSD: ec2_mult.c,v 1.13 2018/07/23 18:24:22 tb Exp $ */ 2 /* ==================================================================== 3 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 4 * 5 * The Elliptic Curve Public-Key Crypto Library (ECC Code) included 6 * herein is developed by SUN MICROSYSTEMS, INC., and is contributed 7 * to the OpenSSL project. 8 * 9 * The ECC Code is licensed pursuant to the OpenSSL open source 10 * license provided below. 11 * 12 * The software is originally written by Sheueling Chang Shantz and 13 * Douglas Stebila of Sun Microsystems Laboratories. 14 * 15 */ 16 /* ==================================================================== 17 * Copyright (c) 1998-2003 The OpenSSL Project. All rights reserved. 18 * 19 * Redistribution and use in source and binary forms, with or without 20 * modification, are permitted provided that the following conditions 21 * are met: 22 * 23 * 1. Redistributions of source code must retain the above copyright 24 * notice, this list of conditions and the following disclaimer. 25 * 26 * 2. Redistributions in binary form must reproduce the above copyright 27 * notice, this list of conditions and the following disclaimer in 28 * the documentation and/or other materials provided with the 29 * distribution. 30 * 31 * 3. All advertising materials mentioning features or use of this 32 * software must display the following acknowledgment: 33 * "This product includes software developed by the OpenSSL Project 34 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 35 * 36 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 37 * endorse or promote products derived from this software without 38 * prior written permission. For written permission, please contact 39 * openssl-core@openssl.org. 40 * 41 * 5. Products derived from this software may not be called "OpenSSL" 42 * nor may "OpenSSL" appear in their names without prior written 43 * permission of the OpenSSL Project. 44 * 45 * 6. Redistributions of any form whatsoever must retain the following 46 * acknowledgment: 47 * "This product includes software developed by the OpenSSL Project 48 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 49 * 50 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 51 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 52 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 53 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 54 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 55 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 56 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 57 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 58 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 59 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 60 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 61 * OF THE POSSIBILITY OF SUCH DAMAGE. 62 * ==================================================================== 63 * 64 * This product includes cryptographic software written by Eric Young 65 * (eay@cryptsoft.com). This product includes software written by Tim 66 * Hudson (tjh@cryptsoft.com). 67 * 68 */ 69 70 #include <openssl/opensslconf.h> 71 72 #include <openssl/err.h> 73 74 #include "bn_lcl.h" 75 #include "ec_lcl.h" 76 77 #ifndef OPENSSL_NO_EC2M 78 79 80 /* Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery projective 81 * coordinates. 82 * Uses algorithm Mdouble in appendix of 83 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 84 * GF(2^m) without precomputation" (CHES '99, LNCS 1717). 85 * modified to not require precomputation of c=b^{2^{m-1}}. 86 */ 87 static int 88 gf2m_Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z, BN_CTX *ctx) 89 { 90 BIGNUM *t1; 91 int ret = 0; 92 93 /* Since Mdouble is static we can guarantee that ctx != NULL. */ 94 BN_CTX_start(ctx); 95 if ((t1 = BN_CTX_get(ctx)) == NULL) 96 goto err; 97 98 if (!group->meth->field_sqr(group, x, x, ctx)) 99 goto err; 100 if (!group->meth->field_sqr(group, t1, z, ctx)) 101 goto err; 102 if (!group->meth->field_mul(group, z, x, t1, ctx)) 103 goto err; 104 if (!group->meth->field_sqr(group, x, x, ctx)) 105 goto err; 106 if (!group->meth->field_sqr(group, t1, t1, ctx)) 107 goto err; 108 if (!group->meth->field_mul(group, t1, &group->b, t1, ctx)) 109 goto err; 110 if (!BN_GF2m_add(x, x, t1)) 111 goto err; 112 113 ret = 1; 114 115 err: 116 BN_CTX_end(ctx); 117 return ret; 118 } 119 120 /* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery 121 * projective coordinates. 122 * Uses algorithm Madd in appendix of 123 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 124 * GF(2^m) without precomputation" (CHES '99, LNCS 1717). 125 */ 126 static int 127 gf2m_Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1, BIGNUM *z1, 128 const BIGNUM *x2, const BIGNUM *z2, BN_CTX *ctx) 129 { 130 BIGNUM *t1, *t2; 131 int ret = 0; 132 133 /* Since Madd is static we can guarantee that ctx != NULL. */ 134 BN_CTX_start(ctx); 135 if ((t1 = BN_CTX_get(ctx)) == NULL) 136 goto err; 137 if ((t2 = BN_CTX_get(ctx)) == NULL) 138 goto err; 139 140 if (!BN_copy(t1, x)) 141 goto err; 142 if (!group->meth->field_mul(group, x1, x1, z2, ctx)) 143 goto err; 144 if (!group->meth->field_mul(group, z1, z1, x2, ctx)) 145 goto err; 146 if (!group->meth->field_mul(group, t2, x1, z1, ctx)) 147 goto err; 148 if (!BN_GF2m_add(z1, z1, x1)) 149 goto err; 150 if (!group->meth->field_sqr(group, z1, z1, ctx)) 151 goto err; 152 if (!group->meth->field_mul(group, x1, z1, t1, ctx)) 153 goto err; 154 if (!BN_GF2m_add(x1, x1, t2)) 155 goto err; 156 157 ret = 1; 158 159 err: 160 BN_CTX_end(ctx); 161 return ret; 162 } 163 164 /* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2) 165 * using Montgomery point multiplication algorithm Mxy() in appendix of 166 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 167 * GF(2^m) without precomputation" (CHES '99, LNCS 1717). 168 * Returns: 169 * 0 on error 170 * 1 if return value should be the point at infinity 171 * 2 otherwise 172 */ 173 static int 174 gf2m_Mxy(const EC_GROUP *group, const BIGNUM *x, const BIGNUM *y, BIGNUM *x1, 175 BIGNUM *z1, BIGNUM *x2, BIGNUM *z2, BN_CTX *ctx) 176 { 177 BIGNUM *t3, *t4, *t5; 178 int ret = 0; 179 180 if (BN_is_zero(z1)) { 181 BN_zero(x2); 182 BN_zero(z2); 183 return 1; 184 } 185 if (BN_is_zero(z2)) { 186 if (!BN_copy(x2, x)) 187 return 0; 188 if (!BN_GF2m_add(z2, x, y)) 189 return 0; 190 return 2; 191 } 192 /* Since Mxy is static we can guarantee that ctx != NULL. */ 193 BN_CTX_start(ctx); 194 if ((t3 = BN_CTX_get(ctx)) == NULL) 195 goto err; 196 if ((t4 = BN_CTX_get(ctx)) == NULL) 197 goto err; 198 if ((t5 = BN_CTX_get(ctx)) == NULL) 199 goto err; 200 201 if (!BN_one(t5)) 202 goto err; 203 204 if (!group->meth->field_mul(group, t3, z1, z2, ctx)) 205 goto err; 206 207 if (!group->meth->field_mul(group, z1, z1, x, ctx)) 208 goto err; 209 if (!BN_GF2m_add(z1, z1, x1)) 210 goto err; 211 if (!group->meth->field_mul(group, z2, z2, x, ctx)) 212 goto err; 213 if (!group->meth->field_mul(group, x1, z2, x1, ctx)) 214 goto err; 215 if (!BN_GF2m_add(z2, z2, x2)) 216 goto err; 217 218 if (!group->meth->field_mul(group, z2, z2, z1, ctx)) 219 goto err; 220 if (!group->meth->field_sqr(group, t4, x, ctx)) 221 goto err; 222 if (!BN_GF2m_add(t4, t4, y)) 223 goto err; 224 if (!group->meth->field_mul(group, t4, t4, t3, ctx)) 225 goto err; 226 if (!BN_GF2m_add(t4, t4, z2)) 227 goto err; 228 229 if (!group->meth->field_mul(group, t3, t3, x, ctx)) 230 goto err; 231 if (!group->meth->field_div(group, t3, t5, t3, ctx)) 232 goto err; 233 if (!group->meth->field_mul(group, t4, t3, t4, ctx)) 234 goto err; 235 if (!group->meth->field_mul(group, x2, x1, t3, ctx)) 236 goto err; 237 if (!BN_GF2m_add(z2, x2, x)) 238 goto err; 239 240 if (!group->meth->field_mul(group, z2, z2, t4, ctx)) 241 goto err; 242 if (!BN_GF2m_add(z2, z2, y)) 243 goto err; 244 245 ret = 2; 246 247 err: 248 BN_CTX_end(ctx); 249 return ret; 250 } 251 252 253 /* Computes scalar*point and stores the result in r. 254 * point can not equal r. 255 * Uses a modified algorithm 2P of 256 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 257 * GF(2^m) without precomputation" (CHES '99, LNCS 1717). 258 * 259 * To protect against side-channel attack the function uses constant time swap, 260 * avoiding conditional branches. 261 */ 262 static int 263 ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r, 264 const BIGNUM *scalar, const EC_POINT *point, BN_CTX *ctx) 265 { 266 BIGNUM *x1, *x2, *z1, *z2; 267 int ret = 0, i; 268 BN_ULONG mask, word; 269 270 if (r == point) { 271 ECerror(EC_R_INVALID_ARGUMENT); 272 return 0; 273 } 274 /* if result should be point at infinity */ 275 if ((scalar == NULL) || BN_is_zero(scalar) || (point == NULL) || 276 EC_POINT_is_at_infinity(group, point) > 0) { 277 return EC_POINT_set_to_infinity(group, r); 278 } 279 /* only support affine coordinates */ 280 if (!point->Z_is_one) 281 return 0; 282 283 /* Since point_multiply is static we can guarantee that ctx != NULL. */ 284 BN_CTX_start(ctx); 285 if ((x1 = BN_CTX_get(ctx)) == NULL) 286 goto err; 287 if ((z1 = BN_CTX_get(ctx)) == NULL) 288 goto err; 289 290 x2 = &r->X; 291 z2 = &r->Y; 292 293 if (!bn_wexpand(x1, group->field.top)) 294 goto err; 295 if (!bn_wexpand(z1, group->field.top)) 296 goto err; 297 if (!bn_wexpand(x2, group->field.top)) 298 goto err; 299 if (!bn_wexpand(z2, group->field.top)) 300 goto err; 301 302 if (!BN_GF2m_mod_arr(x1, &point->X, group->poly)) 303 goto err; /* x1 = x */ 304 if (!BN_one(z1)) 305 goto err; /* z1 = 1 */ 306 if (!group->meth->field_sqr(group, z2, x1, ctx)) 307 goto err; /* z2 = x1^2 = x^2 */ 308 if (!group->meth->field_sqr(group, x2, z2, ctx)) 309 goto err; 310 if (!BN_GF2m_add(x2, x2, &group->b)) 311 goto err; /* x2 = x^4 + b */ 312 313 /* find top most bit and go one past it */ 314 i = scalar->top - 1; 315 mask = BN_TBIT; 316 word = scalar->d[i]; 317 while (!(word & mask)) 318 mask >>= 1; 319 mask >>= 1; 320 /* if top most bit was at word break, go to next word */ 321 if (!mask) { 322 i--; 323 mask = BN_TBIT; 324 } 325 for (; i >= 0; i--) { 326 word = scalar->d[i]; 327 while (mask) { 328 if (!BN_swap_ct(word & mask, x1, x2, group->field.top)) 329 goto err; 330 if (!BN_swap_ct(word & mask, z1, z2, group->field.top)) 331 goto err; 332 if (!gf2m_Madd(group, &point->X, x2, z2, x1, z1, ctx)) 333 goto err; 334 if (!gf2m_Mdouble(group, x1, z1, ctx)) 335 goto err; 336 if (!BN_swap_ct(word & mask, x1, x2, group->field.top)) 337 goto err; 338 if (!BN_swap_ct(word & mask, z1, z2, group->field.top)) 339 goto err; 340 mask >>= 1; 341 } 342 mask = BN_TBIT; 343 } 344 345 /* convert out of "projective" coordinates */ 346 i = gf2m_Mxy(group, &point->X, &point->Y, x1, z1, x2, z2, ctx); 347 if (i == 0) 348 goto err; 349 else if (i == 1) { 350 if (!EC_POINT_set_to_infinity(group, r)) 351 goto err; 352 } else { 353 if (!BN_one(&r->Z)) 354 goto err; 355 r->Z_is_one = 1; 356 } 357 358 /* GF(2^m) field elements should always have BIGNUM::neg = 0 */ 359 BN_set_negative(&r->X, 0); 360 BN_set_negative(&r->Y, 0); 361 362 ret = 1; 363 364 err: 365 BN_CTX_end(ctx); 366 return ret; 367 } 368 369 370 /* Computes the sum 371 * scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1] 372 * gracefully ignoring NULL scalar values. 373 */ 374 int 375 ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 376 size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx) 377 { 378 BN_CTX *new_ctx = NULL; 379 int ret = 0; 380 size_t i; 381 EC_POINT *p = NULL; 382 EC_POINT *acc = NULL; 383 384 if (ctx == NULL) { 385 ctx = new_ctx = BN_CTX_new(); 386 if (ctx == NULL) 387 return 0; 388 } 389 /* 390 * This implementation is more efficient than the wNAF implementation 391 * for 2 or fewer points. Use the ec_wNAF_mul implementation for 3 392 * or more points, or if we can perform a fast multiplication based 393 * on precomputation. 394 */ 395 if ((scalar && (num > 1)) || (num > 2) || 396 (num == 0 && EC_GROUP_have_precompute_mult(group))) { 397 ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx); 398 goto err; 399 } 400 if ((p = EC_POINT_new(group)) == NULL) 401 goto err; 402 if ((acc = EC_POINT_new(group)) == NULL) 403 goto err; 404 405 if (!EC_POINT_set_to_infinity(group, acc)) 406 goto err; 407 408 if (scalar) { 409 if (!ec_GF2m_montgomery_point_multiply(group, p, scalar, group->generator, ctx)) 410 goto err; 411 if (BN_is_negative(scalar)) 412 if (!group->meth->invert(group, p, ctx)) 413 goto err; 414 if (!group->meth->add(group, acc, acc, p, ctx)) 415 goto err; 416 } 417 for (i = 0; i < num; i++) { 418 if (!ec_GF2m_montgomery_point_multiply(group, p, scalars[i], points[i], ctx)) 419 goto err; 420 if (BN_is_negative(scalars[i])) 421 if (!group->meth->invert(group, p, ctx)) 422 goto err; 423 if (!group->meth->add(group, acc, acc, p, ctx)) 424 goto err; 425 } 426 427 if (!EC_POINT_copy(r, acc)) 428 goto err; 429 430 ret = 1; 431 432 err: 433 EC_POINT_free(p); 434 EC_POINT_free(acc); 435 BN_CTX_free(new_ctx); 436 return ret; 437 } 438 439 440 /* Precomputation for point multiplication: fall back to wNAF methods 441 * because ec_GF2m_simple_mul() uses ec_wNAF_mul() if appropriate */ 442 443 int 444 ec_GF2m_precompute_mult(EC_GROUP * group, BN_CTX * ctx) 445 { 446 return ec_wNAF_precompute_mult(group, ctx); 447 } 448 449 int 450 ec_GF2m_have_precompute_mult(const EC_GROUP * group) 451 { 452 return ec_wNAF_have_precompute_mult(group); 453 } 454 455 #endif 456