implement fast point multiplication with precomputation

Submitted by: Nils Larsch
Reviewed by: Bodo Moeller

12 files changed, 613 insertions, 130 deletions

diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h
index 53fb8cf..f68963e 100644
--- a/crypto/ec/ec.h
+++ b/crypto/ec/ec.h
@@ -3,7 +3,7 @@
  * Originally written by Bodo Moeller for the OpenSSL project.
  */
 /* ====================================================================
- * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
+ * Copyright (c) 1998-2003 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
@@ -101,7 +101,7 @@ typedef struct ec_group_st
 	 -- field definition
 	 -- curve coefficients
 	 -- optional generator with associated information (order, cofactor)
-	 -- optional extra data (TODO: precomputed table for fast computation of multiples of generator)
+	 -- optional extra data (precomputed table for fast computation of multiples of generator)
 	 -- ASN1 stuff
 	*/
 	EC_GROUP;
@@ -241,7 +241,11 @@ int EC_POINTs_make_affine(const EC_GROUP *, size_t num, EC_POINT *[], BN_CTX *);
 
 int EC_POINTs_mul(const EC_GROUP *, EC_POINT *r, const BIGNUM *, size_t num, const EC_POINT *[], const BIGNUM *[], BN_CTX *);
 int EC_POINT_mul(const EC_GROUP *, EC_POINT *r, const BIGNUM *, const EC_POINT *, const BIGNUM *, BN_CTX *);
+
+/* EC_GROUP_precompute_mult() stores multiples of generator for faster point multiplication */
 int EC_GROUP_precompute_mult(EC_GROUP *, BN_CTX *);
+/* EC_GROUP_have_precompute_mult() reports whether such precomputation has been done */
+int EC_GROUP_have_precompute_mult(const EC_GROUP *);
 
 
 
@@ -403,7 +407,6 @@ void ERR_load_EC_strings(void);
 #define EC_F_EC_GROUP_GET_CURVE_GF2M			 172
 #define EC_F_EC_GROUP_GET_CURVE_GFP			 130
 #define EC_F_EC_GROUP_GET_DEGREE			 173
-#define EC_F_EC_GROUP_GET_EXTRA_DATA			 107
 #define EC_F_EC_GROUP_GET_ORDER				 141
 #define EC_F_EC_GROUP_GET_PENTANOMIAL_BASIS		 193
 #define EC_F_EC_GROUP_GET_TRINOMIAL_BASIS		 194
@@ -444,6 +447,7 @@ void ERR_load_EC_strings(void);
 #define EC_F_EC_POINT_SET_COMPRESSED_COORDINATES_GFP	 125
 #define EC_F_EC_POINT_SET_JPROJECTIVE_COORDINATES_GFP	 126
 #define EC_F_EC_POINT_SET_TO_INFINITY			 127
+#define EC_F_EC_PRE_COMP_DUP				 207
 #define EC_F_EC_WNAF_MUL				 187
 #define EC_F_EC_WNAF_PRECOMPUTE_MULT			 188
 #define EC_F_GFP_MONT_GROUP_SET_CURVE			 189
@@ -462,7 +466,6 @@ void ERR_load_EC_strings(void);
 #define EC_R_GROUP2PKPARAMETERS_FAILURE			 120
 #define EC_R_I2D_ECPKPARAMETERS_FAILURE			 121
 #define EC_R_INCOMPATIBLE_OBJECTS			 101
-#define EC_R_INTERNAL_ERROR				 132
 #define EC_R_INVALID_ARGUMENT				 112
 #define EC_R_INVALID_COMPRESSED_POINT			 110
 #define EC_R_INVALID_COMPRESSION_BIT			 109
@@ -473,12 +476,11 @@ void ERR_load_EC_strings(void);
 #define EC_R_INVALID_PRIVATE_KEY			 123
 #define EC_R_MISSING_PARAMETERS				 124
 #define EC_R_MISSING_PRIVATE_KEY			 125
-#define EC_R_NOT_A_NIST_PRIME			         135
-#define EC_R_NOT_A_SUPPORTED_NIST_PRIME	                 136
+#define EC_R_NOT_A_NIST_PRIME				 135
+#define EC_R_NOT_A_SUPPORTED_NIST_PRIME			 136
 #define EC_R_NOT_IMPLEMENTED				 126
 #define EC_R_NOT_INITIALIZED				 111
 #define EC_R_NO_FIELD_MOD				 133
-#define EC_R_NO_SUCH_EXTRA_DATA				 105
 #define EC_R_PASSED_NULL_PARAMETER			 134
 #define EC_R_PKPARAMETERS2GROUP_FAILURE			 127
 #define EC_R_POINT_AT_INFINITY				 106
diff --git a/crypto/ec/ec2_mult.c b/crypto/ec/ec2_mult.c
index eefb41a..a0effa9 100644
--- a/crypto/ec/ec2_mult.c
+++ b/crypto/ec/ec2_mult.c
@@ -14,7 +14,7 @@
  *
  */
 /* ====================================================================
- * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
+ * Copyright (c) 1998-2003 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
@@ -326,9 +326,10 @@ int ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 		}
 
 	/* This implementation is more efficient than the wNAF implementation for 2
-	 * or fewer points.  Use the ec_wNAF_mul implementation for 3 or more points.
+	 * or fewer points.  Use the ec_wNAF_mul implementation for 3 or more points,
+	 * or if we can perform a fast multiplication based on precomputation.
 	 */
-	if ((scalar && (num > 1)) || (num > 2))
+	if ((scalar && (num > 1)) || (num > 2) || (num == 0 && EC_GROUP_have_precompute_mult(group)))
 		{
 		ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
 		goto err;
@@ -364,12 +365,15 @@ int ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 	}
 
 
-/* Precomputation for point multiplication. */	
+/* Precomputation for point multiplication: fall back to wNAF methods
+ * because ec_GF2m_simple_mul() uses ec_wNAF_mul() if appropriate */
+
 int ec_GF2m_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
 	{
-	/* There is no precomputation to do for Montgomery scalar multiplication but
-	 * since this implementation falls back to the wNAF multiplication for more than
-	 * two points, call the wNAF implementation's precompute.
-	 */
 	return ec_wNAF_precompute_mult(group, ctx);
-	}
+ 	}
+
+int ec_GF2m_have_precompute_mult(const EC_GROUP *group)
+	{
+	return ec_wNAF_have_precompute_mult(group);
+ 	}
diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c
index a6fa4da..89e8152 100644
--- a/crypto/ec/ec2_smpl.c
+++ b/crypto/ec/ec2_smpl.c
@@ -14,7 +14,7 @@
  *
  */
 /* ====================================================================
- * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
+ * Copyright (c) 1998-2003 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
@@ -99,13 +99,17 @@ const EC_METHOD *EC_GF2m_simple_method(void)
 		ec_GF2m_simple_add,
 		ec_GF2m_simple_dbl,
 		ec_GF2m_simple_invert,
-		ec_GF2m_simple_mul,
-		ec_GF2m_precompute_mult,
 		ec_GF2m_simple_is_at_infinity,
 		ec_GF2m_simple_is_on_curve,
 		ec_GF2m_simple_cmp,
 		ec_GF2m_simple_make_affine,
 		ec_GF2m_simple_points_make_affine,
+
+		/* the following three method functions are defined in ec2_mult.c */
+		ec_GF2m_simple_mul,
+		ec_GF2m_precompute_mult,
+		ec_GF2m_have_precompute_mult,
+
 		ec_GF2m_simple_field_mul,
 		ec_GF2m_simple_field_sqr,
 		ec_GF2m_simple_field_div,
diff --git a/crypto/ec/ec_err.c b/crypto/ec/ec_err.c
index 58ae9d6..7730402 100644
--- a/crypto/ec/ec_err.c
+++ b/crypto/ec/ec_err.c
@@ -1,6 +1,6 @@
 /* crypto/ec/ec_err.c */
 /* ====================================================================
- * Copyright (c) 1999-2002 The OpenSSL Project.  All rights reserved.
+ * Copyright (c) 1999-2003 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
@@ -122,7 +122,6 @@ static ERR_STRING_DATA EC_str_functs[]=
 {ERR_PACK(0,EC_F_EC_GROUP_GET_CURVE_GF2M,0),	"EC_GROUP_get_curve_GF2m"},
 {ERR_PACK(0,EC_F_EC_GROUP_GET_CURVE_GFP,0),	"EC_GROUP_get_curve_GFp"},
 {ERR_PACK(0,EC_F_EC_GROUP_GET_DEGREE,0),	"EC_GROUP_get_degree"},
-{ERR_PACK(0,EC_F_EC_GROUP_GET_EXTRA_DATA,0),	"EC_GROUP_get_extra_data"},
 {ERR_PACK(0,EC_F_EC_GROUP_GET_ORDER,0),	"EC_GROUP_get_order"},
 {ERR_PACK(0,EC_F_EC_GROUP_GET_PENTANOMIAL_BASIS,0),	"EC_GROUP_get_pentanomial_basis"},
 {ERR_PACK(0,EC_F_EC_GROUP_GET_TRINOMIAL_BASIS,0),	"EC_GROUP_get_trinomial_basis"},
@@ -163,6 +162,7 @@ static ERR_STRING_DATA EC_str_functs[]=
 {ERR_PACK(0,EC_F_EC_POINT_SET_COMPRESSED_COORDINATES_GFP,0),	"EC_POINT_set_compressed_coordinates_GFp"},
 {ERR_PACK(0,EC_F_EC_POINT_SET_JPROJECTIVE_COORDINATES_GFP,0),	"EC_POINT_set_Jprojective_coordinates_GFp"},
 {ERR_PACK(0,EC_F_EC_POINT_SET_TO_INFINITY,0),	"EC_POINT_set_to_infinity"},
+{ERR_PACK(0,EC_F_EC_PRE_COMP_DUP,0),	"EC_PRE_COMP_DUP"},
 {ERR_PACK(0,EC_F_EC_WNAF_MUL,0),	"ec_wNAF_mul"},
 {ERR_PACK(0,EC_F_EC_WNAF_PRECOMPUTE_MULT,0),	"ec_wNAF_precompute_mult"},
 {ERR_PACK(0,EC_F_GFP_MONT_GROUP_SET_CURVE,0),	"GFP_MONT_GROUP_SET_CURVE"},
@@ -184,7 +184,6 @@ static ERR_STRING_DATA EC_str_reasons[]=
 {EC_R_GROUP2PKPARAMETERS_FAILURE         ,"group2pkparameters failure"},
 {EC_R_I2D_ECPKPARAMETERS_FAILURE         ,"i2d ecpkparameters failure"},
 {EC_R_INCOMPATIBLE_OBJECTS               ,"incompatible objects"},
-{EC_R_INTERNAL_ERROR                     ,"internal error"},
 {EC_R_INVALID_ARGUMENT                   ,"invalid argument"},
 {EC_R_INVALID_COMPRESSED_POINT           ,"invalid compressed point"},
 {EC_R_INVALID_COMPRESSION_BIT            ,"invalid compression bit"},
@@ -200,7 +199,6 @@ static ERR_STRING_DATA EC_str_reasons[]=
 {EC_R_NOT_IMPLEMENTED                    ,"not implemented"},
 {EC_R_NOT_INITIALIZED                    ,"not initialized"},
 {EC_R_NO_FIELD_MOD                       ,"no field mod"},
-{EC_R_NO_SUCH_EXTRA_DATA                 ,"no such extra data"},
 {EC_R_PASSED_NULL_PARAMETER              ,"passed null parameter"},
 {EC_R_PKPARAMETERS2GROUP_FAILURE         ,"pkparameters2group failure"},
 {EC_R_POINT_AT_INFINITY                  ,"point at infinity"},
diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h
index a96d0df..54b6a45 100644
--- a/crypto/ec/ec_lcl.h
+++ b/crypto/ec/ec_lcl.h
@@ -3,7 +3,7 @@
  * Originally written by Bodo Moeller for the OpenSSL project.
  */
 /* ====================================================================
- * Copyright (c) 1998-2001 The OpenSSL Project.  All rights reserved.
+ * Copyright (c) 1998-2003 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
@@ -136,11 +136,6 @@ struct ec_method_st {
 	int (*dbl)(const EC_GROUP *, EC_POINT *r, const EC_POINT *a, BN_CTX *);
 	int (*invert)(const EC_GROUP *, EC_POINT *, BN_CTX *);
 
-	/* used by EC_POINTs_mul, EC_POINT_mul, EC_POINT_precompute_mult: */
-	int (*mul)(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
-		size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *);
-	int (*precompute_mult)(EC_GROUP *group, BN_CTX *);
-
 	/* used by EC_POINT_is_at_infinity, EC_POINT_is_on_curve, EC_POINT_cmp: */
 	int (*is_at_infinity)(const EC_GROUP *, const EC_POINT *);
 	int (*is_on_curve)(const EC_GROUP *, const EC_POINT *, BN_CTX *);
@@ -150,6 +145,13 @@ struct ec_method_st {
 	int (*make_affine)(const EC_GROUP *, EC_POINT *, BN_CTX *);
 	int (*points_make_affine)(const EC_GROUP *, size_t num, EC_POINT *[], BN_CTX *);
 
+	/* used by EC_POINTs_mul, EC_POINT_mul, EC_POINT_precompute_mult, EC_POINT_have_precompute_mult
+	 * (default implementations are used if the 'mul' pointer is 0): */
+	int (*mul)(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
+		size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *);
+	int (*precompute_mult)(EC_GROUP *group, BN_CTX *);
+	int (*have_precompute_mult)(const EC_GROUP *group);
+
 
 	/* internal functions */
 
@@ -248,10 +250,13 @@ struct ec_point_st {
 
 
 
-/* method functions in ec_mult.c */
+/* method functions in ec_mult.c
+ * (ec_lib.c uses these as defaults if group->method->mul is 0 */
 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 *);
 int ec_wNAF_precompute_mult(EC_GROUP *group, BN_CTX *);
+int ec_wNAF_have_precompute_mult(const EC_GROUP *group);
+
 
 /* method functions in ecp_smpl.c */
 int ec_GFp_simple_group_init(EC_GROUP *);
@@ -363,3 +368,4 @@ int ec_GF2m_simple_field_div(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, const
 int ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 	size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *);
 int ec_GF2m_precompute_mult(EC_GROUP *group, BN_CTX *ctx);
+int ec_GF2m_have_precompute_mult(const EC_GROUP *group);
diff --git a/crypto/ec/ec_lib.c b/crypto/ec/ec_lib.c
index 2cc0dc0..5e3fb5c 100644
--- a/crypto/ec/ec_lib.c
+++ b/crypto/ec/ec_lib.c
@@ -3,7 +3,7 @@
  * Originally written by Bodo Moeller for the OpenSSL project.
  */
 /* ====================================================================
- * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
+ * Copyright (c) 1998-2003 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
@@ -503,7 +503,9 @@ void *EC_GROUP_get_extra_data(const EC_GROUP *group, void *(*extra_data_dup_func
 		|| (group->extra_data_free_func != extra_data_free_func)
 		|| (group->extra_data_clear_free_func != extra_data_clear_free_func))
 		{
+#if 0 /* this was an error in 0.9.7, but that does not make a lot of sense */
 		ECerr(EC_F_EC_GROUP_GET_EXTRA_DATA, EC_R_NO_SUCH_EXTRA_DATA);
+#endif
 		return NULL;
 		}
 
@@ -956,3 +958,58 @@ int EC_POINTs_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[],
 		}
 	return group->meth->points_make_affine(group, num, points, ctx);
 	}
+
+
+/* Functions for point multiplication.
+ *
+ * If group->meth->mul is 0, we use the wNAF-based implementations in ec_mult.c;
+ * otherwise we dispatch through methods.
+ */
+
+int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
+	size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
+	{
+	if (group->meth->mul == 0)
+		/* use default */
+		return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
+
+	return group->meth->mul(group, r, scalar, num, points, scalars, ctx);
+	}
+
+int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar,
+	const EC_POINT *point, const BIGNUM *p_scalar, BN_CTX *ctx)
+	{
+	/* just a convenient interface to EC_POINTs_mul() */
+
+	const EC_POINT *points[1];
+	const BIGNUM *scalars[1];
+
+	points[0] = point;
+	scalars[0] = p_scalar;
+
+	return EC_POINTs_mul(group, r, g_scalar, (point != NULL && p_scalar != NULL), points, scalars, ctx);
+	}
+
+int EC_GROUP_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
+	{
+	if (group->meth->mul == 0)
+		/* use default */
+		return ec_wNAF_precompute_mult(group, ctx);
+
+	if (group->meth->precompute_mult != 0)
+		return group->meth->precompute_mult(group, ctx);
+	else
+		return 1; /* nothing to do, so report success */
+	}
+
+int EC_GROUP_have_precompute_mult(const EC_GROUP *group)
+	{
+	if (group->meth->mul == 0)
+		/* use default */
+		return ec_wNAF_have_precompute_mult(group);
+
+	if (group->meth->have_precompute_mult != 0)
+		return group->meth->have_precompute_mult(group);
+	else
+		return 0; /* cannot tell whether precomputation has been performed */
+	}
diff --git a/crypto/ec/ec_mult.c b/crypto/ec/ec_mult.c
index f5312aa..42cd981 100644
--- a/crypto/ec/ec_mult.c
+++ b/crypto/ec/ec_mult.c
@@ -1,9 +1,9 @@
 /* crypto/ec/ec_mult.c */
 /*
- * Originally written by Bodo Moeller for the OpenSSL project.
+ * Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project.
  */
 /* ====================================================================
- * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
+ * Copyright (c) 1998-2003 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
@@ -66,14 +66,135 @@
 #include "ec_lcl.h"
 
 
-/* TODO: optional precomputation of multiples of the generator */
+/*
+ * 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>).
+ */
 
 
 
-/*
- * wNAF-based interleaving multi-exponentation method
- * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>)
- */
+
+/* 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) */
+} 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)
+		return ret;
+	ret->group = group;
+	ret->blocksize = 8; /* default */
+	ret->numblocks = 0;
+	ret->w = 4; /* default */
+	ret->points = NULL;
+	ret->num = 0;
+	return ret;
+	}
+
+static void *ec_pre_comp_dup(void *src_)
+	{
+	const EC_PRE_COMP *src = src_;
+	EC_PRE_COMP *ret = NULL;
+
+	ret = ec_pre_comp_new(src->group);
+	if (!ret)
+		return ret;
+	ret->blocksize = src->blocksize;
+	ret->numblocks = src->numblocks;
+	ret->w = src->w;
+	ret->num = 0;
+
+	if (src->points)
+		{
+		EC_POINT **src_var, **dest_var;
+
+		ret->points = (EC_POINT **)OPENSSL_malloc((src->num + 1) * sizeof(EC_POINT *));
+		if (!ret->points)
+			{
+			ec_pre_comp_free(ret);
+			return NULL;
+			}
+
+		for (dest_var = ret->points, src_var = src->points; *src_var != NULL; src_var++, dest_var++)
+			{
+			*dest_var = EC_POINT_dup(*src_var, src->group);
+			if (*dest_var == NULL)
+				{
+				ec_pre_comp_free(ret);
+				return NULL;
+				}
+			ret->num++;
+			}
+
+		ret->points[ret->num] = NULL;
+		if (ret->num != src->num)
+			{
+			ec_pre_comp_free(ret);
+			ECerr(EC_F_EC_PRE_COMP_DUP, ERR_R_INTERNAL_ERROR);
+			return NULL;
+			}
+		}
+
+	return ret;
+	}
+
+static void ec_pre_comp_free(void *pre_)
+	{
+	EC_PRE_COMP *pre = pre_;
+
+	if (!pre)
+		return;
+	if (pre->points)
+		{
+		EC_POINT **var;
+
+		for (var = pre->points; *var != NULL; var++)
+			EC_POINT_free(*var);
+		OPENSSL_free(pre->points);
+		}
+	OPENSSL_free(pre);
+	}
+
+static void ec_pre_comp_clear_free(void *pre_)
+	{
+	EC_PRE_COMP *pre = pre_;
+
+	if (!pre)
+		return;
+	if (pre->points)
+		{
+		EC_POINT **p;
+
+		for (p = pre->points; *p != NULL; p++)
+			EC_POINT_clear_free(*p);
+		OPENSSL_cleanse(pre->points, sizeof pre->points);
+		OPENSSL_free(pre->points);
+		}
+	OPENSSL_cleanse(pre, sizeof pre);
+	OPENSSL_free(pre);
+	}
+
+
 
 
 /* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
@@ -108,7 +229,9 @@ static signed char *compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
 		}
 
 	len = BN_num_bits(scalar);
-	r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer than binary representation */
+	r = OPENSSL_malloc(len + 1); /* modified wNAF may be one digit longer than binary representation
+	                              * (*ret_len will be set to the actual length, i.e. at most
+	                              * BN_num_bits(scalar) + 1) */
 	if (r == NULL) goto err;
 
 	if (scalar->d == NULL || scalar->top == 0)
@@ -224,6 +347,8 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 	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;
@@ -235,19 +360,23 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 	size_t num_val;
 	EC_POINT **val = NULL; /* precomputation */
 	EC_POINT **v;
-	EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' */
+	EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' or 'pre_comp->points' */
+	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;
 	
-	if (scalar != NULL)
+	if (group->meth != r->meth)
 		{
-		generator = EC_GROUP_get0_generator(group);
-		if (generator == NULL)
-			{
-			ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR);
-			return 0;
-			}
+		ECerr(EC_F_EC_WNAF_MUL, EC_R_INCOMPATIBLE_OBJECTS);
+		return 0;
 		}
-	
+
+	if ((scalar == NULL) && (num == 0))
+		{
+		return EC_POINT_set_to_infinity(group, r);
+		}
+
 	for (i = 0; i < num; i++)
 		{
 		if (group->meth != points[i]->meth)
@@ -257,40 +386,209 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 			}
 		}
 
-	totalnum = num + (scalar != NULL);
+	if (ctx == NULL)
+		{
+		ctx = new_ctx = BN_CTX_new();
+		if (ctx == NULL)
+			goto err;
+		}
 
-	wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]);
-	wNAF_len = OPENSSL_malloc(totalnum * sizeof wNAF_len[0]);
-	wNAF = OPENSSL_malloc((totalnum + 1) * sizeof wNAF[0]);
-	if (wNAF != NULL)
+	if (scalar != NULL)
 		{
-		wNAF[0] = NULL; /* preliminary pivot */
+		generator = EC_GROUP_get0_generator(group);
+		if (generator == NULL)
+			{
+			ECerr(EC_F_EC_WNAF_MUL, EC_R_UNDEFINED_GENERATOR);
+			goto err;
+			}
+		
+		/* look if we can use precomputed multiples of generator */
+
+		pre_comp = EC_GROUP_get_extra_data(group, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free);
+
+		if (pre_comp && pre_comp->numblocks && (EC_POINT_cmp(group, generator, pre_comp->points[0], ctx) == 0))
+			{
+			blocksize = pre_comp->blocksize;
+
+			/* determine maximum number of blocks that wNAF splitting may yield
+			 * (NB: maximum wNAF length is bit length plus one) */
+			numblocks = (BN_num_bits(scalar) / blocksize) + 1;
+
+			/* we cannot use more blocks than we have precomputation for */
+			if (numblocks > pre_comp->numblocks)
+				numblocks = pre_comp->numblocks;
+
+			pre_points_per_block = 1u << (pre_comp->w - 1);
+
+			/* check that pre_comp looks sane */
+			if (pre_comp->num != (pre_comp->numblocks * pre_points_per_block))
+				{
+				ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
+				goto err;
+				}
+			}
+		else
+			{
+			/* can't use precomputation */
+			pre_comp = NULL;
+			numblocks = 1;
+			num_scalar = 1; /* treat 'scalar' like 'num'-th element of 'scalars' */
+			}
 		}
-	if (wsize == NULL || wNAF_len == NULL || wNAF == NULL) goto err;
+	
+	totalnum = num + numblocks;
+
+	wsize    = OPENSSL_malloc(totalnum * sizeof wsize[0]);
+	wNAF_len = OPENSSL_malloc(totalnum * sizeof wNAF_len[0]);
+	wNAF     = OPENSSL_malloc((totalnum + 1) * sizeof wNAF[0]); /* includes space for pivot */
+	val_sub  = OPENSSL_malloc(totalnum * sizeof val_sub[0]);
+		 
+	if (!wsize || !wNAF_len || !wNAF || !val_sub)
+		goto err;
 
-	/* num_val := total number of points to precompute */
+	wNAF[0] = NULL;	/* preliminary pivot */
+
+	/* num_val will be the total number of temporarily precomputed points */
 	num_val = 0;
-	for (i = 0; i < totalnum; i++)
+
+	for (i = 0; i < num + num_scalar; i++)
 		{
 		size_t bits;
 
 		bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar);
 		wsize[i] = EC_window_bits_for_scalar_size(bits);
 		num_val += 1u << (wsize[i] - 1);
+		wNAF[i + 1] = NULL; /* make sure we always have a pivot */
+		wNAF[i] = compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], &wNAF_len[i]);
+		if (wNAF[i] == NULL)
+			goto err;
+		if (wNAF_len[i] > max_len)
+			max_len = wNAF_len[i];
 		}
 
-	/* all precomputed points go into a single array 'val',
-	 * 'val_sub[i]' is a pointer to the subarray for the i-th point */
+	if (numblocks)
+		{
+		/* we go here iff scalar != NULL */
+		
+		if (pre_comp == NULL)
+			{
+			if (num_scalar != 1)
+				{
+				ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
+				goto err;
+				}
+			/* we have already generated a wNAF for 'scalar' */
+			}
+		else
+			{
+			signed char *tmp_wNAF = NULL;
+			size_t tmp_len = 0;
+			
+			if (num_scalar != 0)
+				{
+				ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
+				goto err;
+				}
+
+			/* use the window size for which we have precomputation */
+			wsize[num] = pre_comp->w;
+			tmp_wNAF = compute_wNAF(scalar, wsize[num], &tmp_len);
+			if (!tmp_wNAF)
+				goto err;
+
+			if (tmp_len <= max_len)
+				{
+				/* 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;
+				totalnum = num + 1; /* don't use wNAF splitting */
+				wNAF[num] = tmp_wNAF;
+				wNAF[num + 1] = NULL;
+				wNAF_len[num] = tmp_len;
+				if (tmp_len > max_len)
+					max_len = tmp_len;
+				/* pre_comp->points starts with the points that we need here: */
+				val_sub[num] = pre_comp->points;
+				}
+			else
+				{
+				/* don't include tmp_wNAF directly into wNAF array
+				 * - use wNAF splitting and include the blocks */
+
+				signed char *pp;
+				EC_POINT **tmp_points;
+				
+				if (tmp_len < numblocks * blocksize)
+					{
+					/* possibly we can do with fewer blocks than estimated */
+					numblocks = (tmp_len + blocksize - 1) / blocksize;
+					if (numblocks > pre_comp->numblocks)
+						{
+						ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
+						goto err;
+						}
+					totalnum = num + numblocks;
+					}
+				
+				/* split wNAF in 'numblocks' parts */
+				pp = tmp_wNAF;
+				tmp_points = pre_comp->points;
+
+				for (i = num; i < totalnum; i++)
+					{
+					if (i < totalnum - 1)
+						{
+						wNAF_len[i] = blocksize;
+						if (tmp_len < blocksize)
+							{
+							ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
+							goto err;
+							}
+						tmp_len -= blocksize;
+						}
+					else
+						/* last block gets whatever is left
+						 * (this could be more or less than 'blocksize'!) */
+						wNAF_len[i] = tmp_len;
+					
+					wNAF[i + 1] = NULL;
+					wNAF[i] = OPENSSL_malloc(wNAF_len[i]);
+					if (wNAF[i] == NULL)
+						{
+						OPENSSL_free(tmp_wNAF);
+						goto err;
+						}
+					memcpy(wNAF[i], pp, wNAF_len[i]);
+					if (wNAF_len[i] > max_len)
+						max_len = wNAF_len[i];
+
+					if (*tmp_points == NULL)
+						{
+						ECerr(EC_F_EC_WNAF_MUL, ERR_R_INTERNAL_ERROR);
+						OPENSSL_free(tmp_wNAF);
+						goto err;
+						}
+					val_sub[i] = tmp_points;
+					tmp_points += pre_points_per_block;
+					pp += blocksize;
+					}
+				OPENSSL_free(tmp_wNAF);
+				}
+			}
+		}
+
+	/* 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. */
 	val = OPENSSL_malloc((num_val + 1) * sizeof val[0]);
 	if (val == NULL) goto err;
 	val[num_val] = NULL; /* pivot element */
 
-	val_sub = OPENSSL_malloc(totalnum * sizeof val_sub[0]);
-	if (val_sub == NULL) goto err;
-
 	/* allocate points for precomputation */
 	v = val;
-	for (i = 0; i < totalnum; i++)
+	for (i = 0; i < num + num_scalar; i++)
 		{
 		val_sub[i] = v;
 		for (j = 0; j < (1u << (wsize[i] - 1)); j++)
@@ -306,15 +604,8 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 		goto err;
 		}
 
-	if (ctx == NULL)
-		{
-		ctx = new_ctx = BN_CTX_new();
-		if (ctx == NULL)
-			goto err;
-		}
-	
-	tmp = EC_POINT_new(group);
-	if (tmp == NULL) goto err;
+	if (!(tmp = EC_POINT_new(group)))
+		goto err;
 
 	/* prepare precomputed values:
 	 *    val_sub[i][0] :=     points[i]
@@ -322,7 +613,7 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 	 *    val_sub[i][2] := 5 * points[i]
 	 *    ...
 	 */
-	for (i = 0; i < totalnum; i++)
+	for (i = 0; i < num + num_scalar; i++)
 		{
 		if (i < num)
 			{
@@ -341,16 +632,11 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 				if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) goto err;
 				}
 			}
-
-		wNAF[i + 1] = NULL; /* make sure we always have a pivot */
-		wNAF[i] = compute_wNAF((i < num ? scalars[i] : scalar), wsize[i], &wNAF_len[i]);
-		if (wNAF[i] == NULL) goto err;
-		if (wNAF_len[i] > max_len)
-			max_len = wNAF_len[i];
 		}
 
 #if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */
-	if (!EC_POINTs_make_affine(group, num_val, val, ctx)) goto err;
+	if (!EC_POINTs_make_affine(group, num_val, val, ctx))
+		goto err;
 #endif
 
 	r_is_at_infinity = 1;
@@ -446,86 +732,203 @@ int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
 	}
 
 
-/* Generic multiplication method.
- * If group->meth does not provide a multiplication method, default to ec_wNAF_mul;
- * otherwise use the group->meth's multiplication.
+/* 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_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
-	size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
-	{
-	if (group->meth->mul == 0)
-		return ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
-	else
-		return group->meth->mul(group, r, scalar, num, points, scalars, ctx);
-	}
-
-
-int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar, const EC_POINT *point, const BIGNUM *p_scalar, BN_CTX *ctx)
-	{
-	const EC_POINT *points[1];
-	const BIGNUM *scalars[1];
-
-	points[0] = point;
-	scalars[0] = p_scalar;
-
-	return EC_POINTs_mul(group, r, g_scalar, (point != NULL && p_scalar != NULL), points, scalars, ctx);
-	}
-
-
 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, *new_pre_comp = NULL;
 	int ret = 0;
 
+	pre_comp = EC_GROUP_get_extra_data(group, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free);
+	if (pre_comp == NULL)
+		if ((pre_comp = new_pre_comp = ec_pre_comp_new(group)) == NULL)
+			return 0;
+
+CRYPTO_push_info("ec_wNAF_precompute_mult");
+
 	generator = EC_GROUP_get0_generator(group);
 	if (generator == NULL)
 		{
 		ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR);
-		return 0;
+		goto err;
 		}
 
 	if (ctx == NULL)
 		{
 		ctx = new_ctx = BN_CTX_new();
 		if (ctx == NULL)
-			return 0;
+			goto err;
 		}
 	
 	BN_CTX_start(ctx);
 	order = BN_CTX_get(ctx);
 	if (order == NULL) goto err;
 	
-	if (!EC_GROUP_get_order(group, order, ctx)) return 0;
+	if (!EC_GROUP_get_order(group, order, ctx)) goto err;		
 	if (BN_is_zero(order))
 		{
 		ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER);
 		goto err;
 		}
 
-	/* TODO */
+	bits = BN_num_bits(order);
+	blocksize = 8;
+	w = 4;
+	if (EC_window_bits_for_scalar_size(bits) > w)
+		{
+		/* let's not make the window too small ... */
+		w = EC_window_bits_for_scalar_size(bits);
+		}
+
+	numblocks = (bits + blocksize - 1) / blocksize; /* max. number of blocks to use for wNAF splitting */
+	
+	pre_points_per_block = 1u << (w - 1);
+	num = pre_points_per_block * numblocks; /* number of points to compute and store */
+
+	points = OPENSSL_malloc(sizeof (EC_POINT*)*(num + 1));
+	if (!points)
+		{
+		ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
+		goto err;
+		}
+
+	var = points;
+	var[num] = NULL; /* pivot */
+	for (i = 0; i < num; i++)
+		{
+		if ((var[i] = EC_POINT_new(group)) == NULL)
+			{
+			ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
+			goto err;
+			}
+		}
 
-	ret = 1;
+	if (!(tmp_point = EC_POINT_new(group)) || !(base = EC_POINT_new(group)))
+		{
+		ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_MALLOC_FAILURE);
+		goto err;
+		}	
+	
+	if (!EC_POINT_copy(base, generator))
+		goto err;
+	
+	/* do the precomputation */
+	for (i = 0; i < numblocks; i++)
+		{
+		size_t j;
+
+		if (!EC_POINT_dbl(group, tmp_point, base, ctx))
+			goto err;
+
+		if (!EC_POINT_copy(*var++, base))
+			goto err;
+
+		for (j = 1; j < pre_points_per_block; j++, var++)
+			{
+			/* calculate odd multiples of the current base point */
+			if (!EC_POINT_add(group, *var, tmp_point, *(var - 1), ctx))
+				goto err;
+			}
+
+		if (i < numblocks - 1)
+			{
+			/* get the next base (multiply current one by 2^blocksize) */
+			size_t k;
+
+			if (blocksize <= 2)
+				{
+				ECerr(EC_F_EC_WNAF_PRECOMPUTE_MULT, ERR_R_INTERNAL_ERROR);
+				goto err;
+				}				
+
+			if (!EC_POINT_dbl(group, base, tmp_point, ctx))
+				goto err;
+			for (k = 2; k < blocksize; k++)
+				{
+				if (!EC_POINT_dbl(group,base,base,ctx))
+					goto err;
+				}
+			}
+ 		}
+
+	if (!EC_POINTs_make_affine(group, num, points, ctx))
+		goto err;
 	
+	pre_comp->group = group;
+	pre_comp->blocksize = blocksize;
+	pre_comp->numblocks = numblocks;
+	pre_comp->w = w;
+	if (pre_comp->points)
+		{
+		EC_POINT **p;
+
+		for (p = pre_comp->points; *p != NULL; p++)
+			EC_POINT_free(*p);
+		OPENSSL_free(pre_comp->points);
+		}
+	pre_comp->points = points;
+	points = NULL;
+	pre_comp->num = num;
+
+	if (new_pre_comp)
+		{
+		if (!EC_GROUP_set_extra_data(group, new_pre_comp, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free))
+			goto err;
+		new_pre_comp = NULL;
+		}
+
+	ret = 1;
  err:
+	CRYPTO_pop_info();
+
 	BN_CTX_end(ctx);
 	if (new_ctx != NULL)
 		BN_CTX_free(new_ctx);
+	if (new_pre_comp)
+		ec_pre_comp_free(new_pre_comp);
+	if (points)
+		{
+		EC_POINT **p;
+
+		for (p = points; *p != NULL; p++)
+			EC_POINT_free(*p);
+		OPENSSL_free(points);
+		}
+	if (tmp_point)
+		EC_POINT_free(tmp_point);
+	if (base)
+		EC_POINT_free(base);
 	return ret;
 	}
 
 
-/* Generic multiplicaiton precomputation method.
- * If group->meth does not provide a multiplication method, default to ec_wNAF_mul and do its
- * precomputation; otherwise use the group->meth's precomputation if it exists.
- */
-int EC_GROUP_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
+int ec_wNAF_have_precompute_mult(const EC_GROUP *group)
 	{
-	if (group->meth->mul == 0)
-		return ec_wNAF_precompute_mult(group, ctx);
-	else if (group->meth->precompute_mult != 0)
-		return group->meth->precompute_mult(group, ctx);
-	else
+	if (EC_GROUP_get_extra_data(group, ec_pre_comp_dup, ec_pre_comp_free, ec_pre_comp_clear_free) != NULL)
 		return 1;
+	else
+		return 0;
 	}
diff --git a/crypto/ec/ecp_mont.c b/crypto/ec/ecp_mont.c
index 36f8236..b64fa68 100644
--- a/crypto/ec/ecp_mont.c
+++ b/crypto/ec/ecp_mont.c
@@ -93,13 +93,14 @@ const EC_METHOD *EC_GFp_mont_method(void)
 		ec_GFp_simple_add,
 		ec_GFp_simple_dbl,
 		ec_GFp_simple_invert,
-		0 /* mul */,
-		0 /* precompute_mult */,
 		ec_GFp_simple_is_at_infinity,
 		ec_GFp_simple_is_on_curve,
 		ec_GFp_simple_cmp,
 		ec_GFp_simple_make_affine,
 		ec_GFp_simple_points_make_affine,
+		0 /* mul */,
+		0 /* precompute_mult */,
+		0 /* have_precompute_mult */,	
 		ec_GFp_mont_field_mul,
 		ec_GFp_mont_field_sqr,
 		0 /* field_div */,
diff --git a/crypto/ec/ecp_nist.c b/crypto/ec/ecp_nist.c
index ba5d180..c28b275 100644
--- a/crypto/ec/ecp_nist.c
+++ b/crypto/ec/ecp_nist.c
@@ -92,13 +92,14 @@ const EC_METHOD *EC_GFp_nist_method(void)
 		ec_GFp_simple_add,
 		ec_GFp_simple_dbl,
 		ec_GFp_simple_invert,
-		0 /* mul */,
-		0 /* precompute_mult */,
 		ec_GFp_simple_is_at_infinity,
 		ec_GFp_simple_is_on_curve,
 		ec_GFp_simple_cmp,
 		ec_GFp_simple_make_affine,
 		ec_GFp_simple_points_make_affine,
+		0 /* mul */,
+		0 /* precompute_mult */,
+		0 /* have_precompute_mult */,	
 		ec_GFp_nist_field_mul,
 		ec_GFp_nist_field_sqr,
 		0 /* field_div */,
diff --git a/crypto/ec/ecp_recp.c b/crypto/ec/ecp_recp.c
index bf456db..e0b28c1 100644
--- a/crypto/ec/ecp_recp.c
+++ b/crypto/ec/ecp_recp.c
@@ -91,13 +91,14 @@ const EC_METHOD *EC_GFp_recp_method(void)
 		ec_GFp_simple_add,
 		ec_GFp_simple_dbl,
 		ec_GFp_simple_invert,
-		0 /* mul */,
-		0 /* precompute_mult */,
 		ec_GFp_simple_is_at_infinity,
 		ec_GFp_simple_is_on_curve,
 		ec_GFp_simple_cmp,
 		ec_GFp_simple_make_affine,
 		ec_GFp_simple_points_make_affine,
+		0 /* mul */,
+		0 /* precompute_mult */,
+		0 /* have_precompute_mult */,	
 		ec_GFp_recp_field_mul,
 		ec_GFp_recp_field_sqr,
 		0 /* field_div */,
diff --git a/crypto/ec/ecp_smpl.c b/crypto/ec/ecp_smpl.c
index 267134a..1abe831 100644
--- a/crypto/ec/ecp_smpl.c
+++ b/crypto/ec/ecp_smpl.c
@@ -94,13 +94,14 @@ const EC_METHOD *EC_GFp_simple_method(void)
 		ec_GFp_simple_add,
 		ec_GFp_simple_dbl,
 		ec_GFp_simple_invert,
-		0 /* mul */,
-		0 /* precompute_mult */,
 		ec_GFp_simple_is_at_infinity,
 		ec_GFp_simple_is_on_curve,
 		ec_GFp_simple_cmp,
 		ec_GFp_simple_make_affine,
 		ec_GFp_simple_points_make_affine,
+		0 /* mul */,
+		0 /* precompute_mult */,
+		0 /* have_precompute_mult */,	
 		ec_GFp_simple_field_mul,
 		ec_GFp_simple_field_sqr,
 		0 /* field_div */,
diff --git a/crypto/evp/Makefile.ssl b/crypto/evp/Makefile.ssl
index f6fcb9a..8fd8c71 100644
--- a/crypto/evp/Makefile.ssl
+++ b/crypto/evp/Makefile.ssl
@@ -141,13 +141,18 @@ bio_ok.o: ../../include/openssl/stack.h ../../include/openssl/symhacks.h
 bio_ok.o: ../cryptlib.h bio_ok.c
 c_all.o: ../../e_os.h ../../include/openssl/asn1.h ../../include/openssl/bio.h
 c_all.o: ../../include/openssl/bn.h ../../include/openssl/buffer.h
-c_all.o: ../../include/openssl/crypto.h ../../include/openssl/e_os2.h
+c_all.o: ../../include/openssl/crypto.h ../../include/openssl/dh.h
+c_all.o: ../../include/openssl/dsa.h ../../include/openssl/e_os2.h
+c_all.o: ../../include/openssl/ec.h ../../include/openssl/ecdh.h
+c_all.o: ../../include/openssl/ecdsa.h ../../include/openssl/engine.h
 c_all.o: ../../include/openssl/err.h ../../include/openssl/evp.h
 c_all.o: ../../include/openssl/lhash.h ../../include/openssl/obj_mac.h
 c_all.o: ../../include/openssl/objects.h ../../include/openssl/opensslconf.h
 c_all.o: ../../include/openssl/opensslv.h ../../include/openssl/ossl_typ.h
+c_all.o: ../../include/openssl/rand.h ../../include/openssl/rsa.h
 c_all.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h
-c_all.o: ../../include/openssl/symhacks.h ../cryptlib.h c_all.c
+c_all.o: ../../include/openssl/symhacks.h ../../include/openssl/ui.h
+c_all.o: ../cryptlib.h c_all.c
 c_allc.o: ../../e_os.h ../../include/openssl/asn1.h ../../include/openssl/bio.h
 c_allc.o: ../../include/openssl/bn.h ../../include/openssl/buffer.h
 c_allc.o: ../../include/openssl/crypto.h ../../include/openssl/dh.h