diff options
author | Niels Möller <nisse@lysator.liu.se> | 2014-09-17 20:58:41 +0200 |
---|---|---|
committer | Niels Möller <nisse@lysator.liu.se> | 2014-09-17 20:59:07 +0200 |
commit | e75c7c45bd445e757420b38c0de0a77236d366d8 (patch) | |
tree | 69f0b688246a5370413a0d5460240a90b174598a | |
parent | 74dea233bb42194c580774513de72678fcf018c3 (diff) | |
download | nettle-e75c7c45bd445e757420b38c0de0a77236d366d8.tar.gz |
Let "affine" points for curve25519 be Edwards coordinates rather than Montgomery coordinates.
-rw-r--r-- | ChangeLog | 17 | ||||
-rw-r--r-- | ecc-eh-to-a.c | 63 | ||||
-rw-r--r-- | ecc-internal.h | 2 | ||||
-rw-r--r-- | ecc-mul-a-eh.c | 4 | ||||
-rw-r--r-- | ecc-point.c | 25 | ||||
-rw-r--r-- | testsuite/ecdh-test.c | 12 | ||||
-rw-r--r-- | testsuite/ecdsa-sign-test.c | 8 | ||||
-rw-r--r-- | testsuite/ecdsa-verify-test.c | 16 |
8 files changed, 72 insertions, 75 deletions
@@ -1,5 +1,22 @@ 2014-09-17 Niels Möller <nisse@lysator.liu.se> + * testsuite/ecdh-test.c (test_main): Update curve25519 test to use + Edwards coordinates. + * testsuite/ecdsa-sign-test.c (test_main): Likewise. + * testsuite/ecdsa-verify-test.c (test_main): Likewise. + + * ecc-point.c (ecc_point_set): Use Edwards rather than Montgomery + curve. + + * ecc-mul-a-eh.c (ecc_mul_a_eh, table_init): Take an Edwards point + as input, not a Montgomery point. Hence, use ecc_a_to_j, not + ecc_a_to_eh. + + * ecc-eh-to-a.c (ecc_eh_to_a): Just convert to affine coordinates, + don't transform from Edwards to Montgomery form. Also reduces + scratch need slightly. + * ecc-internal.h (ECC_EH_TO_A_ITCH): Reduced. + * ecdsa-keygen.c (ecdsa_generate_keypair): Use struct ecc_curve function pointers. diff --git a/ecc-eh-to-a.c b/ecc-eh-to-a.c index ed0d09aa..7891aa77 100644 --- a/ecc-eh-to-a.c +++ b/ecc-eh-to-a.c @@ -41,12 +41,12 @@ mp_size_t ecc_eh_to_a_itch (const struct ecc_curve *ecc) { - /* Needs 2*ecc->size + scratch for ecc_modq_inv */ + /* Needs ecc->size + scratch for ecc_modq_inv */ return ECC_EH_TO_A_ITCH (ecc->size); } /* Convert from homogeneous coordinates on the Edwards curve to affine - coordinates on the corresponding Montgomery curve. */ + coordinates. */ void ecc_eh_to_a (const struct ecc_curve *ecc, int op, @@ -54,41 +54,22 @@ ecc_eh_to_a (const struct ecc_curve *ecc, mp_limb_t *scratch) { #define izp scratch -#define sp (scratch + ecc->size) -#define tp (scratch + 2*ecc->size) +#define tp (scratch + ecc->size) -#define xp r -#define yp (r + ecc->size) -#define up p -#define vp (p + ecc->size) -#define wp (p + 2*ecc->size) - /* x = (1+v)/(1-v), y = t x / u (with t = sqrt(b+2)) - In homogeneous coordinates, - - X = (W + V) U - Y = t (W + V) W - Z = (W - V) U - */ - /* FIXME: Simplify for common case that only x-coordinate is wanted. */ +#define xp p +#define yp (p + ecc->size) +#define zp (p + 2*ecc->size) mp_limb_t cy; - /* NOTE: For the infinity point, this subtraction gives zero (mod - p), which isn't invertible. For curve25519, the desired output is - x = 0, and we should be fine, since ecc_modp_inv returns 0 - in this case. */ - ecc_modp_sub (ecc, izp, wp, vp); - ecc_modp_mul (ecc, izp + ecc->size, izp, up); + mpn_copyi (tp, zp, ecc->size); /* Needs 3*size scratch */ - ecc_modp_inv (ecc, izp, izp + ecc->size, izp + 2*ecc->size); + ecc_modp_inv (ecc, izp, tp, tp + ecc->size); - ecc_modp_add (ecc, sp, wp, vp); - ecc_modp_mul (ecc, tp, sp, up); - mpn_copyi (sp, tp, ecc->size); /* FIXME: Eliminate copy */ - ecc_modp_mul (ecc, tp, sp, izp); - cy = mpn_sub_n (xp, tp, ecc->p, ecc->size); - cnd_copy (cy, xp, tp, ecc->size); + ecc_modp_mul (ecc, tp, xp, izp); + cy = mpn_sub_n (r, tp, ecc->p, ecc->size); + cnd_copy (cy, r, tp, ecc->size); if (op) { @@ -96,26 +77,20 @@ ecc_eh_to_a (const struct ecc_curve *ecc, if (op > 1) { /* Reduce modulo q. FIXME: Hardcoded for curve25519, - duplicates end of ecc_25519_modq. */ + duplicates end of ecc_25519_modq. FIXME: Is this needed + at all? Full reduction mod p is maybe sufficient. */ mp_limb_t cy; unsigned shift; assert (ecc->bit_size == 255); shift = 252 - GMP_NUMB_BITS * (ecc->size - 1); - cy = mpn_submul_1 (xp, ecc->q, ecc->size, - xp[ecc->size-1] >> shift); + cy = mpn_submul_1 (r, ecc->q, ecc->size, + r[ecc->size-1] >> shift); assert (cy < 2); - cnd_add_n (cy, xp, ecc->q, ecc->size); + cnd_add_n (cy, r, ecc->q, ecc->size); } return; } - ecc_modp_add (ecc, sp, wp, vp); /* FIXME: Redundant. Also the (W + - V) Z^-1 multiplication is - redundant. */ - ecc_modp_mul (ecc, tp, sp, wp); - mpn_copyi (sp, tp, ecc->size); /* FIXME: Eliminate copy */ - ecc_modp_mul (ecc, tp, sp, ecc->edwards_root); - mpn_copyi (sp, tp, ecc->size); /* FIXME: Eliminate copy */ - ecc_modp_mul (ecc, tp, sp, izp); - cy = mpn_sub_n (yp, tp, ecc->p, ecc->size); - cnd_copy (cy, yp, tp, ecc->size); + ecc_modp_mul (ecc, tp, yp, izp); + cy = mpn_sub_n (r + ecc->size, tp, ecc->p, ecc->size); + cnd_copy (cy, r + ecc->size, tp, ecc->size); } diff --git a/ecc-internal.h b/ecc-internal.h index f6f0cd1e..ffa6fe26 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -274,7 +274,7 @@ curve25519_eh_to_x (mp_limb_t *xp, const mp_limb_t *p, /* Current scratch needs: */ #define ECC_MODINV_ITCH(size) (3*(size)) #define ECC_J_TO_A_ITCH(size) (5*(size)) -#define ECC_EH_TO_A_ITCH(size) (5*(size)) +#define ECC_EH_TO_A_ITCH(size) (4*(size)) #define ECC_A_TO_EH_ITCH(size) (2*(size)) #define ECC_DUP_JJ_ITCH(size) (5*(size)) #define ECC_DUP_EH_ITCH(size) (5*(size)) diff --git a/ecc-mul-a-eh.c b/ecc-mul-a-eh.c index 1e9f4fc7..095e870c 100644 --- a/ecc-mul-a-eh.c +++ b/ecc-mul-a-eh.c @@ -63,7 +63,7 @@ ecc_mul_a_eh (const struct ecc_curve *ecc, unsigned i; - ecc_a_to_eh (ecc, pe, p, pe + 3*ecc->size); + ecc_a_to_j (ecc, pe, p); /* x = 0, y = 1, z = 1 */ mpn_zero (r, 3*ecc->size); @@ -108,7 +108,7 @@ table_init (const struct ecc_curve *ecc, mpn_zero (TABLE(0), 3*ecc->size); TABLE(0)[ecc->size] = TABLE(0)[2*ecc->size] = 1; - ecc_a_to_eh (ecc, TABLE(1), p, scratch); + ecc_a_to_j (ecc, TABLE(1), p); for (j = 2; j < size; j += 2) { diff --git a/ecc-point.c b/ecc-point.c index 60fbd080..59d2372b 100644 --- a/ecc-point.c +++ b/ecc-point.c @@ -1,6 +1,6 @@ /* ecc-point.c - Copyright (C) 2013 Niels Möller + Copyright (C) 2013, 2014 Niels Möller This file is part of GNU Nettle. @@ -68,15 +68,22 @@ ecc_point_set (struct ecc_point *p, const mpz_t x, const mpz_t y) mpz_init (lhs); mpz_init (rhs); + mpz_mul (lhs, y, y); + if (p->ecc->bit_size == 255) { - /* curve25519 special case. FIXME: Do in some cleaner way? */ - - /* Check that y^2 = x^3 + 486662 x^2 + x (mod p)*/ - mpz_mul (lhs, x, x); /* Reuse lhs as a temporary */ - mpz_add_ui (rhs, x, 486662); - mpz_mul (rhs, rhs, lhs); - mpz_add (rhs, rhs, x); + /* ed25519 special case. FIXME: Do in some cleaner way? */ + mpz_t x2; + mpz_init (x2); + mpz_mul (x2, x, x); + mpz_mul (rhs, x2, lhs); + /* Check that -x^2 + y^2 = 1 - (121665/121666) x^2 y^2 + or 121666 (1 + x^2 - y^2) = 121665 x^2 y^2 */ + mpz_sub (lhs, x2, lhs); + mpz_add_ui (lhs, lhs, 1); + mpz_mul_ui (lhs, lhs, 121666); + mpz_mul_ui (rhs, rhs, 121665); + mpz_clear (x2); } else { @@ -87,8 +94,6 @@ ecc_point_set (struct ecc_point *p, const mpz_t x, const mpz_t y) mpz_add (rhs, rhs, mpz_roinit_n (t, p->ecc->b, size)); } - mpz_mul (lhs, y, y); - res = mpz_congruent_p (lhs, rhs, mpz_roinit_n (t, p->ecc->p, size)); mpz_clear (lhs); diff --git a/testsuite/ecdh-test.c b/testsuite/ecdh-test.c index 0aa17e15..48071e5a 100644 --- a/testsuite/ecdh-test.c +++ b/testsuite/ecdh-test.c @@ -193,11 +193,11 @@ test_main(void) also with curve25519. */ test_dh ("curve25519", &nettle_curve25519, "238301186166219052901200372289459967515481170332211409964804596991365959539", - "16689431791973914300519294566135927090340942991104989847654071982531922134636", - "20308418066388251043787233144732111482161260158474210903552303016733832642783", + "14283836751943535877833976277675258994717521964638468784408792140505262281235", + "43912344711849354965202408139054167824861850336739416536288592824181793690574", "3795950278952272509684177709511717492358770264218705926196469999516028451559", - "33748673775975978547568270043630771161978032265709185964960751948965332685487", - "45040108202870901856797106334440548809561721639881101469282515918034252408802", - "12684624775789228333626692483521764247362476074160626230698999100180553618972", - "22635121008463339848034566659860493350277619617839914078958064757823336329514"); + "9468726108732441384988851273894214794301501512287024874346147472389705411936", + "38072138078045635808869930165213470653418146012939584392304609812494425185763", + "10481077163111981870382976851703705086808805457403127024129174358161599078055", + "29260211489972704256554624312266763530759418996739976957020673870747051409679"); } diff --git a/testsuite/ecdsa-sign-test.c b/testsuite/ecdsa-sign-test.c index db5194cb..794ad721 100644 --- a/testsuite/ecdsa-sign-test.c +++ b/testsuite/ecdsa-sign-test.c @@ -166,8 +166,8 @@ test_main (void) "e62e1706f54037ff 8486e26153b0fa79", /* k */ SHEX("e99df2a098c3c590 ea1e1db6d9547339" "ae760d5331496119 5d967fd881e3b0f5"), /* h */ - " 62cbc248a549765 3641d1cbedda2733" - "a7357821dca43727 d8081448d608030d", /* r */ - " 14726f472f44f84 63fe82c2712231cd" - "937f2aecdcfe9c39 e2ab0d68c390ccf4"); /* s */ + " 515c3a485f57432 0daf3353a0d08110" + "64157c556296de09 4132f74865961b37", /* r */ + " 9ddd3e2fa87328c 372e28ac7a1c0c65" + "697196d643238fd0 c4caa4d1d88a62fe"); /* s */ } diff --git a/testsuite/ecdsa-verify-test.c b/testsuite/ecdsa-verify-test.c index 3ea52e42..b39dbfda 100644 --- a/testsuite/ecdsa-verify-test.c +++ b/testsuite/ecdsa-verify-test.c @@ -148,14 +148,14 @@ test_main (void) test_ecdsa (&nettle_curve25519, /* Public key corresponding to the key in ecdsa-sign-test */ - " eb07d9c7931d614 2669124e12273e1f" - "b9f9555f52bed369 a71cdac173da0ceb", /* x */ - "2e726b0b1ff3abc4 d50798ebc246399e" - "365777c0900a0d5b 425f819278d4281d", /* y */ + "59f8f317fd5f4e82 c02f8d4dec665fe1" + "230f83b8572638e1 b2ac34a30028e24d", /* x */ + "1902a72dc1a6525a 811b9c1845978d56" + "fd97dce5e278ebdd ec695349d7e41498", /* y */ SHEX("e99df2a098c3c590 ea1e1db6d9547339" "ae760d5331496119 5d967fd881e3b0f5"), /* h */ - " 62cbc248a549765 3641d1cbedda2733" - "a7357821dca43727 d8081448d608030d", /* r */ - " 14726f472f44f84 63fe82c2712231cd" - "937f2aecdcfe9c39 e2ab0d68c390ccf4"); /* s */ + " 515c3a485f57432 0daf3353a0d08110" + "64157c556296de09 4132f74865961b37", /* r */ + " 9ddd3e2fa87328c 372e28ac7a1c0c65" + "697196d643238fd0 c4caa4d1d88a62fe"); /* s */ } |