/* $OpenBSD: ec_mult.c,v 1.21 2017/05/02 03:59:44 deraadt Exp $ */

/*

 * 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-exponentation method

 * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>);

 * for multiplication with precomputation, we use wNAF splitting

 * (<URL: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;

	}

static void *

ec_pre_comp_dup(void *src_)

{

	/* no need to actually copy, these objects never change! */

}

static void

ec_pre_comp_free(void *pre_)

{

	int i;

		EC_POINT **p;

static void

ec_pre_comp_clear_free(void *pre_)

{

	int i;

		EC_POINT **p;

		}

	}

}

/* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.

 * This is an array  r[]  of values that are either zero or odd with an

 * absolute value less than  2^w  satisfying

 *     scalar = \sum_j r[j]*2^j

 * where at most one of any  w+1  consecutive digits is non-zero

 * with the exception that the most significant digit may be only

 * w-1 zeros away from that next non-zero digit.

 */

static signed char *

compute_wNAF(const BIGNUM * scalar, int w, size_t * ret_len)

{

	int window_val;

	int ok = 0;

	signed char *r = NULL;

	int sign = 1;

	int bit, next_bit, mask;

	size_t len = 0, j;

		}

	}

		/* 'signed char' can represent integers with

		 * absolute values less than 2^7 */

	}

		sign = -1;

	}

				 * binary representation (*ret_len will be

				 * set to the actual length, i.e. at most

				 * BN_num_bits(scalar) + 1) */

	}

	j = 0;

		/* if j+w+1 >= len, window_val will not increase */

		int digit = 0;

		/* 0 <= window_val <= 2^(w+1) */

			/* 0 < window_val < 2^(w+1) */

#if 1				/* modified wNAF */

					/*

					 * special case for generating

					 * modified wNAFs: no new bits will

					 * be added into window_val, so using

					 * a positive digit here will

					 * decrease the total length of the

					 * representation

					 */

#endif

			} else {

				digit = window_val;	/* 0 < digit < 2^w */

			}

			}

			/*

			 * now window_val is 0 or 2^(w+1) in standard wNAF

			 * generation; for modified window NAFs, it may also

			 * be 2^w

			 */

			}

		}

		}

	}

	len = j;

err:

		r = NULL;

	}

/* TODO: table should be optimised for the wNAF-based implementation,

 *       sometimes smaller windows will give better performance

 *       (thus the boundaries should be increased)

 */

#define EC_window_bits_for_scalar_size(b) \

		((size_t) \

		 ((b) >= 2000 ? 6 : \

		  (b) >=  800 ? 5 : \

		  (b) >=  300 ? 4 : \

		  (b) >=   70 ? 3 : \

		  (b) >=   20 ? 2 : \

		  1))

/* Compute

 *      \sum scalars[i]*points[i],

 * also including

 *      scalar*generator

 * in the addition if scalar != NULL

 */

int

ec_wNAF_mul(const EC_GROUP * group, EC_POINT * r, const BIGNUM * scalar,

    size_t num, const EC_POINT * points[], const BIGNUM * scalars[], BN_CTX * ctx)

{

	BN_CTX *new_ctx = NULL;

	const EC_POINT *generator = NULL;

	EC_POINT *tmp = NULL;

	size_t totalnum;

	size_t blocksize = 0, numblocks = 0;	/* for wNAF splitting */

	size_t pre_points_per_block = 0;

	size_t i, j;

	int k;

	int r_is_inverted = 0;

	int r_is_at_infinity = 1;

	size_t *wsize = NULL;	/* individual window sizes */

	signed char **wNAF = NULL;	/* individual wNAFs */

	signed char *tmp_wNAF = NULL;

	size_t *wNAF_len = NULL;

	size_t max_len = 0;

	size_t num_val;

	EC_POINT **val = NULL;	/* precomputation */

	EC_POINT **v;

	EC_POINT ***val_sub = NULL;	/* pointers to sub-arrays of 'val' or

					 * 'pre_comp->points' */

	const EC_PRE_COMP *pre_comp = NULL;

	int num_scalar = 0;	/* flag: will be set to 1 if 'scalar' must be

				 * treated like other scalars, i.e.

				 * precomputation is not available */

	int ret = 0;

	}

	}

		}

	}

			goto err;

	}

		}

		/* look if we can use precomputed multiples of generator */

			/*

			 * determine maximum number of blocks that wNAF

			 * splitting may yield (NB: maximum wNAF length is

			 * bit length plus one)

			 */

			/*

			 * we cannot use more blocks than we have

			 * precomputation for

			 */

			/* check that pre_comp looks sane */

			}

		} else {

			/* can't use precomputation */

			pre_comp = NULL;

			numblocks = 1;

			num_scalar = 1;	/* treat 'scalar' like 'num'-th

					 * element of 'scalars' */

		}

	}

	/* includes space for pivot */

	}

	}

	/* num_val will be the total number of temporarily precomputed points */

	num_val = 0;

		size_t bits;

		/* we go here iff scalar != NULL */

			}

			/* we have already generated a wNAF for 'scalar' */

		} else {

			}

			/*

			 * use the window size for which we have

			 * precomputation

			 */

				/*

				 * One of the other wNAFs is at least as long

				 * as the wNAF belonging to the generator, so

				 * wNAF splitting will not buy us anything.

				 */

				numblocks = 1;

							 * splitting */

				tmp_wNAF = NULL;

				/*

				 * pre_comp->points starts with the points

				 * that we need here:

				 */

				/*

				 * don't include tmp_wNAF directly into wNAF

				 * array - use wNAF splitting and include the

				 * blocks

				 */

				signed char *pp;

				EC_POINT **tmp_points;

					/*

					 * possibly we can do with fewer

					 * blocks than estimated

					 */

					}

				/* split wNAF in 'numblocks' parts */

				pp = tmp_wNAF;

						}

						/*

						 * last block gets whatever

						 * is left (this could be

						 * more or less than

						 * 'blocksize'!)

						 */

					}

					}

				}

	}

	/*

	 * All points we precompute now go into a single array 'val'.

	 * 'val_sub[i]' is a pointer to the subarray for the i-th point, or

	 * to a subarray of 'pre_comp->points' if we already have

	 * precomputation.

	 */

	}

	/* allocate points for precomputation */

	v = val;

				goto err;

		}

	}

	}

		goto err;

	/*

	 * prepare precomputed values: val_sub[i][0] :=     points[i]

	 * val_sub[i][1] := 3 * points[i] val_sub[i][2] := 5 * points[i] ...

	 */

				goto err;

		} else {

				goto err;

		}

				goto err;

					goto err;

			}

		}

	}

		goto err;

	r_is_at_infinity = 1;

				goto err;

		}

				int is_neg;

						}

					/* digit > 0 */

						r_is_at_infinity = 0;

					}

				}

		}

	}

			goto err;

	} else {

				goto err;

	}

err:

		signed char **w;

/* ec_wNAF_precompute_mult()

 * creates an EC_PRE_COMP object with preprecomputed multiples of the generator

 * for use with wNAF splitting as implemented in ec_wNAF_mul().

 *

 * 'pre_comp->points' is an array of multiples of the generator

 * of the following form:

 * points[0] =     generator;

 * points[1] = 3 * generator;

 * ...

 * points[2^(w-1)-1] =     (2^(w-1)-1) * generator;

 * points[2^(w-1)]   =     2^blocksize * generator;

 * points[2^(w-1)+1] = 3 * 2^blocksize * generator;

 * ...

 * points[2^(w-1)*(numblocks-1)-1] = (2^(w-1)) *  2^(blocksize*(numblocks-2)) * generator

 * points[2^(w-1)*(numblocks-1)]   =              2^(blocksize*(numblocks-1)) * generator

 * ...

 * points[2^(w-1)*numblocks-1]     = (2^(w-1)) *  2^(blocksize*(numblocks-1)) * generator

 * points[2^(w-1)*numblocks]       = NULL

 */

int

ec_wNAF_precompute_mult(EC_GROUP * group, BN_CTX * ctx)

{

	const EC_POINT *generator;

	EC_POINT *tmp_point = NULL, *base = NULL, **var;

	BN_CTX *new_ctx = NULL;

	BIGNUM *order;

	size_t i, bits, w, pre_points_per_block, blocksize, numblocks,

	 num;

	EC_POINT **points = NULL;

	EC_PRE_COMP *pre_comp;

	int ret = 0;

	/* if there is an old EC_PRE_COMP object, throw it away */

	}

			goto err;

	}

		goto err;

		goto err;

	}

	/*

	 * The following parameters mean we precompute (approximately) one

	 * point per bit.

	 *

	 * TBD: The combination  8, 4  is perfect for 160 bits; for other bit

	 * lengths, other parameter combinations might provide better

	 * efficiency.

	 */

	blocksize = 8;

	w = 4;

		/* let's not make the window too small ... */

	}

							 * to use for wNAF

							 * splitting */

						 * compute and store */

	}

	var = points;

		}

	}

	}

		goto err;

	/* do the precomputation */

		size_t j;

			/* calculate odd multiples of the current base point */

		}

			/*

			 * get the next base (multiply current one by

			 * 2^blocksize)

			 */

			size_t k;

			}

			}

		goto err;

	points = NULL;

		ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free))

		goto err;

	pre_comp = NULL;

err:

		EC_POINT **p;

	}

int

ec_wNAF_have_precompute_mult(const EC_GROUP * group)

{

	else