1160814Ssimon/* crypto/ec/ec2_mult.c */ 2160814Ssimon/* ==================================================================== 3160814Ssimon * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 4160814Ssimon * 5160814Ssimon * The Elliptic Curve Public-Key Crypto Library (ECC Code) included 6160814Ssimon * herein is developed by SUN MICROSYSTEMS, INC., and is contributed 7160814Ssimon * to the OpenSSL project. 8160814Ssimon * 9160814Ssimon * The ECC Code is licensed pursuant to the OpenSSL open source 10160814Ssimon * license provided below. 11160814Ssimon * 12160814Ssimon * The software is originally written by Sheueling Chang Shantz and 13160814Ssimon * Douglas Stebila of Sun Microsystems Laboratories. 14160814Ssimon * 15160814Ssimon */ 16160814Ssimon/* ==================================================================== 17160814Ssimon * Copyright (c) 1998-2003 The OpenSSL Project. All rights reserved. 18160814Ssimon * 19160814Ssimon * Redistribution and use in source and binary forms, with or without 20160814Ssimon * modification, are permitted provided that the following conditions 21160814Ssimon * are met: 22160814Ssimon * 23160814Ssimon * 1. Redistributions of source code must retain the above copyright 24280297Sjkim * notice, this list of conditions and the following disclaimer. 25160814Ssimon * 26160814Ssimon * 2. Redistributions in binary form must reproduce the above copyright 27160814Ssimon * notice, this list of conditions and the following disclaimer in 28160814Ssimon * the documentation and/or other materials provided with the 29160814Ssimon * distribution. 30160814Ssimon * 31160814Ssimon * 3. All advertising materials mentioning features or use of this 32160814Ssimon * software must display the following acknowledgment: 33160814Ssimon * "This product includes software developed by the OpenSSL Project 34160814Ssimon * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 35160814Ssimon * 36160814Ssimon * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 37160814Ssimon * endorse or promote products derived from this software without 38160814Ssimon * prior written permission. For written permission, please contact 39160814Ssimon * openssl-core@openssl.org. 40160814Ssimon * 41160814Ssimon * 5. Products derived from this software may not be called "OpenSSL" 42160814Ssimon * nor may "OpenSSL" appear in their names without prior written 43160814Ssimon * permission of the OpenSSL Project. 44160814Ssimon * 45160814Ssimon * 6. Redistributions of any form whatsoever must retain the following 46160814Ssimon * acknowledgment: 47160814Ssimon * "This product includes software developed by the OpenSSL Project 48160814Ssimon * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 49160814Ssimon * 50160814Ssimon * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 51160814Ssimon * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 52160814Ssimon * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 53160814Ssimon * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 54160814Ssimon * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 55160814Ssimon * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 56160814Ssimon * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 57160814Ssimon * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 58160814Ssimon * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 59160814Ssimon * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 60160814Ssimon * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 61160814Ssimon * OF THE POSSIBILITY OF SUCH DAMAGE. 62160814Ssimon * ==================================================================== 63160814Ssimon * 64160814Ssimon * This product includes cryptographic software written by Eric Young 65160814Ssimon * (eay@cryptsoft.com). This product includes software written by Tim 66160814Ssimon * Hudson (tjh@cryptsoft.com). 67160814Ssimon * 68160814Ssimon */ 69160814Ssimon 70160814Ssimon#include <openssl/err.h> 71160814Ssimon 72160814Ssimon#include "ec_lcl.h" 73160814Ssimon 74238405Sjkim#ifndef OPENSSL_NO_EC2M 75160814Ssimon 76280297Sjkim/*- 77280297Sjkim * Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery projective 78160814Ssimon * coordinates. 79280297Sjkim * Uses algorithm Mdouble in appendix of 80280297Sjkim * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 81238405Sjkim * GF(2^m) without precomputation" (CHES '99, LNCS 1717). 82160814Ssimon * modified to not require precomputation of c=b^{2^{m-1}}. 83160814Ssimon */ 84280297Sjkimstatic int gf2m_Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z, 85280297Sjkim BN_CTX *ctx) 86280297Sjkim{ 87280297Sjkim BIGNUM *t1; 88280297Sjkim int ret = 0; 89160814Ssimon 90280297Sjkim /* Since Mdouble is static we can guarantee that ctx != NULL. */ 91280297Sjkim BN_CTX_start(ctx); 92280297Sjkim t1 = BN_CTX_get(ctx); 93280297Sjkim if (t1 == NULL) 94280297Sjkim goto err; 95160814Ssimon 96280297Sjkim if (!group->meth->field_sqr(group, x, x, ctx)) 97280297Sjkim goto err; 98280297Sjkim if (!group->meth->field_sqr(group, t1, z, ctx)) 99280297Sjkim goto err; 100280297Sjkim if (!group->meth->field_mul(group, z, x, t1, ctx)) 101280297Sjkim goto err; 102280297Sjkim if (!group->meth->field_sqr(group, x, x, ctx)) 103280297Sjkim goto err; 104280297Sjkim if (!group->meth->field_sqr(group, t1, t1, ctx)) 105280297Sjkim goto err; 106280297Sjkim if (!group->meth->field_mul(group, t1, &group->b, t1, ctx)) 107280297Sjkim goto err; 108280297Sjkim if (!BN_GF2m_add(x, x, t1)) 109280297Sjkim goto err; 110160814Ssimon 111280297Sjkim ret = 1; 112280297Sjkim 113160814Ssimon err: 114280297Sjkim BN_CTX_end(ctx); 115280297Sjkim return ret; 116280297Sjkim} 117160814Ssimon 118280297Sjkim/*- 119280297Sjkim * Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery 120160814Ssimon * projective coordinates. 121280297Sjkim * Uses algorithm Madd in appendix of 122280297Sjkim * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 123238405Sjkim * GF(2^m) without precomputation" (CHES '99, LNCS 1717). 124160814Ssimon */ 125280297Sjkimstatic int gf2m_Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1, 126280297Sjkim BIGNUM *z1, const BIGNUM *x2, const BIGNUM *z2, 127280297Sjkim BN_CTX *ctx) 128280297Sjkim{ 129280297Sjkim BIGNUM *t1, *t2; 130280297Sjkim int ret = 0; 131160814Ssimon 132280297Sjkim /* Since Madd is static we can guarantee that ctx != NULL. */ 133280297Sjkim BN_CTX_start(ctx); 134280297Sjkim t1 = BN_CTX_get(ctx); 135280297Sjkim t2 = BN_CTX_get(ctx); 136280297Sjkim if (t2 == NULL) 137280297Sjkim goto err; 138160814Ssimon 139280297Sjkim if (!BN_copy(t1, x)) 140280297Sjkim goto err; 141280297Sjkim if (!group->meth->field_mul(group, x1, x1, z2, ctx)) 142280297Sjkim goto err; 143280297Sjkim if (!group->meth->field_mul(group, z1, z1, x2, ctx)) 144280297Sjkim goto err; 145280297Sjkim if (!group->meth->field_mul(group, t2, x1, z1, ctx)) 146280297Sjkim goto err; 147280297Sjkim if (!BN_GF2m_add(z1, z1, x1)) 148280297Sjkim goto err; 149280297Sjkim if (!group->meth->field_sqr(group, z1, z1, ctx)) 150280297Sjkim goto err; 151280297Sjkim if (!group->meth->field_mul(group, x1, z1, t1, ctx)) 152280297Sjkim goto err; 153280297Sjkim if (!BN_GF2m_add(x1, x1, t2)) 154280297Sjkim goto err; 155160814Ssimon 156280297Sjkim ret = 1; 157280297Sjkim 158160814Ssimon err: 159280297Sjkim BN_CTX_end(ctx); 160280297Sjkim return ret; 161280297Sjkim} 162160814Ssimon 163280297Sjkim/*- 164280297Sjkim * Compute the x, y affine coordinates from the point (x1, z1) (x2, z2) 165280297Sjkim * using Montgomery point multiplication algorithm Mxy() in appendix of 166280297Sjkim * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 167238405Sjkim * GF(2^m) without precomputation" (CHES '99, LNCS 1717). 168160814Ssimon * Returns: 169160814Ssimon * 0 on error 170160814Ssimon * 1 if return value should be the point at infinity 171160814Ssimon * 2 otherwise 172160814Ssimon */ 173280297Sjkimstatic int gf2m_Mxy(const EC_GROUP *group, const BIGNUM *x, const BIGNUM *y, 174280297Sjkim BIGNUM *x1, BIGNUM *z1, BIGNUM *x2, BIGNUM *z2, 175280297Sjkim BN_CTX *ctx) 176280297Sjkim{ 177280297Sjkim BIGNUM *t3, *t4, *t5; 178280297Sjkim int ret = 0; 179160814Ssimon 180280297Sjkim if (BN_is_zero(z1)) { 181280297Sjkim BN_zero(x2); 182280297Sjkim BN_zero(z2); 183280297Sjkim return 1; 184280297Sjkim } 185160814Ssimon 186280297Sjkim if (BN_is_zero(z2)) { 187280297Sjkim if (!BN_copy(x2, x)) 188280297Sjkim return 0; 189280297Sjkim if (!BN_GF2m_add(z2, x, y)) 190280297Sjkim return 0; 191280297Sjkim return 2; 192280297Sjkim } 193160814Ssimon 194280297Sjkim /* Since Mxy is static we can guarantee that ctx != NULL. */ 195280297Sjkim BN_CTX_start(ctx); 196280297Sjkim t3 = BN_CTX_get(ctx); 197280297Sjkim t4 = BN_CTX_get(ctx); 198280297Sjkim t5 = BN_CTX_get(ctx); 199280297Sjkim if (t5 == NULL) 200280297Sjkim goto err; 201160814Ssimon 202280297Sjkim if (!BN_one(t5)) 203280297Sjkim goto err; 204160814Ssimon 205280297Sjkim if (!group->meth->field_mul(group, t3, z1, z2, ctx)) 206280297Sjkim goto err; 207160814Ssimon 208280297Sjkim if (!group->meth->field_mul(group, z1, z1, x, ctx)) 209280297Sjkim goto err; 210280297Sjkim if (!BN_GF2m_add(z1, z1, x1)) 211280297Sjkim goto err; 212280297Sjkim if (!group->meth->field_mul(group, z2, z2, x, ctx)) 213280297Sjkim goto err; 214280297Sjkim if (!group->meth->field_mul(group, x1, z2, x1, ctx)) 215280297Sjkim goto err; 216280297Sjkim if (!BN_GF2m_add(z2, z2, x2)) 217280297Sjkim goto err; 218160814Ssimon 219280297Sjkim if (!group->meth->field_mul(group, z2, z2, z1, ctx)) 220280297Sjkim goto err; 221280297Sjkim if (!group->meth->field_sqr(group, t4, x, ctx)) 222280297Sjkim goto err; 223280297Sjkim if (!BN_GF2m_add(t4, t4, y)) 224280297Sjkim goto err; 225280297Sjkim if (!group->meth->field_mul(group, t4, t4, t3, ctx)) 226280297Sjkim goto err; 227280297Sjkim if (!BN_GF2m_add(t4, t4, z2)) 228280297Sjkim goto err; 229160814Ssimon 230280297Sjkim if (!group->meth->field_mul(group, t3, t3, x, ctx)) 231280297Sjkim goto err; 232280297Sjkim if (!group->meth->field_div(group, t3, t5, t3, ctx)) 233280297Sjkim goto err; 234280297Sjkim if (!group->meth->field_mul(group, t4, t3, t4, ctx)) 235280297Sjkim goto err; 236280297Sjkim if (!group->meth->field_mul(group, x2, x1, t3, ctx)) 237280297Sjkim goto err; 238280297Sjkim if (!BN_GF2m_add(z2, x2, x)) 239280297Sjkim goto err; 240280297Sjkim 241280297Sjkim if (!group->meth->field_mul(group, z2, z2, t4, ctx)) 242280297Sjkim goto err; 243280297Sjkim if (!BN_GF2m_add(z2, z2, y)) 244280297Sjkim goto err; 245280297Sjkim 246280297Sjkim ret = 2; 247280297Sjkim 248160814Ssimon err: 249280297Sjkim BN_CTX_end(ctx); 250280297Sjkim return ret; 251280297Sjkim} 252160814Ssimon 253280297Sjkim/*- 254280297Sjkim * Computes scalar*point and stores the result in r. 255160814Ssimon * point can not equal r. 256264265Sdelphij * Uses a modified algorithm 2P of 257280297Sjkim * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 258238405Sjkim * GF(2^m) without precomputation" (CHES '99, LNCS 1717). 259264265Sdelphij * 260264265Sdelphij * To protect against side-channel attack the function uses constant time swap, 261264265Sdelphij * avoiding conditional branches. 262160814Ssimon */ 263280297Sjkimstatic int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, 264280297Sjkim EC_POINT *r, 265280297Sjkim const BIGNUM *scalar, 266280297Sjkim const EC_POINT *point, 267280297Sjkim BN_CTX *ctx) 268280297Sjkim{ 269280297Sjkim BIGNUM *x1, *x2, *z1, *z2; 270312826Sjkim int ret = 0, i, group_top; 271280297Sjkim BN_ULONG mask, word; 272160814Ssimon 273280297Sjkim if (r == point) { 274280297Sjkim ECerr(EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY, EC_R_INVALID_ARGUMENT); 275280297Sjkim return 0; 276280297Sjkim } 277160814Ssimon 278280297Sjkim /* if result should be point at infinity */ 279280297Sjkim if ((scalar == NULL) || BN_is_zero(scalar) || (point == NULL) || 280280297Sjkim EC_POINT_is_at_infinity(group, point)) { 281280297Sjkim return EC_POINT_set_to_infinity(group, r); 282280297Sjkim } 283160814Ssimon 284280297Sjkim /* only support affine coordinates */ 285280297Sjkim if (!point->Z_is_one) 286280297Sjkim return 0; 287160814Ssimon 288280297Sjkim /* 289280297Sjkim * Since point_multiply is static we can guarantee that ctx != NULL. 290280297Sjkim */ 291280297Sjkim BN_CTX_start(ctx); 292280297Sjkim x1 = BN_CTX_get(ctx); 293280297Sjkim z1 = BN_CTX_get(ctx); 294280297Sjkim if (z1 == NULL) 295280297Sjkim goto err; 296160814Ssimon 297280297Sjkim x2 = &r->X; 298280297Sjkim z2 = &r->Y; 299264265Sdelphij 300312826Sjkim group_top = group->field.top; 301312826Sjkim if (bn_wexpand(x1, group_top) == NULL 302312826Sjkim || bn_wexpand(z1, group_top) == NULL 303312826Sjkim || bn_wexpand(x2, group_top) == NULL 304312826Sjkim || bn_wexpand(z2, group_top) == NULL) 305312826Sjkim goto err; 306160814Ssimon 307280297Sjkim if (!BN_GF2m_mod_arr(x1, &point->X, group->poly)) 308280297Sjkim goto err; /* x1 = x */ 309280297Sjkim if (!BN_one(z1)) 310280297Sjkim goto err; /* z1 = 1 */ 311280297Sjkim if (!group->meth->field_sqr(group, z2, x1, ctx)) 312280297Sjkim goto err; /* z2 = x1^2 = x^2 */ 313280297Sjkim if (!group->meth->field_sqr(group, x2, z2, ctx)) 314280297Sjkim goto err; 315280297Sjkim if (!BN_GF2m_add(x2, x2, &group->b)) 316280297Sjkim goto err; /* x2 = x^4 + b */ 317160814Ssimon 318280297Sjkim /* find top most bit and go one past it */ 319280297Sjkim i = scalar->top - 1; 320280297Sjkim mask = BN_TBIT; 321280297Sjkim word = scalar->d[i]; 322280297Sjkim while (!(word & mask)) 323280297Sjkim mask >>= 1; 324280297Sjkim mask >>= 1; 325280297Sjkim /* if top most bit was at word break, go to next word */ 326280297Sjkim if (!mask) { 327280297Sjkim i--; 328280297Sjkim mask = BN_TBIT; 329280297Sjkim } 330160814Ssimon 331280297Sjkim for (; i >= 0; i--) { 332280297Sjkim word = scalar->d[i]; 333280297Sjkim while (mask) { 334312826Sjkim BN_consttime_swap(word & mask, x1, x2, group_top); 335312826Sjkim BN_consttime_swap(word & mask, z1, z2, group_top); 336280297Sjkim if (!gf2m_Madd(group, &point->X, x2, z2, x1, z1, ctx)) 337280297Sjkim goto err; 338280297Sjkim if (!gf2m_Mdouble(group, x1, z1, ctx)) 339280297Sjkim goto err; 340312826Sjkim BN_consttime_swap(word & mask, x1, x2, group_top); 341312826Sjkim BN_consttime_swap(word & mask, z1, z2, group_top); 342280297Sjkim mask >>= 1; 343280297Sjkim } 344280297Sjkim mask = BN_TBIT; 345280297Sjkim } 346160814Ssimon 347280297Sjkim /* convert out of "projective" coordinates */ 348280297Sjkim i = gf2m_Mxy(group, &point->X, &point->Y, x1, z1, x2, z2, ctx); 349280297Sjkim if (i == 0) 350280297Sjkim goto err; 351280297Sjkim else if (i == 1) { 352280297Sjkim if (!EC_POINT_set_to_infinity(group, r)) 353280297Sjkim goto err; 354280297Sjkim } else { 355280297Sjkim if (!BN_one(&r->Z)) 356280297Sjkim goto err; 357280297Sjkim r->Z_is_one = 1; 358280297Sjkim } 359160814Ssimon 360280297Sjkim /* GF(2^m) field elements should always have BIGNUM::neg = 0 */ 361280297Sjkim BN_set_negative(&r->X, 0); 362280297Sjkim BN_set_negative(&r->Y, 0); 363160814Ssimon 364280297Sjkim ret = 1; 365280297Sjkim 366160814Ssimon err: 367280297Sjkim BN_CTX_end(ctx); 368280297Sjkim return ret; 369280297Sjkim} 370160814Ssimon 371280297Sjkim/*- 372280297Sjkim * Computes the sum 373160814Ssimon * scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1] 374160814Ssimon * gracefully ignoring NULL scalar values. 375160814Ssimon */ 376280297Sjkimint ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r, 377280297Sjkim const BIGNUM *scalar, size_t num, 378280297Sjkim const EC_POINT *points[], const BIGNUM *scalars[], 379280297Sjkim BN_CTX *ctx) 380280297Sjkim{ 381280297Sjkim BN_CTX *new_ctx = NULL; 382280297Sjkim int ret = 0; 383280297Sjkim size_t i; 384280297Sjkim EC_POINT *p = NULL; 385280297Sjkim EC_POINT *acc = NULL; 386160814Ssimon 387280297Sjkim if (ctx == NULL) { 388280297Sjkim ctx = new_ctx = BN_CTX_new(); 389280297Sjkim if (ctx == NULL) 390280297Sjkim return 0; 391280297Sjkim } 392160814Ssimon 393280297Sjkim /* 394280297Sjkim * This implementation is more efficient than the wNAF implementation for 395280297Sjkim * 2 or fewer points. Use the ec_wNAF_mul implementation for 3 or more 396280297Sjkim * points, or if we can perform a fast multiplication based on 397280297Sjkim * precomputation. 398280297Sjkim */ 399280297Sjkim if ((scalar && (num > 1)) || (num > 2) 400280297Sjkim || (num == 0 && EC_GROUP_have_precompute_mult(group))) { 401280297Sjkim ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx); 402280297Sjkim goto err; 403280297Sjkim } 404160814Ssimon 405280297Sjkim if ((p = EC_POINT_new(group)) == NULL) 406280297Sjkim goto err; 407280297Sjkim if ((acc = EC_POINT_new(group)) == NULL) 408280297Sjkim goto err; 409160814Ssimon 410280297Sjkim if (!EC_POINT_set_to_infinity(group, acc)) 411280297Sjkim goto err; 412160814Ssimon 413280297Sjkim if (scalar) { 414280297Sjkim if (!ec_GF2m_montgomery_point_multiply 415280297Sjkim (group, p, scalar, group->generator, ctx)) 416280297Sjkim goto err; 417280297Sjkim if (BN_is_negative(scalar)) 418280297Sjkim if (!group->meth->invert(group, p, ctx)) 419280297Sjkim goto err; 420280297Sjkim if (!group->meth->add(group, acc, acc, p, ctx)) 421280297Sjkim goto err; 422280297Sjkim } 423160814Ssimon 424280297Sjkim for (i = 0; i < num; i++) { 425280297Sjkim if (!ec_GF2m_montgomery_point_multiply 426280297Sjkim (group, p, scalars[i], points[i], ctx)) 427280297Sjkim goto err; 428280297Sjkim if (BN_is_negative(scalars[i])) 429280297Sjkim if (!group->meth->invert(group, p, ctx)) 430280297Sjkim goto err; 431280297Sjkim if (!group->meth->add(group, acc, acc, p, ctx)) 432280297Sjkim goto err; 433280297Sjkim } 434160814Ssimon 435280297Sjkim if (!EC_POINT_copy(r, acc)) 436280297Sjkim goto err; 437215697Ssimon 438280297Sjkim ret = 1; 439160814Ssimon 440280297Sjkim err: 441280297Sjkim if (p) 442280297Sjkim EC_POINT_free(p); 443280297Sjkim if (acc) 444280297Sjkim EC_POINT_free(acc); 445280297Sjkim if (new_ctx != NULL) 446280297Sjkim BN_CTX_free(new_ctx); 447280297Sjkim return ret; 448280297Sjkim} 449160814Ssimon 450280297Sjkim/* 451280297Sjkim * Precomputation for point multiplication: fall back to wNAF methods because 452280297Sjkim * ec_GF2m_simple_mul() uses ec_wNAF_mul() if appropriate 453280297Sjkim */ 454160814Ssimon 455160814Ssimonint ec_GF2m_precompute_mult(EC_GROUP *group, BN_CTX *ctx) 456280297Sjkim{ 457280297Sjkim return ec_wNAF_precompute_mult(group, ctx); 458280297Sjkim} 459160814Ssimon 460160814Ssimonint ec_GF2m_have_precompute_mult(const EC_GROUP *group) 461280297Sjkim{ 462280297Sjkim return ec_wNAF_have_precompute_mult(group); 463280297Sjkim} 464238405Sjkim 465238405Sjkim#endif 466