More EC stuff, including EC_POINTs_mul() for simultaneous scalar
authorBodo Möller <bodo@openssl.org>
Sat, 10 Mar 2001 23:18:35 +0000 (23:18 +0000)
committerBodo Möller <bodo@openssl.org>
Sat, 10 Mar 2001 23:18:35 +0000 (23:18 +0000)
multiplication of an arbitrary number of points.

13 files changed:
CHANGES
crypto/bn/Makefile.ssl
crypto/bn/bn_lcl.h
crypto/ec/ec.h
crypto/ec/ec_err.c
crypto/ec/ec_lcl.h
crypto/ec/ec_lib.c
crypto/ec/ec_mult.c
crypto/ec/ecp_mont.c
crypto/ec/ecp_nist.c
crypto/ec/ecp_recp.c
crypto/ec/ecp_smpl.c
crypto/ec/ectest.c

diff --git a/CHANGES b/CHANGES
index f4298c9..dc55a7d 100644 (file)
--- 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
index 17a289a..19db2b5 100644 (file)
@@ -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
index df12a01..73792f1 100644 (file)
@@ -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
        {
index a9f6c16..87c1f45 100644 (file)
@@ -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
index 6fd7464..7dd1131 100644 (file)
@@ -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"},
index 38ce24b..cc4cf27 100644 (file)
@@ -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 */
index 6aaacb3..e0d78d6 100644 (file)
@@ -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);
+       }
index d43bdc2..0515e72 100644 (file)
@@ -1,4 +1,3 @@
-/* TODO */
 /* crypto/ec/ec_mult.c */
 /* ====================================================================
  * Copyright (c) 1998-2001 The OpenSSL Project.  All rights reserved.
  *
  */
 
+#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;
+       }
index 8ba2227..7b30d4c 100644 (file)
@@ -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_NOT_INITIALIZED);
                return 0;
                }
 
-       return BN_from_montgomery(r, a, group->field_data, ctx);
+       return BN_from_montgomery(r, a, group->field_data1, ctx);
+       }
+
+
+int ec_GFp_mont_field_set_to_one(const EC_GROUP *group, BIGNUM *r, BN_CTX *ctx)
+       {
+       if (group->field_data2 == NULL)
+               {
+               ECerr(EC_F_EC_GFP_MONT_FIELD_DECODE, EC_R_NOT_INITIALIZED);
+               return 0;
+               }
+
+       if (!BN_copy(r, group->field_data2)) return 0;
+       return 1;
        }
index 354130b..ed07748 100644 (file)
@@ -88,10 +88,12 @@ const EC_METHOD *EC_GFp_nist_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_nist_field_mul,
                ec_GFp_nist_field_sqr,
                0 /* field_encode */,
-               0 /* field_decode */ };
+               0 /* field_decode */,
+               0 /* field_set_to_one */ };
 
        return &ret;
        }
@@ -103,7 +105,7 @@ int ec_GFp_nist_group_init(EC_GROUP *group)
        int ok;
 
        ok = ec_GFp_simple_group_init(group);
-       group->field_data = NULL;
+       group->field_data1 = NULL;
        return ok;
        }
 
index e8d8382..fec843b 100644 (file)
@@ -88,10 +88,12 @@ const EC_METHOD *EC_GFp_recp_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_recp_field_mul,
                ec_GFp_recp_field_sqr,
                0 /* field_encode */,
-               0 /* field_decode */ };
+               0 /* field_decode */,
+               0 /* field_set_to_one */ };
 
        return &ret;
        }
@@ -102,7 +104,7 @@ int ec_GFp_recp_group_init(EC_GROUP *group)
        int ok;
 
        ok = ec_GFp_simple_group_init(group);
-       group->field_data = NULL;
+       group->field_data1 = NULL;
        return ok;
        }
 
index 4c23b71..30178f7 100644 (file)
@@ -92,10 +92,12 @@ const EC_METHOD *EC_GFp_simple_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_simple_field_mul,
                ec_GFp_simple_field_sqr,
                0 /* field_encode */,
-               0 /* field_decode */ };
+               0 /* field_decode */,
+               0 /* field_set_to_one */ };
 
        return &ret;
        }
@@ -230,7 +232,7 @@ int ec_GFp_simple_group_set_curve_GFp(EC_GROUP *group,
        }
 
 
-int ec_GFp_simple_group_get_curve_GFp(EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
+int ec_GFp_simple_group_get_curve_GFp(const EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIGNUM *b, BN_CTX *ctx)
        {
        int ret = 0;
        BN_CTX *new_ctx = NULL;
@@ -285,7 +287,7 @@ int ec_GFp_simple_group_get_curve_GFp(EC_GROUP *group, BIGNUM *p, BIGNUM *a, BIG
 int ec_GFp_simple_group_set_generator(EC_GROUP *group, const EC_POINT *generator,
        const BIGNUM *order, const BIGNUM *cofactor)
        {
-       if (generator)
+       if (generator == NULL)
                {
                ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_GENERATOR, ERR_R_PASSED_NULL_PARAMETER);
                return 0   ;
@@ -312,13 +314,13 @@ int ec_GFp_simple_group_set_generator(EC_GROUP *group, const EC_POINT *generator
        }
 
 
-EC_POINT *ec_GFp_simple_group_get0_generator(EC_GROUP *group)
+EC_POINT *ec_GFp_simple_group_get0_generator(const EC_GROUP *group)
        {
        return group->generator;
        }
 
 
-int ec_GFp_simple_group_get_order(EC_GROUP *group, BIGNUM *order, BN_CTX *ctx)
+int ec_GFp_simple_group_get_order(const EC_GROUP *group, BIGNUM *order, BN_CTX *ctx)
        {
        if (!BN_copy(order, &group->order))
                return 0;
@@ -327,7 +329,7 @@ int ec_GFp_simple_group_get_order(EC_GROUP *group, BIGNUM *order, BN_CTX *ctx)
        }
 
 
-int ec_GFp_simple_group_get_cofactor(EC_GROUP *group, BIGNUM *cofactor, BN_CTX *ctx)
+int ec_GFp_simple_group_get_cofactor(const EC_GROUP *group, BIGNUM *cofactor, BN_CTX *ctx)
        {
        if (!BN_copy(cofactor, &group->cofactor))
                return 0;
@@ -421,7 +423,14 @@ int ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP *group, EC_POIN
                Z_is_one = BN_is_one(&point->Z);
                if (group->meth->field_encode)
                        {
-                       if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
+                       if (Z_is_one && (group->meth->field_set_to_one != 0))
+                               {
+                               if (!group->meth->field_set_to_one(group, &point->Z, ctx)) goto err;
+                               }
+                       else
+                               {
+                               if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) goto err;
+                               }
                        }
                point->Z_is_one = Z_is_one;
                }
@@ -566,17 +575,44 @@ int ec_GFp_simple_point_get_affine_coordinates_GFp(const EC_GROUP *group, const
                        ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES_GFP, ERR_R_BN_LIB);
                        goto err;
                        }
-               if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
+               
+               if (group->meth->field_encode == 0)
+                       {
+                       /* field_sqr works on standard representation */
+                       if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) goto err;
+                       }
+               else
+                       {
+                       if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) goto err;
+                       }
        
                if (x != NULL)
                        {
-                       if (!BN_mod_mul(x, X_, Z_2, &group->field, ctx)) goto err;
+                       if (group->meth->field_encode == 0)
+                               {
+                               /* field_mul works on standard representation */
+                               if (!group->meth->field_mul(group, x, X_, Z_2, ctx)) goto err;
+                               }
+                       else
+                               {
+                               if (!BN_mod_mul(x, X_, Z_2, &group->field, ctx)) goto err;
+                               }
                        }
 
                if (y != NULL)
                        {
-                       if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
-                       if (!BN_mod_mul(y, Y_, Z_3, &group->field, ctx)) goto err;
+                       if (group->meth->field_encode == 0)
+                               {
+                               /* field_mul works on standard representation */
+                               if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) goto err;
+                               if (!group->meth->field_mul(group, y, Y_, Z_3, ctx)) goto err;
+                               
+                               }
+                       else
+                               {
+                               if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) goto err;
+                               if (!BN_mod_mul(y, Y_, Z_3, &group->field, ctx)) goto err;
+                               }
                        }
                }
 
@@ -591,10 +627,10 @@ int ec_GFp_simple_point_get_affine_coordinates_GFp(const EC_GROUP *group, const
 
 
 int ec_GFp_simple_set_compressed_coordinates_GFp(const EC_GROUP *group, EC_POINT *point,
-       const BIGNUM *x, int y_bit, BN_CTX *ctx)
+       const BIGNUM *x_, int y_bit, BN_CTX *ctx)
        {
        BN_CTX *new_ctx = NULL;
-       BIGNUM *tmp1, *tmp2, *y;
+       BIGNUM *tmp1, *tmp2, *x, *y;
        int ret = 0;
 
        if (ctx == NULL)
@@ -609,6 +645,7 @@ int ec_GFp_simple_set_compressed_coordinates_GFp(const EC_GROUP *group, EC_POINT
        BN_CTX_start(ctx);
        tmp1 = BN_CTX_get(ctx);
        tmp2 = BN_CTX_get(ctx);
+       x = BN_CTX_get(ctx);
        y = BN_CTX_get(ctx);
        if (y == NULL) goto err;
 
@@ -618,8 +655,18 @@ int ec_GFp_simple_set_compressed_coordinates_GFp(const EC_GROUP *group, EC_POINT
         */
 
        /* tmp1 := x^3 */
-       if (!BN_mod_sqr(tmp2, x, &group->field, ctx)) goto err;
-       if (!BN_mod_mul(tmp1, tmp2, x, &group->field, ctx)) goto err;
+       if (!BN_nnmod(x, x_, &group->field,ctx)) goto err;
+       if (group->meth->field_decode == 0)
+               {
+               /* field_{sqr,mul} work on standard representation */
+               if (!group->meth->field_sqr(group, tmp2, x_, ctx)) goto err;
+               if (!group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) goto err;
+               }
+       else
+               {
+               if (!BN_mod_sqr(tmp2, x_, &group->field, ctx)) goto err;
+               if (!BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) goto err;
+               }
        
        /* tmp1 := tmp1 + a*x */
        if (group->a_is_minus3)
@@ -637,7 +684,8 @@ int ec_GFp_simple_set_compressed_coordinates_GFp(const EC_GROUP *group, EC_POINT
                        }
                else
                        {
-                       if (!BN_mod_mul(tmp2, &group->a, x, &group->field, ctx)) goto err;
+                       /* field_mul works on standard representation */
+                       if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) goto err;
                        }
                
                if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) goto err;
@@ -656,7 +704,15 @@ int ec_GFp_simple_set_compressed_coordinates_GFp(const EC_GROUP *group, EC_POINT
        
        if (!BN_mod_sqrt(y, tmp1, &group->field, ctx))
                {
-               ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP, ERR_R_BN_LIB);
+               unsigned long err = ERR_peek_error();
+               
+               if (ERR_GET_LIB(err) == ERR_LIB_BN && ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE)
+                       {
+                       (void)ERR_get_error();
+                       ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP, EC_R_INVALID_COMPRESSED_POINT);
+                       }
+               else
+                       ECerr(EC_F_EC_GFP_SIMPLE_SET_COMPRESSED_COORDINATES_GFP, ERR_R_BN_LIB);
                goto err;
                }
        /* If tmp1 is not a square (i.e. there is no point on the curve with
@@ -1479,6 +1535,176 @@ int ec_GFp_simple_make_affine(const EC_GROUP *group, EC_POINT *point, BN_CTX *ct
        }
 
 
+int ec_GFp_simple_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[], BN_CTX *ctx)
+       {
+       BN_CTX *new_ctx = NULL;
+       BIGNUM *tmp0, *tmp1;
+       size_t pow2 = 0;
+       BIGNUM **heap = NULL;
+       size_t i;
+       int ret = 0;
+
+       if (num == 0)
+               return 1;
+
+       if (ctx == NULL)
+               {
+               ctx = new_ctx = BN_CTX_new();
+               if (ctx == NULL)
+                       return 0;
+               }
+
+       BN_CTX_start(ctx);
+       tmp0 = BN_CTX_get(ctx);
+       tmp1 = BN_CTX_get(ctx);
+       if (tmp0  == NULL || tmp1 == NULL) goto err;
+
+       /* Before converting the individual points, compute inverses of all Z values.
+        * Modular inversion is rather slow, but luckily we can do with a single
+        * explicit inversion, plus about 3 multiplications per input value.
+        */
+
+       pow2 = 1;
+       while (num > pow2)
+               pow2 <<= 1;
+       /* Now pow2 is the smallest power of 2 satifsying pow2 >= num.
+        * We need twice that. */
+       pow2 <<= 1;
+
+       heap = OPENSSL_malloc(pow2 * sizeof heap[0]);
+       if (heap == NULL) goto err;
+       
+       /* The array is used as a binary tree, exactly as in heapsort:
+        *
+        *                               heap[1]
+        *                 heap[2]                     heap[3]
+        *          heap[4]       heap[5]       heap[6]       heap[7]
+        *   heap[8]heap[9] heap[10]heap[11] heap[12]heap[13] heap[14] heap[15]
+        *
+        * We put the Z's in the last line;
+        * then we set each other node to the product of its two child-nodes (where
+        * empty or 0 entries are treated as ones);
+        * then we invert heap[1];
+        * then we invert each other node by replacing it by the product of its
+        * parent (after inversion) and its sibling (before inversion).
+        */
+       heap[0] = NULL;
+       for (i = pow2/2 - 1; i > 0; i--)
+               heap[i] = NULL;
+       for (i = 0; i < num; i++)
+               heap[pow2/2 + i] = &points[i]->Z;
+       for (i = pow2/2 + num; i < pow2; i++)
+               heap[i] = NULL;
+       
+       /* set each node to the product of its children */
+       for (i = pow2/2 - 1; i > 0; i--)
+               {
+               heap[i] = BN_new();
+               if (heap[i] == NULL) goto err;
+               
+               if (heap[2*i] != NULL)
+                       {
+                       if ((heap[2*i + 1] == NULL) || BN_is_zero(heap[2*i + 1]))
+                               {
+                               if (!BN_copy(heap[i], heap[2*i])) goto err;
+                               }
+                       else
+                               {
+                               if (BN_is_zero(heap[2*i]))
+                                       {
+                                       if (!BN_copy(heap[i], heap[2*i + 1])) goto err;
+                                       }
+                               else
+                                       {
+                                       if (!group->meth->field_mul(group, heap[i],
+                                               heap[2*i], heap[2*i + 1], ctx)) goto err;
+                                       }
+                               }
+                       }
+               }
+
+       /* invert heap[1] */
+       if (!BN_is_zero(heap[1]))
+               {
+               if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx))
+                       {
+                       ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB);
+                       goto err;
+                       }
+               }
+       if (group->meth->field_encode != 0)
+               {
+               /* in the Montgomery case, we just turned  R*H  (representing H)
+                * into  1/(R*H),  but we need  R*(1/H)  (representing 1/H);
+                * i.e. we have need to multiply by the Montgomery factor twice */
+               if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
+               if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) goto err;
+               }
+
+       /* set other heap[i]'s to their inverses */
+       for (i = 2; i < pow2/2 + num; i += 2)
+               {
+               /* i is even */
+               if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1]))
+                       {
+                       if (!group->meth->field_mul(group, tmp0, heap[i/2], heap[i + 1], ctx)) goto err;
+                       if (!group->meth->field_mul(group, tmp1, heap[i/2], heap[i], ctx)) goto err;
+                       if (!BN_copy(heap[i], tmp0)) goto err;
+                       if (!BN_copy(heap[i + 1], tmp1)) goto err;
+                       }
+               else
+                       {
+                       if (!BN_copy(heap[i], heap[i/2])) goto err;
+                       }
+               }
+
+       /* we have replaced all non-zero Z's by their inverses, now fix up all the points */
+       for (i = 0; i < num; i++)
+               {
+               EC_POINT *p = points[i];
+               
+               if (!BN_is_zero(&p->Z))
+                       {
+                       /* turn  (X, Y, 1/Z)  into  (X/Z^2, Y/Z^3, 1) */
+
+                       if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) goto err;
+                       if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) goto err;
+
+                       if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) goto err;
+                       if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) goto err;
+               
+                       if (group->meth->field_set_to_one != 0)
+                               {
+                               if (!group->meth->field_set_to_one(group, &p->Z, ctx)) goto err;
+                               }
+                       else
+                               {
+                               if (!BN_one(&p->Z)) goto err;
+                               }
+                       p->Z_is_one = 1;
+                       }
+               }
+
+       ret = 1;
+               
+ err:
+       BN_CTX_end(ctx);
+       if (new_ctx != NULL)
+               BN_CTX_free(new_ctx);
+       if (heap != NULL)
+               {
+               /* heap[pow2/2] .. heap[pow2-1] have not been allocated locally! */
+               for (i = pow2/2 - 1; i > 0; i--)
+                       {
+                       if (heap[i] != NULL)
+                               BN_clear_free(heap[i]);
+                       }
+               OPENSSL_free(heap);
+               }
+       return ret;
+       }
+
+
 int ec_GFp_simple_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
        {
        return BN_mod_mul(r, a, b, &group->field, ctx);
index 53f88c6..ac9eec8 100644 (file)
@@ -55,6 +55,7 @@
 
 #include <stdio.h>
 #include <stdlib.h>
+#include <time.h>
 
 
 #ifdef OPENSSL_NO_EC
@@ -66,16 +67,88 @@ int main(int argc, char * argv[]) { puts("Elliptic curves are disabled."); retur
 #include <openssl/err.h>
 
 #define ABORT do { \
+       fflush(stdout); \
        fprintf(stderr, "%s:%d: ABORT\n", __FILE__, __LINE__); \
        ERR_print_errors_fp(stderr); \
        exit(1); \
 } while (0)
 
+
+void timings(EC_GROUP *group, int simult, BN_CTX *ctx)
+       {
+       clock_t clck;
+       int i, j;
+       BIGNUM *s, *s0;
+       EC_POINT *P;
+       EC_POINT *points[1];
+       BIGNUM *scalars[1];
+               
+       s = BN_new();
+       s0 = BN_new();
+       if (s == NULL || s0 == NULL) ABORT;
+
+       if (!EC_GROUP_get_curve_GFp(group, s, NULL, NULL, ctx)) ABORT;
+       fprintf(stdout, "Timings for %d bit prime, ", (int)BN_num_bits(s));
+       if (!EC_GROUP_get_order(group, s, ctx)) ABORT;
+       fprintf(stdout, "%d bit exponents ", (int)BN_num_bits(s));
+       fflush(stdout);
+
+       P = EC_POINT_new(group);
+       if (P == NULL) ABORT;
+       EC_POINT_copy(P, EC_GROUP_get0_generator(group));
+
+       points[0] = P;
+       scalars[0] = s0;
+
+       clck = clock();
+       for (i = 0; i < 10; i++)
+               {
+               if (!BN_pseudo_rand(s, BN_num_bits(s), 0, 0)) ABORT;
+               if (simult)
+                       {
+                       if (!BN_pseudo_rand(s0, BN_num_bits(s), 0, 0)) ABORT;
+                       }
+               for (j = 0; j < 10; j++)
+                       {
+                       if (!EC_POINTs_mul(group, P, s, simult != 0, points, scalars, ctx)) ABORT;
+                       }
+               fprintf(stdout, ".");
+               fflush(stdout);
+               }
+       fprintf(stdout, "\n");
+       
+       clck = clock() - clck;
+
+#ifdef CLOCKS_PER_SEC
+       /* "To determine the time in seconds, the value returned
+        * by the clock function should be divided by the value
+        * of the macro CLOCKS_PER_SEC."
+        *                                       -- ISO/IEC 9899 */
+#      define UNIT "s"
+#else
+       /* "`CLOCKS_PER_SEC' undeclared (first use this function)"
+        *                            -- cc on NeXTstep/OpenStep */
+#      define UNIT "units"
+#      define CLOCKS_PER_SEC 1
+#endif
+
+       fprintf(stdout, "%i %s in %.2f " UNIT "\n", i*j,
+               simult ? "s*P+t*Q operations" : "point multiplications",
+               (double)clck/CLOCKS_PER_SEC);
+       fprintf(stdout, "average: %.4f " UNIT "\n", (double)clck/(CLOCKS_PER_SEC*i*j));
+
+       EC_POINT_free(P);
+       BN_free(s);
+       BN_free(s0);
+       }
+
+
 int main(int argc, char *argv[])
        {       
        BN_CTX *ctx = NULL;
        BIGNUM *p, *a, *b;
        EC_GROUP *group;
+       EC_GROUP *P_192 = NULL, *P_224 = NULL, *P_256 = NULL, *P_384 = NULL, *P_521 = NULL;
        EC_POINT *P, *Q, *R;
        BIGNUM *x, *y, *z;
        unsigned char buf[100];
@@ -84,7 +157,7 @@ int main(int argc, char *argv[])
        CRYPTO_mem_ctrl(CRYPTO_MEM_CHECK_ON);
        ERR_load_crypto_strings();
 
-#if 0 /* optional */
+#if 1 /* optional */
        ctx = BN_CTX_new();
        if (!ctx) ABORT;
 #endif
@@ -98,9 +171,21 @@ int main(int argc, char *argv[])
        if (!BN_hex2bn(&a, "1")) ABORT;
        if (!BN_hex2bn(&b, "1")) ABORT;
        
-       group = EC_GROUP_new(EC_GFp_mont_method());
+       group = EC_GROUP_new(EC_GFp_mont_method()); /* applications should use EC_GROUP_new_curve_GFp
+                                                    * so that the library gets to choose the EC_METHOD */
        if (!group) ABORT;
+
        if (!EC_GROUP_set_curve_GFp(group, p, a, b, ctx)) ABORT;
+
+       {
+               EC_GROUP *tmp;
+               tmp = EC_GROUP_new(EC_GROUP_method_of(group));
+               if (!tmp) ABORT;
+               if (!EC_GROUP_copy(tmp, group));
+               EC_GROUP_free(group);
+               group = tmp;
+       }
+       
        if (!EC_GROUP_get_curve_GFp(group, p, a, b, ctx)) ABORT;
 
        fprintf(stdout, "Curve defined by Weierstrass equation\n     y^2 = x^3 + a*x + b  (mod 0x");
@@ -163,8 +248,16 @@ int main(int argc, char *argv[])
                if (!EC_POINT_add(group, P, P, Q, ctx)) ABORT;
 
 #if 0 /* optional */
-               if (!EC_POINT_make_affine(group, P, ctx)) ABORT;
+               {
+                       EC_POINT *points[3];
+               
+                       points[0] = R;
+                       points[1] = Q;
+                       points[2] = P;
+                       if (!EC_POINTs_make_affine(group, 2, points, ctx)) ABORT;
+               }
 #endif
+
                }
        while (!EC_POINT_is_at_infinity(group, P));
 
@@ -204,7 +297,240 @@ int main(int argc, char *argv[])
        if (!EC_POINT_invert(group, P, ctx)) ABORT;
        if (0 != EC_POINT_cmp(group, P, R, ctx)) ABORT;
 
-       /* ... */
+
+       /* Curve P-192 (FIPS PUB 186-2, App. 6) */
+       
+       if (!BN_hex2bn(&p, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF")) ABORT;
+       if (1 != BN_is_prime(p, BN_prime_checks, 0, ctx, NULL)) ABORT;
+       if (!BN_hex2bn(&a, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC")) ABORT;
+       if (!BN_hex2bn(&b, "64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1")) ABORT;
+       if (!EC_GROUP_set_curve_GFp(group, p, a, b, ctx)) ABORT;
+
+       if (!BN_hex2bn(&x, "188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012")) ABORT;
+       if (!EC_POINT_set_compressed_coordinates_GFp(group, P, x, 1, ctx)) ABORT;
+       if (!EC_POINT_is_on_curve(group, P, ctx)) ABORT;
+       if (!BN_hex2bn(&z, "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831")) ABORT;
+       if (!EC_GROUP_set_generator(group, P, z, BN_value_one())) ABORT;
+
+       if (!EC_POINT_get_affine_coordinates_GFp(group, P, x, y, ctx)) ABORT;
+       fprintf(stdout, "\nNIST curve P-192 -- Generator:\n     x = 0x");
+       BN_print_fp(stdout, x);
+       fprintf(stdout, "\n     y = 0x");
+       BN_print_fp(stdout, y);
+       fprintf(stdout, "\n");
+       /* G_y value taken from the standard: */
+       if (!BN_hex2bn(&z, "07192B95FFC8DA78631011ED6B24CDD573F977A11E794811")) ABORT;
+       if (0 != BN_cmp(y, z)) ABORT;
+       
+       fprintf(stdout, "verify group order ... ");
+       if (!EC_GROUP_get_order(group, z, ctx)) ABORT;
+       if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT;
+       if (!EC_POINT_is_at_infinity(group, Q)) ABORT;
+       fprintf(stdout, "ok\n");
+
+       if (!(P_192 = EC_GROUP_new(EC_GROUP_method_of(group)))) ABORT;
+       if (!EC_GROUP_copy(P_192, group)) ABORT;
+
+
+       /* Curve P-224 (FIPS PUB 186-2, App. 6) */
+       
+       if (!BN_hex2bn(&p, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001")) ABORT;
+       if (1 != BN_is_prime(p, BN_prime_checks, 0, ctx, NULL)) ABORT;
+       if (!BN_hex2bn(&a, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFE")) ABORT;
+       if (!BN_hex2bn(&b, "B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4")) ABORT;
+       if (!EC_GROUP_set_curve_GFp(group, p, a, b, ctx)) ABORT;
+
+       if (!BN_hex2bn(&x, "B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21")) ABORT;
+       if (!EC_POINT_set_compressed_coordinates_GFp(group, P, x, 0, ctx)) ABORT;
+       if (!EC_POINT_is_on_curve(group, P, ctx)) ABORT;
+       if (!BN_hex2bn(&z, "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D")) ABORT;
+       if (!EC_GROUP_set_generator(group, P, z, BN_value_one())) ABORT;
+
+       if (!EC_POINT_get_affine_coordinates_GFp(group, P, x, y, ctx)) ABORT;
+       fprintf(stdout, "\nNIST curve P-224 -- Generator:\n     x = 0x");
+       BN_print_fp(stdout, x);
+       fprintf(stdout, "\n     y = 0x");
+       BN_print_fp(stdout, y);
+       fprintf(stdout, "\n");
+       /* G_y value taken from the standard: */
+       if (!BN_hex2bn(&z, "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34")) ABORT;
+       if (0 != BN_cmp(y, z)) ABORT;
+       
+       fprintf(stdout, "verify group order ... ");
+       if (!EC_GROUP_get_order(group, z, ctx)) ABORT;
+       if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT;
+       if (!EC_POINT_is_at_infinity(group, Q)) ABORT;
+       fprintf(stdout, "ok\n");
+       
+       if (!(P_224 = EC_GROUP_new(EC_GROUP_method_of(group)))) ABORT;
+       if (!EC_GROUP_copy(P_224, group)) ABORT;
+
+
+       /* Curve P-256 (FIPS PUB 186-2, App. 6) */
+       
+       if (!BN_hex2bn(&p, "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")) ABORT;
+       if (1 != BN_is_prime(p, BN_prime_checks, 0, ctx, NULL)) ABORT;
+       if (!BN_hex2bn(&a, "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")) ABORT;
+       if (!BN_hex2bn(&b, "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")) ABORT;
+       if (!EC_GROUP_set_curve_GFp(group, p, a, b, ctx)) ABORT;
+
+       if (!BN_hex2bn(&x, "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296")) ABORT;
+       if (!EC_POINT_set_compressed_coordinates_GFp(group, P, x, 1, ctx)) ABORT;
+       if (!EC_POINT_is_on_curve(group, P, ctx)) ABORT;
+       if (!BN_hex2bn(&z, "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E"
+               "84F3B9CAC2FC632551")) ABORT;
+       if (!EC_GROUP_set_generator(group, P, z, BN_value_one())) ABORT;
+
+       if (!EC_POINT_get_affine_coordinates_GFp(group, P, x, y, ctx)) ABORT;
+       fprintf(stdout, "\nNIST curve P-256 -- Generator:\n     x = 0x");
+       BN_print_fp(stdout, x);
+       fprintf(stdout, "\n     y = 0x");
+       BN_print_fp(stdout, y);
+       fprintf(stdout, "\n");
+       /* G_y value taken from the standard: */
+       if (!BN_hex2bn(&z, "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")) ABORT;
+       if (0 != BN_cmp(y, z)) ABORT;
+       
+       fprintf(stdout, "verify group order ... ");
+       if (!EC_GROUP_get_order(group, z, ctx)) ABORT;
+       if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT;
+       if (!EC_POINT_is_at_infinity(group, Q)) ABORT;
+       fprintf(stdout, "ok\n");
+       
+       if (!(P_256 = EC_GROUP_new(EC_GROUP_method_of(group)))) ABORT;
+       if (!EC_GROUP_copy(P_256, group)) ABORT;
+
+
+       /* Curve P-384 (FIPS PUB 186-2, App. 6) */
+       
+       if (!BN_hex2bn(&p, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+               "FFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF")) ABORT;
+       if (1 != BN_is_prime(p, BN_prime_checks, 0, ctx, NULL)) ABORT;
+       if (!BN_hex2bn(&a, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+               "FFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFC")) ABORT;
+       if (!BN_hex2bn(&b, "B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141"
+               "120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF")) ABORT;
+       if (!EC_GROUP_set_curve_GFp(group, p, a, b, ctx)) ABORT;
+
+       if (!BN_hex2bn(&x, "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B"
+               "9859F741E082542A385502F25DBF55296C3A545E3872760AB7")) ABORT;
+       if (!EC_POINT_set_compressed_coordinates_GFp(group, P, x, 1, ctx)) ABORT;
+       if (!EC_POINT_is_on_curve(group, P, ctx)) ABORT;
+       if (!BN_hex2bn(&z, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+               "FFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973")) ABORT;
+       if (!EC_GROUP_set_generator(group, P, z, BN_value_one())) ABORT;
+
+       if (!EC_POINT_get_affine_coordinates_GFp(group, P, x, y, ctx)) ABORT;
+       fprintf(stdout, "\nNIST curve P-384 -- Generator:\n     x = 0x");
+       BN_print_fp(stdout, x);
+       fprintf(stdout, "\n     y = 0x");
+       BN_print_fp(stdout, y);
+       fprintf(stdout, "\n");
+       /* G_y value taken from the standard: */
+       if (!BN_hex2bn(&z, "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A14"
+               "7CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F")) ABORT;
+       if (0 != BN_cmp(y, z)) ABORT;
+       
+       fprintf(stdout, "verify group order ... ");
+       if (!EC_GROUP_get_order(group, z, ctx)) ABORT;
+       if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT;
+       if (!EC_POINT_is_at_infinity(group, Q)) ABORT;
+       fprintf(stdout, "ok\n");
+       
+       if (!(P_384 = EC_GROUP_new(EC_GROUP_method_of(group)))) ABORT;
+       if (!EC_GROUP_copy(P_384, group)) ABORT;
+
+
+       /* Curve P-521 (FIPS PUB 186-2, App. 6) */
+       
+       if (!BN_hex2bn(&p, "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+               "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+               "FFFFFFFFFFFFFFFFFFFFFFFFFFFF")) ABORT;
+       if (1 != BN_is_prime(p, BN_prime_checks, 0, ctx, NULL)) ABORT;
+       if (!BN_hex2bn(&a, "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+               "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+               "FFFFFFFFFFFFFFFFFFFFFFFFFFFC")) ABORT;
+       if (!BN_hex2bn(&b, "051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B"
+               "315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573"
+               "DF883D2C34F1EF451FD46B503F00")) ABORT;
+       if (!EC_GROUP_set_curve_GFp(group, p, a, b, ctx)) ABORT;
+
+       if (!BN_hex2bn(&x, "C6858E06B70404E9CD9E3ECB662395B4429C648139053F"
+               "B521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B"
+               "3C1856A429BF97E7E31C2E5BD66")) ABORT;
+       if (!EC_POINT_set_compressed_coordinates_GFp(group, P, x, 0, ctx)) ABORT;
+       if (!EC_POINT_is_on_curve(group, P, ctx)) ABORT;
+       if (!BN_hex2bn(&z, "1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+               "FFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5"
+               "C9B8899C47AEBB6FB71E91386409")) ABORT;
+       if (!EC_GROUP_set_generator(group, P, z, BN_value_one())) ABORT;
+
+       if (!EC_POINT_get_affine_coordinates_GFp(group, P, x, y, ctx)) ABORT;
+       fprintf(stdout, "\nNIST curve P-521 -- Generator:\n     x = 0x");
+       BN_print_fp(stdout, x);
+       fprintf(stdout, "\n     y = 0x");
+       BN_print_fp(stdout, y);
+       fprintf(stdout, "\n");
+       /* G_y value taken from the standard: */
+       if (!BN_hex2bn(&z, "11839296A789A3BC0045C8A5FB42C7D1BD998F54449579"
+               "B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C"
+               "7086A272C24088BE94769FD16650")) ABORT;
+       if (0 != BN_cmp(y, z)) ABORT;
+       
+       fprintf(stdout, "verify group order ... ");
+       if (!EC_GROUP_get_order(group, z, ctx)) ABORT;
+       if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT;
+       if (!EC_POINT_is_at_infinity(group, Q)) ABORT;
+       fprintf(stdout, "ok\n");
+
+       if (!(P_521 = EC_GROUP_new(EC_GROUP_method_of(group)))) ABORT;
+       if (!EC_GROUP_copy(P_521, group)) ABORT;
+
+
+       /* more tests using the last curve */
+
+       if (!EC_POINT_copy(Q, P)) ABORT;
+       if (EC_POINT_is_at_infinity(group, Q)) ABORT;
+       if (!EC_POINT_dbl(group, P, P, ctx)) ABORT;
+       if (!EC_POINT_is_on_curve(group, P, ctx)) ABORT;
+       if (!EC_POINT_invert(group, Q, ctx)) ABORT; /* P = -2Q */
+
+       if (!EC_POINT_add(group, R, P, Q, ctx)) ABORT;
+       if (!EC_POINT_add(group, R, R, Q, ctx)) ABORT;
+       if (!EC_POINT_is_at_infinity(group, R)) ABORT; /* R = P + 2Q */
+
+       {
+               EC_POINT *points[2];
+               BIGNUM *scalars[2];
+       
+               if (EC_POINT_is_at_infinity(group, Q)) ABORT;
+
+               if (!BN_add(y, z, BN_value_one())) ABORT;
+               if (BN_is_odd(y)) ABORT;
+               if (!BN_rshift1(y, y)) ABORT;
+
+               points[0] = Q;
+               points[1] = Q;
+               scalars[0] = y; /* (group order + 1)/2,  so  y*Q + y*Q = Q */
+               scalars[1] = y;
+
+               fprintf(stdout, "simultaneous multiplication ... ");
+
+               /* z is still the group order */
+               if (!EC_POINTs_mul(group, P, NULL, 2, points, scalars, ctx)) ABORT;
+               if (!EC_POINTs_mul(group, R, z, 2, points, scalars, ctx)) ABORT;
+               if (0 != EC_POINT_cmp(group, P, R, ctx)) ABORT;
+               if (0 != EC_POINT_cmp(group, R, Q, ctx)) ABORT;
+
+               fprintf(stdout, "ok\n\n");
+       }
+
+
+#if 0
+       timings(P_192, 0, ctx);
+       timings(P_192, 1, ctx);
+#endif
+
 
        if (ctx)
                BN_CTX_free(ctx);
@@ -215,6 +541,12 @@ int main(int argc, char *argv[])
        EC_POINT_free(R);
        BN_free(x); BN_free(y); BN_free(z);
 
+       if (P_192) EC_GROUP_free(P_192);
+       if (P_224) EC_GROUP_free(P_224);
+       if (P_256) EC_GROUP_free(P_256);
+       if (P_384) EC_GROUP_free(P_384);
+       if (P_521) EC_GROUP_free(P_521);
+
        ERR_free_strings();
        ERR_remove_state(0);
        CRYPTO_mem_leaks_fp(stderr);