ec2_mult.c revision 215697
11553Srgrimes/* crypto/ec/ec2_mult.c */ 21553Srgrimes/* ==================================================================== 31553Srgrimes * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. 41553Srgrimes * 51553Srgrimes * The Elliptic Curve Public-Key Crypto Library (ECC Code) included 61553Srgrimes * herein is developed by SUN MICROSYSTEMS, INC., and is contributed 71553Srgrimes * to the OpenSSL project. 81553Srgrimes * 91553Srgrimes * The ECC Code is licensed pursuant to the OpenSSL open source 101553Srgrimes * license provided below. 111553Srgrimes * 121553Srgrimes * The software is originally written by Sheueling Chang Shantz and 131553Srgrimes * Douglas Stebila of Sun Microsystems Laboratories. 141553Srgrimes * 151553Srgrimes */ 161553Srgrimes/* ==================================================================== 171553Srgrimes * Copyright (c) 1998-2003 The OpenSSL Project. All rights reserved. 181553Srgrimes * 191553Srgrimes * Redistribution and use in source and binary forms, with or without 201553Srgrimes * modification, are permitted provided that the following conditions 211553Srgrimes * are met: 221553Srgrimes * 231553Srgrimes * 1. Redistributions of source code must retain the above copyright 241553Srgrimes * notice, this list of conditions and the following disclaimer. 251553Srgrimes * 261553Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 271553Srgrimes * notice, this list of conditions and the following disclaimer in 281553Srgrimes * the documentation and/or other materials provided with the 291553Srgrimes * distribution. 301553Srgrimes * 3152007Speter * 3. All advertising materials mentioning features or use of this 321553Srgrimes * software must display the following acknowledgment: 331553Srgrimes * "This product includes software developed by the OpenSSL Project 3479607Sdd * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 351553Srgrimes * 366494Sbde * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 3716073Sphk * endorse or promote products derived from this software without 381553Srgrimes * prior written permission. For written permission, please contact 391553Srgrimes * openssl-core@openssl.org. 4045775Speter * 4145775Speter * 5. Products derived from this software may not be called "OpenSSL" 421553Srgrimes * nor may "OpenSSL" appear in their names without prior written 4379607Sdd * permission of the OpenSSL Project. 4479607Sdd * 4579607Sdd * 6. Redistributions of any form whatsoever must retain the following 4679607Sdd * acknowledgment: 4779607Sdd * "This product includes software developed by the OpenSSL Project 4879607Sdd * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 4979607Sdd * 5079607Sdd * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 5179607Sdd * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 5279607Sdd * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 5379607Sdd * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 5479607Sdd * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 5579607Sdd * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 561553Srgrimes * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 571553Srgrimes * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 581553Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 591553Srgrimes * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 6072684Speter * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 611553Srgrimes * OF THE POSSIBILITY OF SUCH DAMAGE. 621553Srgrimes * ==================================================================== 6346855Speter * 641553Srgrimes * This product includes cryptographic software written by Eric Young 65152018Sru * (eay@cryptsoft.com). This product includes software written by Tim 661553Srgrimes * Hudson (tjh@cryptsoft.com). 67141615Sdes * 68111582Sru */ 69141615Sdes 7082393Speter#include <openssl/err.h> 7161640Speter 721553Srgrimes#include "ec_lcl.h" 7352653Smarcel 74153063Sru 751553Srgrimes/* Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery projective 76111582Sru * coordinates. 77152023Sru * Uses algorithm Mdouble in appendix of 781553Srgrimes * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over 7967109Sphk * GF(2^m) without precomputation". 8048402Speter * modified to not require precomputation of c=b^{2^{m-1}}. 811553Srgrimes */ 82111582Srustatic int gf2m_Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z, BN_CTX *ctx) 83136429Sphk { 8479607Sdd BIGNUM *t1; 85129073Scognet int ret = 0; 861553Srgrimes 871553Srgrimes /* Since Mdouble is static we can guarantee that ctx != NULL. */ 8829451Scharnier BN_CTX_start(ctx); 8929451Scharnier t1 = BN_CTX_get(ctx); 9079607Sdd if (t1 == NULL) goto err; 9179607Sdd 9261640Speter if (!group->meth->field_sqr(group, x, x, ctx)) goto err; 9398555Sjmallett if (!group->meth->field_sqr(group, t1, z, ctx)) goto err; 9498555Sjmallett if (!group->meth->field_mul(group, z, x, t1, ctx)) goto err; 9579607Sdd if (!group->meth->field_sqr(group, x, x, ctx)) goto err; 9629451Scharnier if (!group->meth->field_sqr(group, t1, t1, ctx)) goto err; 971553Srgrimes if (!group->meth->field_mul(group, t1, &group->b, t1, ctx)) goto err; 9846104Sluoqi if (!BN_GF2m_add(x, x, t1)) goto err; 99180922Sobrien 100134542Speter ret = 1; 1011553Srgrimes 102134542Speter err: 1031553Srgrimes BN_CTX_end(ctx); 1041553Srgrimes return ret; 10546104Sluoqi } 1061553Srgrimes 1071553Srgrimes/* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery 1086494Sbde * projective coordinates. 1091553Srgrimes * Uses algorithm Madd in appendix of 1101553Srgrimes * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over 1111553Srgrimes * GF(2^m) without precomputation". 1121553Srgrimes */ 11312772Speterstatic int gf2m_Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1, BIGNUM *z1, 11446104Sluoqi const BIGNUM *x2, const BIGNUM *z2, BN_CTX *ctx) 11546104Sluoqi { 11646104Sluoqi BIGNUM *t1, *t2; 11712772Speter int ret = 0; 11812772Speter 11912772Speter /* Since Madd is static we can guarantee that ctx != NULL. */ 1201553Srgrimes BN_CTX_start(ctx); 12146104Sluoqi t1 = BN_CTX_get(ctx); 12246104Sluoqi t2 = BN_CTX_get(ctx); 1236494Sbde if (t2 == NULL) goto err; 1241553Srgrimes 1251553Srgrimes if (!BN_copy(t1, x)) goto err; 12648402Speter if (!group->meth->field_mul(group, x1, x1, z2, ctx)) goto err; 12746104Sluoqi if (!group->meth->field_mul(group, z1, z1, x2, ctx)) goto err; 12846104Sluoqi if (!group->meth->field_mul(group, t2, x1, z1, ctx)) goto err; 12946104Sluoqi if (!BN_GF2m_add(z1, z1, x1)) goto err; 13046104Sluoqi if (!group->meth->field_sqr(group, z1, z1, ctx)) goto err; 1311553Srgrimes if (!group->meth->field_mul(group, x1, z1, t1, ctx)) goto err; 1321553Srgrimes if (!BN_GF2m_add(x1, x1, t2)) goto err; 1331553Srgrimes 1341553Srgrimes ret = 1; 1351553Srgrimes 1361553Srgrimes err: 1371553Srgrimes BN_CTX_end(ctx); 1381553Srgrimes return ret; 13946104Sluoqi } 14046021Speter 14146021Speter/* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2) 14246021Speter * using Montgomery point multiplication algorithm Mxy() in appendix of 1431553Srgrimes * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over 1441553Srgrimes * GF(2^m) without precomputation". 1451553Srgrimes * Returns: 1461553Srgrimes * 0 on error 1471553Srgrimes * 1 if return value should be the point at infinity 1481553Srgrimes * 2 otherwise 1491553Srgrimes */ 1501553Srgrimesstatic int gf2m_Mxy(const EC_GROUP *group, const BIGNUM *x, const BIGNUM *y, BIGNUM *x1, 1511553Srgrimes BIGNUM *z1, BIGNUM *x2, BIGNUM *z2, BN_CTX *ctx) 1521553Srgrimes { 1531553Srgrimes BIGNUM *t3, *t4, *t5; 1541553Srgrimes int ret = 0; 1554242Swollman 1561553Srgrimes if (BN_is_zero(z1)) 1571553Srgrimes { 15846104Sluoqi BN_zero(x2); 15979607Sdd BN_zero(z2); 16079607Sdd return 1; 16179607Sdd } 16279607Sdd 16379607Sdd if (BN_is_zero(z2)) 16479607Sdd { 16579607Sdd if (!BN_copy(x2, x)) return 0; 16679607Sdd if (!BN_GF2m_add(z2, x, y)) return 0; 16779607Sdd return 2; 16879607Sdd } 169180922Sobrien 170180922Sobrien /* Since Mxy is static we can guarantee that ctx != NULL. */ 171180922Sobrien BN_CTX_start(ctx); 172180922Sobrien t3 = BN_CTX_get(ctx); 173180922Sobrien t4 = BN_CTX_get(ctx); 1741553Srgrimes t5 = BN_CTX_get(ctx); 1751553Srgrimes if (t5 == NULL) goto err; 1761553Srgrimes 1771553Srgrimes if (!BN_one(t5)) goto err; 1781553Srgrimes 1791553Srgrimes if (!group->meth->field_mul(group, t3, z1, z2, ctx)) goto err; 1801553Srgrimes 1811553Srgrimes if (!group->meth->field_mul(group, z1, z1, x, ctx)) goto err; 1821553Srgrimes if (!BN_GF2m_add(z1, z1, x1)) goto err; 18329451Scharnier if (!group->meth->field_mul(group, z2, z2, x, ctx)) goto err; 18461640Speter if (!group->meth->field_mul(group, x1, z2, x1, ctx)) goto err; 1851553Srgrimes if (!BN_GF2m_add(z2, z2, x2)) goto err; 18661640Speter 1871553Srgrimes if (!group->meth->field_mul(group, z2, z2, z1, ctx)) goto err; 1881553Srgrimes if (!group->meth->field_sqr(group, t4, x, ctx)) goto err; 1891553Srgrimes if (!BN_GF2m_add(t4, t4, y)) goto err; 1901553Srgrimes if (!group->meth->field_mul(group, t4, t4, t3, ctx)) goto err; 1911553Srgrimes if (!BN_GF2m_add(t4, t4, z2)) goto err; 1921553Srgrimes 1931553Srgrimes if (!group->meth->field_mul(group, t3, t3, x, ctx)) goto err; 1941553Srgrimes if (!group->meth->field_div(group, t3, t5, t3, ctx)) goto err; 1951553Srgrimes if (!group->meth->field_mul(group, t4, t3, t4, ctx)) goto err; 1961553Srgrimes if (!group->meth->field_mul(group, x2, x1, t3, ctx)) goto err; 1971553Srgrimes if (!BN_GF2m_add(z2, x2, x)) goto err; 19898555Sjmallett 19998555Sjmallett if (!group->meth->field_mul(group, z2, z2, t4, ctx)) goto err; 2001553Srgrimes if (!BN_GF2m_add(z2, z2, y)) goto err; 20198555Sjmallett 2021553Srgrimes ret = 2; 2031553Srgrimes 2041553Srgrimes err: 2051553Srgrimes BN_CTX_end(ctx); 2061553Srgrimes return ret; 20798555Sjmallett } 20898555Sjmallett 2091553Srgrimes/* Computes scalar*point and stores the result in r. 21098555Sjmallett * point can not equal r. 2111553Srgrimes * Uses algorithm 2P of 2121553Srgrimes * Lopex, J. and Dahab, R. "Fast multiplication on elliptic curves over 2131553Srgrimes * GF(2^m) without precomputation". 2141553Srgrimes */ 21579607Sddstatic int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 216169507Swkoszek const EC_POINT *point, BN_CTX *ctx) 217169507Swkoszek { 218169507Swkoszek BIGNUM *x1, *x2, *z1, *z2; 219169507Swkoszek int ret = 0, i, j; 22079607Sdd BN_ULONG mask; 221169507Swkoszek 222169507Swkoszek if (r == point) 223169507Swkoszek { 224169507Swkoszek ECerr(EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY, EC_R_INVALID_ARGUMENT); 225169507Swkoszek return 0; 226169507Swkoszek } 227169507Swkoszek 228169507Swkoszek /* if result should be point at infinity */ 229169507Swkoszek if ((scalar == NULL) || BN_is_zero(scalar) || (point == NULL) || 230169507Swkoszek EC_POINT_is_at_infinity(group, point)) 231169507Swkoszek { 232169507Swkoszek return EC_POINT_set_to_infinity(group, r); 233169507Swkoszek } 234169507Swkoszek 235169507Swkoszek /* only support affine coordinates */ 236169507Swkoszek if (!point->Z_is_one) return 0; 237169507Swkoszek 238169507Swkoszek /* Since point_multiply is static we can guarantee that ctx != NULL. */ 239169507Swkoszek BN_CTX_start(ctx); 240169507Swkoszek x1 = BN_CTX_get(ctx); 24179607Sdd z1 = BN_CTX_get(ctx); 24279607Sdd if (z1 == NULL) goto err; 24379607Sdd 24479607Sdd x2 = &r->X; 24579607Sdd z2 = &r->Y; 24679607Sdd 24779607Sdd if (!BN_GF2m_mod_arr(x1, &point->X, group->poly)) goto err; /* x1 = x */ 24879607Sdd if (!BN_one(z1)) goto err; /* z1 = 1 */ 24979607Sdd if (!group->meth->field_sqr(group, z2, x1, ctx)) goto err; /* z2 = x1^2 = x^2 */ 25079607Sdd if (!group->meth->field_sqr(group, x2, z2, ctx)) goto err; 25179607Sdd if (!BN_GF2m_add(x2, x2, &group->b)) goto err; /* x2 = x^4 + b */ 25279607Sdd 253136872Sdes /* find top most bit and go one past it */ 25479607Sdd i = scalar->top - 1; j = BN_BITS2 - 1; 255169507Swkoszek mask = BN_TBIT; 25679607Sdd while (!(scalar->d[i] & mask)) { mask >>= 1; j--; } 257136872Sdes mask >>= 1; j--; 258136872Sdes /* if top most bit was at word break, go to next word */ 259136872Sdes if (!mask) 260136872Sdes { 261136872Sdes i--; j = BN_BITS2 - 1; 262136872Sdes mask = BN_TBIT; 263136872Sdes } 26479607Sdd 265136872Sdes for (; i >= 0; i--) 26679607Sdd { 26779607Sdd for (; j >= 0; j--) 268169507Swkoszek { 26979607Sdd if (scalar->d[i] & mask) 27079607Sdd { 27179607Sdd if (!gf2m_Madd(group, &point->X, x1, z1, x2, z2, ctx)) goto err; 27279607Sdd if (!gf2m_Mdouble(group, x2, z2, ctx)) goto err; 27379607Sdd } 27479607Sdd else 27579607Sdd { 27679607Sdd if (!gf2m_Madd(group, &point->X, x2, z2, x1, z1, ctx)) goto err; 27779607Sdd if (!gf2m_Mdouble(group, x1, z1, ctx)) goto err; 27879607Sdd } 27979607Sdd mask >>= 1; 28079607Sdd } 28179607Sdd j = BN_BITS2 - 1; 28279607Sdd mask = BN_TBIT; 28379607Sdd } 28479607Sdd 28579607Sdd /* convert out of "projective" coordinates */ 28679607Sdd i = gf2m_Mxy(group, &point->X, &point->Y, x1, z1, x2, z2, ctx); 28779607Sdd if (i == 0) goto err; 28879607Sdd else if (i == 1) 28979607Sdd { 29079607Sdd if (!EC_POINT_set_to_infinity(group, r)) goto err; 29179607Sdd } 29279607Sdd else 29379607Sdd { 29479607Sdd if (!BN_one(&r->Z)) goto err; 29579607Sdd r->Z_is_one = 1; 29679607Sdd } 29779607Sdd 29879607Sdd /* GF(2^m) field elements should always have BIGNUM::neg = 0 */ 29979607Sdd BN_set_negative(&r->X, 0); 30079607Sdd BN_set_negative(&r->Y, 0); 30179607Sdd 30279607Sdd ret = 1; 30379607Sdd 30479607Sdd err: 30579607Sdd BN_CTX_end(ctx); 306 return ret; 307 } 308 309 310/* Computes the sum 311 * scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1] 312 * gracefully ignoring NULL scalar values. 313 */ 314int ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, 315 size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx) 316 { 317 BN_CTX *new_ctx = NULL; 318 int ret = 0; 319 size_t i; 320 EC_POINT *p=NULL; 321 EC_POINT *acc = NULL; 322 323 if (ctx == NULL) 324 { 325 ctx = new_ctx = BN_CTX_new(); 326 if (ctx == NULL) 327 return 0; 328 } 329 330 /* This implementation is more efficient than the wNAF implementation for 2 331 * or fewer points. Use the ec_wNAF_mul implementation for 3 or more points, 332 * or if we can perform a fast multiplication based on precomputation. 333 */ 334 if ((scalar && (num > 1)) || (num > 2) || (num == 0 && EC_GROUP_have_precompute_mult(group))) 335 { 336 ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx); 337 goto err; 338 } 339 340 if ((p = EC_POINT_new(group)) == NULL) goto err; 341 if ((acc = EC_POINT_new(group)) == NULL) goto err; 342 343 if (!EC_POINT_set_to_infinity(group, acc)) goto err; 344 345 if (scalar) 346 { 347 if (!ec_GF2m_montgomery_point_multiply(group, p, scalar, group->generator, ctx)) goto err; 348 if (BN_is_negative(scalar)) 349 if (!group->meth->invert(group, p, ctx)) goto err; 350 if (!group->meth->add(group, acc, acc, p, ctx)) goto err; 351 } 352 353 for (i = 0; i < num; i++) 354 { 355 if (!ec_GF2m_montgomery_point_multiply(group, p, scalars[i], points[i], ctx)) goto err; 356 if (BN_is_negative(scalars[i])) 357 if (!group->meth->invert(group, p, ctx)) goto err; 358 if (!group->meth->add(group, acc, acc, p, ctx)) goto err; 359 } 360 361 if (!EC_POINT_copy(r, acc)) goto err; 362 363 ret = 1; 364 365 err: 366 if (p) EC_POINT_free(p); 367 if (acc) EC_POINT_free(acc); 368 if (new_ctx != NULL) 369 BN_CTX_free(new_ctx); 370 return ret; 371 } 372 373 374/* Precomputation for point multiplication: fall back to wNAF methods 375 * because ec_GF2m_simple_mul() uses ec_wNAF_mul() if appropriate */ 376 377int ec_GF2m_precompute_mult(EC_GROUP *group, BN_CTX *ctx) 378 { 379 return ec_wNAF_precompute_mult(group, ctx); 380 } 381 382int ec_GF2m_have_precompute_mult(const EC_GROUP *group) 383 { 384 return ec_wNAF_have_precompute_mult(group); 385 } 386