diff options
author | Werner Koch <wk@gnupg.org> | 2013-09-03 12:01:15 +0200 |
---|---|---|
committer | Werner Koch <wk@gnupg.org> | 2013-09-04 11:25:06 +0200 |
commit | c26be7a337d0bf98193bc58e043209e46d0769bb (patch) | |
tree | 71f15800908d68666f80fee8c42a7b344f5be178 | |
parent | 8698530b2f9ef95542f1dd550961de7af86cc256 (diff) | |
download | libgcrypt-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.h | 5 | ||||
-rw-r--r-- | cipher/ecc-curves.c | 39 | ||||
-rw-r--r-- | cipher/ecc-misc.c | 19 | ||||
-rw-r--r-- | cipher/ecc.c | 8 | ||||
-rw-r--r-- | mpi/ec.c | 92 | ||||
-rw-r--r-- | src/ec-context.h | 4 | ||||
-rw-r--r-- | src/mpi.h | 12 | ||||
-rw-r--r-- | tests/Makefile.am | 7 |
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]); @@ -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. */ @@ -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. |