More EC stuff, including EC_POINTs_mul() for simultaneous scalar

multiplication of an arbitrary number of points.

13 files changed, 1059 insertions, 88 deletions

diff --git a/CHANGES b/CHANGES
index f4298c93bc..dc55a7d1fb 100644
--- a/CHANGES
+++ b/CHANGES
@@ -3,6 +3,36 @@
 
  Changes between 0.9.6 and 0.9.7  [xx XXX 2000]
 
+  *) Function EC_POINTs_mul for simultaneous scalar multiplication
+     of an arbitrary number of elliptic curve points.
+     [Bodo Moeller]
+
+  *) First EC_METHODs for curves over GF(p):
+
+     EC_GFp_simple_method() uses the basic BN_mod_mul and BN_mod_sqr
+     operations and provides various method functions that can also
+     operate with faster implementations of modular arithmetic.     
+
+     EC_GFp_mont_method() reuses most functions that are part of
+     EC_GFp_simple_method, but uses Montgomery arithmetic.
+
+     [Bodo Moeller; point addition and point doubling
+     implementation directly derived from source code provided by
+     Lenka Fibikova <fibikova@exp-math.uni-essen.de>]
+
+  *) Framework for elliptic curves (crypto/ec/ec.h, crypto/ec/ec_lcl.h,
+     crypto/ec/ec_lib.c):
+
+     Curves are EC_GROUP objects (with an optional generator) based
+     on EC_METHODs that are built into the library.
+
+     Points are EC_POINT objects based on EC_GROUP objects.
+
+     Most of the framework would be able to handle curves over arbitrary
+     finite fields, but as there are no obvious types for GF(2^n),
+     some functions are limited to GF(p) for now.
+     [Bodo Moeller]
+
   *) Add the -HTTP option to s_server.  It is similar to -WWW, but requires
      that the file contains a complete HTTP response.
      [Richard Levitte]
@@ -27,7 +57,7 @@
      [Jeremy Cooper <jeremy@baymoo.org>]
 
   *) Hide BN_CTX structure details in bn_lcl.h instead of publishing them
-     in <openssl/bn.h>.  Also further increase BN_CTX_NUM to 24.
+     in <openssl/bn.h>.  Also further increase BN_CTX_NUM to 32.
      [Bodo Moeller]
 
   *) Modify EVP_Digest*() routines so they now return values. Although the
diff --git a/crypto/bn/Makefile.ssl b/crypto/bn/Makefile.ssl
index 17a289ab6d..19db2b5275 100644
--- a/crypto/bn/Makefile.ssl
+++ b/crypto/bn/Makefile.ssl
@@ -195,7 +195,7 @@ bn_ctx.o: ../../include/openssl/e_os2.h ../../include/openssl/err.h
 bn_ctx.o: ../../include/openssl/lhash.h ../../include/openssl/opensslconf.h
 bn_ctx.o: ../../include/openssl/opensslv.h ../../include/openssl/safestack.h
 bn_ctx.o: ../../include/openssl/stack.h ../../include/openssl/symhacks.h
-bn_ctx.o: ../cryptlib.h bn_ctx.c
+bn_ctx.o: ../cryptlib.h bn_ctx.c bn_lcl.h
 bn_div.o: ../../e_os.h ../../include/openssl/bio.h ../../include/openssl/bn.h
 bn_div.o: ../../include/openssl/buffer.h ../../include/openssl/crypto.h
 bn_div.o: ../../include/openssl/e_os2.h ../../include/openssl/err.h
diff --git a/crypto/bn/bn_lcl.h b/crypto/bn/bn_lcl.h
index df12a01b7a..73792f1220 100644
--- a/crypto/bn/bn_lcl.h
+++ b/crypto/bn/bn_lcl.h
@@ -120,7 +120,7 @@ extern "C" {
 
 
 /* Used for temp variables */
-#define BN_CTX_NUM	24
+#define BN_CTX_NUM	32
 #define BN_CTX_NUM_POS	12
 struct bignum_ctx
 	{
diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h
index a9f6c16db4..87c1f457c3 100644
--- a/crypto/ec/ec.h
+++ b/crypto/ec/ec.h
@@ -94,38 +94,43 @@ typedef struct ec_point_st EC_POINT;
 /* EC_METHODs for curves over GF(p).
  * EC_GFp_simple_method provides the basis for the optimized methods.
  */
- 
 const EC_METHOD *EC_GFp_simple_method(void);
 const EC_METHOD *EC_GFp_mont_method(void);
-const EC_METHOD *EC_GFp_recp_method(void);
-const EC_METHOD *EC_GFp_nist_method(void);
+const EC_METHOD *EC_GFp_recp_method(void); /* TODO */
+const EC_METHOD *EC_GFp_nist_method(void); /* TODO */
 
 
 EC_GROUP *EC_GROUP_new(const EC_METHOD *);
+void EC_GROUP_free(EC_GROUP *);
+void EC_GROUP_clear_free(EC_GROUP *);
+int EC_GROUP_copy(EC_GROUP *, const EC_GROUP *);
+
+const EC_METHOD *EC_GROUP_method_of(const EC_GROUP *);
+	
+
 /* We don't have types for field specifications and field elements in general.
- * Otherwise we would declare
+ * Otherwise we could declare
  *     int EC_GROUP_set_curve(EC_GROUP *, .....);
  */
-void EC_GROUP_free(EC_GROUP *);
-void EC_GROUP_clear_free(EC_GROUP *);
-int EC_GROUP_copy(EC_GROUP *, const EC_GROUP*);
 int EC_GROUP_set_curve_GFp(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *);
-int EC_GROUP_get_curve_GFp(EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *);
+int EC_GROUP_get_curve_GFp(const EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *);
 
 /* EC_GROUP_new_GFp() calls EC_GROUP_new() and EC_GROUP_set_GFp()
  * after choosing an appropriate EC_METHOD */
 EC_GROUP *EC_GROUP_new_curve_GFp(const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *);
 
 int EC_GROUP_set_generator(EC_GROUP *, const EC_POINT *generator, const BIGNUM *order, const BIGNUM *cofactor);
-EC_POINT *EC_group_get0_generator(EC_GROUP *);
-int EC_GROUP_get_order(EC_GROUP *, BIGNUM *order, BN_CTX *);
-int EC_GROUP_get_cofactor(EC_GROUP *, BIGNUM *cofactor, BN_CTX *);
+EC_POINT *EC_GROUP_get0_generator(const EC_GROUP *);
+int EC_GROUP_get_order(const EC_GROUP *, BIGNUM *order, BN_CTX *);
+int EC_GROUP_get_cofactor(const EC_GROUP *, BIGNUM *cofactor, BN_CTX *);
 
 EC_POINT *EC_POINT_new(const EC_GROUP *);
 void EC_POINT_free(EC_POINT *);
 void EC_POINT_clear_free(EC_POINT *);
 int EC_POINT_copy(EC_POINT *, const EC_POINT *);
  
+const EC_METHOD *EC_POINT_method_of(const EC_POINT *);
+
 int EC_POINT_set_to_infinity(const EC_GROUP *, EC_POINT *);
 int EC_POINT_set_Jprojective_coordinates_GFp(const EC_GROUP *, EC_POINT *,
 	const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *);
@@ -152,10 +157,10 @@ int EC_POINT_is_on_curve(const EC_GROUP *, const EC_POINT *, BN_CTX *);
 int EC_POINT_cmp(const EC_GROUP *, const EC_POINT *a, const EC_POINT *b, BN_CTX *);
 
 int EC_POINT_make_affine(const EC_GROUP *, EC_POINT *, BN_CTX *);
+int EC_POINTs_make_affine(const EC_GROUP *, size_t num, EC_POINT *[], BN_CTX *);
 
 
-
-/* TODO: scalar multiplication */
+int EC_POINTs_mul(const EC_GROUP *, EC_POINT *r, BIGNUM *, size_t num, EC_POINT *[], BIGNUM *[], BN_CTX *);
 
 
 
@@ -177,16 +182,22 @@ void ERR_load_EC_strings(void);
 #define EC_F_EC_GFP_SIMPLE_MAKE_AFFINE			 102
 #define EC_F_EC_GFP_SIMPLE_OCT2POINT			 103
 #define EC_F_EC_GFP_SIMPLE_POINT2OCT			 104
+#define EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE		 137
 #define EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES_GFP 105
 #define EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES_GFP 128
 #define EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP 129
 #define EC_F_EC_GROUP_COPY				 106
+#define EC_F_EC_GROUP_GET0_GENERATOR			 139
+#define EC_F_EC_GROUP_GET_COFACTOR			 140
 #define EC_F_EC_GROUP_GET_CURVE_GFP			 130
 #define EC_F_EC_GROUP_GET_EXTRA_DATA			 107
+#define EC_F_EC_GROUP_GET_ORDER				 141
 #define EC_F_EC_GROUP_NEW				 108
 #define EC_F_EC_GROUP_SET_CURVE_GFP			 109
 #define EC_F_EC_GROUP_SET_EXTRA_DATA			 110
 #define EC_F_EC_GROUP_SET_GENERATOR			 111
+#define EC_F_EC_POINTS_MAKE_AFFINE			 136
+#define EC_F_EC_POINTS_MUL				 138
 #define EC_F_EC_POINT_ADD				 112
 #define EC_F_EC_POINT_CMP				 113
 #define EC_F_EC_POINT_COPY				 114
@@ -208,12 +219,14 @@ void ERR_load_EC_strings(void);
 /* Reason codes. */
 #define EC_R_BUFFER_TOO_SMALL				 100
 #define EC_R_INCOMPATIBLE_OBJECTS			 101
+#define EC_R_INVALID_ARGUMENT				 112
 #define EC_R_INVALID_COMPRESSED_POINT			 110
 #define EC_R_INVALID_COMPRESSION_BIT			 109
 #define EC_R_INVALID_ENCODING				 102
 #define EC_R_INVALID_FIELD				 103
 #define EC_R_INVALID_FORM				 104
 #define EC_R_NOT_INITIALIZED				 111
+#define EC_R_NO_GENERATOR_SET				 113
 #define EC_R_NO_SUCH_EXTRA_DATA				 105
 #define EC_R_POINT_AT_INFINITY				 106
 #define EC_R_POINT_IS_NOT_ON_CURVE			 107
diff --git a/crypto/ec/ec_err.c b/crypto/ec/ec_err.c
index 6fd74640da..7dd1131f63 100644
--- a/crypto/ec/ec_err.c
+++ b/crypto/ec/ec_err.c
@@ -75,16 +75,22 @@ static ERR_STRING_DATA EC_str_functs[]=
 {ERR_PACK(0,EC_F_EC_GFP_SIMPLE_MAKE_AFFINE,0),	"ec_GFp_simple_make_affine"},
 {ERR_PACK(0,EC_F_EC_GFP_SIMPLE_OCT2POINT,0),	"ec_GFp_simple_oct2point"},
 {ERR_PACK(0,EC_F_EC_GFP_SIMPLE_POINT2OCT,0),	"ec_GFp_simple_point2oct"},
+{ERR_PACK(0,EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE,0),	"ec_GFp_simple_points_make_affine"},
 {ERR_PACK(0,EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES_GFP,0),	"ec_GFp_simple_point_get_affine_coordinates_GFp"},
 {ERR_PACK(0,EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES_GFP,0),	"ec_GFp_simple_point_set_affine_coordinates_GFp"},
 {ERR_PACK(0,EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP,0),	"ec_GFp_simple_set_compressed_coordinates_GFp"},
 {ERR_PACK(0,EC_F_EC_GROUP_COPY,0),	"EC_GROUP_copy"},
+{ERR_PACK(0,EC_F_EC_GROUP_GET0_GENERATOR,0),	"EC_GROUP_get0_generator"},
+{ERR_PACK(0,EC_F_EC_GROUP_GET_COFACTOR,0),	"EC_GROUP_get_cofactor"},
 {ERR_PACK(0,EC_F_EC_GROUP_GET_CURVE_GFP,0),	"EC_GROUP_get_curve_GFp"},
 {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_NEW,0),	"EC_GROUP_new"},
 {ERR_PACK(0,EC_F_EC_GROUP_SET_CURVE_GFP,0),	"EC_GROUP_set_curve_GFp"},
 {ERR_PACK(0,EC_F_EC_GROUP_SET_EXTRA_DATA,0),	"EC_GROUP_set_extra_data"},
 {ERR_PACK(0,EC_F_EC_GROUP_SET_GENERATOR,0),	"EC_GROUP_set_generator"},
+{ERR_PACK(0,EC_F_EC_POINTS_MAKE_AFFINE,0),	"EC_POINTs_make_affine"},
+{ERR_PACK(0,EC_F_EC_POINTS_MUL,0),	"EC_POINTs_mul"},
 {ERR_PACK(0,EC_F_EC_POINT_ADD,0),	"EC_POINT_add"},
 {ERR_PACK(0,EC_F_EC_POINT_CMP,0),	"EC_POINT_cmp"},
 {ERR_PACK(0,EC_F_EC_POINT_COPY,0),	"EC_POINT_copy"},
@@ -109,12 +115,14 @@ static ERR_STRING_DATA EC_str_reasons[]=
 	{
 {EC_R_BUFFER_TOO_SMALL                   ,"buffer too small"},
 {EC_R_INCOMPATIBLE_OBJECTS               ,"incompatible objects"},
+{EC_R_INVALID_ARGUMENT                   ,"invalid argument"},
 {EC_R_INVALID_COMPRESSED_POINT           ,"invalid compressed point"},
 {EC_R_INVALID_COMPRESSION_BIT            ,"invalid compression bit"},
 {EC_R_INVALID_ENCODING                   ,"invalid encoding"},
 {EC_R_INVALID_FIELD                      ,"invalid field"},
 {EC_R_INVALID_FORM                       ,"invalid form"},
 {EC_R_NOT_INITIALIZED                    ,"not initialized"},
+{EC_R_NO_GENERATOR_SET                   ,"no generator set"},
 {EC_R_NO_SUCH_EXTRA_DATA                 ,"no such extra data"},
 {EC_R_POINT_AT_INFINITY                  ,"point at infinity"},
 {EC_R_POINT_IS_NOT_ON_CURVE              ,"point is not on curve"},
diff --git a/crypto/ec/ec_lcl.h b/crypto/ec/ec_lcl.h
index 38ce24b06c..cc4cf27755 100644
--- a/crypto/ec/ec_lcl.h
+++ b/crypto/ec/ec_lcl.h
@@ -71,16 +71,16 @@ struct ec_method_st {
 
 	/* used by EC_GROUP_set_curve_GFp and EC_GROUP_get_curve_GFp: */
 	int (*group_set_curve_GFp)(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *);
-	int (*group_get_curve_GFp)(EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *);
+	int (*group_get_curve_GFp)(const EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *);
 
-	/* used by EC_GROUP_set_generator, EC_group_get0_generator,
+	/* used by EC_GROUP_set_generator, EC_GROUP_get0_generator,
 	 * EC_GROUP_get_order, EC_GROUP_get_cofactor:
 	 */
 	int (*group_set_generator)(EC_GROUP *, const EC_POINT *generator,
 	        const BIGNUM *order, const BIGNUM *cofactor);
-	EC_POINT *(*group_get0_generator)(EC_GROUP *);
-	int (*group_get_order)(EC_GROUP *, BIGNUM *order, BN_CTX *);
-	int (*group_get_cofactor)(EC_GROUP *, BIGNUM *cofactor, BN_CTX *);
+	EC_POINT *(*group_get0_generator)(const EC_GROUP *);
+	int (*group_get_order)(const EC_GROUP *, BIGNUM *order, BN_CTX *);
+	int (*group_get_cofactor)(const EC_GROUP *, BIGNUM *cofactor, BN_CTX *);
 
 	/* used by EC_POINT_new, EC_POINT_free, EC_POINT_clear_free, EC_POINT_copy: */
 	int (*point_init)(EC_POINT *);
@@ -121,8 +121,9 @@ struct ec_method_st {
 	int (*is_on_curve)(const EC_GROUP *, const EC_POINT *, BN_CTX *);
 	int (*point_cmp)(const EC_GROUP *, const EC_POINT *a, const EC_POINT *b, BN_CTX *);
 
-	/* used by EC_POINT_make_affine: */
+	/* used by EC_POINT_make_affine, EC_POINTs_make_affine: */
 	int (*make_affine)(const EC_GROUP *, EC_POINT *, BN_CTX *);
+	int (*points_make_affine)(const EC_GROUP *, size_t num, EC_POINT *[], BN_CTX *);
 
 
 	/* internal functions */
@@ -135,6 +136,7 @@ struct ec_method_st {
 
 	int (*field_encode)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); /* e.g. to Montgomery */
 	int (*field_decode)(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *); /* e.g. from Montgomery */
+	int (*field_set_to_one)(const EC_GROUP *, BIGNUM *r, BN_CTX *);
 } /* EC_METHOD */;
 
 
@@ -164,7 +166,8 @@ struct ec_group_st {
 	EC_POINT *generator; /* optional */
 	BIGNUM order, cofactor;
 
-	void *field_data; /* method-specific (e.g., Montgomery structure) */
+	void *field_data1; /* method-specific (e.g., Montgomery structure) */
+	void *field_data2; /* method-specific */
 } /* EC_GROUP */;
 
 
@@ -176,7 +179,7 @@ struct ec_group_st {
  * if necessary.) */
 int EC_GROUP_set_extra_data(EC_GROUP *, void *extra_data, void *(*extra_data_dup_func)(void *),
 	void (*extra_data_free_func)(void *), void (*extra_data_clear_free_func)(void *));
-void *EC_GROUP_get_extra_data(EC_GROUP *, void *(*extra_data_dup_func)(void *),
+void *EC_GROUP_get_extra_data(const EC_GROUP *, void *(*extra_data_dup_func)(void *),
 	void (*extra_data_free_func)(void *), void (*extra_data_clear_free_func)(void *));
 void EC_GROUP_free_extra_data(EC_GROUP *);
 void EC_GROUP_clear_free_extra_data(EC_GROUP *);
@@ -204,12 +207,12 @@ void ec_GFp_simple_group_finish(EC_GROUP *);
 void ec_GFp_simple_group_clear_finish(EC_GROUP *);
 int ec_GFp_simple_group_copy(EC_GROUP *, const EC_GROUP *);
 int ec_GFp_simple_group_set_curve_GFp(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *);
-int ec_GFp_simple_group_get_curve_GFp(EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *);
+int ec_GFp_simple_group_get_curve_GFp(const EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *);
 int ec_GFp_simple_group_set_generator(EC_GROUP *, const EC_POINT *generator,
 	const BIGNUM *order, const BIGNUM *cofactor);
-EC_POINT *ec_GFp_simple_group_get0_generator(EC_GROUP *);
-int ec_GFp_simple_group_get_order(EC_GROUP *, BIGNUM *order, BN_CTX *);
-int ec_GFp_simple_group_get_cofactor(EC_GROUP *, BIGNUM *cofactor, BN_CTX *);
+EC_POINT *ec_GFp_simple_group_get0_generator(const EC_GROUP *);
+int ec_GFp_simple_group_get_order(const EC_GROUP *, BIGNUM *order, BN_CTX *);
+int ec_GFp_simple_group_get_cofactor(const EC_GROUP *, BIGNUM *cofactor, BN_CTX *);
 int ec_GFp_simple_point_init(EC_POINT *);
 void ec_GFp_simple_point_finish(EC_POINT *);
 void ec_GFp_simple_point_clear_finish(EC_POINT *);
@@ -236,6 +239,7 @@ int ec_GFp_simple_is_at_infinity(const EC_GROUP *, const EC_POINT *);
 int ec_GFp_simple_is_on_curve(const EC_GROUP *, const EC_POINT *, BN_CTX *);
 int ec_GFp_simple_cmp(const EC_GROUP *, const EC_POINT *a, const EC_POINT *b, BN_CTX *);
 int ec_GFp_simple_make_affine(const EC_GROUP *, EC_POINT *, BN_CTX *);
+int ec_GFp_simple_points_make_affine(const EC_GROUP *, size_t num, EC_POINT *[], BN_CTX *);
 int ec_GFp_simple_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *);
 int ec_GFp_simple_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *);
 
@@ -250,6 +254,7 @@ int ec_GFp_mont_field_mul(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, const BI
 int ec_GFp_mont_field_sqr(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *);
 int ec_GFp_mont_field_encode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *);
 int ec_GFp_mont_field_decode(const EC_GROUP *, BIGNUM *r, const BIGNUM *a, BN_CTX *);
+int ec_GFp_mont_field_set_to_one(const EC_GROUP *, BIGNUM *r, BN_CTX *);
 
 
 /* method functions in ecp_recp.c */
diff --git a/crypto/ec/ec_lib.c b/crypto/ec/ec_lib.c
index 6aaacb343f..e0d78d67fb 100644
--- a/crypto/ec/ec_lib.c
+++ b/crypto/ec/ec_lib.c
@@ -163,6 +163,12 @@ int EC_GROUP_copy(EC_GROUP *dest, const EC_GROUP *src)
 	}
 
 
+const EC_METHOD *EC_GROUP_method_of(const EC_GROUP *group)
+	{
+	return group->meth;
+	}
+
+
 int EC_GROUP_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 	{
 	if (group->meth->group_set_curve_GFp == 0)
@@ -174,7 +180,7 @@ int EC_GROUP_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a, co
 	}
 
 
-int EC_GROUP_get_curve_GFp(EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
+int EC_GROUP_get_curve_GFp(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
 	{
 	if (group->meth->group_get_curve_GFp == 0)
 		{
@@ -196,6 +202,39 @@ int EC_GROUP_set_generator(EC_GROUP *group, const EC_POINT *generator, const BIG
 	}
 
 
+EC_POINT *EC_GROUP_get0_generator(const EC_GROUP *group)
+	{
+	if (group->meth->group_get0_generator == 0)
+		{
+		ECerr(EC_F_EC_GROUP_GET0_GENERATOR, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+		return 0;
+		}
+	return group->meth->group_get0_generator(group);
+	}
+
+
+int EC_GROUP_get_order(const EC_GROUP *group, BIGNUM *order, BN_CTX *ctx)
+	{
+	if (group->meth->group_get_order == 0)
+		{
+		ECerr(EC_F_EC_GROUP_GET_ORDER, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+		return 0;
+		}
+	return group->meth->group_get_order(group, order, ctx);
+	}
+
+
+int EC_GROUP_get_cofactor(const EC_GROUP *group, BIGNUM *cofactor, BN_CTX *ctx)
+	{
+	if (group->meth->group_get_cofactor == 0)
+		{
+		ECerr(EC_F_EC_GROUP_GET_COFACTOR, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+		return 0;
+		}
+	return group->meth->group_get_cofactor(group, cofactor, ctx);
+	}
+
+
 /* this has 'package' visibility */
 int EC_GROUP_set_extra_data(EC_GROUP *group, void *extra_data, void *(*extra_data_dup_func)(void *),
 	void (*extra_data_free_func)(void *), void (*extra_data_clear_free_func)(void *))
@@ -218,7 +257,7 @@ int EC_GROUP_set_extra_data(EC_GROUP *group, void *extra_data, void *(*extra_dat
 
 
 /* this has 'package' visibility */
-void *EC_GROUP_get_extra_data(EC_GROUP *group, void *(*extra_data_dup_func)(void *),
+void *EC_GROUP_get_extra_data(const EC_GROUP *group, void *(*extra_data_dup_func)(void *),
 	void (*extra_data_free_func)(void *), void (*extra_data_clear_free_func)(void *))
 	{
 	if ((group->extra_data_dup_func != extra_data_dup_func)
@@ -333,6 +372,12 @@ int EC_POINT_copy(EC_POINT *dest, const EC_POINT *src)
 	}
 
 
+const EC_METHOD *EC_POINT_method_of(const EC_POINT *point)
+	{
+	return point->meth;
+	}
+
+
 int EC_POINT_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
 	{
 	if (group->meth->point_set_to_infinity == 0)
@@ -578,3 +623,24 @@ int EC_POINT_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
 		}
 	return group->meth->make_affine(group, point, ctx);
 	}
+
+
+int EC_POINTs_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
+	{
+	size_t i;
+
+	if (group->meth->points_make_affine == 0)
+		{
+		ECerr(EC_F_EC_POINTS_MAKE_AFFINE, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
+		return 0;
+		}
+	for (i = 0; i < num; i++)
+		{
+		if (group->meth != points[i]->meth)
+			{
+			ECerr(EC_F_EC_POINTS_MAKE_AFFINE, EC_R_INCOMPATIBLE_OBJECTS);
+			return 0;
+			}
+		}
+	return group->meth->points_make_affine(group, num, points, ctx);
+	}
diff --git a/crypto/ec/ec_mult.c b/crypto/ec/ec_mult.c
index d43bdc2ba5..0515e728ec 100644
--- a/crypto/ec/ec_mult.c
+++ b/crypto/ec/ec_mult.c
@@ -1,4 +1,3 @@
-/* TODO */
 /* crypto/ec/ec_mult.c */
 /* ====================================================================
  * Copyright (c) 1998-2001 The OpenSSL Project.  All rights reserved.
@@ -54,4 +53,237 @@
  *
  */
 
+#include <openssl/err.h>
+
 #include "ec_lcl.h"
+
+
+/* TODO: width-m NAFs */
+
+/* TODO: optional Lim-Lee precomputation for the generator */
+
+
+/* this is just BN_window_bits_for_exponent_size from bn_lcl.h for now;
+ * the table should be updated for EC */ /* TODO */
+#define EC_window_bits_for_scalar_size(b) \
+		((b) > 671 ? 6 : \
+		 (b) > 239 ? 5 : \
+		 (b) >  79 ? 4 : \
+	 	 (b) >  23 ? 3 : 1)
+
+/* Compute
+ *      \sum scalar[i]*points[i]
+ * where
+ *      scalar*generator
+ * is included in the addition if scalar != NULL
+ */
+int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, BIGNUM *scalar,
+	size_t num, EC_POINT *points[], BIGNUM *scalars[], BN_CTX *ctx)
+	{
+	BN_CTX *new_ctx = NULL;
+	EC_POINT *generator = NULL;
+	EC_POINT *tmp = NULL;
+	size_t totalnum;
+	size_t i, j;
+	int k, t;
+	int r_is_at_infinity = 1;
+	size_t max_bits = 0;
+	size_t *wsize = NULL; /* individual window sizes */
+	unsigned long *wbits = NULL; /* individual window contents */
+	int *wpos = NULL; /* position of bottom bit of current individual windows
+	                   * (wpos[i] is valid if wbits[i] != 0) */
+	size_t num_val;
+	EC_POINT **val = NULL; /* precomputation */
+	EC_POINT **v;
+	EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' */
+	int ret = 0;
+	
+	if (scalar != NULL)
+		{
+		generator = EC_GROUP_get0_generator(group);
+		if (generator == NULL)
+			{
+			ECerr(EC_F_EC_POINTS_MUL, EC_R_NO_GENERATOR_SET);
+			return 0;
+			}
+		}
+	
+	for (i = 0; i < num; i++)
+		{
+		if (group->meth != points[i]->meth)
+			{
+			ECerr(EC_F_EC_POINTS_MUL, EC_R_INCOMPATIBLE_OBJECTS);
+			return 0;
+			}
+		}
+
+	totalnum = num + (scalar != NULL);
+
+	wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]);
+	wbits = OPENSSL_malloc(totalnum * sizeof wbits[0]);
+	wpos = OPENSSL_malloc(totalnum * sizeof wpos[0]);
+	if (wsize == NULL || wbits == NULL || wpos == NULL) goto err;
+
+	/* num_val := total number of points to precompute */
+	num_val = 0;
+	for (i = 0; i < totalnum; 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 += 1 << (wsize[i] - 1);
+		if (bits > max_bits)
+			max_bits = bits;
+		wbits[i] = 0;
+		wpos[i] = 0;
+		}
+
+	/* all precomputed points go into a single array 'val',
+	 * 'val_sub[i]' is a pointer to the subarray for the i-th point */
+	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++)
+		{
+		val_sub[i] = v;
+		for (j = 0; j < (1 << (wsize[i] - 1)); j++)
+			{
+			*v = EC_POINT_new(group);
+			if (*v == NULL) goto err;
+			v++;
+			}
+		}
+	if (!(v == val + num_val))
+		{
+		ECerr(EC_F_EC_POINTS_MUL, ERR_R_INTERNAL_ERROR);
+		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;
+
+	/* prepare precomputed values:
+	 *    val_sub[i][0] :=     points[i]
+	 *    val_sub[i][1] := 3 * points[i]
+	 *    val_sub[i][2] := 5 * points[i]
+	 *    ...
+	 */
+	for (i = 0; i < totalnum; i++)
+		{
+		if (i < num)
+			{
+			if (!EC_POINT_copy(val_sub[i][0], points[i])) goto err;
+			}
+		else
+			{
+			if (!EC_POINT_copy(val_sub[i][0], generator)) goto err;
+			}
+
+		if (wsize[i] > 1)
+			{
+			if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) goto err;
+			for (j = 1; j < (1 << (wsize[i] - 1)); j++)
+				{
+				if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) goto err;
+				}
+			}
+		}
+
+#if 1 /* optional, maybe we should only do this if total_num > 1 */
+	if (!EC_POINTs_make_affine(group, num_val, val, ctx)) goto err;
+#endif
+
+	r_is_at_infinity = 1;
+
+	for (k = max_bits - 1; k >= 0; k--)
+		{
+		if (!r_is_at_infinity)
+			{
+			if (!EC_POINT_dbl(group, r, r, ctx)) goto err;
+			}
+		
+		for (i = 0; i < totalnum; i++)
+			{
+			if (wbits[i] == 0)
+				{
+				BIGNUM *s;
+
+				s = i < num ? scalars[i] : scalar;
+
+				if (BN_is_bit_set(s, k))
+					{
+					/* look at bits  k - wsize[i] + 1 .. k  for this window */
+					t = k - wsize[i] + 1;
+					while (!BN_is_bit_set(s, t)) /* BN_is_bit_set is false for t < 0 */
+						t++;
+					wpos[i] = t;
+					wbits[i] = 1;
+					for (t = k - 1; t >= wpos[i]; t--)
+						{
+						wbits[i] <<= 1;
+						if (BN_is_bit_set(s, t))
+							wbits[i]++;
+						}
+					/* now wbits[i] is the odd bit pattern at bits wpos[i] .. k */
+					}
+				}
+			
+			if ((wbits[i] != 0) && (wpos[i] == k))
+				{
+				if (r_is_at_infinity)
+					{
+					if (!EC_POINT_copy(r, val_sub[i][wbits[i] >> 1])) goto err;
+					r_is_at_infinity = 0;
+					}
+				else
+					{
+					if (!EC_POINT_add(group, r, r, val_sub[i][wbits[i] >> 1], ctx)) goto err;
+					}
+				wbits[i] = 0;
+				}
+			}
+		}
+
+	if (r_is_at_infinity)
+		if (!EC_POINT_set_to_infinity(group, r)) goto err;
+	
+	ret = 1;
+
+ err:
+	if (new_ctx != NULL)
+		BN_CTX_free(new_ctx);
+	if (tmp != NULL)
+		EC_POINT_free(tmp);
+	if (wsize != NULL)
+		OPENSSL_free(wsize);
+	if (wbits != NULL)
+		OPENSSL_free(wbits);
+	if (wpos != NULL)
+		OPENSSL_free(wpos);
+	if (val != NULL)
+		{
+		for (v = val; *v != NULL; v++)
+			EC_POINT_clear_free(*v);
+
+		OPENSSL_free(val);
+		}
+	if (val_sub != NULL)
+		{
+		OPENSSL_free(val_sub);
+		}
+	return ret;
+	}
diff --git a/crypto/ec/ecp_mont.c b/crypto/ec/ecp_mont.c
index 8ba2227404..7b30d4c38a 100644
--- a/crypto/ec/ecp_mont.c
+++ b/crypto/ec/ecp_mont.c
@@ -90,10 +90,12 @@ const EC_METHOD *EC_GFp_mont_method(void)
 		ec_GFp_simple_is_on_curve,
 		ec_GFp_simple_cmp,
 		ec_GFp_simple_make_affine,
+		ec_GFp_simple_points_make_affine,
 		ec_GFp_mont_field_mul,
 		ec_GFp_mont_field_sqr,
 		ec_GFp_mont_field_encode,
-		ec_GFp_mont_field_decode };
+		ec_GFp_mont_field_decode,
+		ec_GFp_mont_field_set_to_one };
 
 	return &ret;
 	}
@@ -104,7 +106,8 @@ int ec_GFp_mont_group_init(EC_GROUP *group)
 	int ok;
 
 	ok = ec_GFp_simple_group_init(group);
-	group->field_data = NULL;
+	group->field_data1 = NULL;
+	group->field_data2 = NULL;
 	return ok;
 	}
 
@@ -113,12 +116,18 @@ int ec_GFp_mont_group_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGN
 	{
 	BN_CTX *new_ctx = NULL;
 	BN_MONT_CTX *mont = NULL;
+	BIGNUM *one = NULL;
 	int ret = 0;
 
-	if (group->field_data != NULL)
+	if (group->field_data1 != NULL)
 		{
-		BN_MONT_CTX_free(group->field_data);
-		group->field_data = NULL;
+		BN_MONT_CTX_free(group->field_data1);
+		group->field_data1 = NULL;
+		}
+	if (group->field_data2 != NULL)
+		{
+		BN_free(group->field_data2);
+		group->field_data2 = NULL;
 		}
 	
 	if (ctx == NULL)
@@ -135,16 +144,23 @@ int ec_GFp_mont_group_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGN
 		ECerr(EC_F_GFP_MONT_GROUP_SET_CURVE_GFP, ERR_R_BN_LIB);
 		goto err;
 		}
+	one = BN_new();
+	if (one == NULL) goto err;
+	if (!BN_to_montgomery(one, BN_value_one(), mont, ctx)) goto err;
 
-	group->field_data = mont;
+	group->field_data1 = mont;
 	mont = NULL;
-	
+	group->field_data2 = one;
+	one = NULL;
+
 	ret = ec_GFp_simple_group_set_curve_GFp(group, p, a, b, ctx);
 
 	if (!ret)
 		{
-		BN_MONT_CTX_free(group->field_data);
-		group->field_data = NULL;
+		BN_MONT_CTX_free(group->field_data1);
+		group->field_data1 = NULL;
+		BN_free(group->field_data2);
+		group->field_data2 = NULL;
 		}
 
  err:
@@ -158,10 +174,15 @@ int ec_GFp_mont_group_set_curve_GFp(EC_GROUP *group, const BIGNUM *p, const BIGN
 
 void ec_GFp_mont_group_finish(EC_GROUP *group)
 	{
-	if (group->field_data != NULL)
+	if (group->field_data1 != NULL)
 		{
-		BN_MONT_CTX_free(group->field_data);
-		group->field_data = NULL;
+		BN_MONT_CTX_free(group->field_data1);
+		group->field_data1 = NULL;
+		}
+	if (group->field_data2 != NULL)
+		{
+		BN_free(group->field_data2);
+		group->field_data2 = NULL;
 		}
 	ec_GFp_simple_group_finish(group);
 	}
@@ -169,10 +190,15 @@ void ec_GFp_mont_group_finish(EC_GROUP *group)
 
 void ec_GFp_mont_group_clear_finish(EC_GROUP *group)
 	{
-	if (group->field_data != NULL)
+	if (group->field_data1 != NULL)
+		{
+		BN_MONT_CTX_free(group->field_data1);
+		group->field_data1 = NULL;
+		}
+	if (group->field_data2 != NULL)
 		{
-		BN_MONT_CTX_free(group->field_data);
-		group->field_data = NULL;
+		BN_clear_free(group->field_data2);
+		group->field_data2 = NULL;
 		}
 	ec_GFp_simple_group_clear_finish(group);
 	}
@@ -180,70 +206,99 @@ void ec_GFp_mont_group_clear_finish(EC_GROUP *group)
 
 int ec_GFp_mont_group_copy(EC_GROUP *dest, const EC_GROUP *src)
 	{
-	if (dest->field_data != NULL)
+	if (dest->field_data1 != NULL)
+		{
+		BN_MONT_CTX_free(dest->field_data1);
+		dest->field_data1 = NULL;
+		}
+	if (dest->field_data2 != NULL)
 		{
-		BN_MONT_CTX_free(dest->field_data);
-		dest->field_data = NULL;
+		BN_clear_free(dest->field_data2);
+		dest->field_data2 = NULL;
 		}
 
 	if (!ec_GFp_simple_group_copy(dest, src)) return 0;
 
-	dest->field_data = BN_MONT_CTX_new();
-	if (dest->field_data == NULL) return 0;
-	if (!BN_MONT_CTX_copy(dest->field_data, src->field_data))
+	if (src->field_data1 != NULL)
 		{
-		BN_MONT_CTX_free(dest->field_data);
-		dest->field_data = NULL;
-		return 0;
+		dest->field_data1 = BN_MONT_CTX_new();
+		if (dest->field_data1 == NULL) return 0;
+		if (!BN_MONT_CTX_copy(dest->field_data1, src->field_data1)) goto err;
+		}
+	if (src->field_data2 != NULL)
+		{
+		dest->field_data2 = BN_dup(src->field_data2);
+		if (dest->field_data2 == NULL) goto err;
 		}
 
 	return 1;
+
+ err:
+	if (dest->field_data1 != NULL)
+		{
+		BN_MONT_CTX_free(dest->field_data1);
+		dest->field_data1 = NULL;
+		}
+	return 0;	
 	}
 
 
 int ec_GFp_mont_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
 	{
-	if (group->field_data == NULL)
+	if (group->field_data1 == NULL)
 		{
 		ECerr(EC_F_EC_GFP_MONT_FIELD_MUL, EC_R_NOT_INITIALIZED);
 		return 0;
 		}
 
-	return BN_mod_mul_montgomery(r, a, b, group->field_data, ctx);
+	return BN_mod_mul_montgomery(r, a, b, group->field_data1, ctx);
 	}
 
 
 int ec_GFp_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
 	{
-	if (group->field_data == NULL)
+	if (group->field_data1 == NULL)
 		{
 		ECerr(EC_F_EC_GFP_MONT_FIELD_SQR, EC_R_NOT_INITIALIZED);
 		return 0;
 		}
 
-	return BN_mod_mul_montgomery(r, a, a, group->field_data, ctx);
+	return BN_mod_mul_montgomery(r, a, a, group->field_data1, ctx);
 	}
 
 
 int ec_GFp_mont_field_encode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
 	{
-	if (group->field_data == NULL)
+	if (group->field_data1 == NULL)
 		{
 		ECerr(EC_F_EC_GFP_MONT_FIELD_ENCODE, EC_R_NOT_INITIALIZED);
 		return 0;
 		}
 
-	return BN_to_montgomery(r, a, (BN_MONT_CTX *)group->field_data, ctx);
+	return BN_to_montgomery(r, a, (BN_MONT_CTX *)group->field_data1, ctx);
 	}
 
 
 int ec_GFp_mont_field_decode(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
 	{
-	if (group->field_data == NULL)
+	if (group->field_data1 == NULL)
 		{
 		ECerr(EC_F_EC_GFP_MONT_FIELD_DECODE, EC_R_NO