/* crypto/ec/ec_mult.c */
/*
* Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project.
*/
/* ====================================================================
* Copyright (c) 1998-2007 The OpenSSL Project. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* 3. All advertising materials mentioning features or use of this
* software must display the following acknowledgment:
* "This product includes software developed by the OpenSSL Project
* for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
*
* 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
* endorse or promote products derived from this software without
* prior written permission. For written permission, please contact
* openssl-core@openssl.org.
*
* 5. Products derived from this software may not be called "OpenSSL"
* nor may "OpenSSL" appear in their names without prior written
* permission of the OpenSSL Project.
*
* 6. Redistributions of any form whatsoever must retain the following
* acknowledgment:
* "This product includes software developed by the OpenSSL Project
* for use in the OpenSSL Toolkit (http://www.openssl.org/)"
*
* THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
* EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
* OF THE POSSIBILITY OF SUCH DAMAGE.
* ====================================================================
*
* This product includes cryptographic software written by Eric Young
* (eay@cryptsoft.com). This product includes software written by Tim
* Hudson (tjh@cryptsoft.com).
*
*/
/* ====================================================================
* Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
* Portions of this software developed by SUN MICROSYSTEMS, INC.,
* and contributed to the OpenSSL project.
*/
#include <string.h>
#include <openssl/err.h>
#include "ec_lcl.h"
/*
* This file implements the wNAF-based interleaving multi-exponentiation method
* Formerly at:
* http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp
* You might now find it here:
* http://link.springer.com/chapter/10.1007%2F3-540-45537-X_13
* http://www.bmoeller.de/pdf/TI-01-08.multiexp.pdf
* For multiplication with precomputation, we use wNAF splitting, formerly at:
* http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#fastexp
*/
/* structure for precomputed multiples of the generator */
typedef struct ec_pre_comp_st {
const EC_GROUP *group; /* parent EC_GROUP object */
size_t blocksize; /* block size for wNAF splitting */
size_t numblocks; /* max. number of blocks for which we have
* precomputation */
size_t w; /* window size */
EC_POINT **points; /* array with pre-calculated multiples of
* generator: 'num' pointers to EC_POINT
* objects followed by a NULL */
size_t num; /* numblocks * 2^(w-1) */
int references;
} EC_PRE_COMP;
/* functions to manage EC_PRE_COMP within the EC_GROUP extra_data framework */
static void *ec_pre_comp_dup(void *);
static void ec_pre_comp_free(void *);
static void ec_pre_comp_clear_free(void *);
static EC_PRE_COMP *ec_pre_comp_new(const EC_GROUP *group)
{
EC_PRE_COMP *ret = NULL;
if (!group)
return NULL;
ret = (EC_PRE_COMP *)OPENSSL_malloc(sizeof(EC_PRE_COMP));
if (!ret) {
ECerr(EC_F_EC_PRE_COMP_NEW, ERR_R_MALLOC_FAILURE);
return ret;
}
ret->group = group;
ret->blocksize = 8; /* default */
ret->numblocks = 0;
ret->w = 4; /* default */
ret->points = NULL;
ret->num = 0;
ret->references = 1;
return ret;
}
static void *ec_pre_comp_dup(void *src_)
{
EC_PRE_COMP *src = src_;
/* no need to actually copy, these objects never change! */
CRYPTO_add(&src->references, 1, CRYPTO_LOCK_EC_PRE_COMP);
return src_;
}
static void ec_pre_comp_free(void *pre_)
{
int i;
EC_PRE_COMP *pre = pre_;
if (!pre)
return;