add support for elliptic curves over binary fields

Submitted by: Duglas Stebila <douglas.stebila@sun.com>,
              Sheueling Chang <sheueling.chang@sun.com>

(CHANGES entries by Bodo Moeller)

16 files changed, 3194 insertions, 119 deletions

diff --git a/crypto/ec/Makefile.ssl b/crypto/ec/Makefile.ssl
index cf6059d76a..8591ef14e0 100644
--- a/crypto/ec/Makefile.ssl
+++ b/crypto/ec/Makefile.ssl
@@ -24,10 +24,10 @@ APPS=
 
 LIB=$(TOP)/libcrypto.a
 LIBSRC=	ec_lib.c ecp_smpl.c ecp_mont.c ecp_recp.c ecp_nist.c ec_cvt.c ec_mult.c \
-	ec_err.c ec_curve.c ec_check.c ec_print.c ec_asn1.c
+	ec_err.c ec_curve.c ec_check.c ec_print.c ec_asn1.c ec2_smpl.c ec2_mult.c
 
 LIBOBJ=	ec_lib.o ecp_smpl.o ecp_mont.o ecp_recp.o ecp_nist.o ec_cvt.o ec_mult.o \
-	ec_err.o ec_curve.o ec_check.o ec_print.o ec_asn1.o
+	ec_err.o ec_curve.o ec_check.o ec_print.o ec_asn1.o ec2_smpl.o ec2_mult.o
 
 SRC= $(LIBSRC)
 
@@ -176,3 +176,17 @@ ecp_smpl.o: ../../include/openssl/obj_mac.h ../../include/openssl/opensslconf.h
 ecp_smpl.o: ../../include/openssl/opensslv.h ../../include/openssl/ossl_typ.h
 ecp_smpl.o: ../../include/openssl/safestack.h ../../include/openssl/stack.h
 ecp_smpl.o: ../../include/openssl/symhacks.h ec_lcl.h ecp_smpl.c
+ec2_smpl.o: ../../include/openssl/bio.h ../../include/openssl/bn.h
+ec2_smpl.o: ../../include/openssl/crypto.h ../../include/openssl/e_os2.h
+ec2_smpl.o: ../../include/openssl/ec.h ../../include/openssl/err.h
+ec2_smpl.o: ../../include/openssl/lhash.h ../../include/openssl/opensslconf.h
+ec2_smpl.o: ../../include/openssl/opensslv.h ../../include/openssl/safestack.h
+ec2_smpl.o: ../../include/openssl/stack.h ../../include/openssl/symhacks.h
+ec2_smpl.o: ec_lcl.h ec2_smpl.c ec2_smpt.c
+ec2_mult.o: ../../include/openssl/bio.h ../../include/openssl/bn.h
+ec2_mult.o: ../../include/openssl/crypto.h ../../include/openssl/e_os2.h
+ec2_mult.o: ../../include/openssl/ec.h ../../include/openssl/err.h
+ec2_mult.o: ../../include/openssl/lhash.h ../../include/openssl/opensslconf.h
+ec2_mult.o: ../../include/openssl/opensslv.h ../../include/openssl/safestack.h
+ec2_mult.o: ../../include/openssl/stack.h ../../include/openssl/symhacks.h
+ec2_mult.o: ec_lcl.h ec2_mult.c
diff --git a/crypto/ec/ec.h b/crypto/ec/ec.h
index 55f9cabd03..16ebeb37d4 100644
--- a/crypto/ec/ec.h
+++ b/crypto/ec/ec.h
@@ -52,6 +52,32 @@
  * Hudson (tjh@cryptsoft.com).
  *
  */
+/* ====================================================================
+ * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
+ *
+ * Portions of the attached software ("Contribution") are developed by 
+ * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
+ *
+ * The Contribution is licensed pursuant to the OpenSSL open source
+ * license provided above.
+ *
+ * In addition, Sun covenants to all licensees who provide a reciprocal
+ * covenant with respect to their own patents if any, not to sue under
+ * current and future patent claims necessarily infringed by the making,
+ * using, practicing, selling, offering for sale and/or otherwise
+ * disposing of the Contribution as delivered hereunder 
+ * (or portions thereof), provided that such covenant shall not apply:
+ *  1) for code that a licensee deletes from the Contribution;
+ *  2) separates from the Contribution; or
+ *  3) for infringements caused by:
+ *       i) the modification of the Contribution or
+ *      ii) the combination of the Contribution with other software or
+ *          devices where such combination causes the infringement.
+ *
+ * The elliptic curve binary polynomial software is originally written by 
+ * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories.
+ *
+ */
 
 #ifndef HEADER_EC_H
 #define HEADER_EC_H
@@ -103,11 +129,17 @@ const EC_METHOD *EC_GFp_recp_method(void); /* TODO */
 const EC_METHOD *EC_GFp_nist_method(void); /* TODO */
 #endif
 
+/* EC_METHODs for curves over GF(2^m).
+ * EC_GF2m_simple_method provides the basis for the optimized methods.
+ */
+const EC_METHOD *EC_GF2m_simple_method(void);
+
 
 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 *);
+EC_GROUP *EC_GROUP_dup(const EC_GROUP *);
 
 const EC_METHOD *EC_GROUP_method_of(const EC_GROUP *);
 int EC_METHOD_get_field_type(const EC_METHOD *);
@@ -130,12 +162,12 @@ unsigned char *EC_GROUP_get0_seed(const EC_GROUP *);
 size_t EC_GROUP_get_seed_len(const EC_GROUP *);
 size_t EC_GROUP_set_seed(EC_GROUP *, const unsigned char *, size_t len);
 
-/* We don't have types for field specifications and field elements in general.
- * Otherwise we could declare
- *     int EC_GROUP_set_curve(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(const EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *);
+int EC_GROUP_set_curve_GF2m(EC_GROUP *, const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *);
+int EC_GROUP_get_curve_GF2m(const EC_GROUP *, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *);
+
+int EC_GROUP_get_degree(const EC_GROUP *);
 
 /* EC_GROUP_check() returns 1 if 'group' defines a valid group, 0 otherwise */
 int EC_GROUP_check(const EC_GROUP *group, BN_CTX *ctx);
@@ -143,9 +175,10 @@ int EC_GROUP_check(const EC_GROUP *group, BN_CTX *ctx);
  * elliptic curve is not zero, 0 otherwise */
 int EC_GROUP_check_discriminant(const EC_GROUP *, BN_CTX *);
 
-/* EC_GROUP_new_GFp() calls EC_GROUP_new() and EC_GROUP_set_GFp()
+/* EC_GROUP_new_GF*() calls EC_GROUP_new() and EC_GROUP_set_GF*()
  * after choosing an appropriate EC_METHOD */
 EC_GROUP *EC_GROUP_new_curve_GFp(const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *);
+EC_GROUP *EC_GROUP_new_curve_GF2m(const BIGNUM *p, const BIGNUM *a, const BIGNUM *b, BN_CTX *);
 
 /* EC_GROUP_new_by_nid() and EC_GROUP_new_by_name() also set
  * generator and order */
@@ -181,15 +214,66 @@ EC_GROUP *EC_GROUP_new_by_name(int name);
 #define EC_GROUP_SECG_PRIME_384R1	NID_secp384r1
 #define EC_GROUP_SECG_PRIME_521R1	NID_secp521r1
 #define EC_GROUP_WTLS_6			NID_wap_wsg_idm_ecid_wtls6
-#define EC_GROUP_WTLS_7			NID_secp160r1
+#define EC_GROUP_WTLS_7			NID_wap_wsg_idm_ecid_wtls7
 #define EC_GROUP_WTLS_8			NID_wap_wsg_idm_ecid_wtls8
 #define EC_GROUP_WTLS_9			NID_wap_wsg_idm_ecid_wtls9
-#define EC_GROUP_WTLS_12		NID_secp224r1
+#define EC_GROUP_WTLS_12		NID_wap_wsg_idm_ecid_wtls12
+#define EC_GROUP_NIST_CHAR2_K163	NID_sect163k1
+#define EC_GROUP_NIST_CHAR2_B163	NID_sect163r2
+#define EC_GROUP_NIST_CHAR2_K233	NID_sect233k1
+#define EC_GROUP_NIST_CHAR2_B233	NID_sect233r1
+#define EC_GROUP_NIST_CHAR2_K283	NID_sect283k1
+#define EC_GROUP_NIST_CHAR2_B283	NID_sect283r1
+#define EC_GROUP_NIST_CHAR2_K409	NID_sect409k1
+#define EC_GROUP_NIST_CHAR2_B409	NID_sect409r1
+#define EC_GROUP_NIST_CHAR2_K571	NID_sect571k1
+#define EC_GROUP_NIST_CHAR2_B571	NID_sect571r1
+#define EC_GROUP_X9_62_CHAR2_163V1	NID_X9_62_c2pnb163v1
+#define EC_GROUP_X9_62_CHAR2_163V2	NID_X9_62_c2pnb163v2
+#define EC_GROUP_X9_62_CHAR2_163V3	NID_X9_62_c2pnb163v3
+#define EC_GROUP_X9_62_CHAR2_176V1	NID_X9_62_c2pnb176v1
+#define EC_GROUP_X9_62_CHAR2_191V1	NID_X9_62_c2tnb191v1
+#define EC_GROUP_X9_62_CHAR2_191V2	NID_X9_62_c2tnb191v2
+#define EC_GROUP_X9_62_CHAR2_191V3	NID_X9_62_c2tnb191v3
+#define EC_GROUP_X9_62_CHAR2_208W1	NID_X9_62_c2pnb208w1
+#define EC_GROUP_X9_62_CHAR2_239V1	NID_X9_62_c2tnb239v1
+#define EC_GROUP_X9_62_CHAR2_239V2	NID_X9_62_c2tnb239v2
+#define EC_GROUP_X9_62_CHAR2_239V3	NID_X9_62_c2tnb239v3
+#define EC_GROUP_X9_62_CHAR2_272W1	NID_X9_62_c2pnb272w1
+#define EC_GROUP_X9_62_CHAR2_304W1	NID_X9_62_c2pnb304w1
+#define EC_GROUP_X9_62_CHAR2_359V1	NID_X9_62_c2tnb359v1
+#define EC_GROUP_X9_62_CHAR2_368W1	NID_X9_62_c2pnb368w1
+#define EC_GROUP_X9_62_CHAR2_431R1	NID_X9_62_c2tnb431r1
+#define EC_GROUP_SECG_CHAR2_113R1	NID_sect113r1
+#define EC_GROUP_SECG_CHAR2_113R2	NID_sect113r2
+#define EC_GROUP_SECG_CHAR2_131R1	NID_sect131r1
+#define EC_GROUP_SECG_CHAR2_131R2	NID_sect131r2
+#define EC_GROUP_SECG_CHAR2_163K1	NID_sect163k1
+#define EC_GROUP_SECG_CHAR2_163R1	NID_sect163r1
+#define EC_GROUP_SECG_CHAR2_163R2	NID_sect163r2
+#define EC_GROUP_SECG_CHAR2_193R1	NID_sect193r1
+#define EC_GROUP_SECG_CHAR2_193R2	NID_sect193r2
+#define EC_GROUP_SECG_CHAR2_233K1	NID_sect233k1
+#define EC_GROUP_SECG_CHAR2_233R1	NID_sect233r1
+#define EC_GROUP_SECG_CHAR2_239K1	NID_sect239k1
+#define EC_GROUP_SECG_CHAR2_283K1	NID_sect283k1
+#define EC_GROUP_SECG_CHAR2_283R1	NID_sect283r1
+#define EC_GROUP_SECG_CHAR2_409K1	NID_sect409k1
+#define EC_GROUP_SECG_CHAR2_409R1	NID_sect409r1
+#define EC_GROUP_SECG_CHAR2_571K1	NID_sect571k1
+#define EC_GROUP_SECG_CHAR2_571R1	NID_sect571r1
+#define EC_GROUP_WTLS_1			NID_wap_wsg_idm_ecid_wtls1
+#define EC_GROUP_WTLS_3			NID_wap_wsg_idm_ecid_wtls3
+#define EC_GROUP_WTLS_4			NID_wap_wsg_idm_ecid_wtls4
+#define EC_GROUP_WTLS_5			NID_wap_wsg_idm_ecid_wtls5
+#define EC_GROUP_WTLS_10		NID_wap_wsg_idm_ecid_wtls10
+#define EC_GROUP_WTLS_11		NID_wap_wsg_idm_ecid_wtls11
 
 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 *);
+EC_POINT *EC_POINT_dup(const EC_POINT *, const EC_GROUP *);
  
 const EC_METHOD *EC_POINT_method_of(const EC_POINT *);
 
@@ -205,6 +289,17 @@ int EC_POINT_get_affine_coordinates_GFp(const EC_GROUP *, const EC_POINT *,
 int EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP *, EC_POINT *,
 	const BIGNUM *x, int y_bit, BN_CTX *);
 
+int EC_POINT_set_Jprojective_coordinates_GF2m(const EC_GROUP *, EC_POINT *,
+	const BIGNUM *x, const BIGNUM *y, const BIGNUM *z, BN_CTX *);
+int EC_POINT_get_Jprojective_coordinates_GF2m(const EC_GROUP *, const EC_POINT *,
+	BIGNUM *x, BIGNUM *y, BIGNUM *z, BN_CTX *);
+int EC_POINT_set_affine_coordinates_GF2m(const EC_GROUP *, EC_POINT *,
+	const BIGNUM *x, const BIGNUM *y, BN_CTX *);
+int EC_POINT_get_affine_coordinates_GF2m(const EC_GROUP *, const EC_POINT *,
+	BIGNUM *x, BIGNUM *y, BN_CTX *);
+int EC_POINT_set_compressed_coordinates_GF2m(const EC_GROUP *, EC_POINT *,
+	const BIGNUM *x, int y_bit, BN_CTX *);
+
 size_t EC_POINT_point2oct(const EC_GROUP *, const EC_POINT *, point_conversion_form_t form,
         unsigned char *buf, size_t len, BN_CTX *);
 int EC_POINT_oct2point(const EC_GROUP *, EC_POINT *,
@@ -309,6 +404,12 @@ void ERR_load_EC_strings(void);
 #define EC_F_EC_ASN1_GROUP2PKPARAMETERS			 162
 #define EC_F_EC_ASN1_PARAMETERS2GROUP			 157
 #define EC_F_EC_ASN1_PKPARAMETERS2GROUP			 163
+#define EC_F_EC_GF2M_SIMPLE_GROUP_CHECK_DISCRIMINANT	 168
+#define EC_F_EC_GF2M_SIMPLE_OCT2POINT			 169
+#define EC_F_EC_GF2M_SIMPLE_POINT2OCT			 170
+#define EC_F_EC_GF2M_SIMPLE_POINT_GET_AFFINE_COORDINATES_GF2M 171
+#define EC_F_EC_GF2M_SIMPLE_POINT_SET_AFFINE_COORDINATES_GF2M 172
+#define EC_F_EC_GF2M_SIMPLE_SET_COMPRESSED_COORDINATES_GF2M 185
 #define EC_F_EC_GFP_MONT_FIELD_DECODE			 133
 #define EC_F_EC_GFP_MONT_FIELD_ENCODE			 134
 #define EC_F_EC_GFP_MONT_FIELD_MUL			 131
@@ -328,15 +429,19 @@ void ERR_load_EC_strings(void);
 #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_GF2M			 173
 #define EC_F_EC_GROUP_GET_CURVE_GFP			 130
+#define EC_F_EC_GROUP_GET_DEGREE			 174
 #define EC_F_EC_GROUP_GET_EXTRA_DATA			 107
 #define EC_F_EC_GROUP_GET_ORDER				 141
 #define EC_F_EC_GROUP_GROUP2NID				 147
 #define EC_F_EC_GROUP_NEW				 108
 #define EC_F_EC_GROUP_NEW_BY_NAME			 144
 #define EC_F_EC_GROUP_NEW_BY_NID			 146
+#define EC_F_EC_GROUP_NEW_GF2M_FROM_HEX			 175
 #define EC_F_EC_GROUP_NEW_GFP_FROM_HEX			 148
 #define EC_F_EC_GROUP_PRECOMPUTE_MULT			 142
+#define EC_F_EC_GROUP_SET_CURVE_GF2M			 176
 #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
@@ -346,18 +451,26 @@ void ERR_load_EC_strings(void);
 #define EC_F_EC_POINT_CMP				 113
 #define EC_F_EC_POINT_COPY				 114
 #define EC_F_EC_POINT_DBL				 115
+#define EC_F_EC_POINT_GET_AFFINE_COORDINATES_GF2M	 177
 #define EC_F_EC_POINT_GET_AFFINE_COORDINATES_GFP	 116
+#define EC_F_EC_POINT_GET_JPROJECTIVE_COORDINATES_GF2M	 178
 #define EC_F_EC_POINT_GET_JPROJECTIVE_COORDINATES_GFP	 117
 #define EC_F_EC_POINT_IS_AT_INFINITY			 118
 #define EC_F_EC_POINT_IS_ON_CURVE			 119
 #define EC_F_EC_POINT_MAKE_AFFINE			 120
+#define EC_F_EC_POINT_MUL				 179
 #define EC_F_EC_POINT_NEW				 121
 #define EC_F_EC_POINT_OCT2POINT				 122
 #define EC_F_EC_POINT_POINT2OCT				 123
+#define EC_F_EC_POINT_SET_AFFINE_COORDINATES_GF2M	 180
 #define EC_F_EC_POINT_SET_AFFINE_COORDINATES_GFP	 124
+#define EC_F_EC_POINT_SET_COMPRESSED_COORDINATES_GF2M	 181
 #define EC_F_EC_POINT_SET_COMPRESSED_COORDINATES_GFP	 125
+#define EC_F_EC_POINT_SET_JPROJECTIVE_COORDINATES_GF2M	 182
 #define EC_F_EC_POINT_SET_JPROJECTIVE_COORDINATES_GFP	 126
 #define EC_F_EC_POINT_SET_TO_INFINITY			 127
+#define EC_F_EC_WNAF_MUL				 183
+#define EC_F_EC_WNAF_PRECOMPUTE_MULT			 184
 #define EC_F_GFP_MONT_GROUP_SET_CURVE_GFP		 135
 #define EC_F_I2D_ECDSAPARAMETERS			 158
 #define EC_F_I2D_ECPARAMETERS				 164
diff --git a/crypto/ec/ec2_mult.c b/crypto/ec/ec2_mult.c
new file mode 100644
index 0000000000..d766375369
--- /dev/null
+++ b/crypto/ec/ec2_mult.c
@@ -0,0 +1,387 @@
+/* crypto/ec/ec2_mult.c */
+/* ====================================================================
+ * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
+ *
+ * The Elliptic Curve Public-Key Crypto Library (ECC Code) included
+ * herein is developed by SUN MICROSYSTEMS, INC., and is contributed
+ * to the OpenSSL project.
+ *
+ * The ECC Code is licensed pursuant to the OpenSSL open source
+ * license provided below.
+ *
+ * In addition, Sun covenants to all licensees who provide a reciprocal
+ * covenant with respect to their own patents if any, not to sue under
+ * current and future patent claims necessarily infringed by the making,
+ * using, practicing, selling, offering for sale and/or otherwise
+ * disposing of the ECC Code as delivered hereunder (or portions thereof),
+ * provided that such covenant shall not apply:
+ *  1) for code that a licensee deletes from the ECC Code;
+ *  2) separates from the ECC Code; or
+ *  3) for infringements caused by:
+ *       i) the modification of the ECC Code or
+ *      ii) the combination of the ECC Code with other software or
+ *          devices where such combination causes the infringement.
+ *
+ * The software is originally written by Sheueling Chang Shantz and
+ * Douglas Stebila of Sun Microsystems Laboratories.
+ *
+ */
+/* ====================================================================
+ * Copyright (c) 1998-2002 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).
+ *
+ */
+
+#include <openssl/err.h>
+
+#include "ec_lcl.h"
+
+
+/* Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery projective 
+ * coordinates.
+ * Uses algorithm Mdouble in appendix of 
+ *     Lopez, J. and Dahab, R.  "Fast multiplication on elliptic curves over 
+ *     GF(2^m) without precomputation".
+ * modified to not require precomputation of c=b^{2^{m-1}}.
+ */
+static int Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z, BN_CTX *ctx)
+	{
+	BIGNUM *t1;
+	int ret = 0;
+	
+	/* Since Mdouble is static we can guarantee that ctx != NULL. */
+	BN_CTX_start(ctx);
+	t1 = BN_CTX_get(ctx);
+	if (t1 == NULL) goto err;
+
+	if (!group->meth->field_sqr(group, x, x, ctx)) goto err;
+	if (!group->meth->field_sqr(group, t1, z, ctx)) goto err;
+	if (!group->meth->field_mul(group, z, x, t1, ctx)) goto err;
+	if (!group->meth->field_sqr(group, x, x, ctx)) goto err;
+	if (!group->meth->field_sqr(group, t1, t1, ctx)) goto err;
+	if (!group->meth->field_mul(group, t1, &group->b, t1, ctx)) goto err;
+	if (!BN_GF2m_add(x, x, t1)) goto err;
+
+	ret = 1;
+
+ err:
+	BN_CTX_end(ctx);
+	return ret;
+	}
+
+/* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery 
+ * projective coordinates.
+ * Uses algorithm Madd in appendix of 
+ *     Lopex, J. and Dahab, R.  "Fast multiplication on elliptic curves over 
+ *     GF(2^m) without precomputation".
+ */
+static int Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1, BIGNUM *z1, 
+	const BIGNUM *x2, const BIGNUM *z2, BN_CTX *ctx)
+	{
+	BIGNUM *t1, *t2;
+	int ret = 0;
+	
+	/* Since Madd is static we can guarantee that ctx != NULL. */
+	BN_CTX_start(ctx);
+	t1 = BN_CTX_get(ctx);
+	t2 = BN_CTX_get(ctx);
+	if (t2 == NULL) goto err;
+
+	if (!BN_copy(t1, x)) goto err;
+	if (!group->meth->field_mul(group, x1, x1, z2, ctx)) goto err;
+	if (!group->meth->field_mul(group, z1, z1, x2, ctx)) goto err;
+	if (!group->meth->field_mul(group, t2, x1, z1, ctx)) goto err;
+	if (!BN_GF2m_add(z1, z1, x1)) goto err;
+	if (!group->meth->field_sqr(group, z1, z1, ctx)) goto err;
+	if (!group->meth->field_mul(group, x1, z1, t1, ctx)) goto err;
+	if (!BN_GF2m_add(x1, x1, t2)) goto err;
+
+	ret = 1;
+
+ err:
+	BN_CTX_end(ctx);
+	return ret;
+	}
+
+/* Compute the affine coordinates x2, y2=z2 for the point (x1/z1) and (x2/x2) in
+ * Montgomery projective coordinates.
+ * Uses algorithm Mxy in appendix of 
+ *     Lopex, J. and Dahab, R.  "Fast multiplication on elliptic curves over 
+ *     GF(2^m) without precomputation".
+ * Returns:
+ *     0 on error
+ *     1 if return value should be the point at infinity
+ *     2 otherwise
+ */
+static int Mxy(const EC_GROUP *group, const BIGNUM *x, const BIGNUM *y, BIGNUM *x1, 
+	BIGNUM *z1, BIGNUM *x2, BIGNUM *z2, BN_CTX *ctx)
+	{
+	BIGNUM *t3, *t4, *t5;
+	int ret = 0;
+	
+	if (BN_is_zero(z1))
+		{
+		if (!BN_zero(x2)) return 0;
+		if (!BN_zero(z2)) return 0;
+		return 1;
+		}
+	
+	if (BN_is_zero(z2))
+		{
+		if (!BN_copy(x2, x)) return 0;
+		if (!BN_GF2m_add(z2, x, y)) return 0;
+		return 2;
+		}
+		
+	/* Since Mxy is static we can guarantee that ctx != NULL. */
+	BN_CTX_start(ctx);
+	t3 = BN_CTX_get(ctx);
+	t4 = BN_CTX_get(ctx);
+	t5 = BN_CTX_get(ctx);
+	if (t5 == NULL) goto err;
+
+	if (!BN_one(t5)) goto err;
+
+	if (!group->meth->field_mul(group, t3, z1, z2, ctx)) goto err;
+
+	if (!group->meth->field_mul(group, z1, z1, x, ctx)) goto err;
+	if (!BN_GF2m_add(z1, z1, x1)) goto err;
+	if (!group->meth->field_mul(group, z2, z2, x, ctx)) goto err;
+	if (!group->meth->field_mul(group, x1, z2, x1, ctx)) goto err;
+	if (!BN_GF2m_add(z2, z2, x2)) goto err;
+
+	if (!group->meth->field_mul(group, z2, z2, z1, ctx)) goto err;
+	if (!group->meth->field_sqr(group, t4, x, ctx)) goto err;
+	if (!BN_GF2m_add(t4, t4, y)) goto err;
+	if (!group->meth->field_mul(group, t4, t4, t3, ctx)) goto err;
+	if (!BN_GF2m_add(t4, t4, z2)) goto err;
+
+	if (!group->meth->field_mul(group, t3, t3, x, ctx)) goto err;
+	if (!group->meth->field_div(group, t3, t5, t3, ctx)) goto err;
+	if (!group->meth->field_mul(group, t4, t3, t4, ctx)) goto err;
+	if (!group->meth->field_mul(group, x2, x1, t3, ctx)) goto err;
+	if (!BN_GF2m_add(z2, x2, x)) goto err;
+
+	if (!group->meth->field_mul(group, z2, z2, t4, ctx)) goto err;
+	if (!BN_GF2m_add(z2, z2, y)) goto err;
+
+	ret = 2;
+
+ err:
+	BN_CTX_end(ctx);
+	return ret;
+	}
+
+/* Computes scalar*point and stores the result in r.
+ * point can not equal r.
+ * Uses algorithm 2P of
+ *     Lopex, J. and Dahab, R.  "Fast multiplication on elliptic curves over 
+ *     GF(2^m) without precomputation".
+ */
+static int point_multiply(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
+	const EC_POINT *point, BN_CTX *ctx)
+	{
+	BIGNUM *x1, *x2, *z1, *z2;
+	int ret = 0, i, j;
+	BN_ULONG mask;
+
+	if (r == point)
+		{
+		ECerr(EC_F_EC_POINT_MUL, EC_R_INVALID_ARGUMENT);
+		return 0;
+		}
+	
+	/* if result should be point at infinity */
+	if ((scalar == NULL) || BN_is_zero(scalar) || (point == NULL) || 
+		EC_POINT_is_at_infinity(group, point))
+		{
+		return EC_POINT_set_to_infinity(group, r);
+		}
+
+	/* only support affine coordinates */
+	if (!point->Z_is_one) return 0;
+
+	/* Since point_multiply is static we can guarantee that ctx != NULL. */
+	BN_CTX_start(ctx);
+	x1 = BN_CTX_get(ctx);
+	z1 = BN_CTX_get(ctx);
+	if (z1 == NULL) goto err;
+
+	x2 = &r->X;
+	z2 = &r->Y;
+
+	if (!BN_GF2m_mod_arr(x1, &point->X, group->poly)) goto err; /* x1 = x */
+	if (!BN_one(z1)) goto err; /* z1 = 1 */
+	if (!group->meth->field_sqr(group, z2, x1, ctx)) goto err; /* z2 = x1^2 = x^2 */
+	if (!group->meth->field_sqr(group, x2, z2, ctx)) goto err;
+	if (!BN_GF2m_add(x2, x2, &group->b)) goto err; /* x2 = x^4 + b */
+
+	/* find top most bit and go one past it */
+	i = scalar->top - 1; j = BN_BITS2 - 1;
+	mask = BN_TBIT;
+	while (!(scalar->d[i] & mask)) { mask >>= 1; j--; }
+	mask >>= 1; j--;
+	/* if top most bit was at word break, go to next word */
+	if (!mask) 
+		{
+		i--; j = BN_BITS2 - 1;
+		mask = BN_TBIT;
+		}
+
+	for (; i >= 0; i--)
+		{
+		for (; j >= 0; j--)
+			{
+			if (scalar->d[i] & mask)
+				{
+				if (!Madd(group, &point->X, x1, z1, x2, z2, ctx)) goto err;
+				if (!Mdouble(group, x2, z2, ctx)) goto err;
+				}
+			else
+				{
+				if (!Madd(group, &point->X, x2, z2, x1, z1, ctx)) goto err;
+				if (!Mdouble(group, x1, z1, ctx)) goto err;
+				}
+			mask >>= 1;
+			}
+		j = BN_BITS2 - 1;
+		mask = BN_TBIT;
+		}
+
+	/* convert out of "projective" coordinates */
+	i = Mxy(group, &point->X, &point->Y, x1, z1, x2, z2, ctx);
+	if (i == 0) goto err;
+	else if (i == 1) 
+		{
+		if (!EC_POINT_set_to_infinity(group, r)) goto err;
+		}
+	else
+		{
+		if (!BN_one(&r->Z)) goto err;
+		r->Z_is_one = 1;
+		}
+
+	/* GF(2^m) field elements should always have BIGNUM::neg = 0 */
+	r->X.neg = 0;
+	r->Y.neg = 0;
+
+	ret = 1;
+
+ err:
+	BN_CTX_end(ctx);
+	return ret;
+	}
+
+
+/* Computes the sum
+ *     scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1]
+ * gracefully ignoring NULL scalar values.
+ */
+int ec_GF2m_mont_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;
+	int ret = 0, i;
+	EC_POINT *p=NULL;
+
+	if (ctx == NULL)
+		{
+		ctx = new_ctx = BN_CTX_new();
+		if (ctx == NULL)
+			return 0;
+		}
+
+	/* This implementation is more efficient than the wNAF implementation for 2
+	 * or fewer points.  Use the ec_wNAF_mul implementation 3 or more points.
+	 */
+	if ((scalar && (num > 1)) || (num > 2))
+		{
+		ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
+		goto err;
+		}
+
+	if ((p = EC_POINT_new(group)) == NULL) goto err;
+
+	if (!EC_POINT_set_to_infinity(group, r)) goto err;
+
+	if (scalar)
+		{
+		if (!point_multiply(group, p, scalar, group->generator, ctx)) goto err;
+		if (scalar->neg) if (!group->meth->invert(group, p, ctx)) goto err;
+		if (!group->meth->add(group, r, r, p, ctx)) goto err;
+		}
+
+	for (i = 0; i < num; i++)
+		{
+		if (!point_multiply(group, p, scalars[i], points[i], ctx)) goto err;
+		if (scalars[i]->neg) if (!group->meth->invert(group, p, ctx)) goto err;
+		if (!group->meth->add(group, r, r, p, ctx)) goto err;
+		}
+
+	ret = 1;
+
+  err:
+	if (p) EC_POINT_free(p);
+	if (new_ctx != NULL)
+		BN_CTX_free(new_ctx);
+	return ret;
+	}
+
+
+/* Precomputation for point multiplication. */	
+int ec_GF2m_mont_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);
+	}
diff --git a/crypto/ec/ec2_smpl.c b/crypto/ec/ec2_smpl.c
new file mode 100644
index 0000000000..09ce539334
--- /dev/null
+++ b/crypto/ec/ec2_smpl.c
@@ -0,0 +1,980 @@
+/* crypto/ec/ec2_smpl.c */
+/* ====================================================================
+ * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
+ *
+ * The Elliptic Curve Public-Key Crypto Library (ECC Code) included
+ * herein is developed by SUN MICROSYSTEMS, INC., and is contributed
+ * to the OpenSSL project.
+ *
+ * The ECC Code is licensed pursuant to the OpenSSL open source
+ * license provided below.
+ *
+ * In addition, Sun covenants to all licensees who provide a reciprocal
+ * covenant with respect to their own patents if any, not to sue under
+ * current and future patent claims necessarily infringed by the making,
+ * using, practicing, selling, offering for sale and/or otherwise
+ * disposing of the ECC Code as delivered hereunder (or portions thereof),
+ * provided that such covenant shall not apply:
+ *  1) for code that a licensee deletes from the ECC Code;
+ *  2) separates from the ECC Code; or
+ *  3) for infringements caused by:
+ *       i) the modification of the ECC Code or
+ *      ii) the combination of the ECC Code with other software or
+ *          devices where such combination causes the infringement.
+ *
+ * The software is originally written by Sheueling Chang Shantz and
+ * Douglas Stebila of Sun Microsystems Laboratories.
+ *
+ */
+/* ====================================================================
+ * Copyright (c) 1998-2002 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).
+ *
+ */
+
+#include <openssl/err.h>
+
+#include "ec_lcl.h"
+
+
+const EC_METHOD *EC_GF2m_simple_method(void)
+	{
+	static const EC_METHOD ret = {
+		NID_X9_62_characteristic_two_field,
+		ec_GF2m_simple_group_init,
+		ec_GF2m_simple_group_finish,
+		ec_GF2m_simple_group_clear_finish,
+		ec_GF2m_simple_group_copy,
+		ec_GF2m_simple_group_set_curve_GF2m,
+		ec_GF2m_simple_group_get_curve_GF2m,
+		ec_GF2m_simple_group_get_degree,
+		ec_GF2m_simple_group_check_discriminant,
+		ec_GF2m_simple_point_init,
+		ec_GF2m_simple_point_finish,
+		ec_GF2m_simple_point_clear_finish,
+		ec_GF2m_simple_point_copy,
+		ec_GF2m_simple_point_set_to_infinity,
+		0 /* set_Jprojective_coordinates_GF2m */,
+		0 /* get_Jprojective_coordinates_GF2m */,
+		ec_GF2m_simple_point_set_affine_coordinates_GF2m,
+		ec_GF2m_simple_point_get_affine_coordinates_GF2m,
+		ec_GF2m_simple_set_compressed_coordinates_GF2m,
+		ec_GF2m_simple_point2oct,
+		ec_GF2m_simple_oct2point,
+		ec_GF2m_simple_add,
+		ec_GF2m_simple_dbl,
+		ec_GF2m_simple_invert,
+		ec_GF2m_mont_mul,
+		ec_GF2m_mont_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,
+		ec_GF2m_simple_field_mul,
+		ec_GF2m_simple_field_sqr,
+		ec_GF2m_simple_field_div,
+		0 /* field_encode */,
+		0 /* field_decode */,
+		0 /* field_set_to_one */ };
+
+	return &ret;
+	}
+
+
+/* Initialize a GF(2^m)-based EC_GROUP structure.
+ * Note that all other members are handled by EC_GROUP_new.
+ */
+int ec_GF2m_simple_group_init(EC_GROUP *group)
+	{
+	BN_init(&group->field);
+	BN_init(&group->a);
+	BN_init(&group->b);
+	return 1;
+	}
+
+
+/* Free a GF(2^m)-based EC_GROUP structure.
+ * Note that all other members are handled by EC_GROUP_free.
+ */
+void ec_GF2m_simple_group_finish(EC_GROUP *group)
+	{
+	BN_free(&group->field);
+	BN_free(&group->a);
+	BN_free(&group->b);
+	}