1 /* $OpenBSD: ec2_mult.c,v 1.7 2015/02/09 15:49:22 jsing 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 "ec_lcl.h" 75 76 #ifndef OPENSSL_NO_EC2M 77 78 79 /* Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery projective 80 * coordinates. 81 * Uses algorithm Mdouble in appendix of 82 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 83 * GF(2^m) without precomputation" (CHES '99, LNCS 1717). 84 * modified to not require precomputation of c=b^{2^{m-1}}. 85 */ 86 static int 87 gf2m_Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z, BN_CTX *ctx) 88 { 89 BIGNUM *t1; 90 int ret = 0; 91 92 /* Since Mdouble is static we can guarantee that ctx != NULL. */ 93 BN_CTX_start(ctx); 94 if ((t1 = BN_CTX_get(ctx)) == NULL) 95 goto err; 96 97 if (!group->meth->field_sqr(group, x, x, ctx)) 98 goto err; 99 if (!group->meth->field_sqr(group, t1, z, ctx)) 100 goto err; 101 if (!group->meth->field_mul(group, z, x, t1, ctx)) 102 goto err; 103 if (!group->meth->field_sqr(group, x, x, ctx)) 104 goto err; 105 if (!group->meth->field_sqr(group, t1, t1, ctx)) 106 goto err; 107 if (!group->meth->field_mul(group, t1, &group->b, t1, ctx)) 108 goto err; 109 if (!BN_GF2m_add(x, x, t1)) 110 goto err; 111 112 ret = 1; 113 114 err: 115 BN_CTX_end(ctx); 116 return ret; 117 } 118 119 /* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery 120 * projective coordinates. 121 * Uses algorithm Madd in appendix of 122 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 123 * GF(2^m) without precomputation" (CHES '99, LNCS 1717). 124 */ 125 static int 126 gf2m_Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1, BIGNUM *z1, 127 const BIGNUM *x2, const BIGNUM *z2, BN_CTX *ctx) 128 { 129 BIGNUM *t1, *t2; 130 int ret = 0; 131 132 /* Since Madd is static we can guarantee that ctx != NULL. */ 133 BN_CTX_start(ctx); 134 if ((t1 = BN_CTX_get(ctx)) == NULL) 135 goto err; 136 if ((t2 = BN_CTX_get(ctx)) == NULL) 137 goto err; 138 139 if (!BN_copy(t1, x)) 140 goto err; 141 if (!group->meth->field_mul(group, x1, x1, z2, ctx)) 142 goto err; 143 if (!group->meth->field_mul(group, z1, z1, x2, ctx)) 144 goto err; 145 if (!group->meth->field_mul(group, t2, x1, z1, ctx)) 146 goto err; 147 if (!BN_GF2m_add(z1, z1, x1)) 148 goto err; 149 if (!group->meth->field_sqr(group, z1, z1, ctx)) 150 goto err; 151 if (!group->meth->field_mul(group, x1, z1, t1, ctx)) 152 goto err; 153 if (!BN_GF2m_add(x1, x1, t2)) 154 goto err; 155 156 ret = 1; 157 158 err: 159 BN_CTX_end(ctx); 160 return ret; 161 } 162 163 /* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2) 164 * using Montgomery point multiplication algorithm Mxy() in appendix of 165 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 166 * GF(2^m) without precomputation" (CHES '99, LNCS 1717). 167 * Returns: 168 * 0 on error 169 * 1 if return value should be the point at infinity 170 * 2 otherwise 171 */ 172 static int 173 gf2m_Mxy(const EC_GROUP *group, const BIGNUM *x, const BIGNUM *y, BIGNUM *x1, 174 BIGNUM *z1, BIGNUM *x2, BIGNUM *z2, BN_CTX *ctx) 175 { 176 BIGNUM *t3, *t4, *t5; 177 int ret = 0; 178 179 if (BN_is_zero(z1)) { 180 BN_zero(x2); 181 BN_zero(z2); 182 return 1; 183 } 184 if (BN_is_zero(z2)) { 185 if (!BN_copy(x2, x)) 186 return 0; 187 if (!BN_GF2m_add(z2, x, y)) 188 return 0; 189 return 2; 190 } 191 /* Since Mxy is static we can guarantee that ctx != NULL. */ 192 BN_CTX_start(ctx); 193 if ((t3 = BN_CTX_get(ctx)) == NULL) 194 goto err; 195 if ((t4 = BN_CTX_get(ctx)) == NULL) 196 goto err; 197 if ((t5 = BN_CTX_get(ctx)) == NULL) 198 goto err; 199 200 if (!BN_one(t5)) 201 goto err; 202 203 if (!group->meth->field_mul(group, t3, z1, z2, ctx)) 204 goto err; 205 206 if (!group->meth->field_mul(group, z1, z1, x, ctx)) 207 goto err; 208 if (!BN_GF2m_add(z1, z1, x1)) 209 goto err; 210 if (!group->meth->field_mul(group, z2, z2, x, ctx)) 211 goto err; 212 if (!group->meth->field_mul(group, x1, z2, x1, ctx)) 213 goto err; 214 if (!BN_GF2m_add(z2, z2, x2)) 215 goto err; 216 217 if (!group->meth->field_mul(group, z2, z2, z1, ctx)) 218 goto err; 219 if (!group->meth->field_sqr(group, t4, x, ctx)) 220 goto err; 221 if (!BN_GF2m_add(t4, t4, y)) 222 goto err; 223 if (!group->meth->field_mul(group, t4, t4, t3, ctx)) 224 goto err; 225 if (!BN_GF2m_add(t4, t4, z2)) 226 goto err; 227 228 if (!group->meth->field_mul(group, t3, t3, x, ctx)) 229 goto err; 230 if (!group->meth->field_div(group, t3, t5, t3, ctx)) 231 goto err; 232 if (!group->meth->field_mul(group, t4, t3, t4, ctx)) 233 goto err; 234 if (!group->meth->field_mul(group, x2, x1, t3, ctx)) 235 goto err; 236 if (!BN_GF2m_add(z2, x2, x)) 237 goto err; 238 239 if (!group->meth->field_mul(group, z2, z2, t4, ctx)) 240 goto err; 241 if (!BN_GF2m_add(z2, z2, y)) 242 goto err; 243 244 ret = 2; 245 246 err: 247 BN_CTX_end(ctx); 248 return ret; 249 } 250 251 252 /* Computes scalar*point and stores the result in r. 253 * point can not equal r. 254 * Uses a modified algorithm 2P of 255 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 256 * GF(2^m) without precomputation" (CHES '99, LNCS 1717). 257 * 258 * To protect against side-channel attack the function uses constant time swap, 259 * avoiding conditional branches. 260 */ 261 static int 262 ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r, 263 const BIGNUM *scalar, const EC_POINT *point, BN_CTX *ctx) 264 { 265 BIGNUM *x1, *x2, *z1, *z2; 266 int ret = 0, i; 267 BN_ULONG mask, word; 268 269 if (r == point) { 270 ECerr(EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY, EC_R_INVALID_ARGUMENT); 271 return 0; 272 } 273 /* if result should be point at infinity */ 274 if ((scalar == NULL) || BN_is_zero(scalar) || (point == NULL) || 275 EC_POINT_is_at_infinity(group, point) > 0) { 276 return EC_POINT_set_to_infinity(group, r); 277 } 278 /* only support affine coordinates */ 279 if (!point->Z_is_one) 280 return 0; 281 282 /* Since point_multiply is static we can guarantee that ctx != NULL. */ 283 BN_CTX_start(ctx); 284 if ((x1 = BN_CTX_get(ctx)) == NULL) 285 goto err; 286 if ((z1 = BN_CTX_get(ctx)) == NULL) 287 goto err; 288 289 x2 = &r->X; 290 z2 = &r->Y; 291 292 if (!bn_wexpand(x1, group->field.top)) 293 goto err; 294 if (!bn_wexpand(z1, group->field.top)) 295 goto err; 296 if (!bn_wexpand(x2, group->field.top)) 297 goto err; 298 if (!bn_wexpand(z2, group->field.top)) 299 goto err; 300 301 if (!BN_GF2m_mod_arr(x1, &point->X, group->poly)) 302 goto err; /* x1 = x */ 303 if (!BN_one(z1)) 304 goto err; /* z1 = 1 */ 305 if (!group->meth->field_sqr(group, z2, x1, ctx)) 306 goto err; /* z2 = x1^2 = x^2 */ 307 if (!group->meth->field_sqr(group, x2, z2, ctx)) 308 goto err; 309 if (!BN_GF2m_add(x2, x2, &group->b)) 310 goto err; /* x2 = x^4 + b */ 311 312 /* find top most bit and go one past it */ 313 i = scalar->top - 1; 314 mask = BN_TBIT; 315 word = scalar->d[i]; 316 while (!(word & mask)) 317 mask >>= 1; 318 mask >>= 1; 319 /* if top most bit was at word break, go to next word */ 320 if (!mask) { 321 i--; 322 mask = BN_TBIT; 323 } 324 for (; i >= 0; i--) { 325 word = scalar->d[i]; 326 while (mask) { 327 BN_consttime_swap(word & mask, x1, x2, group->field.top); 328 BN_consttime_swap(word & mask, z1, z2, group->field.top); 329 if (!gf2m_Madd(group, &point->X, x2, z2, x1, z1, ctx)) 330 goto err; 331 if (!gf2m_Mdouble(group, x1, z1, ctx)) 332 goto err; 333 BN_consttime_swap(word & mask, x1, x2, group->field.top); 334 BN_consttime_swap(word & mask, z1, z2, group->field.top); 335 mask >>= 1; 336 } 337 mask = BN_TBIT; 338 } 339 340 /* convert out of "projective" coordinates */ 341 i = gf2m_Mxy(group, &point->X, &point->Y, x1, z1, x2, z2, ctx); 342 if (i == 0) 343 goto err; 344 else if (i == 1) { 345 if (!EC_POINT_set_to_infinity(group, r)) 346 goto err; 347 } else { 348 if (!BN_one(&r->Z)) 349 goto err; 350 r->Z_is_one = 1; 351 } 352 353 /* GF(2^m) field elements should always have BIGNUM::neg = 0 */ 354 BN_set_negative(&r->X, 0); 355 BN_set_negative(&r->Y, 0); 356 357 ret = 1; 358 359 err: 360 BN_CTX_end(ctx); 361 return ret; 362 } 363 364 365 /* Computes the sum 366 * scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1] 367 * gracefully ignoring NULL scalar values. 368 */ 369 int 370 ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 371 size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx) 372 { 373 BN_CTX *new_ctx = NULL; 374 int ret = 0; 375 size_t i; 376 EC_POINT *p = NULL; 377 EC_POINT *acc = NULL; 378 379 if (ctx == NULL) { 380 ctx = new_ctx = BN_CTX_new(); 381 if (ctx == NULL) 382 return 0; 383 } 384 /* 385 * This implementation is more efficient than the wNAF implementation 386 * for 2 or fewer points. Use the ec_wNAF_mul implementation for 3 387 * or more points, or if we can perform a fast multiplication based 388 * on precomputation. 389 */ 390 if ((scalar && (num > 1)) || (num > 2) || 391 (num == 0 && EC_GROUP_have_precompute_mult(group))) { 392 ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx); 393 goto err; 394 } 395 if ((p = EC_POINT_new(group)) == NULL) 396 goto err; 397 if ((acc = EC_POINT_new(group)) == NULL) 398 goto err; 399 400 if (!EC_POINT_set_to_infinity(group, acc)) 401 goto err; 402 403 if (scalar) { 404 if (!ec_GF2m_montgomery_point_multiply(group, p, scalar, group->generator, ctx)) 405 goto err; 406 if (BN_is_negative(scalar)) 407 if (!group->meth->invert(group, p, ctx)) 408 goto err; 409 if (!group->meth->add(group, acc, acc, p, ctx)) 410 goto err; 411 } 412 for (i = 0; i < num; i++) { 413 if (!ec_GF2m_montgomery_point_multiply(group, p, scalars[i], points[i], ctx)) 414 goto err; 415 if (BN_is_negative(scalars[i])) 416 if (!group->meth->invert(group, p, ctx)) 417 goto err; 418 if (!group->meth->add(group, acc, acc, p, ctx)) 419 goto err; 420 } 421 422 if (!EC_POINT_copy(r, acc)) 423 goto err; 424 425 ret = 1; 426 427 err: 428 EC_POINT_free(p); 429 EC_POINT_free(acc); 430 BN_CTX_free(new_ctx); 431 return ret; 432 } 433 434 435 /* Precomputation for point multiplication: fall back to wNAF methods 436 * because ec_GF2m_simple_mul() uses ec_wNAF_mul() if appropriate */ 437 438 int 439 ec_GF2m_precompute_mult(EC_GROUP * group, BN_CTX * ctx) 440 { 441 return ec_wNAF_precompute_mult(group, ctx); 442 } 443 444 int 445 ec_GF2m_have_precompute_mult(const EC_GROUP * group) 446 { 447 return ec_wNAF_have_precompute_mult(group); 448 } 449 450 #endif 451