summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorWerner Koch <wk@gnupg.org>2013-09-03 12:01:15 +0200
committerWerner Koch <wk@gnupg.org>2013-09-04 11:25:06 +0200
commitc26be7a337d0bf98193bc58e043209e46d0769bb (patch)
tree71f15800908d68666f80fee8c42a7b344f5be178
parent8698530b2f9ef95542f1dd550961de7af86cc256 (diff)
downloadlibgcrypt-c26be7a337d0bf98193bc58e043209e46d0769bb.tar.gz
Prepare support for non-Weierstrass EC equations.
* 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>
-rw-r--r--cipher/ecc-common.h5
-rw-r--r--cipher/ecc-curves.c39
-rw-r--r--cipher/ecc-misc.c19
-rw-r--r--cipher/ecc.c8
-rw-r--r--mpi/ec.c92
-rw-r--r--src/ec-context.h4
-rw-r--r--src/mpi.h12
-rw-r--r--tests/Makefile.am7
8 files changed, 167 insertions, 19 deletions
diff --git a/cipher/ecc-common.h b/cipher/ecc-common.h
index 94da73e1..614baae0 100644
--- a/cipher/ecc-common.h
+++ b/cipher/ecc-common.h
@@ -23,9 +23,11 @@
/* 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);
diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index e813b6b4..e956dad8 100644
--- a/cipher/ecc-curves.c
+++ b/cipher/ecc-curves.c
@@ -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
diff --git a/cipher/ecc-misc.c b/cipher/ecc-misc.c
index 5e06bef9..5c86121a 100644
--- a/cipher/ecc-misc.c
+++ b/cipher/ecc-misc.c
@@ -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)
{
diff --git a/cipher/ecc.c b/cipher/ecc.c
index 9174f9bc..8a7ca0be 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -108,8 +108,8 @@ _gcry_register_pk_ecc_progress (void (*cb) (void *, const char *,
-/****************
- * 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]);
diff --git a/mpi/ec.c b/mpi/ec.c
index 8fb47a30..54fa0286 100644
--- 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,
-/* 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.
diff --git a/src/ec-context.h b/src/ec-context.h
index 7002d475..7df35769 100644
--- a/src/ec-context.h
+++ b/src/ec-context.h
@@ -23,8 +23,10 @@
/* 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. */
diff --git a/src/mpi.h b/src/mpi.h
index fd265bf2..0114dba7 100644
--- 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;
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 35bcd60b..4cbc34bf 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -18,9 +18,10 @@
## 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.