diff options
| -rw-r--r-- | ChangeLog | 17 | ||||
| -rw-r--r-- | Makefile.in | 6 | ||||
| -rw-r--r-- | ecc-25519.c | 91 | ||||
| -rw-r--r-- | ecc-curve.h | 1 | ||||
| -rw-r--r-- | eccdata.c | 6 | ||||
| -rw-r--r-- | testsuite/ecc-mod-test.c | 115 |
6 files changed, 180 insertions, 56 deletions
@@ -1,3 +1,20 @@ +2014-07-04 Niels Möller <nisse@lysator.liu.se> + + * ecc-25519.c: New file. + (ecc_25519_modp): New function. + (nettle_curve25519): New curve. + + * ecc-curve.h (nettle_curve25519): Declare it. + + * Makefile.in (hogweed_SOURCES): Added ecc-25519.c. + (ecc-25519.h): New generated file. Add as explicit dependency for + ecc-25519.o. + + * testsuite/ecc-mod-test.c (test_curve): New function, extracted + from test_main. Tolerate NULL modq function pointer. + (test_main): Use test_curve, iterate over supported curves, and + also test curve_25519 for the new modp function. + 2014-07-02 Niels Möller <nisse@lysator.liu.se> * eccdata.c (ecc_dup): Use mpz_submul_ui, now available in diff --git a/Makefile.in b/Makefile.in index b4082110..5888b004 100644 --- a/Makefile.in +++ b/Makefile.in @@ -164,6 +164,7 @@ hogweed_SOURCES = sexp.c sexp-format.c \ ecc-mod.c ecc-generic-modp.c ecc-generic-modq.c \ ecc-modp.c ecc-modq.c ecc-generic-redc.c \ ecc-192.c ecc-224.c ecc-256.c ecc-384.c ecc-521.c \ + ecc-25519.c \ ecc-size.c ecc-j-to-a.c ecc-a-to-j.c \ ecc-dup-jj.c ecc-add-jja.c ecc-add-jjj.c \ ecc-mul-g.c ecc-mul-a.c ecc-hash.c ecc-random.c \ @@ -347,6 +348,9 @@ ecc-384.h: eccdata.stamp ecc-521.h: eccdata.stamp ./eccdata$(EXEEXT_FOR_BUILD) 521 56 6 $(GMP_NUMB_BITS) > $@T && mv $@T $@ +ecc-25519.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) 255 14 6 $(GMP_NUMB_BITS) > $@T && mv $@T $@ + eccdata.stamp: eccdata.c $(MAKE) eccdata$(EXEEXT_FOR_BUILD) echo stamp > eccdata.stamp @@ -356,12 +360,14 @@ ecc-224.$(OBJEXT): ecc-224.h ecc-256.$(OBJEXT): ecc-256.h ecc-384.$(OBJEXT): ecc-384.h ecc-521.$(OBJEXT): ecc-521.h +ecc-25519.$(OBJEXT): ecc-25519.h ecc-192.p$(OBJEXT): ecc-192.h ecc-224.p$(OBJEXT): ecc-224.h ecc-256.p$(OBJEXT): ecc-256.h ecc-384.p$(OBJEXT): ecc-384.h ecc-521.p$(OBJEXT): ecc-521.h +ecc-25519.p$(OBJEXT): ecc-25519.h .asm.s: $(srcdir)/asm.m4 machine.m4 config.m4 $(M4) $(srcdir)/asm.m4 machine.m4 config.m4 $< >$@T \ diff --git a/ecc-25519.c b/ecc-25519.c new file mode 100644 index 00000000..890fbe59 --- /dev/null +++ b/ecc-25519.c @@ -0,0 +1,91 @@ +/* ecc-25519 + + Arithmetic and tables for curve25519, + + Copyright (C) 2014 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include "ecc-internal.h" + +#define USE_REDC 0 + +#include "ecc-25519.h" + +#define HIGH_BITS (GMP_NUMB_BITS * ECC_LIMB_SIZE - 255) + +#if HIGH_BITS == 0 +#error Unsupported limb size */ +#endif + +static void +ecc_25519_modp(const struct ecc_curve *ecc UNUSED, mp_limb_t *rp) +{ + mp_limb_t hi, cy; + + cy = mpn_addmul_1 (rp, rp + ECC_LIMB_SIZE, ECC_LIMB_SIZE, + (mp_limb_t) 19 << HIGH_BITS); + hi = rp[ECC_LIMB_SIZE-1]; + cy = (cy << HIGH_BITS) + (hi >> (GMP_NUMB_BITS - HIGH_BITS)); + rp[ECC_LIMB_SIZE-1] = (hi & (GMP_NUMB_MASK >> HIGH_BITS)) + + sec_add_1 (rp, rp, ECC_LIMB_SIZE - 1, 19 * cy); +} + +const struct ecc_curve nettle_curve25519 = +{ + 255, + ECC_LIMB_SIZE, + ECC_BMODP_SIZE, + ECC_BMODQ_SIZE, + 0, /* No redc */ + 0, + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + ecc_p, + ecc_b, + ecc_q, + ecc_g, + ecc_redc_g, + ecc_25519_modp, + NULL, + ecc_25519_modp, + NULL, + ecc_Bmodp, + ecc_Bmodp_shifted, + ecc_pp1h, + ecc_redc_ppm1, + ecc_unit, + ecc_Bmodq, + ecc_Bmodq_shifted, + ecc_qp1h, + ecc_table +}; diff --git a/ecc-curve.h b/ecc-curve.h index b5f0f975..df72569c 100644 --- a/ecc-curve.h +++ b/ecc-curve.h @@ -46,6 +46,7 @@ extern const struct ecc_curve nettle_secp_224r1; extern const struct ecc_curve nettle_secp_256r1; extern const struct ecc_curve nettle_secp_384r1; extern const struct ecc_curve nettle_secp_521r1; +extern const struct ecc_curve nettle_curve25519; #ifdef __cplusplus } @@ -529,8 +529,10 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) "7fffffffffffffffffffffffffffffff" "ffffffffffffffffffffffffffffffed", "76d06", - /* Order of the subgroup is 2^252 + - 27742317777372353535851937790883648493 */ + /* Order of the subgroup is 2^252 + q_0, where + q_0 = 27742317777372353535851937790883648493, + 125 bits. + */ "10000000000000000000000000000000" "14def9dea2f79cd65812631a5cf5d3ed", "9", diff --git a/testsuite/ecc-mod-test.c b/testsuite/ecc-mod-test.c index 5caee758..b2360e9b 100644 --- a/testsuite/ecc-mod-test.c +++ b/testsuite/ecc-mod-test.c @@ -19,70 +19,65 @@ ref_mod (mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *mp, mp_size_t mn) #define MAX_SIZE (2*MAX_ECC_SIZE) #define COUNT 50000 -void -test_main (void) +static void +test_curve (gmp_randstate_t rands, const struct ecc_curve *ecc) { - gmp_randstate_t rands; mp_limb_t a[MAX_SIZE]; mp_limb_t m[MAX_SIZE]; mp_limb_t ref[MAX_SIZE]; - unsigned i; mpz_t r; + unsigned j; - gmp_randinit_default (rands); - mpz_init (r); - for (i = 0; ecc_curves[i]; i++) + for (j = 0; j < COUNT; j++) { - const struct ecc_curve *ecc = ecc_curves[i]; - unsigned j; - for (j = 0; j < COUNT; j++) - { - if (j & 1) - mpz_rrandomb (r, rands, 2*ecc->size * GMP_NUMB_BITS); - else - mpz_urandomb (r, rands, 2*ecc->size * GMP_NUMB_BITS); + if (j & 1) + mpz_rrandomb (r, rands, 2*ecc->size * GMP_NUMB_BITS); + else + mpz_urandomb (r, rands, 2*ecc->size * GMP_NUMB_BITS); + + mpz_limbs_copy (a, r, 2*ecc->size); + + ref_mod (ref, a, ecc->p, ecc->size); - mpz_limbs_copy (a, r, 2*ecc->size); + mpn_copyi (m, a, 2*ecc->size); + ecc->modp (ecc, m); + if (mpn_cmp (m, ecc->p, ecc->size) >= 0) + mpn_sub_n (m, m, ecc->p, ecc->size); - ref_mod (ref, a, ecc->p, ecc->size); + if (mpn_cmp (m, ref, ecc->size)) + { + fprintf (stderr, "ecc->modp failed: bit_size = %u\n", + ecc->bit_size); + gmp_fprintf (stderr, "a = %Nx\n", a, 2*ecc->size); + gmp_fprintf (stderr, "m = %Nx (bad)\n", m, ecc->size); + gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size); + abort (); + } + if (ecc->Bmodp_size < ecc->size) + { mpn_copyi (m, a, 2*ecc->size); - ecc->modp (ecc, m); + ecc_generic_modp (ecc, m); if (mpn_cmp (m, ecc->p, ecc->size) >= 0) mpn_sub_n (m, m, ecc->p, ecc->size); if (mpn_cmp (m, ref, ecc->size)) { - fprintf (stderr, "ecc->modp failed: bit_size = %u\n", + fprintf (stderr, "ecc_generic_modp failed: bit_size = %u\n", ecc->bit_size); gmp_fprintf (stderr, "a = %Nx\n", a, 2*ecc->size); gmp_fprintf (stderr, "m = %Nx (bad)\n", m, ecc->size); gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size); abort (); } + } - if (ecc->Bmodp_size < ecc->size) - { - mpn_copyi (m, a, 2*ecc->size); - ecc_generic_modp (ecc, m); - if (mpn_cmp (m, ecc->p, ecc->size) >= 0) - mpn_sub_n (m, m, ecc->p, ecc->size); - - if (mpn_cmp (m, ref, ecc->size)) - { - fprintf (stderr, "ecc_generic_modp failed: bit_size = %u\n", - ecc->bit_size); - gmp_fprintf (stderr, "a = %Nx\n", a, 2*ecc->size); - gmp_fprintf (stderr, "m = %Nx (bad)\n", m, ecc->size); - gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size); - abort (); - } - } - - ref_mod (ref, a, ecc->q, ecc->size); + ref_mod (ref, a, ecc->q, ecc->size); + if (ecc->modq) + { mpn_copyi (m, a, 2*ecc->size); ecc->modq (ecc, m); if (mpn_cmp (m, ecc->q, ecc->size) >= 0) @@ -97,28 +92,40 @@ test_main (void) gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size); abort (); } + } + if (ecc->Bmodq_size < ecc->size) + { + mpn_copyi (m, a, 2*ecc->size); + ecc_generic_modq (ecc, m); + if (mpn_cmp (m, ecc->q, ecc->size) >= 0) + mpn_sub_n (m, m, ecc->q, ecc->size); - if (ecc->Bmodq_size < ecc->size) + if (mpn_cmp (m, ref, ecc->size)) { - mpn_copyi (m, a, 2*ecc->size); - ecc_generic_modq (ecc, m); - if (mpn_cmp (m, ecc->q, ecc->size) >= 0) - mpn_sub_n (m, m, ecc->q, ecc->size); - - if (mpn_cmp (m, ref, ecc->size)) - { - fprintf (stderr, "ecc_generic_modp failed: bit_size = %u\n", - ecc->bit_size); - gmp_fprintf (stderr, "a = %Nx\n", a, 2*ecc->size); - gmp_fprintf (stderr, "m = %Nx (bad)\n", m, ecc->size); - gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size); - abort (); - } + fprintf (stderr, "ecc_generic_modp failed: bit_size = %u\n", + ecc->bit_size); + gmp_fprintf (stderr, "a = %Nx\n", a, 2*ecc->size); + gmp_fprintf (stderr, "m = %Nx (bad)\n", m, ecc->size); + gmp_fprintf (stderr, "ref = %Nx\n", ref, ecc->size); + abort (); } } } - mpz_clear (r); +} + +void +test_main (void) +{ + gmp_randstate_t rands; + unsigned i; + + gmp_randinit_default (rands); + + for (i = 0; ecc_curves[i]; i++) + test_curve (rands, ecc_curves[i]); + + test_curve (rands, &nettle_curve25519); gmp_randclear (rands); } #endif /* ! NETTLE_USE_MINI_GMP */ |