From 5f2814e261ed76663979c0831fb89f7975911d34 Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Sat, 17 Oct 2015 18:09:32 +0200 Subject: Add support for the Ed25519 curve --- include/libuecc/ecc.h | 61 ++++++++++++++++++--- src/ec25519.c | 147 +++++++++++++++++++++++++++++++++++++++++++++----- 2 files changed, 187 insertions(+), 21 deletions(-) diff --git a/include/libuecc/ecc.h b/include/libuecc/ecc.h index 547cca4..56c7538 100644 --- a/include/libuecc/ecc.h +++ b/include/libuecc/ecc.h @@ -97,12 +97,18 @@ extern const ecc_25519_work_t ecc_25519_work_base_legacy; DEPRECATED extern const ecc_25519_work_t ecc_25519_work_default_base; +/** Loads a point of the Ed25519 curve with given coordinates into its unpacked representation */ +int ecc_25519_load_xy_ed25519(ecc_25519_work_t *out, const ecc_int256_t *x, const ecc_int256_t *y); -/** Loads a point with given coordinates into its unpacked representation */ +/** + * Loads a point of the legacy curve with given coordinates into its unpacked representation + * + * New software should use \ref ecc_25519_load_xy_ed25519, which uses the same curve as the Ed25519 algorithm. + */ int ecc_25519_load_xy_legacy(ecc_25519_work_t *out, const ecc_int256_t *x, const ecc_int256_t *y); /** - * Loads a point with given coordinates into its unpacked representation + * Loads a point of the legacy curve with given coordinates into its unpacked representation * * \deprecated Use \ref ecc_25519_load_xy_legacy */ @@ -110,7 +116,18 @@ DEPRECATED int ecc_25519_load_xy(ecc_25519_work_t *out, const ecc_int256_t *x, c /** - * Stores a point's x and y coordinates + * Stores the x and y coordinates of a point of the Ed25519 curve + * + * \param x Returns the x coordinate of the point. May be NULL. + * \param y Returns the y coordinate of the point. May be NULL. + * \param in The unpacked point to store. + */ +void ecc_25519_store_xy_ed25519(ecc_int256_t *x, ecc_int256_t *y, const ecc_25519_work_t *in); + +/** + * Stores the x and y coordinates of a point of the legacy curve + * + * New software should use \ref ecc_25519_store_xy_ed25519, which uses the same curve as the Ed25519 algorithm. * * \param x Returns the x coordinate of the point. May be NULL. * \param y Returns the y coordinate of the point. May be NULL. @@ -130,22 +147,52 @@ void ecc_25519_store_xy_legacy(ecc_int256_t *x, ecc_int256_t *y, const ecc_25519 DEPRECATED void ecc_25519_store_xy(ecc_int256_t *x, ecc_int256_t *y, const ecc_25519_work_t *in); -/** Loads a packed point into its unpacked representation */ +/** + * Loads a packed point of the Ed25519 curve into its unpacked representation + * + * The packed format is different from the legacy one: the legacy format contains that X coordinate and the parity of the Y coordinate, + * Ed25519 uses the Y coordinate and the parity of the X coordinate. +*/ +int ecc_25519_load_packed_ed25519(ecc_25519_work_t *out, const ecc_int256_t *in); + +/** + * Loads a packed point of the legacy curve into its unpacked representation + * + * New software should use \ref ecc_25519_load_packed_ed25519, which uses the same curve and packed representation as the Ed25519 algorithm. + * + * The packed format is different from the Ed25519 one: the legacy format contains that X coordinate and the parity of the Y coordinate, + * Ed25519 uses the Y coordinate and the parity of the X coordinate. + */ int ecc_25519_load_packed_legacy(ecc_25519_work_t *out, const ecc_int256_t *in); /** - * Loads a packed point into its unpacked representation + * Loads a packed point of the legacy curve into its unpacked representation * * \deprecated Use \ref ecc_25519_load_packed_legacy */ DEPRECATED int ecc_25519_load_packed(ecc_25519_work_t *out, const ecc_int256_t *in); -/** Stores a point into its packed representation */ +/** + * Stores a point of the Ed25519 curve into its packed representation + * + * The packed format is different from the Ed25519 one: the legacy format contains that X coordinate and the parity of the Y coordinate, + * Ed25519 uses the Y coordinate and the parity of the X coordinate. + */ +void ecc_25519_store_packed_ed25519(ecc_int256_t *out, const ecc_25519_work_t *in); + +/** + * Stores a point of the legacy curve into its packed representation + * + * New software should use \ref ecc_25519_store_packed_ed25519, which uses the same curve and packed representation as the Ed25519 algorithm. + * + * The packed format is different from the Ed25519 one: the legacy format contains that X coordinate and the parity of the Y coordinate, + * Ed25519 uses the Y coordinate and the parity of the X coordinate. + */ void ecc_25519_store_packed_legacy(ecc_int256_t *out, const ecc_25519_work_t *in); /** - * Stores a point into its packed representation + * Stores a point of the legacy curve into its packed representation * * \deprecated Use \ref ecc_25519_store_packed_legacy */ diff --git a/src/ec25519.c b/src/ec25519.c index b3d1a36..1b0ac73 100644 --- a/src/ec25519.c +++ b/src/ec25519.c @@ -25,12 +25,25 @@ */ /** \file - * EC group operations for Twisted Edwards Curve \f$ ax^2 + y^2 = 1 + dx^2y^2 \f$ with + * EC group operations for Twisted Edwards Curve \f$ ax^2 + y^2 = 1 + dx^2y^2 \f$ + * on prime field \f$ p = 2^{255} - 19 \f$. + * + * Two different (isomorphic) sets of curve parameters are supported: + * * \f$ a = 486664 \f$ and * \f$ d = 486660 \f$ - * on prime field \f$ p = 2^{255} - 19 \f$. + * are the parameters used by the original libuecc implementation (till v5). + * To use points on this curve, use the functions with the suffix \em legacy. + * + * The other supported curve uses the parameters + * \f$ a = -1 \f$ and + * \f$ d = -(121665/121666) \f$, + * which is the curve used by the Ed25519 algorithm. The functions for this curve + * have the suffix \em ed25519. + * + * Internally, libuecc always uses the former representation for its \em work structure. * - * The curve is equivalent to the Montgomery Curve used in D. J. Bernstein's + * The curves are equivalent to the Montgomery Curve used in D. J. Bernstein's * Curve25519 Diffie-Hellman algorithm. * * See http://hyperelliptic.org/EFD/g1p/auto-twisted-extended.html for add and @@ -102,6 +115,23 @@ static const uint32_t zero[32] = {0}; static const uint32_t one[32] = {1}; +/** Factor to multiply the X coordinate with to convert from the legacy to the Ed25519 curve */ +static const uint32_t legacy_to_ed25519[32] = { + 0x06, 0x7e, 0x45, 0xff, 0xaa, 0x04, 0x6e, 0xcc, + 0x82, 0x1a, 0x7d, 0x4b, 0xd1, 0xd3, 0xa1, 0xc5, + 0x7e, 0x4f, 0xfc, 0x03, 0xdc, 0x08, 0x7b, 0xd2, + 0xbb, 0x06, 0xa0, 0x60, 0xf4, 0xed, 0x26, 0x0f, +}; + +/** Factor to multiply the X coordinate with to convert from the Ed25519 to the legacy curve */ +static const uint32_t ed25519_to_legacy[32] = { + 0x04, 0x97, 0xbd, 0x24, 0x50, 0xfb, 0x4b, 0xbf, + 0x5e, 0x2a, 0xbc, 0x0d, 0x06, 0xc7, 0xce, 0xd7, + 0xfe, 0xe8, 0xfa, 0x98, 0x64, 0x7e, 0x9e, 0x07, + 0x56, 0xa4, 0xc1, 0x95, 0xdf, 0x98, 0xb4, 0x5b, +}; + + /** Adds two unpacked integers (modulo p) */ static void add(uint32_t out[32], const uint32_t a[32], const uint32_t b[32]) { unsigned int j; @@ -524,19 +554,17 @@ static void recip(uint32_t out[32], const uint32_t z[32]) { /* 2^255 - 21 */ mult(out, t1, z11); } -int ecc_25519_load_xy_legacy(ecc_25519_work_t *out, const ecc_int256_t *x, const ecc_int256_t *y) { - int i; +/** + * Checks if the X and Y coordinates of a work structure represent a valid point of the curve + * + * Also fills out the T coordinate. + */ +static int check_load_xy(ecc_25519_work_t *val) { uint32_t X2[32], Y2[32], aX2[32], dX2[32], dX2Y2[32], aX2_Y2[32], _1_dX2Y2[32], r[32]; - for (i = 0; i < 32; i++) { - out->X[i] = x->p[i]; - out->Y[i] = y->p[i]; - out->Z[i] = (i == 0); - } - /* Check validity */ - square(X2, out->X); - square(Y2, out->Y); + square(X2, val->X); + square(Y2, val->Y); mult_int(aX2, UINT32_C(486664), X2); mult_int(dX2, UINT32_C(486660), X2); mult(dX2Y2, dX2, Y2); @@ -548,16 +576,65 @@ int ecc_25519_load_xy_legacy(ecc_25519_work_t *out, const ecc_int256_t *x, const if (!check_zero(r)) return 0; - mult(out->T, out->X, out->Y); + mult(val->T, val->X, val->Y); return 1; } +int ecc_25519_load_xy_ed25519(ecc_25519_work_t *out, const ecc_int256_t *x, const ecc_int256_t *y) { + int i; + uint32_t tmp[32]; + + for (i = 0; i < 32; i++) { + tmp[i] = x->p[i]; + out->Y[i] = y->p[i]; + out->Z[i] = (i == 0); + } + + mult(out->X, tmp, ed25519_to_legacy); + + return check_load_xy(out); +} + +int ecc_25519_load_xy_legacy(ecc_25519_work_t *out, const ecc_int256_t *x, const ecc_int256_t *y) { + int i; + + for (i = 0; i < 32; i++) { + out->X[i] = x->p[i]; + out->Y[i] = y->p[i]; + out->Z[i] = (i == 0); + } + + return check_load_xy(out); +} + int ecc_25519_load_xy(ecc_25519_work_t *out, const ecc_int256_t *x, const ecc_int256_t *y) { return ecc_25519_load_xy_legacy(out, x, y); } +void ecc_25519_store_xy_ed25519(ecc_int256_t *x, ecc_int256_t *y, const ecc_25519_work_t *in) { + uint32_t X[32], tmp[32], Y[32], Z[32]; + int i; + + recip(Z, in->Z); + + if (x) { + mult(tmp, Z, in->X); + mult(X, tmp, legacy_to_ed25519); + freeze(X); + for (i = 0; i < 32; i++) + x->p[i] = X[i]; + } + + if (y) { + mult(Y, Z, in->Y); + freeze(Y); + for (i = 0; i < 32; i++) + y->p[i] = Y[i]; + } +} + void ecc_25519_store_xy_legacy(ecc_int256_t *x, ecc_int256_t *y, const ecc_25519_work_t *in) { uint32_t X[32], Y[32], Z[32]; int i; @@ -584,6 +661,41 @@ void ecc_25519_store_xy(ecc_int256_t *x, ecc_int256_t *y, const ecc_25519_work_t } +int ecc_25519_load_packed_ed25519(ecc_25519_work_t *out, const ecc_int256_t *in) { + static const uint32_t a[32] = {UINT32_C(486664)}; + int i; + uint32_t Y2[32] /* Y^2 */, dY2[32] /* dY^2 */, _1_Y2[32] /* 1-Y^2 */, a_dY2[32] /* a-dY^2 */, _1_a_dY2[32] /* 1/(a-dY^2) */; + uint32_t X2[32] /* X^2 */, X[32], Xt[32], X_ed25519[32]; + + for (i = 0; i < 32; i++) { + out->Y[i] = in->p[i]; + out->Z[i] = (i == 0); + } + + out->Y[31] &= 0x7f; + + square(Y2, out->Y); + mult_int(dY2, UINT32_C(486660), Y2); + sub(_1_Y2, one, Y2); + sub(a_dY2, a, dY2); + recip(_1_a_dY2, a_dY2); + mult(X2, _1_Y2, _1_a_dY2); + + if (!square_root(X, X2)) + return 0; + + mult(X_ed25519, X, legacy_to_ed25519); + + /* No squeeze is necessary after subtractions from zero if the subtrahend is squeezed */ + sub(Xt, zero, X); + + select(out->X, X, Xt, (in->p[31] >> 7) ^ parity(X_ed25519)); + + mult(out->T, out->X, out->Y); + + return 1; +} + int ecc_25519_load_packed_legacy(ecc_25519_work_t *out, const ecc_int256_t *in) { int i; uint32_t X2[32] /* X^2 */, aX2[32] /* aX^2 */, dX2[32] /* dX^2 */, _1_aX2[32] /* 1-aX^2 */, _1_dX2[32] /* 1-aX^2 */; @@ -622,6 +734,13 @@ int ecc_25519_load_packed(ecc_25519_work_t *out, const ecc_int256_t *in) { } +void ecc_25519_store_packed_ed25519(ecc_int256_t *out, const ecc_25519_work_t *in) { + ecc_int256_t x; + + ecc_25519_store_xy_ed25519(&x, out, in); + out->p[31] |= (x.p[0] << 7); +} + void ecc_25519_store_packed_legacy(ecc_int256_t *out, const ecc_25519_work_t *in) { ecc_int256_t y; -- cgit v1.2.3