implement fast point multiplication with precomputation
authorBodo Möller <bodo@openssl.org>
Thu, 6 Feb 2003 19:25:12 +0000 (19:25 +0000)
committerBodo Möller <bodo@openssl.org>
Thu, 6 Feb 2003 19:25:12 +0000 (19:25 +0000)
Submitted by: Nils Larsch
Reviewed by: Bodo Moeller

15 files changed:
CHANGES
apps/speed.c
crypto/ec/ec.h
crypto/ec/ec2_mult.c
crypto/ec/ec2_smpl.c
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/evp/Makefile.ssl
util/mkerr.pl

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