+ 2014-08-27 Niels Möller <nisse@lysator.liu.se>
+
++ Merged camellia-reorg changes (starting at 2014-07-04).
+ * Makefile.in (clean-here): Added ecc-25519.h.
+
+ 2014-08-26 Niels Möller <nisse@lysator.liu.se>
+
+ * examples/ecc-benchmark.c (bench_mul_g, bench_mul_a): Use struct
+ ecc_curve function pointers.
+ (bench_mul_g_eh, bench_mul_a_eh): Deleted.
+ (bench_curve): Make modq benchmark unconditional. Use bench_mul_g
+ and bench_mul_a also for curve25519.
+
+ * testsuite/ecc-mod-test.c (test_curve): Make modq test
+ unconditional, partially reverting 2014-07-04 change.
+
+ * ecc-25519.c (ecc_25519_modq): New function.
+
+ * eccdata.c (output_curve): Precomputation for curve25519 mod q.
+
+ * mini-gmp.c (mpz_abs_sub_bit): Do full normalization, needed in
+ case the most significant bit is cleared.
+
+ 2014-08-25 Niels Möller <nisse@lysator.liu.se>
+
+ * testsuite/ecdh-test.c (set_point): Check return value of
+ ecc_point_set.
+ (test_main): Enable curve25519 test.
+
+ * ecc-point-mul-g.c (ecc_point_mul_g): Use ecc->mul_g and
+ ecc->h_to_a function pointers.
+ * ecc-point-mul.c (ecc_point_mul): Use the ecc->mul and
+ ecc->h_to_a function pointers.
+
+ * ecc-internal.h (ecc_mul_g_func, ecc_mul_func, ecc_h_to_a_func):
+ New typedefs.
+ (struct ecc_curve): New function pointers mul, mul_g, h_to_a, and
+ constans for their scratch requirements. Updated all instances.
+
+ * ecc-point.c (ecc_point_set): Handle curve25519 as a special
+ case, when checking if the point is on the curve.
+
+ 2014-08-24 Niels Möller <nisse@lysator.liu.se>
+
+ * testsuite/ecdh-test.c: Test ecc_point_mul and ecc_point_mul_g,
+ using test data generated by ecc-ref.gp. Tests for all curves
+ except curve25519, which doesn't yet work with the general
+ ecc_point interface.
+
+ * testsuite/Makefile.in (TS_HOGWEED_SOURCES): Added ecdh-test.c.
+
+ * misc/ecc-ref.gp: Script to generate ECDH test data.
+
+ 2014-08-23 Niels Möller <nisse@lysator.liu.se>
+
+ * ecc-a-to-j.c (ecc_a_to_j): Deleted INITIAL argument.
+ * ecc.h (ecc_a_to_j): Updated prototype.
+ * ecc-mul-a.c (ecc_mul_a, table_init): Updated calls to ecc_a_to_j.
+
+ * ecc-mul-a.c (ecc_mul_a): Deleted INITIAL argument, all callers,
+ except the tests, pass 1. Updated all callers.
+ (table_init): Likewise deleted INITIAL.
+ * ecc.h (ecc_mul_a): Updated prototype.
+ * testsuite/ecc-mul-a-test.c (test_main): Deleted tests for
+ ecc_mul_a with INITIAL == 0.
+
+ * ecc-internal.h (struct ecc_curve): Reordered struct, moved
+ function pointers before pointers to bignum constants.
+
+ * sec-modinv.c (sec_modinv): Document that for a == 0 (mod m), we
+ should produce the "inverse" 0.
+
+ * testsuite/ecc-modinv-test.c (test_main): Check that ecc_modp_inv
+ produces 0 if a == 0 or a == p.
+
+ 2014-08-22 Niels Möller <nisse@lysator.liu.se>
+
+ * x86_64/ecc-25519-modp.asm: New file. Assembly implementation,
+ initial version yields 30% speedup of ecc_25519_modp. Early
+ folding eliminates one pass of carry propagation, and yields
+ almost 20% additional speedup.
+
+ * ecc-25519.c [HAVE_NATIVE_ecc_25519_modp]: Use assembly version
+ if available.
+
+ * configure.ac (asm_hogweed_optional_list): Added ecc-25519-modp.asm.
+ Also add HAVE_NATIVE_ecc_25519_modp to config.h.in.
+
+ 2014-08-19 Niels Möller <nisse@lysator.liu.se>
+
+ * examples/ecc-benchmark.c (bench_curve): Support benchmarking of
+ curve25519, for now handled as a special case.
+ (curves): Added nettle_curve25519.
+ (bench_dup_eh, bench_add_eh, bench_add_ehh, bench_mul_g_eh): New
+ functions.
+
+ 2014-08-18 Niels Möller <nisse@lysator.liu.se>
+
+ * testsuite/curve25519-dh-test.c (test_a): Use curve25519_mul.
+ (test_main): Use little-endian inputs for test_a.
+ (curve25519_sqrt, curve_25519): Deleted static helper functions,
+ no longer needed.
+
+ * curve25519-mul.c (curve25519_mul): New file and function.
+ * curve25519.h (curve25519_mul): Declare it.
+ * Makefile.in (hogweed_SOURCES): Added curve25519-mul.c.
+
+ * curve25519-mul-g.c (curve25519_mul_g): Renamed file and
+ function, updated callers.
+ * curve25519-base.c (curve25519_base): ... old names.
+ * Makefile.in (hogweed_SOURCES): Updated for rename.
+
+ * eccdata.c (output_curve): Compute constants needed for
+ Shanks-Tonelli.
+ * ecc-25519.c (ecc_modp_powm_2kp1, ecc_25519_sqrt): New functions.
+ * ecc-internal.h (ecc_25519_sqrt): Declare it.
+
+ 2014-08-06 Niels Möller <nisse@lysator.liu.se>
+
+ * testsuite/curve25519-dh-test.c (test_g): Use curve25519_base.
+ (test_main): Use little-endian inputs for test_g.
+
+ * curve25519-base.c (curve25519_base): New file, new function.
+ Analogous to NaCl's crypto_scalarmult_base.
+ * curve25519.h: New file.
+ * Makefile.in (hogweed_SOURCES): Added curve25519-base.c.
+ (HEADERS): Added curve25519.h.
+
+ * gmp-glue.c (mpn_set_base256_le, mpn_get_base256_le): New functions.
+ * gmp-glue.h: Declare them.
+
+ 2014-08-02 Niels Möller <nisse@lysator.liu.se>
+
+ * testsuite/curve25519-dh-test.c (curve25519_sqrt): Fixed memory
+ leak, a mpz_clear call was missing.
+
+ * ecc-internal.h (ECC_MUL_A_EH_WBITS): Set to 4, to enable
+ window-based scalar multiplication.
+
+ * ecc-mul-a-eh.c (table_init) [ECC_MUL_A_EH_WBITS > 0]: Fixed
+ initialization of TABLE(1).
+
+ 2014-07-29 Niels Möller <nisse@lysator.liu.se>
+
+ * ecc-internal.h (ECC_MUL_A_EH_WBITS): New constant.
+ (ECC_A_TO_EH_ITCH, ECC_MUL_A_EH_ITCH): New macros.
+ * ecc-a-to-eh.c (ecc_a_to_eh, ecc_a_to_eh_itch): New file, new
+ functions.
+ * ecc-mul-a-eh.c: New file.
+ (ecc_mul_a_eh): New function. The case [ECC_MUL_A_EH_WBITS > 0]
+ not yet working).
+ (ecc_mul_a_eh_itch): New function.
+ * ecc.h: Declare new functions.
+ * Makefile.in (hogweed_SOURCES): Added ecc-a-to-eh.c and
+ ecc-mul-a-eh.c.
+
+ * testsuite/curve25519-dh-test.c (curve25519_sqrt): New function.
+ (curve_25519): Use ecc_mul_a_eh.
+ (test_a): New function.
+ (test_main): Test construction of shared secret, using scalar
+ multiplication with points other than the fix generator.
+
+ 2014-07-26 Niels Möller <nisse@lysator.liu.se>
+
+ * ecc-add-ehh.c (ecc_add_ehh): Reduce scratch need.
+ * ecc-internal.h (ECC_ADD_EHH_ITCH): Reduced to 7*size.
+
+ 2014-07-23 Niels Möller <nisse@lysator.liu.se>
+
+ * testsuite/curve25519-dh-test.c: New test case, based on
+ draft-josefsson-tls-curve25519-05 test vectors.
+ * testsuite/Makefile.in (TS_HOGWEED_SOURCES): Added curve25519-dh-test.c.
+
+ 2014-07-18 Niels Möller <nisse@lysator.liu.se>
+
+ * ecc-mul-g-eh.c (ecc_mul_g_eh, ecc_mul_g_eh_itch): New file and
+ functions. Untested.
+ * ecc.h (ecc_mul_g_eh_itch): Declare new functions.
+ * ecc-internal.h (ECC_MUL_G_EH_ITCH): New macro.
+ * Makefile.in (hogweed_SOURCES): Added ecc-mul-g-eh.c.
+
+ 2014-07-17 Niels Möller <nisse@lysator.liu.se>
+
+ * ecc-add-eh.c (ecc_add_eh): Reduce scratch need.
+ * ecc-internal.h (ECC_ADD_EH_ITCH): Reduced to 6*size.
+
+ * testsuite/curve25519-dup-test.c (test_main): Free allocated
+ storage.
+
+ 2014-07-15 Niels Möller <nisse@lysator.liu.se>
+
+ * ecc-add-eh.c (ecc_add_eh, ecc_add_eh_itch): New file, new
+ functions.
+ * ecc.h: Declare new functions.
+ * ecc-internal.h (ECC_ADD_EH_ITCH): New macro.
+ * Makefile.in (hogweed_SOURCES): Added ecc-add-eh.c.
+ * testsuite/curve25519-add-test.c (test_main): Test ecc_add_eh.
+ Additional test for g2+g2. Free allocated storage.
+
+ 2014-07-14 Niels Möller <nisse@lysator.liu.se>
+
+ * testsuite/curve25519-add-test.c: New test case.
+ * testsuite/Makefile.in (TS_HOGWEED_SOURCES): Added
+ curve25519-add-test.c.
+
+ * ecc-add-ehh.c (ecc_add_ehh, ecc_add_ehh_itch): New file, new
+ functions.
+ * ecc.h (ecc_add_ehh, ecc_add_ehh_itch): Declare them.
+ * ecc-internal.h (ECC_ADD_EHH_ITCH): New macro.
+ * Makefile.in (hogweed_SOURCES): Added ecc-add-ehh.c.
+
+ * ecc-25519.c (nettle_curve25519): Use ecc_d instead of ecc_b.
+
+ * eccdata.c: For curve25519, output the Edwards curve constant,
+ ecc_d = (121665/121666) mod p.
+
+ * testsuite/curve25519-dup-test.c (test_main): Add test for 4g.
+ Delete some left-over debug output.
+
+ 2014-07-11 Niels Möller <nisse@lysator.liu.se>
+
+ * misc/ecc-formulas.tex: Some ECC notes.
+
+ * testsuite/curve25519-dup-test.c: New testcase.
+ * testsuite/Makefile.in (TS_HOGWEED_SOURCES): Added
+ curve25519-dup-test.c.
+
+ * testsuite/testutils.c (test_ecc_point): Made non-static.
+ * testsuite/testutils.h (struct ecc_ref_point): Moved here, from
+ testutils.h.
+ (test_ecc_point): Declare it.
+
+ * ecc-dup-eh.c (ecc_dup_eh, ecc_dup_eh_itch): New file, new functions.
+ * ecc-eh-to-a.c (ecc_eh_to_a, ecc_eh_to_a_itch): New file, new
+ functions.
+ * ecc.h: Declare new functions.
+ * ecc-internal.h (ECC_EH_TO_A_ITCH, ECC_DUP_EH_ITCH): New macros.
+ * Makefile.in (hogweed_SOURCES): Added ecc-dup-eh.c and
+ ecc-eh-to-a.c.
+
+ * ecc-internal.h (struct ecc_curve): New constant edwards_root.
+ * ecc-192.c (nettle_secp_192r1): Updated accordingly, additional
+ NULL pointer.
+ * ecc-224.c (nettle_secp_224r1): Likewise.
+ * ecc-256.c (nettle_secp_256r1): Likewise.
+ * ecc-384.c (nettle_secp_384r1): Likewise.
+ * ecc-521.c (nettle_secp_521r1): Likewise.
+ * ecc-25519.c (nettle_curve25519): Initialize new constant.
+
+ * eccdata.c (ecc_curve_init): For curve 25519, use correct
+ constant for edwards coordinate transform, and output the constant
+ as ecc_edwards.
+
+ 2014-07-06 Niels Möller <nisse@lysator.liu.se>
+
+ * eccdata.c: Use separate is_zero flag to represent the neutral
+ element.
+ (output_point, output_point_redc): Unified to a single function,
+ with a use_redc flag argument. Also support conversion to Edwards
+ form.
+ (ecc_curve_init_str): New argument for Edwards curve conversion
+ constant.
+
+ 2014-07-04 Niels Möller <nisse@lysator.liu.se>
+
++ Started curve25519 branch.
+ * 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-08-23 Niels Möller <nisse@lysator.liu.se>
+
+ * ecc-modp.c (ecc_modp_sub_1): Deleted unused function.
+ * ecc-internal.h: Deleted corresponding declaration.
+
+ * examples/nettle-benchmark.c (time_cipher): Fixed memset calls,
+ amending the totally broken change from 2014-02-06.
+
2014-07-02 Niels Möller <nisse@lysator.liu.se>
* eccdata.c (ecc_dup): Use mpz_submul_ui, now available in
#define ecc_generic_modq _nettle_ecc_generic_modq
#define ecc_modp_add _nettle_ecc_modp_add
#define ecc_modp_sub _nettle_ecc_modp_sub
-#define ecc_modp_sub_1 _nettle_ecc_modp_sub_1
#define ecc_modp_mul_1 _nettle_ecc_modp_mul_1
#define ecc_modp_addmul_1 _nettle_ecc_modp_addmul_1
#define ecc_modp_submul_1 _nettle_ecc_modp_submul_1
#define sec_sub_1 _nettle_sec_sub_1
#define sec_tabselect _nettle_sec_tabselect
#define sec_modinv _nettle_sec_modinv
+ #define ecc_25519_sqrt _nettle_ecc_25519_sqrt
#define ECC_MAX_SIZE ((521 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
/* Window size for ecc_mul_a. Using 4 bits seems like a good choice,
for both Intel x86_64 and ARM Cortex A9. For the larger curves, of
- 384 and 521 bits, we could improve seepd by a few percent if we go
+ 384 and 521 bits, we could improve speed by a few percent if we go
up to 5 bits, but I don't think that's worth doubling the
storage. */
#define ECC_MUL_A_WBITS 4
+ /* And for ecc_mul_a_eh */
+ #define ECC_MUL_A_EH_WBITS 4
+
/* Reduces from 2*ecc->size to ecc->size. */
/* Required to return a result < 2q. This property is inherited by
modp_mul and modp_add. */
typedef void ecc_mod_func (const struct ecc_curve *ecc, mp_limb_t *rp);
+ typedef void ecc_mul_g_func (const struct ecc_curve *ecc, mp_limb_t *r,
+ const mp_limb_t *np, mp_limb_t *scratch);
+
+ typedef void ecc_mul_func (const struct ecc_curve *ecc,
+ mp_limb_t *r,
+ const mp_limb_t *np, const mp_limb_t *p,
+ mp_limb_t *scratch);
+
+ typedef void ecc_h_to_a_func (const struct ecc_curve *ecc,
+ int flags,
+ mp_limb_t *r, const mp_limb_t *p,
+ mp_limb_t *scratch);
+
/* Represents an elliptic curve of the form
y^2 = x^3 - 3x + b (mod p)
unsigned short pippenger_k;
unsigned short pippenger_c;
+ unsigned short mul_itch;
+ unsigned short mul_g_itch;
+ unsigned short h_to_a_itch;
+
+ ecc_mod_func *modp;
+ ecc_mod_func *redc;
+ ecc_mod_func *reduce;
+ ecc_mod_func *modq;
+
+ ecc_mul_func *mul;
+ ecc_mul_g_func *mul_g;
+ ecc_h_to_a_func *h_to_a;
+
/* The prime p. */
const mp_limb_t *p;
const mp_limb_t *b;
const mp_limb_t *g;
/* Generator with coordinates in Montgomery form. */
const mp_limb_t *redc_g;
-
- ecc_mod_func *modp;
- ecc_mod_func *redc;
- ecc_mod_func *reduce;
- ecc_mod_func *modq;
+ /* If non-NULL, the constant needed for transformation to the
+ equivalent Edwards curve. */
+ const mp_limb_t *edwards_root;
/* B^size mod p. Expected to have at least 32 leading zeros
(equality for secp_256r1). */
ecc_modp_sub (const struct ecc_curve *ecc, mp_limb_t *rp,
const mp_limb_t *ap, const mp_limb_t *bp);
-void
-ecc_modp_sub_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
- const mp_limb_t *ap, mp_limb_t b);
-
void
ecc_modp_mul_1 (const struct ecc_curve *ecc, mp_limb_t *rp,
const mp_limb_t *ap, const mp_limb_t b);
const mp_limb_t *mp, const mp_limb_t *mp1h, mp_size_t bit_size,
mp_limb_t *scratch);
+ int
+ ecc_25519_sqrt(mp_limb_t *rp, const mp_limb_t *ap);
+
/* Current scratch needs: */
#define ECC_MODINV_ITCH(size) (3*(size))
#define ECC_J_TO_A_ITCH(size) (5*(size))
- #define ECC_DUP_JA_ITCH(size) (5*(size))
+ #define ECC_EH_TO_A_ITCH(size) (5*(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))
#define ECC_ADD_JJA_ITCH(size) (6*(size))
#define ECC_ADD_JJJ_ITCH(size) (8*(size))
+ #define ECC_ADD_EH_ITCH(size) (6*(size))
+ #define ECC_ADD_EHH_ITCH(size) (7*(size))
#define ECC_MUL_G_ITCH(size) (9*(size))
+ #define ECC_MUL_G_EH_ITCH(size) (9*(size))
#if ECC_MUL_A_WBITS == 0
#define ECC_MUL_A_ITCH(size) (12*(size))
#else
#define ECC_MUL_A_ITCH(size) \
(((3 << ECC_MUL_A_WBITS) + 11) * (size))
#endif
+ #if ECC_MUL_A_EH_WBITS == 0
+ #define ECC_MUL_A_EH_ITCH(size) (13*(size))
+ #else
+ #define ECC_MUL_A_EH_ITCH(size) \
+ (((3 << ECC_MUL_A_EH_WBITS) + 10) * (size))
+ #endif
#define ECC_ECDSA_SIGN_ITCH(size) (12*(size))
#define ECC_ECDSA_VERIFY_ITCH(size) \
(6*(size) + ECC_MUL_A_ITCH ((size)))
git.samba.org / gd / nettle / commitdiff