Prepare support for non-Weierstrass EC equations.
authorWerner Koch <wk@gnupg.org>
Tue, 3 Sep 2013 10:01:15 +0000 (12:01 +0200)
committerWerner Koch <wk@gnupg.org>
Wed, 4 Sep 2013 09:25:06 +0000 (11:25 +0200)
* src/mpi.h (gcry_mpi_ec_models): New.
* src/ec-context.h (mpi_ec_ctx_s): Add MODEL.
* cipher/ecc-common.h (elliptic_curve_t): Ditto.
* cipher/ecc-curves.c (ecc_domain_parms_t): Ditto.
(domain_parms): Mark als as Weierstrass.
(_gcry_ecc_fill_in_curve): Check model.
(_gcry_ecc_get_curve): Set model to Weierstrass.
* cipher/ecc-misc.c (_gcry_ecc_model2str): New.
* cipher/ecc.c (generate_key, ecc_generate_ext): Print model in the
debug output.

* mpi/ec.c (_gcry_mpi_ec_dup_point): Switch depending on model.
Factor code out to ...
(dup_point_weierstrass): new.
(dup_point_montgomery, dup_point_twistededwards): New stub functions.
(_gcry_mpi_ec_add_points): Switch depending on model.  Factor code out
to ...
(add_points_weierstrass): new.
(add_points_montgomery, add_points_twistededwards): New stub
functions.

* tests/Makefile.am (TESTS): Reorder tests.

Signed-off-by: Werner Koch <wk@gnupg.org>
cipher/ecc-common.h
cipher/ecc-curves.c
cipher/ecc-misc.c
cipher/ecc.c
mpi/ec.c
src/ec-context.h
src/mpi.h
tests/Makefile.am

index 94da73e..614baae 100644 (file)
 /* Definition of a curve.  */
 typedef struct
 {
+  enum gcry_mpi_ec_models model;/* The model descrinbing this curve.  */
   gcry_mpi_t p;         /* Prime specifying the field GF(p).  */
   gcry_mpi_t a;         /* First coefficient of the Weierstrass equation.  */
-  gcry_mpi_t b;         /* Second coefficient of the Weierstrass equation.  */
+  gcry_mpi_t b;         /* Second coefficient of the Weierstrass equation.
+                           or d as used by Twisted Edwards curves.  */
   mpi_point_struct G;   /* Base point (generator).  */
   gcry_mpi_t n;         /* Order of G.  */
   const char *name;     /* Name of the curve or NULL.  */
@@ -73,6 +75,7 @@ gcry_sexp_t     _gcry_ecc_get_param_sexp (const char *name);
 /*-- ecc-misc.c --*/
 void _gcry_ecc_curve_free (elliptic_curve_t *E);
 elliptic_curve_t _gcry_ecc_curve_copy (elliptic_curve_t E);
+const char *_gcry_ecc_model2str (enum gcry_mpi_ec_models model);
 gcry_mpi_t   _gcry_ecc_ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p);
 gcry_error_t _gcry_ecc_os2ec (mpi_point_t result, gcry_mpi_t value);
 
index e813b6b..e956dad 100644 (file)
@@ -77,8 +77,12 @@ typedef struct
   const char *desc;           /* Description of the curve.  */
   unsigned int nbits;         /* Number of bits.  */
   unsigned int fips:1;        /* True if this is a FIPS140-2 approved curve. */
+
+  enum gcry_mpi_ec_models model;/* The model describing this curve.  */
+
   const char *p;              /* Order of the prime field.  */
-  const char *a, *b;          /* The coefficients. */
+  const char *a, *b;          /* The coefficients.  For Twisted Edwards
+                                 Curves b is used for d.  */
   const char *n;              /* The order of the base point.  */
   const char *g_x, *g_y;      /* Base point.  */
 } ecc_domain_parms_t;
@@ -89,6 +93,7 @@ static const ecc_domain_parms_t domain_parms[] =
   {
     {
       "NIST P-192", 192, 1,
+      MPI_EC_WEIERSTRASS,
       "0xfffffffffffffffffffffffffffffffeffffffffffffffff",
       "0xfffffffffffffffffffffffffffffffefffffffffffffffc",
       "0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1",
@@ -99,6 +104,7 @@ static const ecc_domain_parms_t domain_parms[] =
     },
     {
       "NIST P-224", 224, 1,
+      MPI_EC_WEIERSTRASS,
       "0xffffffffffffffffffffffffffffffff000000000000000000000001",
       "0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe",
       "0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4",
@@ -109,6 +115,7 @@ static const ecc_domain_parms_t domain_parms[] =
     },
     {
       "NIST P-256", 256, 1,
+      MPI_EC_WEIERSTRASS,
       "0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff",
       "0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc",
       "0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b",
@@ -119,6 +126,7 @@ static const ecc_domain_parms_t domain_parms[] =
     },
     {
       "NIST P-384", 384, 1,
+      MPI_EC_WEIERSTRASS,
       "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
       "ffffffff0000000000000000ffffffff",
       "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe"
@@ -135,6 +143,7 @@ static const ecc_domain_parms_t domain_parms[] =
     },
     {
       "NIST P-521", 521, 1,
+      MPI_EC_WEIERSTRASS,
       "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
       "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff",
       "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
@@ -151,6 +160,7 @@ static const ecc_domain_parms_t domain_parms[] =
     },
 
     { "brainpoolP160r1", 160, 0,
+      MPI_EC_WEIERSTRASS,
       "0xe95e4a5f737059dc60dfc7ad95b3d8139515620f",
       "0x340e7be2a280eb74e2be61bada745d97e8f7c300",
       "0x1e589a8595423412134faa2dbdec95c8d8675e58",
@@ -160,6 +170,7 @@ static const ecc_domain_parms_t domain_parms[] =
     },
 
     { "brainpoolP192r1", 192, 0,
+      MPI_EC_WEIERSTRASS,
       "0xc302f41d932a36cda7a3463093d18db78fce476de1a86297",
       "0x6a91174076b1e0e19c39c031fe8685c1cae040e5c69a28ef",
       "0x469a28ef7c28cca3dc721d044f4496bcca7ef4146fbf25c9",
@@ -169,6 +180,7 @@ static const ecc_domain_parms_t domain_parms[] =
     },
 
     { "brainpoolP224r1", 224, 0,
+      MPI_EC_WEIERSTRASS,
       "0xd7c134aa264366862a18302575d1d787b09f075797da89f57ec8c0ff",
       "0x68a5e62ca9ce6c1c299803a6c1530b514e182ad8b0042a59cad29f43",
       "0x2580f63ccfe44138870713b1a92369e33e2135d266dbb372386c400b",
@@ -178,6 +190,7 @@ static const ecc_domain_parms_t domain_parms[] =
     },
 
     { "brainpoolP256r1", 256, 0,
+      MPI_EC_WEIERSTRASS,
       "0xa9fb57dba1eea9bc3e660a909d838d726e3bf623d52620282013481d1f6e5377",
       "0x7d5a0975fc2c3057eef67530417affe7fb8055c126dc5c6ce94a4b44f330b5d9",
       "0x26dc5c6ce94a4b44f330b5d9bbd77cbf958416295cf7e1ce6bccdc18ff8c07b6",
@@ -187,6 +200,7 @@ static const ecc_domain_parms_t domain_parms[] =
     },
 
     { "brainpoolP320r1", 320, 0,
+      MPI_EC_WEIERSTRASS,
       "0xd35e472036bc4fb7e13c785ed201e065f98fcfa6f6f40def4f92b9ec7893ec28"
       "fcd412b1f1b32e27",
       "0x3ee30b568fbab0f883ccebd46d3f3bb8a2a73513f5eb79da66190eb085ffa9f4"
@@ -202,6 +216,7 @@ static const ecc_domain_parms_t domain_parms[] =
     },
 
     { "brainpoolP384r1", 384, 0,
+      MPI_EC_WEIERSTRASS,
       "0x8cb91e82a3386d280f5d6f7e50e641df152f7109ed5456b412b1da197fb71123"
       "acd3a729901d1a71874700133107ec53",
       "0x7bc382c63d8c150c3c72080ace05afa0c2bea28e4fb22787139165efba91f90f"
@@ -217,6 +232,7 @@ static const ecc_domain_parms_t domain_parms[] =
     },
 
     { "brainpoolP512r1", 512, 0,
+      MPI_EC_WEIERSTRASS,
       "0xaadd9db8dbe9c48b3fd4e6ae33c9fc07cb308db3b3c9d20ed6639cca70330871"
       "7d4d9b009bc66842aecda12ae6a380e62881ff2f2d82c68528aa6056583a48f3",
       "0x7830a3318b603b89e2327145ac234cc594cbdd8d3df91610a83441caea9863bc"
@@ -231,7 +247,7 @@ static const ecc_domain_parms_t domain_parms[] =
       "b2dcde494a5f485e5bca4bd88a2763aed1ca2b2fa8f0540678cd1e0f3ad80892"
     },
 
-    { NULL, 0, 0, NULL, NULL, NULL, NULL }
+    { NULL, 0, 0, 0, NULL, NULL, NULL, NULL }
   };
 
 
@@ -302,10 +318,23 @@ _gcry_ecc_fill_in_curve (unsigned int nbits, const char *name,
      possible to bypass this check by specifying the curve parameters
      directly.  */
   if (fips_mode () && !domain_parms[idx].fips )
+
     return GPG_ERR_NOT_SUPPORTED;
 
+  switch (domain_parms[idx].model)
+    {
+    case MPI_EC_WEIERSTRASS:
+      break;
+    case MPI_EC_TWISTEDEDWARDS:
+    case MPI_EC_MONTGOMERY:
+      return GPG_ERR_NOT_SUPPORTED;
+    default:
+      return GPG_ERR_BUG;
+    }
+
   if (r_nbits)
     *r_nbits = domain_parms[idx].nbits;
+
   curve->p = scanval (domain_parms[idx].p);
   curve->a = scanval (domain_parms[idx].a);
   curve->b = scanval (domain_parms[idx].b);
@@ -319,7 +348,8 @@ _gcry_ecc_fill_in_curve (unsigned int nbits, const char *name,
 }
 
 
-/* Return the name matching the parameters in PKEY.  */
+/* Return the name matching the parameters in PKEY.  This works only
+   with curves described by the Weierstrass equation. */
 const char *
 _gcry_ecc_get_curve (gcry_mpi_t *pkey, int iterator, unsigned int *r_nbits)
 {
@@ -347,6 +377,7 @@ _gcry_ecc_get_curve (gcry_mpi_t *pkey, int iterator, unsigned int *r_nbits)
   if (!pkey[0] || !pkey[1] || !pkey[2] || !pkey[3] || !pkey[4])
     return NULL;
 
+  E.model = MPI_EC_WEIERSTRASS;
   E.p = pkey[0];
   E.a = pkey[1];
   E.b = pkey[2];
@@ -505,7 +536,7 @@ point_from_keyparam (gcry_mpi_point_t *r_a,
 
 /* This function creates a new context for elliptic curve operations.
    Either KEYPARAM or CURVENAME must be given.  If both are given and
-   KEYPARAM has no curve parameter CURVENAME is used to add missing
+   KEYPARAM has no curve parameter, CURVENAME is used to add missing
    parameters.  On success 0 is returned and the new context stored at
    R_CTX.  On error NULL is stored at R_CTX and an error code is
    returned.  The context needs to be released using
index 5e06bef..5c86121 100644 (file)
@@ -64,6 +64,25 @@ _gcry_ecc_curve_copy (elliptic_curve_t E)
 }
 
 
+/*
+ * Return a description of the curve model.
+ */
+const char *
+_gcry_ecc_model2str (enum gcry_mpi_ec_models model)
+{
+  const char *str = "?";
+  switch (model)
+    {
+    case MPI_EC_WEIERSTRASS:    str = "Weierstrass"; break;
+    case MPI_EC_MONTGOMERY:     str = "Montgomery";  break;
+    case MPI_EC_TWISTEDEDWARDS: str = "Twisted Edwards"; break;
+    }
+  return str;
+}
+
+
+
+
 gcry_mpi_t
 _gcry_ecc_ec2os (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t p)
 {
index 9174f9b..8a7ca0b 100644 (file)
@@ -108,8 +108,8 @@ _gcry_register_pk_ecc_progress (void (*cb) (void *, const char *,
 
 \f
 
-/****************
- * Solve the right side of the equation that defines a curve.
+/*
+ * Solve the right side of the Weierstrass equation.
  */
 static gcry_mpi_t
 gen_y_2 (gcry_mpi_t x, elliptic_curve_t *base)
@@ -158,6 +158,7 @@ generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
 
   if (DBG_CIPHER)
     {
+      log_debug ("ecgen curve model: %s\n", _gcry_ecc_model2str (E.model));
       log_mpidump ("ecgen curve  p", E.p);
       log_mpidump ("ecgen curve  a", E.a);
       log_mpidump ("ecgen curve  b", E.b);
@@ -166,7 +167,7 @@ generate_key (ECC_secret_key *sk, unsigned int nbits, const char *name,
       log_mpidump ("ecgen curve Gy", E.G.y);
       log_mpidump ("ecgen curve Gz", E.G.z);
       if (E.name)
-        log_debug   ("ecgen curve used: %s\n", E.name);
+        log_debug ("ecgen curve used: %s\n", E.name);
     }
 
   random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM;
@@ -696,6 +697,7 @@ ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
 
   if (DBG_CIPHER)
     {
+      log_debug ("ecgen result model: %s\n", _gcry_ecc_model2str (sk.E.model));
       log_mpidump ("ecgen result p", skey[0]);
       log_mpidump ("ecgen result a", skey[1]);
       log_mpidump ("ecgen result b", skey[2]);
index 8fb47a3..54fa028 100644 (file)
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -684,9 +684,9 @@ _gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t point,
 
 
 \f
-/*  RESULT = 2 * POINT  */
-void
-_gcry_mpi_ec_dup_point (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
+/*  RESULT = 2 * POINT  (Weierstrass version). */
+static void
+dup_point_weierstrass (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
 {
 #define x3 (result->x)
 #define y3 (result->y)
@@ -767,12 +767,48 @@ _gcry_mpi_ec_dup_point (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
 }
 
 
+/*  RESULT = 2 * POINT  (Montgomery version). */
+static void
+dup_point_montgomery (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
+{
+  log_fatal ("%s: %s not yet supported\n",
+             "_gcry_mpi_ec_dup_point", "Montgomery");
+}
+
 
-/* RESULT = P1 + P2 */
+/*  RESULT = 2 * POINT  (Twisted Edwards version). */
+static void
+dup_point_twistededwards (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
+{
+  log_fatal ("%s: %s not yet supported\n",
+             "_gcry_mpi_ec_dup_point", "Twisted Edwards");
+}
+
+
+/*  RESULT = 2 * POINT  */
 void
-_gcry_mpi_ec_add_points (mpi_point_t result,
-                         mpi_point_t p1, mpi_point_t p2,
-                         mpi_ec_t ctx)
+_gcry_mpi_ec_dup_point (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)
+{
+  switch (ctx->model)
+    {
+    case MPI_EC_WEIERSTRASS:
+      dup_point_weierstrass (result, point, ctx);
+      break;
+    case MPI_EC_MONTGOMERY:
+      dup_point_montgomery (result, point, ctx);
+      break;
+    case MPI_EC_TWISTEDEDWARDS:
+      dup_point_twistededwards (result, point, ctx);
+      break;
+    }
+}
+
+
+/* RESULT = P1 + P2  (Weierstrass version).*/
+static void
+add_points_weierstrass (mpi_point_t result,
+                        mpi_point_t p1, mpi_point_t p2,
+                        mpi_ec_t ctx)
 {
 #define x1 (p1->x    )
 #define y1 (p1->y    )
@@ -910,6 +946,48 @@ _gcry_mpi_ec_add_points (mpi_point_t result,
 }
 
 
+/* RESULT = P1 + P2  (Montgomery version).*/
+static void
+add_points_montgomery (mpi_point_t result,
+                       mpi_point_t p1, mpi_point_t p2,
+                       mpi_ec_t ctx)
+{
+  log_fatal ("%s: %s not yet supported\n",
+             "_gcry_mpi_ec_add_points", "Montgomery");
+}
+
+
+/* RESULT = P1 + P2  (Twisted Edwards version).*/
+static void
+add_points_twistededwards (mpi_point_t result,
+                           mpi_point_t p1, mpi_point_t p2,
+                           mpi_ec_t ctx)
+{
+  log_fatal ("%s: %s not yet supported\n",
+             "_gcry_mpi_ec_add_points", "Twisted Edwards");
+}
+
+
+/* RESULT = P1 + P2 */
+void
+_gcry_mpi_ec_add_points (mpi_point_t result,
+                         mpi_point_t p1, mpi_point_t p2,
+                         mpi_ec_t ctx)
+{
+  switch (ctx->model)
+    {
+    case MPI_EC_WEIERSTRASS:
+      add_points_weierstrass (result, p1, p2, ctx);
+      break;
+    case MPI_EC_MONTGOMERY:
+      add_points_montgomery (result, p1, p2, ctx);
+      break;
+    case MPI_EC_TWISTEDEDWARDS:
+      add_points_twistededwards (result, p1, p2, ctx);
+      break;
+    }
+}
+
 
 /* Scalar point multiplication - the main function for ECC.  If takes
    an integer SCALAR and a POINT as well as the usual context CTX.
index 7002d47..7df3576 100644 (file)
 /* This context is used with all our EC functions. */
 struct mpi_ec_ctx_s
 {
+  enum gcry_mpi_ec_models model; /* The model describing this curve.  */
+
   /* Domain parameters.  Note that they may not all be set and if set
-     the MPIs may be flaged as constant.*/
+     the MPIs may be flaged as constant. */
   gcry_mpi_t p;         /* Prime specifying the field GF(p).  */
   gcry_mpi_t a;         /* First coefficient of the Weierstrass equation.  */
   gcry_mpi_t b;         /* Second coefficient of the Weierstrass equation.  */
index fd265bf..0114dba 100644 (file)
--- a/src/mpi.h
+++ b/src/mpi.h
@@ -272,6 +272,18 @@ void _gcry_mpi_get_point (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z,
 void _gcry_mpi_snatch_point (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z,
                              mpi_point_t point);
 
+/* Models describing an elliptic curve.  */
+enum gcry_mpi_ec_models
+  {
+
+    MPI_EC_WEIERSTRASS = 0,
+    MPI_EC_MONTGOMERY,
+    MPI_EC_TWISTEDEDWARDS
+    /* The equation for Twisted Edwards curves is
+          ax^2 + y^2 = 1 + bx^2y^2
+       Note that we use 'b' instead of the commonly used 'd'.  */
+  };
+
 /* Context used with elliptic curve functions.  */
 struct mpi_ec_ctx_s;
 typedef struct mpi_ec_ctx_s *mpi_ec_t;
index 35bcd60..4cbc34b 100644 (file)
 
 ## Process this file with automake to produce Makefile.in
 
-TESTS = version t-convert t-mpi-bit t-mpi-point prime basic \
-        mpitests tsexp keygen pubkey hmac keygrip fips186-dsa aeswrap \
-       curves t-kdf pkcs1v2 random dsa-rfc6979
+TESTS = version mpitests tsexp t-convert \
+       t-mpi-bit t-mpi-point curves \
+       prime basic keygen pubkey hmac t-kdf keygrip \
+       fips186-dsa aeswrap pkcs1v2 random dsa-rfc6979
 
 
 # The last test to run.