Add functions EC_POINT_mul and EC_GROUP_precompute.
authorBodo Möller <bodo@openssl.org>
Sun, 11 Mar 2001 12:27:24 +0000 (12:27 +0000)
committerBodo Möller <bodo@openssl.org>
Sun, 11 Mar 2001 12:27:24 +0000 (12:27 +0000)
The latter does nothing for now, but its existence means
that applications can request precomputation when appropriate.

CHANGES
crypto/ec/ec.h
crypto/ec/ec_err.c
crypto/ec/ec_mult.c
crypto/ec/ectest.c

diff --git a/CHANGES b/CHANGES
index c516fe7..8ed1b98 100644 (file)
--- a/CHANGES
+++ b/CHANGES
@@ -4,7 +4,11 @@
  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.
+     of an arbitrary number of elliptic curve points, optionally
+     including the generator defined for the EC_GROUP.
+     EC_POINT_mul is a simple wrapper function for the typical case
+     that the point list has just one item (besides the optional
+     generator).
      [Bodo Moeller]
 
   *) First EC_METHODs for curves over GF(p):
index 0842444..499c933 100644 (file)
@@ -160,7 +160,9 @@ 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 *);
 
 
-int EC_POINTs_mul(const EC_GROUP *, EC_POINT *r, BIGNUM *, size_t num, EC_POINT *[], BIGNUM *[], 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 *);
+int EC_GROUP_precompute(EC_GROUP *, BN_CTX *);
 
 
 
@@ -193,6 +195,7 @@ void ERR_load_EC_strings(void);
 #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_PRECOMPUTE                        142
 #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
@@ -231,6 +234,7 @@ void ERR_load_EC_strings(void);
 #define EC_R_POINT_IS_NOT_ON_CURVE                      107
 #define EC_R_SLOT_FULL                                  108
 #define EC_R_UNDEFINED_GENERATOR                        113
+#define EC_R_UNKNOWN_ORDER                              114
 
 #ifdef  __cplusplus
 }
index f885015..c0573e8 100644 (file)
@@ -86,6 +86,7 @@ static ERR_STRING_DATA EC_str_functs[]=
 {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_PRECOMPUTE,0),       "EC_GROUP_precompute"},
 {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"},
@@ -127,6 +128,7 @@ static ERR_STRING_DATA EC_str_reasons[]=
 {EC_R_POINT_IS_NOT_ON_CURVE              ,"point is not on curve"},
 {EC_R_SLOT_FULL                          ,"slot full"},
 {EC_R_UNDEFINED_GENERATOR                ,"undefined generator"},
+{EC_R_UNKNOWN_ORDER                      ,"unknown order"},
 {0,NULL}
        };
 
index 01574d8..0a749e8 100644 (file)
@@ -77,8 +77,8 @@
  *      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)
+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)
        {
        BN_CTX *new_ctx = NULL;
        EC_POINT *generator = NULL;
@@ -228,7 +228,7 @@ int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, BIGNUM *scalar,
                        {
                        if (wbits[i] == 0)
                                {
-                               BIGNUM *s;
+                               const BIGNUM *s;
 
                                s = i < num ? scalars[i] : scalar;
 
@@ -295,3 +295,59 @@ int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, BIGNUM *scalar,
                }
        return ret;
        }
+
+
+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_GROUP_precompute(EC_GROUP *group, BN_CTX *ctx)
+       {
+       const EC_POINT *generator;
+       BN_CTX *new_ctx = NULL;
+       BIGNUM *order;
+       int ret = 0;
+
+       generator = EC_GROUP_get0_generator(group);
+       if (generator == NULL)
+               {
+               ECerr(EC_F_EC_GROUP_PRECOMPUTE, EC_R_UNDEFINED_GENERATOR);
+               return 0;
+               }
+
+       if (ctx == NULL)
+               {
+               ctx = new_ctx = BN_CTX_new();
+               if (ctx == NULL)
+                       return 0;
+               }
+       
+       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 (BN_is_zero(order))
+               {
+               ECerr(EC_F_EC_GROUP_PRECOMPUTE, EC_R_UNKNOWN_ORDER);
+               goto err;
+               }
+
+       /* TODO */
+
+       ret = 1;
+       
+ err:
+       BN_CTX_end(ctx);
+       if (new_ctx != NULL)
+               BN_CTX_free(new_ctx);
+       return ret;
+       }
index 766a0db..1ccc9ab 100644 (file)
@@ -80,8 +80,6 @@ void timings(EC_GROUP *group, int simult, BN_CTX *ctx)
        int i, j;
        BIGNUM *s, *s0;
        EC_POINT *P;
-       EC_POINT *points[1];
-       BIGNUM *scalars[1];
                
        s = BN_new();
        s0 = BN_new();
@@ -97,9 +95,6 @@ void timings(EC_GROUP *group, int simult, BN_CTX *ctx)
        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++)
                {
@@ -110,7 +105,7 @@ void timings(EC_GROUP *group, int simult, BN_CTX *ctx)
                        }
                for (j = 0; j < 10; j++)
                        {
-                       if (!EC_POINTs_mul(group, P, s, simult != 0, points, scalars, ctx)) ABORT;
+                       if (!EC_POINT_mul(group, P, s, simult ? P : NULL, simult ? s0 : NULL, ctx)) ABORT;
                        }
                fprintf(stdout, ".");
                fflush(stdout);
@@ -322,12 +317,17 @@ int main(int argc, char *argv[])
        if (!BN_hex2bn(&z, "07192B95FFC8DA78631011ED6B24CDD573F977A11E794811")) ABORT;
        if (0 != BN_cmp(y, z)) ABORT;
        
-       fprintf(stdout, "verify group order ... ");
+       fprintf(stdout, "verify group order ...");
        fflush(stdout);
        if (!EC_GROUP_get_order(group, z, ctx)) ABORT;
-       if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT;
+       if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT;
+       if (!EC_POINT_is_at_infinity(group, Q)) ABORT;
+       fprintf(stdout, ".");
+       fflush(stdout);
+       if (!EC_GROUP_precompute(group, ctx)) ABORT;
+       if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT;
        if (!EC_POINT_is_at_infinity(group, Q)) ABORT;
-       fprintf(stdout, "ok\n");
+       fprintf(stdout, " ok\n");
 
        if (!(P_192 = EC_GROUP_new(EC_GROUP_method_of(group)))) ABORT;
        if (!EC_GROUP_copy(P_192, group)) ABORT;
@@ -357,13 +357,18 @@ int main(int argc, char *argv[])
        if (!BN_hex2bn(&z, "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34")) ABORT;
        if (0 != BN_cmp(y, z)) ABORT;
        
-       fprintf(stdout, "verify group order ... ");
+       fprintf(stdout, "verify group order ...");
        fflush(stdout);
        if (!EC_GROUP_get_order(group, z, ctx)) ABORT;
-       if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT;
+       if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT;
        if (!EC_POINT_is_at_infinity(group, Q)) ABORT;
-       fprintf(stdout, "ok\n");
-       
+       fprintf(stdout, ".");
+       fflush(stdout);
+       if (!EC_GROUP_precompute(group, ctx)) ABORT;
+       if (!EC_POINT_mul(group, Q, z, 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;
 
@@ -393,13 +398,18 @@ int main(int argc, char *argv[])
        if (!BN_hex2bn(&z, "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")) ABORT;
        if (0 != BN_cmp(y, z)) ABORT;
        
-       fprintf(stdout, "verify group order ... ");
+       fprintf(stdout, "verify group order ...");
        fflush(stdout);
        if (!EC_GROUP_get_order(group, z, ctx)) ABORT;
-       if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT;
+       if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT;
        if (!EC_POINT_is_at_infinity(group, Q)) ABORT;
-       fprintf(stdout, "ok\n");
-       
+       fprintf(stdout, ".");
+       fflush(stdout);
+       if (!EC_GROUP_precompute(group, ctx)) ABORT;
+       if (!EC_POINT_mul(group, Q, z, 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;
 
@@ -434,13 +444,18 @@ int main(int argc, char *argv[])
                "7CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F")) ABORT;
        if (0 != BN_cmp(y, z)) ABORT;
        
-       fprintf(stdout, "verify group order ... ");
+       fprintf(stdout, "verify group order ...");
        fflush(stdout);
        if (!EC_GROUP_get_order(group, z, ctx)) ABORT;
-       if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT;
+       if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT;
        if (!EC_POINT_is_at_infinity(group, Q)) ABORT;
-       fprintf(stdout, "ok\n");
-       
+       fprintf(stdout, ".");
+       fflush(stdout);
+       if (!EC_GROUP_precompute(group, ctx)) ABORT;
+       if (!EC_POINT_mul(group, Q, z, 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;
 
@@ -481,12 +496,17 @@ int main(int argc, char *argv[])
                "7086A272C24088BE94769FD16650")) ABORT;
        if (0 != BN_cmp(y, z)) ABORT;
        
-       fprintf(stdout, "verify group order ... ");
+       fprintf(stdout, "verify group order ...");
        fflush(stdout);
        if (!EC_GROUP_get_order(group, z, ctx)) ABORT;
-       if (!EC_POINTs_mul(group, Q, z, 0, NULL, NULL, ctx)) ABORT;
+       if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT;
+       if (!EC_POINT_is_at_infinity(group, Q)) ABORT;
+       fprintf(stdout, ".");
+       fflush(stdout);
+       if (!EC_GROUP_precompute(group, ctx)) ABORT;
+       if (!EC_POINT_mul(group, Q, z, NULL, NULL, ctx)) ABORT;
        if (!EC_POINT_is_at_infinity(group, Q)) ABORT;
-       fprintf(stdout, "ok\n");
+       fprintf(stdout, " ok\n");
 
        if (!(P_521 = EC_GROUP_new(EC_GROUP_method_of(group)))) ABORT;
        if (!EC_GROUP_copy(P_521, group)) ABORT;
@@ -505,17 +525,17 @@ int main(int argc, char *argv[])
        if (!EC_POINT_is_at_infinity(group, R)) ABORT; /* R = P + 2Q */
 
        {
-               EC_POINT *points[2];
-               BIGNUM *scalars[2];
+               const EC_POINT *points[3];
+               const BIGNUM *scalars[3];
        
                if (EC_POINT_is_at_infinity(group, Q)) ABORT;
+               points[0] = Q;
+               points[1] = Q;
+               points[2] = Q;
 
                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;
 
@@ -534,20 +554,30 @@ int main(int argc, char *argv[])
                if (!BN_pseudo_rand(y, BN_num_bits(y), 0, 0)) ABORT;
                if (!BN_copy(z, y)) ABORT;
                z->neg = 1;
-
-               points[0] = Q;
-               points[1] = Q;
                scalars[0] = y;
-               scalars[1] = z;
+               scalars[1] = z; /* z = -y */
 
                if (!EC_POINTs_mul(group, P, NULL, 2, points, scalars, ctx)) ABORT;
                if (!EC_POINT_is_at_infinity(group, P)) ABORT;
 
+               fprintf(stdout, ".");
+               fflush(stdout);
+
+               if (!BN_pseudo_rand(x, BN_num_bits(y) - 1, 0, 0)) ABORT;
+               if (!BN_add(z, x, y)) ABORT;
+               z->neg = 1;
+               scalars[0] = x;
+               scalars[1] = y;
+               scalars[2] = z; /* z = -(x+y) */
+
+               if (!EC_POINTs_mul(group, P, NULL, 3, points, scalars, ctx)) ABORT;
+               if (!EC_POINT_is_at_infinity(group, P)) ABORT;
+
                fprintf(stdout, " ok\n\n");
        }
 
 
-#if 0
+#if 1
        timings(P_192, 0, ctx);
        timings(P_192, 1, ctx);
        timings(P_224, 0, ctx);