+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-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-a-to-eh.c ecc-eh-to-a.c \
+ ecc-dup-eh.c ecc-add-eh.c ecc-add-ehh.c \
+ ecc-mul-g-eh.c ecc-mul-a-eh.c \
ecc-mul-g.c ecc-mul-a.c ecc-hash.c ecc-random.c \
ecc-point.c ecc-scalar.c ecc-point-mul.c ecc-point-mul-g.c \
ecc-ecdsa-sign.c ecdsa-sign.c \
ecc-ecdsa-verify.c ecdsa-verify.c ecdsa-keygen.c \
+ curve25519-mul-g.c curve25519-mul.c \
$(OPT_HOGWEED_SOURCES)
HEADERS = aes.h arcfour.h arctwo.h asn1.h blowfish.h \
base16.h base64.h buffer.h camellia.h cast128.h \
cbc.h ccm.h chacha.h chacha-poly1305.h ctr.h \
- des.h des-compat.h dsa.h dsa-compat.h eax.h \
+ curve25519.h des.h des-compat.h dsa.h dsa-compat.h eax.h \
ecc-curve.h ecc.h ecdsa.h \
gcm.h gosthash94.h hmac.h \
knuth-lfib.h \
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
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 \
clean-here:
-rm -f $(TARGETS) $(IMPLICIT_TARGETS) *.$(OBJEXT) *.p$(OBJEXT) *.s \
- ecc-192.h ecc-224.h ecc-256.h ecc-384.h ecc-521.h \
+ ecc-192.h ecc-224.h ecc-256.h ecc-384.h ecc-521.h ecc-25519.h \
eccdata$(EXEEXT_FOR_BUILD) eccdata.stamp
-rm -rf .lib libnettle.stamp libhogweed.stamp
asm_hogweed_optional_list=""
if test "x$enable_public_key" = "xyes" ; then
asm_hogweed_optional_list="ecc-192-modp.asm ecc-224-modp.asm \
- ecc-256-redc.asm ecc-384-modp.asm ecc-521-modp.asm"
+ ecc-25519-modp.asm ecc-256-redc.asm ecc-384-modp.asm ecc-521-modp.asm"
fi
OPT_ASM_NETTLE_SOURCES=""
#undef HAVE_NATIVE_ecc_192_redc
#undef HAVE_NATIVE_ecc_224_modp
#undef HAVE_NATIVE_ecc_224_redc
+#undef HAVE_NATIVE_ecc_25519_modp
#undef HAVE_NATIVE_ecc_256_modp
#undef HAVE_NATIVE_ecc_256_redc
#undef HAVE_NATIVE_ecc_384_modp
--- /dev/null
+/* curve25519-mul-g.c
+
+ 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 <string.h>
+
+#include "curve25519.h"
+
+#include "ecc.h"
+#include "ecc-internal.h"
+
+/* Intended to be compatible with NaCl's crypto_scalarmult_base. */
+void
+curve25519_mul_g (uint8_t *r, const uint8_t *n)
+{
+ uint8_t t[CURVE25519_SIZE];
+ mp_limb_t *scratch;
+ mp_size_t ecc_size;
+ mp_size_t itch;
+
+#define p scratch
+#define x (scratch + 3*ecc_size)
+#define scratch_out (scratch + 4*ecc_size)
+
+ memcpy (t, n, sizeof(t));
+ t[0] &= ~7;
+ t[CURVE25519_SIZE-1] = (t[CURVE25519_SIZE-1] & 0x3f) | 0x40;
+
+ ecc_size = nettle_curve25519.size;
+ itch = 4*ecc_size + ECC_MUL_G_EH_ITCH(ecc_size);
+ scratch = gmp_alloc_limbs (itch);
+
+ mpn_set_base256_le (x, ecc_size, t, CURVE25519_SIZE);
+
+ ecc_mul_g_eh (&nettle_curve25519, p, x, scratch_out);
+ ecc_eh_to_a (&nettle_curve25519, 2, x, p, scratch_out);
+
+ mpn_get_base256_le (r, CURVE25519_SIZE, x, ecc_size);
+ gmp_free_limbs (scratch, itch);
+}
--- /dev/null
+/* curve25519-mul.c
+
+ 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 <string.h>
+
+#include "curve25519.h"
+
+#include "ecc.h"
+#include "ecc-internal.h"
+
+/* Intended to be compatible with NaCl's crypto_scalarmult. NOTE: Not
+ side-channel silent, due to the sqrt. */
+int
+curve25519_mul (uint8_t *q, const uint8_t *n, const uint8_t *p)
+{
+ uint8_t t[CURVE25519_SIZE];
+ mp_size_t itch;
+ mp_limb_t *scratch;
+ const struct ecc_curve *ecc = &nettle_curve25519;
+
+#define x scratch
+#define y (scratch + ecc->size)
+#define s (scratch + 3*ecc->size)
+#define scratch_out (scratch + 4*ecc->size)
+
+ itch = 5*ecc->size + ECC_MUL_A_EH_ITCH (ecc->size);
+ scratch = gmp_alloc_limbs (itch);
+
+ mpn_set_base256_le (x, ecc->size, p, CURVE25519_SIZE);
+
+ /* First compute y coordinate, from
+
+ y^2 = x^3 + b x^2 + x = (x^2 + bx + 1) x
+ */
+ ecc_modp_sqr (&nettle_curve25519, y, x);
+ ecc_modp_addmul_1 (&nettle_curve25519, y, x, 0x76d06ULL);
+ ecc_modp_add (ecc, s, y, ecc->unit);
+ ecc_modp_mul (ecc, y, s, x);
+
+ /* FIXME: Pass s as scratch space to ecc_25519_sqrt */
+ if (!ecc_25519_sqrt (y, y))
+ /* y-coordinate doesn't belong to base field F_p. FIXME: Implement
+ case of y in F_{p^2}? */
+ return 0;
+
+ memcpy (t, n, sizeof(t));
+ t[0] &= ~7;
+ t[CURVE25519_SIZE-1] = (t[CURVE25519_SIZE-1] & 0x3f) | 0x40;
+
+ mpn_set_base256_le (s, ecc->size, t, CURVE25519_SIZE);
+
+ ecc_mul_a_eh (ecc, x, s, x, scratch_out);
+ ecc_eh_to_a (ecc, 2, s, x, scratch_out);
+ mpn_get_base256_le (q, CURVE25519_SIZE, s, ecc->size);
+
+ gmp_free_limbs (scratch, itch);
+ return 1;
+}
--- /dev/null
+/* curve25519.h
+
+ 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/.
+*/
+
+#ifndef NETTLE_CURVE25519_H
+#define NETTLE_CURVE25519_H
+
+#include "nettle-types.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/* Name mangling */
+#define curve25519_mul_g nettle_curve25519_mul_g
+#define curve25519_mul nettle_curve25519_mul
+
+#define CURVE25519_SIZE 32
+
+void
+curve25519_mul_g (uint8_t *q, const uint8_t *n);
+
+int
+curve25519_mul (uint8_t *q, const uint8_t *n, const uint8_t *p);
+
+#endif /* NETTLE_CURVE25519_H */
#include <assert.h>
+/* FIXME: Remove ecc.h include, once prototypes of more internal
+ functions are moved to ecc-internal.h */
+#include "ecc.h"
#include "ecc-internal.h"
#define USE_REDC 0
ECC_REDC_SIZE,
ECC_PIPPENGER_K,
ECC_PIPPENGER_C,
+
+ ECC_MUL_A_ITCH (ECC_LIMB_SIZE),
+ ECC_MUL_G_ITCH (ECC_LIMB_SIZE),
+ ECC_J_TO_A_ITCH (ECC_LIMB_SIZE),
+
+ ecc_192_modp,
+ ecc_generic_redc,
+ ecc_192_modp,
+ ecc_generic_modq,
+
+ ecc_mul_a,
+ ecc_mul_g,
+ ecc_j_to_a,
+
ecc_p,
ecc_b,
ecc_q,
ecc_g,
ecc_redc_g,
- ecc_192_modp,
- ecc_generic_redc,
- ecc_192_modp,
- ecc_generic_modq,
+ NULL,
ecc_Bmodp,
ecc_Bmodp_shifted,
ecc_pp1h,
# include "config.h"
#endif
+#include "ecc.h"
#include "ecc-internal.h"
#if HAVE_NATIVE_ecc_224_modp
ECC_REDC_SIZE,
ECC_PIPPENGER_K,
ECC_PIPPENGER_C,
+
+ ECC_MUL_A_ITCH (ECC_LIMB_SIZE),
+ ECC_MUL_G_ITCH (ECC_LIMB_SIZE),
+ ECC_J_TO_A_ITCH (ECC_LIMB_SIZE),
+
+ ecc_224_modp,
+ ecc_generic_redc,
+ USE_REDC ? ecc_generic_redc : ecc_224_modp,
+ ecc_generic_modq,
+
+ ecc_mul_a,
+ ecc_mul_g,
+ ecc_j_to_a,
+
ecc_p,
ecc_b,
ecc_q,
ecc_g,
ecc_redc_g,
- ecc_224_modp,
- ecc_generic_redc,
- USE_REDC ? ecc_generic_redc : ecc_224_modp,
- ecc_generic_modq,
+ NULL,
ecc_Bmodp,
ecc_Bmodp_shifted,
ecc_pp1h,
--- /dev/null
+/* ecc-25519.c
+
+ 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 <assert.h>
+
+#include "ecc.h"
+#include "ecc-internal.h"
+
+#define USE_REDC 0
+
+#include "ecc-25519.h"
+
+#if HAVE_NATIVE_ecc_25519_modp
+
+#define ecc_25519_modp nettle_ecc_25519_modp
+void
+ecc_25519_modp (const struct ecc_curve *ecc, mp_limb_t *rp);
+#else
+
+#define PHIGH_BITS (GMP_NUMB_BITS * ECC_LIMB_SIZE - 255)
+
+#if PHIGH_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 << PHIGH_BITS);
+ hi = rp[ECC_LIMB_SIZE-1];
+ cy = (cy << PHIGH_BITS) + (hi >> (GMP_NUMB_BITS - PHIGH_BITS));
+ rp[ECC_LIMB_SIZE-1] = (hi & (GMP_NUMB_MASK >> PHIGH_BITS))
+ + sec_add_1 (rp, rp, ECC_LIMB_SIZE - 1, 19 * cy);
+}
+#endif /* HAVE_NATIVE_ecc_25519_modp */
+
+#define QHIGH_BITS (GMP_NUMB_BITS * ECC_LIMB_SIZE - 252)
+
+#if QHIGH_BITS == 0
+#error Unsupported limb size */
+#endif
+
+static void
+ecc_25519_modq (const struct ecc_curve *ecc, mp_limb_t *rp)
+{
+ mp_size_t n;
+ mp_limb_t cy;
+
+ /* n is the offset where we add in the next term */
+ for (n = ECC_LIMB_SIZE; n-- > 0;)
+ {
+ mp_limb_t cy;
+
+ cy = mpn_submul_1 (rp + n,
+ ecc->Bmodq_shifted, ECC_LIMB_SIZE,
+ rp[n + ECC_LIMB_SIZE]);
+ /* Top limb of mBmodq_shifted is zero, so we get cy == 0 or 1 */
+ assert (cy < 2);
+ cnd_add_n (cy, rp+n, ecc_q, ECC_LIMB_SIZE);
+ }
+
+ cy = mpn_submul_1 (rp, ecc_q, ECC_LIMB_SIZE,
+ rp[ECC_LIMB_SIZE-1] >> (GMP_NUMB_BITS - QHIGH_BITS));
+ assert (cy < 2);
+ cnd_add_n (cy, rp, ecc_q, ECC_LIMB_SIZE);
+}
+
+/* Needs 2*ecc->size limbs at rp, and 2*ecc->size additional limbs of
+ scratch space. No overlap allowed. */
+static void
+ecc_modp_powm_2kp1 (const struct ecc_curve *ecc,
+ mp_limb_t *rp, const mp_limb_t *xp,
+ unsigned k, mp_limb_t *tp)
+{
+ if (k & 1)
+ {
+ ecc_modp_sqr (ecc, tp, xp);
+ k--;
+ }
+ else
+ {
+ ecc_modp_sqr (ecc, rp, xp);
+ ecc_modp_sqr (ecc, tp, rp);
+ k -= 2;
+ }
+ while (k > 0)
+ {
+ ecc_modp_sqr (ecc, rp, tp);
+ ecc_modp_sqr (ecc, tp, rp);
+ k -= 2;
+ }
+ ecc_modp_mul (ecc, rp, tp, xp);
+#undef t1
+#undef t2
+}
+
+/* Compute x such that x^2 = a (mod p). Returns one on success, zero
+ on failure. using the e == 2 special case of the Shanks-Tonelli
+ algorithm (see http://www.math.vt.edu/people/brown/doc/sqrts.pdf,
+ or Henri Cohen, Computational Algebraic Number Theory, 1.5.1.
+
+ NOTE: Not side-channel silent. FIXME: Compute square root in the
+ extended field if a isn't a square (mod p)? FIXME: Accept scratch
+ space from caller (could allow scratch == rp). */
+#if ECC_SQRT_E != 2
+#error Broken curve25519 parameters
+#endif
+int
+ecc_25519_sqrt(mp_limb_t *rp, const mp_limb_t *ap)
+{
+ mp_size_t itch;
+ mp_limb_t *scratch;
+ int res;
+ const struct ecc_curve *ecc = &nettle_curve25519;
+
+ itch = 7*ECC_LIMB_SIZE;
+ scratch = gmp_alloc_limbs (itch);
+
+#define t0 scratch
+#define a7 (scratch + 2*ECC_LIMB_SIZE)
+#define t1 (scratch + 3*ECC_LIMB_SIZE)
+#define t2 (scratch + 5*ECC_LIMB_SIZE)
+#define scratch_out (scratch + 3*ECC_LIMB_SIZE) /* overlap t1, t2 */
+
+#define xp (scratch + ECC_LIMB_SIZE)
+#define bp (scratch + 2*ECC_LIMB_SIZE)
+
+ /* a^{2^252 - 3} = a^{(p-5)/8}, using the addition chain
+ 2^252 - 3
+ = 1 + (2^252-4)
+ = 1 + 4 (2^250-1)
+ = 1 + 4 (2^125+1)(2^125-1)
+ = 1 + 4 (2^125+1)(1+2(2^124-1))
+ = 1 + 4 (2^125+1)(1+2(2^62+1)(2^62-1))
+ = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(2^31-1))
+ = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^28-1)))
+ = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^14-1)))
+ = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^7+1)(2^7-1)))
+ = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^7+1)(1+2(2^6-1))))
+ = 1 + 4 (2^125+1)(1+2(2^62+1)(2^31+1)(7+8(2^14+1)(2^7+1)(1+2(2^3+1)*7)))
+ */
+
+ ecc_modp_powm_2kp1 (ecc, t1, ap, 1, t2); /* a^3 */
+ ecc_modp_sqr (ecc, t0, t1); /* a^6 */
+ ecc_modp_mul (ecc, a7, t0, ap); /* a^7 */
+ ecc_modp_powm_2kp1 (ecc, t0, a7, 3, t1); /* a^63 = a^{2^6-1} */
+ ecc_modp_sqr (ecc, t1, t0); /* a^{2^7-2} */
+ ecc_modp_mul (ecc, t0, t1, ap); /* a^{2^7-1} */
+ ecc_modp_powm_2kp1 (ecc, t1, t0, 7, t2); /* a^{2^14-1}*/
+ ecc_modp_powm_2kp1 (ecc, t0, t1, 14, t2); /* a^{2^28-1} */
+ ecc_modp_sqr (ecc, t1, t0); /* a^{2^29-2} */
+ ecc_modp_sqr (ecc, t2, t1); /* a^{2^30-4} */
+ ecc_modp_sqr (ecc, t1, t2); /* a^{2^31-8} */
+ ecc_modp_mul (ecc, t0, t1, a7); /* a^{2^31-1} */
+ ecc_modp_powm_2kp1 (ecc, t1, t0, 31, t2); /* a^{2^62-1} */
+ ecc_modp_powm_2kp1 (ecc, t0, t1, 62, t2); /* a^{2^124-1}*/
+ ecc_modp_sqr (ecc, t1, t0); /* a^{2^125-2} */
+ ecc_modp_mul (ecc, t0, t1, ap); /* a^{2^125-1} */
+ ecc_modp_powm_2kp1 (ecc, t1, t0, 125, t2); /* a^{2^250-1} */
+ ecc_modp_sqr (ecc, t0, t1); /* a^{2^251-2} */
+ ecc_modp_sqr (ecc, t1, t0); /* a^{2^252-4} */
+ ecc_modp_mul (ecc, t0, t1, ap); /* a^{2^252-3} */
+
+ /* Compute candidate root x and fudgefactor b. */
+ ecc_modp_mul (ecc, xp, t0, ap); /* a^{(p+3)/8 */
+ ecc_modp_mul (ecc, bp, t0, xp); /* a^{(p-1)/4} */
+ /* Check if b == 1 (mod p) */
+ if (mpn_cmp (bp, ecc->p, ECC_LIMB_SIZE) >= 0)
+ mpn_sub_n (bp, bp, ecc->p, ECC_LIMB_SIZE);
+ if (mpn_cmp (bp, ecc->unit, ECC_LIMB_SIZE) == 0)
+ {
+ mpn_copyi (rp, xp, ECC_LIMB_SIZE);
+ res = 1;
+ }
+ else
+ {
+ mpn_add_1 (bp, bp, ECC_LIMB_SIZE, 1);
+ if (mpn_cmp (bp, ecc->p, ECC_LIMB_SIZE) == 0)
+ {
+ ecc_modp_mul (&nettle_curve25519, bp, xp, ecc_sqrt_z);
+ mpn_copyi (rp, bp, ECC_LIMB_SIZE);
+ res = 1;
+ }
+ else
+ res = 0;
+ }
+ gmp_free_limbs (scratch, itch);
+ return res;
+#undef t0
+#undef t1
+#undef t2
+#undef a7
+#undef xp
+#undef bp
+#undef scratch_out
+}
+
+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_MUL_A_EH_ITCH (ECC_LIMB_SIZE),
+ ECC_MUL_G_EH_ITCH (ECC_LIMB_SIZE),
+ ECC_EH_TO_A_ITCH (ECC_LIMB_SIZE),
+
+ ecc_25519_modp,
+ NULL,
+ ecc_25519_modp,
+ ecc_25519_modq,
+
+
+ ecc_mul_a_eh,
+ ecc_mul_g_eh,
+ ecc_eh_to_a,
+
+ ecc_p,
+ ecc_d, /* Use the Edwards curve constant. */
+ ecc_q,
+ ecc_g,
+ ecc_redc_g,
+ ecc_edwards,
+ ecc_Bmodp,
+ ecc_Bmodp_shifted,
+ ecc_pp1h,
+ ecc_redc_ppm1,
+ ecc_unit,
+ ecc_Bmodq,
+ ecc_mBmodq_shifted, /* Use q - 2^{252} instead. */
+ ecc_qp1h,
+ ecc_table
+};
#include <assert.h>
+#include "ecc.h"
#include "ecc-internal.h"
#if HAVE_NATIVE_ecc_256_redc
ECC_REDC_SIZE,
ECC_PIPPENGER_K,
ECC_PIPPENGER_C,
+
+ ECC_MUL_A_ITCH (ECC_LIMB_SIZE),
+ ECC_MUL_G_ITCH (ECC_LIMB_SIZE),
+ ECC_J_TO_A_ITCH (ECC_LIMB_SIZE),
+
+ ecc_256_modp,
+ ecc_256_redc,
+ USE_REDC ? ecc_256_redc : ecc_256_modp,
+ ecc_256_modq,
+
+ ecc_mul_a,
+ ecc_mul_g,
+ ecc_j_to_a,
+
ecc_p,
ecc_b,
ecc_q,
ecc_g,
ecc_redc_g,
- ecc_256_modp,
- ecc_256_redc,
- USE_REDC ? ecc_256_redc : ecc_256_modp,
- ecc_256_modq,
+ NULL,
ecc_Bmodp,
ecc_Bmodp_shifted,
ecc_pp1h,
#include <assert.h>
+#include "ecc.h"
#include "ecc-internal.h"
#define USE_REDC 0
ECC_REDC_SIZE,
ECC_PIPPENGER_K,
ECC_PIPPENGER_C,
+
+ ECC_MUL_A_ITCH (ECC_LIMB_SIZE),
+ ECC_MUL_G_ITCH (ECC_LIMB_SIZE),
+ ECC_J_TO_A_ITCH (ECC_LIMB_SIZE),
+
+ ecc_384_modp,
+ ECC_REDC_SIZE != 0 ? ecc_generic_redc : NULL,
+ ecc_384_modp,
+ ecc_generic_modq,
+
+ ecc_mul_a,
+ ecc_mul_g,
+ ecc_j_to_a,
+
ecc_p,
ecc_b,
ecc_q,
ecc_g,
ecc_redc_g,
- ecc_384_modp,
- ECC_REDC_SIZE != 0 ? ecc_generic_redc : NULL,
- ecc_384_modp,
- ecc_generic_modq,
+ NULL,
ecc_Bmodp,
ecc_Bmodp_shifted,
ecc_pp1h,
# include "config.h"
#endif
+#include "ecc.h"
#include "ecc-internal.h"
#define USE_REDC 0
ECC_REDC_SIZE,
ECC_PIPPENGER_K,
ECC_PIPPENGER_C,
+
+ ECC_MUL_A_ITCH (ECC_LIMB_SIZE),
+ ECC_MUL_G_ITCH (ECC_LIMB_SIZE),
+ ECC_J_TO_A_ITCH (ECC_LIMB_SIZE),
+
+ ecc_521_modp,
+ ecc_generic_redc,
+ ecc_521_modp,
+ ecc_generic_modq,
+
+ ecc_mul_a,
+ ecc_mul_g,
+ ecc_j_to_a,
+
ecc_p,
ecc_b,
ecc_q,
ecc_g,
ecc_redc_g,
- ecc_521_modp,
- ecc_generic_redc,
- ecc_521_modp,
- ecc_generic_modq,
+ NULL,
ecc_Bmodp,
ecc_Bmodp_shifted,
ecc_pp1h,
--- /dev/null
+/* ecc-a-to-eh.c
+
+ 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.h"
+#include "ecc-internal.h"
+
+mp_size_t
+ecc_a_to_eh_itch (const struct ecc_curve *ecc)
+{
+ return ECC_A_TO_EH_ITCH (ecc->size);
+}
+
+/* Convert from affine coordinates to homogeneous coordinates on the
+ corresponding Edwards curve. */
+void
+ecc_a_to_eh (const struct ecc_curve *ecc,
+ mp_limb_t *r, const mp_limb_t *p,
+ mp_limb_t *scratch)
+{
+#define xp p
+#define yp (p + ecc->size)
+
+#define up r
+#define vp (r + ecc->size)
+#define wp (r + 2*ecc->size)
+
+ /* u = t x / y
+ v = (x-1) / (x+1)
+
+ or in homogeneous coordinates
+
+ U = t x (x+1)
+ V = (x-1) y
+ W = (x+1) y
+ */
+
+ ecc_modp_mul (ecc, scratch, xp, yp);
+ ecc_modp_add (ecc, wp, scratch, yp);
+ ecc_modp_sub (ecc, vp, scratch, yp);
+
+ ecc_modp_sqr (ecc, scratch, xp);
+ ecc_modp_add (ecc, up, scratch, xp);
+ ecc_modp_mul (ecc, scratch, up, ecc->edwards_root);
+ mpn_copyi (up, scratch, ecc->size);
+}
void
ecc_a_to_j (const struct ecc_curve *ecc,
- int initial,
mp_limb_t *r, const mp_limb_t *p)
{
- if (ecc->use_redc && initial)
+ if (ecc->use_redc)
{
mpn_copyd (r + ecc->size, p, 2*ecc->size);
--- /dev/null
+/* ecc-add-eh.c
+
+ 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.h"
+#include "ecc-internal.h"
+
+mp_size_t
+ecc_add_eh_itch (const struct ecc_curve *ecc)
+{
+ return ECC_ADD_EH_ITCH (ecc->size);
+}
+
+/* Add two points on an Edwards curve, with result and first point in
+ homogeneous coordinates. */
+void
+ecc_add_eh (const struct ecc_curve *ecc,
+ mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
+ mp_limb_t *scratch)
+{
+#define x1 p
+#define y1 (p + ecc->size)
+#define z1 (p + 2*ecc->size)
+
+#define x2 q
+#define y2 (q + ecc->size)
+
+#define x3 r
+#define y3 (r + ecc->size)
+#define z3 (r + 2*ecc->size)
+
+ /* Formulas (from djb,
+ http://www.hyperelliptic.org/EFD/g1p/auto-edwards-projective.html#doubling-dbl-2007-bl):
+
+ Computation Operation Live variables
+
+ C = x1*x2 mul C
+ D = y1*y2 mul C, D
+ T = (x1+y1)(x2+y2) - C - D C, D, T
+ E = b*C*D 2 mul C, E, T (Replace C <-- D - C)
+ B = z1^2 sqr B, C, E, T
+ F = B - E B, C, E, F, T
+ G = B + E C, F, G, T
+ x3 = z1*F*T 3 mul C, F, G, T
+ y3 = z1*G*(D-C) 2 mul F, G
+ z3 = F*G mul
+ */
+#define C (scratch)
+#define D (scratch + 1*ecc->size)
+#define T (scratch + 2*ecc->size)
+#define E (scratch + 3*ecc->size)
+#define B (scratch + 4*ecc->size)
+#define F D
+#define G E
+
+ ecc_modp_mul (ecc, C, x1, x2);
+ ecc_modp_mul (ecc, D, y1, y2);
+ ecc_modp_add (ecc, x3, x1, y1);
+ ecc_modp_add (ecc, y3, x2, y2);
+ ecc_modp_mul (ecc, T, x3, y3);
+ ecc_modp_sub (ecc, T, T, C);
+ ecc_modp_sub (ecc, T, T, D);
+ ecc_modp_mul (ecc, x3, C, D);
+ ecc_modp_mul (ecc, E, x3, ecc->b);
+
+ ecc_modp_sub (ecc, C, D, C);
+ ecc_modp_sqr (ecc, B, z1);
+ ecc_modp_sub (ecc, F, B, E);
+ ecc_modp_add (ecc, G, B, E);
+
+ /* x3 */
+ ecc_modp_mul (ecc, B, F, T);
+ ecc_modp_mul (ecc, x3, B, z1);
+
+ /* y3 */
+ ecc_modp_mul (ecc, B, G, C);
+ ecc_modp_mul (ecc, y3, B, z1);
+
+ /* z3 */
+ ecc_modp_mul (ecc, B, F, G);
+ mpn_copyi (z3, B, ecc->size);
+}
--- /dev/null
+/* ecc-add-ehh.c
+
+ 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.h"
+#include "ecc-internal.h"
+
+mp_size_t
+ecc_add_ehh_itch (const struct ecc_curve *ecc)
+{
+ return ECC_ADD_EHH_ITCH (ecc->size);
+}
+
+/* Add two points on an Edwards curve, in homogeneous coordinates */
+void
+ecc_add_ehh (const struct ecc_curve *ecc,
+ mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
+ mp_limb_t *scratch)
+{
+#define x1 p
+#define y1 (p + ecc->size)
+#define z1 (p + 2*ecc->size)
+
+#define x2 q
+#define y2 (q + ecc->size)
+#define z2 (q + 2*ecc->size)
+
+#define x3 r
+#define y3 (r + ecc->size)
+#define z3 (r + 2*ecc->size)
+
+ /* Formulas (from djb,
+ http://www.hyperelliptic.org/EFD/g1p/auto-edwards-projective.html#doubling-dbl-2007-bl):
+
+ Computation Operation Live variables
+
+ C = x1*x2 mul C
+ D = y1*y2 mul C, D
+ T = (x1+y1)(x2+y2) - C - D C, D, T
+ E = b*C*D 2 mul C, E, T (Replace C <-- D - C)
+ A = z1*z2 mul A, C, E, T
+ B = A^2 sqr A, B, C, E, T
+ F = B - E A, B, C, E, F, T
+ G = B + E A, C, F, G, T
+ x3 = A*F*T 3 mul A, C, G
+ y3 = A*G*(D-C) 2 mul F, G
+ z3 = F*G mul
+ */
+#define C scratch
+#define D (scratch + ecc->size)
+#define T (scratch + 2*ecc->size)
+#define E (scratch + 3*ecc->size)
+#define A (scratch + 4*ecc->size)
+#define B (scratch + 5*ecc->size)
+#define F D
+#define G E
+
+ ecc_modp_mul (ecc, C, x1, x2);
+ ecc_modp_mul (ecc, D, y1, y2);
+ ecc_modp_add (ecc, A, x1, y1);
+ ecc_modp_add (ecc, B, x2, y2);
+ ecc_modp_mul (ecc, T, A, B);
+ ecc_modp_sub (ecc, T, T, C);
+ ecc_modp_sub (ecc, T, T, D);
+ ecc_modp_mul (ecc, x3, C, D);
+ ecc_modp_mul (ecc, E, x3, ecc->b);
+ ecc_modp_sub (ecc, C, D, C);
+
+ ecc_modp_mul (ecc, A, z1, z2);
+ ecc_modp_sqr (ecc, B, A);
+
+ ecc_modp_sub (ecc, F, B, E);
+ ecc_modp_add (ecc, G, B, E);
+
+ /* x3 */
+ ecc_modp_mul (ecc, B, F, T);
+ ecc_modp_mul (ecc, x3, B, A);
+
+ /* y3 */
+ ecc_modp_mul (ecc, B, G, C);
+ ecc_modp_mul (ecc, y3, B, A);
+
+ /* z3 */
+ ecc_modp_mul (ecc, B, F, G);
+ mpn_copyi (z3, B, ecc->size);
+}
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
}
--- /dev/null
+/* ecc-dup-eh.c
+
+ 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.h"
+#include "ecc-internal.h"
+
+mp_size_t
+ecc_dup_eh_itch (const struct ecc_curve *ecc)
+{
+ return ECC_DUP_EH_ITCH (ecc->size);
+}
+
+/* Double a point on an Edwards curve, in homogeneous coordinates */
+void
+ecc_dup_eh (const struct ecc_curve *ecc,
+ mp_limb_t *r, const mp_limb_t *p,
+ mp_limb_t *scratch)
+{
+ /* Formulas (from djb,
+ http://www.hyperelliptic.org/EFD/g1p/auto-edwards-projective.html#doubling-dbl-2007-bl):
+
+ Computation Operation Live variables
+
+ b = (x+y)^2 sqr b
+ c = x^2 sqr b, c
+ d = y^2 sqr b, c, d
+ e = c+d b, c, d, e
+ h = z^2 sqr b, c, d, e, h
+ j = e-2*h b, c, d, e, j
+ x' = (b-e)*j mul c, d, e, j
+ y' = e*(c-d) mul e, j
+ z' = e*j mul
+ */
+#define b scratch
+#define c (scratch + ecc->size)
+#define d (scratch + 2*ecc->size)
+#define e (scratch + 3*ecc->size)
+#define j (scratch + 4*ecc->size)
+
+ /* b */
+ ecc_modp_add (ecc, e, p, p + ecc->size);
+ ecc_modp_sqr (ecc, b, e);
+
+ /* c */
+ ecc_modp_sqr (ecc, c, p);
+ /* d */
+ ecc_modp_sqr (ecc, d, p + ecc->size);
+ /* h, can use r as scratch, even for in-place operation. */
+ ecc_modp_sqr (ecc, r, p + 2*ecc->size);
+ /* e, */
+ ecc_modp_add (ecc, e, c, d);
+ /* b - e */
+ ecc_modp_sub (ecc, b, b, e);
+ /* j */
+ ecc_modp_add (ecc, r, r, r);
+ ecc_modp_sub (ecc, j, e, r);
+
+ /* x' */
+ ecc_modp_mul (ecc, r, b, j);
+ /* y' */
+ ecc_modp_sub (ecc, c, c, d);
+ ecc_modp_mul (ecc, r + ecc->size, e, c);
+ /* z' */
+ ecc_modp_mul (ecc, b, e, j);
+ mpn_copyi (r + 2*ecc->size, b, ecc->size);
+}
ecc_modq_mul (ecc, u2, rp, sinv);
/* Total storage: 5*ecc->size + ECC_MUL_A_ITCH (ecc->size) */
- ecc_mul_a (ecc, 1, P2, u2, pp, u2 + ecc->size);
+ ecc_mul_a (ecc, P2, u2, pp, u2 + ecc->size);
/* u1 = h / s, P1 = u1 * G */
ecc_hash (ecc, hp, length, digest);
--- /dev/null
+/* ecc-eh-to-a.c
+
+ 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.h"
+#include "ecc-internal.h"
+
+mp_size_t
+ecc_eh_to_a_itch (const struct ecc_curve *ecc)
+{
+ /* Needs 2*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. */
+void
+ecc_eh_to_a (const struct ecc_curve *ecc,
+ int flags,
+ mp_limb_t *r, const mp_limb_t *p,
+ mp_limb_t *scratch)
+{
+#define izp scratch
+#define sp (scratch + ecc->size)
+#define tp (scratch + 2*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 = (v+1)/(v-1), 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. */
+
+ 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);
+ /* Needs 3*size scratch */
+ ecc_modp_inv (ecc, izp, izp + ecc->size, izp + 2*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);
+
+ if (flags & 2)
+ /* Skip y coordinate */
+ 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);
+}
#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). */
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)))
--- /dev/null
+/* ecc-mul-a-eh.c
+
+ Copyright (C) 2013, 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 <assert.h>
+
+#include "ecc.h"
+#include "ecc-internal.h"
+
+mp_size_t
+ecc_mul_a_eh_itch (const struct ecc_curve *ecc)
+{
+ /* Binary algorithm needs 6*ecc->size + scratch for ecc_add_ehh,
+ total 13 ecc->size
+
+ Window algorithm needs (3<<w) * ecc->size for the table,
+ 3*ecc->size for a temporary point, and scratch for
+ ecc_add_ehh. */
+ return ECC_MUL_A_EH_ITCH (ecc->size);
+}
+
+#if ECC_MUL_A_EH_WBITS == 0
+void
+ecc_mul_a_eh (const struct ecc_curve *ecc,
+ mp_limb_t *r,
+ const mp_limb_t *np, const mp_limb_t *p,
+ mp_limb_t *scratch)
+{
+#define pe scratch
+#define tp (scratch + 3*ecc->size)
+#define scratch_out (scratch + 6*ecc->size)
+
+ unsigned i;
+
+ ecc_a_to_eh (ecc, pe, p, pe + 3*ecc->size);
+
+ /* x = 0, y = 1, z = 1 */
+ mpn_zero (r, 3*ecc->size);
+ r[ecc->size] = r[2*ecc->size] = 1;
+
+ for (i = ecc->size; i-- > 0; )
+ {
+ mp_limb_t w = np[i];
+ mp_limb_t bit;
+
+ for (bit = (mp_limb_t) 1 << (GMP_NUMB_BITS - 1);
+ bit > 0;
+ bit >>= 1)
+ {
+ int digit;
+
+ ecc_dup_eh (ecc, r, r, scratch_out);
+ ecc_add_ehh (ecc, tp, r, pe, scratch_out);
+
+ digit = (w & bit) > 0;
+ /* If we had a one-bit, use the sum. */
+ cnd_copy (digit, r, tp, 3*ecc->size);
+ }
+ }
+}
+#else /* ECC_MUL_A_EH_WBITS > 1 */
+
+#define TABLE_SIZE (1U << ECC_MUL_A_EH_WBITS)
+#define TABLE_MASK (TABLE_SIZE - 1)
+
+#define TABLE(j) (table + (j) * 3*ecc->size)
+
+static void
+table_init (const struct ecc_curve *ecc,
+ mp_limb_t *table, unsigned bits,
+ const mp_limb_t *p,
+ mp_limb_t *scratch)
+{
+ unsigned size = 1 << bits;
+ unsigned j;
+
+ 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);
+
+ for (j = 2; j < size; j += 2)
+ {
+ ecc_dup_eh (ecc, TABLE(j), TABLE(j/2), scratch);
+ ecc_add_ehh (ecc, TABLE(j+1), TABLE(j), TABLE(1), scratch);
+ }
+}
+
+void
+ecc_mul_a_eh (const struct ecc_curve *ecc,
+ mp_limb_t *r,
+ const mp_limb_t *np, const mp_limb_t *p,
+ mp_limb_t *scratch)
+{
+#define tp scratch
+#define table (scratch + 3*ecc->size)
+ mp_limb_t *scratch_out = table + (3*ecc->size << ECC_MUL_A_EH_WBITS);
+
+ /* Avoid the mp_bitcnt_t type for compatibility with older GMP
+ versions. */
+ unsigned blocks = (ecc->bit_size + ECC_MUL_A_EH_WBITS - 1) / ECC_MUL_A_EH_WBITS;
+ unsigned bit_index = (blocks-1) * ECC_MUL_A_EH_WBITS;
+
+ mp_size_t limb_index = bit_index / GMP_NUMB_BITS;
+ unsigned shift = bit_index % GMP_NUMB_BITS;
+ mp_limb_t w, bits;
+
+ table_init (ecc, table, ECC_MUL_A_EH_WBITS, p, scratch_out);
+
+ w = np[limb_index];
+ bits = w >> shift;
+ if (limb_index < ecc->size - 1)
+ bits |= np[limb_index + 1] << (GMP_NUMB_BITS - shift);
+
+ assert (bits < TABLE_SIZE);
+
+ sec_tabselect (r, 3*ecc->size, table, TABLE_SIZE, bits);
+
+ for (;;)
+ {
+ unsigned j;
+ if (shift >= ECC_MUL_A_EH_WBITS)
+ {
+ shift -= ECC_MUL_A_EH_WBITS;
+ bits = w >> shift;
+ }
+ else
+ {
+ if (limb_index == 0)
+ {
+ assert (shift == 0);
+ break;
+ }
+ bits = w << (ECC_MUL_A_EH_WBITS - shift);
+ w = np[--limb_index];
+ shift = shift + GMP_NUMB_BITS - ECC_MUL_A_EH_WBITS;
+ bits |= w >> shift;
+ }
+ for (j = 0; j < ECC_MUL_A_EH_WBITS; j++)
+ ecc_dup_eh (ecc, r, r, scratch_out);
+
+ bits &= TABLE_MASK;
+ sec_tabselect (tp, 3*ecc->size, table, TABLE_SIZE, bits);
+ ecc_add_ehh (ecc, r, tp, r, scratch_out);
+ }
+#undef table
+#undef tp
+}
+
+#endif /* ECC_MUL_A_EH_WBITS > 1 */
#if ECC_MUL_A_WBITS == 0
void
ecc_mul_a (const struct ecc_curve *ecc,
- int initial, mp_limb_t *r,
+ mp_limb_t *r,
const mp_limb_t *np, const mp_limb_t *p,
mp_limb_t *scratch)
{
unsigned i;
- ecc_a_to_j (ecc, initial, pj, p);
+ ecc_a_to_j (ecc, pj, p);
mpn_zero (r, 3*ecc->size);
for (i = ecc->size, is_zero = 1; i-- > 0; )
static void
table_init (const struct ecc_curve *ecc,
mp_limb_t *table, unsigned bits,
- int initial, const mp_limb_t *p,
+ const mp_limb_t *p,
mp_limb_t *scratch)
{
unsigned size = 1 << bits;
unsigned j;
mpn_zero (TABLE(0), 3*ecc->size);
- ecc_a_to_j (ecc, initial, TABLE(1), p);
+ ecc_a_to_j (ecc, TABLE(1), p);
for (j = 2; j < size; j += 2)
{
void
ecc_mul_a (const struct ecc_curve *ecc,
- int initial, mp_limb_t *r,
+ mp_limb_t *r,
const mp_limb_t *np, const mp_limb_t *p,
mp_limb_t *scratch)
{
unsigned shift = bit_index % GMP_NUMB_BITS;
mp_limb_t w, bits;
- table_init (ecc, table, ECC_MUL_A_WBITS, initial, p, scratch_out);
+ table_init (ecc, table, ECC_MUL_A_WBITS, p, scratch_out);
w = np[limb_index];
bits = w >> shift;
--- /dev/null
+/* ecc-mul-g-eh.c
+
+ Copyright (C) 2013, 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/.
+*/
+
+/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
+
+#if HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include <assert.h>
+
+#include "ecc.h"
+#include "ecc-internal.h"
+
+mp_size_t
+ecc_mul_g_eh_itch (const struct ecc_curve *ecc)
+{
+ /* Needs 3*ecc->size + scratch for ecc_add_jja. */
+ return ECC_MUL_G_EH_ITCH (ecc->size);
+}
+
+void
+ecc_mul_g_eh (const struct ecc_curve *ecc, mp_limb_t *r,
+ const mp_limb_t *np, mp_limb_t *scratch)
+{
+ /* Scratch need determined by the ecc_add_eh call. Current total is
+ 9 * ecc->size, at most 648 bytes. */
+#define tp scratch
+#define scratch_out (scratch + 3*ecc->size)
+
+ unsigned k, c;
+ unsigned i, j;
+ unsigned bit_rows;
+
+ k = ecc->pippenger_k;
+ c = ecc->pippenger_c;
+
+ bit_rows = (ecc->bit_size + k - 1) / k;
+
+ /* x = 0, y = 1, z = 1 */
+ mpn_zero (r, 3*ecc->size);
+ r[ecc->size] = r[2*ecc->size] = 1;
+
+ for (i = k; i-- > 0; )
+ {
+ ecc_dup_eh (ecc, r, r, scratch);
+ for (j = 0; j * c < bit_rows; j++)
+ {
+ unsigned bits;
+ /* Avoid the mp_bitcnt_t type for compatibility with older GMP
+ versions. */
+ unsigned bit_index;
+
+ /* Extract c bits from n, stride k, starting at i + kcj,
+ ending at i + k (cj + c - 1)*/
+ for (bits = 0, bit_index = i + k*(c*j+c); bit_index > i + k*c*j; )
+ {
+ mp_size_t limb_index;
+ unsigned shift;
+
+ bit_index -= k;
+
+ limb_index = bit_index / GMP_NUMB_BITS;
+ if (limb_index >= ecc->size)
+ continue;
+
+ shift = bit_index % GMP_NUMB_BITS;
+ bits = (bits << 1) | ((np[limb_index] >> shift) & 1);
+ }
+ sec_tabselect (tp, 2*ecc->size,
+ (ecc->pippenger_table
+ + (2*ecc->size * (mp_size_t) j << c)),
+ 1<<c, bits);
+
+ ecc_add_eh (ecc, r, r, tp, scratch_out);
+ }
+ }
+#undef tp
+#undef scratch_out
+}
ecc_point_mul_g (struct ecc_point *r, const struct ecc_scalar *n)
{
TMP_DECL(scratch, mp_limb_t, 3*ECC_MAX_SIZE + ECC_MUL_G_ITCH (ECC_MAX_SIZE));
- mp_limb_t size = r->ecc->size;
- mp_size_t itch = 3*size + ECC_MUL_G_ITCH (size);
+ const struct ecc_curve *ecc = r->ecc;
+ mp_limb_t size = ecc->size;
+ mp_size_t itch = 3*size + ecc->mul_g_itch;
- assert (r->ecc == n->ecc);
+ assert (n->ecc == ecc);
TMP_ALLOC (scratch, itch);
- ecc_mul_g (r->ecc, scratch, n->p, scratch + 3*size);
- ecc_j_to_a (r->ecc, 1, r->p, scratch, scratch + 3*size);
+ ecc->mul_g (ecc, scratch, n->p, scratch + 3*size);
+ ecc->h_to_a (ecc, 1, r->p, scratch, scratch + 3*size);
}
ecc_point_mul (struct ecc_point *r, const struct ecc_scalar *n,
const struct ecc_point *p)
{
- mp_limb_t size = p->ecc->size;
- mp_size_t itch = 3*size + ECC_MUL_A_ITCH (size);
+ const struct ecc_curve *ecc = r->ecc;
+ mp_limb_t size = ecc->size;
+ mp_size_t itch = 3*size + ecc->mul_itch;
mp_limb_t *scratch = gmp_alloc_limbs (itch);
- assert (n->ecc == p->ecc);
- assert (r->ecc == p->ecc);
+ assert (n->ecc == ecc);
+ assert (p->ecc == ecc);
- ecc_mul_a (p->ecc, 1, scratch, n->p, p->p, scratch + 3*size);
- ecc_j_to_a (r->ecc, 1, r->p, scratch, scratch + 3*size);
+ ecc->mul (ecc, scratch, n->p, p->p, scratch + 3*size);
+ ecc->h_to_a (ecc, 1, r->p, scratch, scratch + 3*size);
gmp_free_limbs (scratch, itch);
}
mpz_init (lhs);
mpz_init (rhs);
- /* Check that y^2 = x^3 - 3*x + b (mod p) */
+ 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);
+ }
+ else
+ {
+ /* Check that y^2 = x^3 - 3*x + b (mod p) */
+ mpz_mul (rhs, x, x);
+ mpz_sub_ui (rhs, rhs, 3);
+ mpz_mul (rhs, rhs, x);
+ mpz_add (rhs, rhs, mpz_roinit_n (t, p->ecc->b, size));
+ }
+
mpz_mul (lhs, y, y);
- mpz_mul (rhs, x, x);
- mpz_sub_ui (rhs, rhs, 3);
- mpz_mul (rhs, rhs, x);
- mpz_add (rhs, rhs, mpz_roinit_n (t, p->ecc->b, size));
res = mpz_congruent_p (lhs, rhs, mpz_roinit_n (t, p->ecc->p, size));
#define ecc_size nettle_ecc_size
#define ecc_size_a nettle_ecc_size_a
#define ecc_size_j nettle_ecc_size_j
-#define ecc_a_to_a_itch nettle_ecc_a_to_a_itch
-#define ecc_a_to_a nettle_ecc_a_to_a
#define ecc_a_to_j nettle_ecc_a_to_j
#define ecc_j_to_a_itch nettle_ecc_j_to_a_itch
#define ecc_j_to_a nettle_ecc_j_to_a
-#define ecc_dup_ja_itch nettle_ecc_dup_ja_itch
-#define ecc_dup_ja nettle_ecc_dup_ja
+#define ecc_eh_to_a_itch nettle_ecc_eh_to_a_itch
+#define ecc_eh_to_a nettle_ecc_eh_to_a
+#define ecc_a_to_eh_itch nettle_ecc_a_to_eh_itch
+#define ecc_a_to_eh nettle_ecc_a_to_eh
#define ecc_dup_jj_itch nettle_ecc_dup_jj_itch
#define ecc_dup_jj nettle_ecc_dup_jj
#define ecc_add_jja_itch nettle_ecc_add_jja_itch
#define ecc_add_jja nettle_ecc_add_jja
#define ecc_add_jjj_itch nettle_ecc_add_jjj_itch
#define ecc_add_jjj nettle_ecc_add_jjj
+#define ecc_dup_eh_itch nettle_ecc_dup_eh_itch
+#define ecc_dup_eh nettle_ecc_dup_eh
+#define ecc_add_eh_itch nettle_ecc_add_eh_itch
+#define ecc_add_eh nettle_ecc_add_eh
+#define ecc_add_ehh_itch nettle_ecc_add_ehh_itch
+#define ecc_add_ehh nettle_ecc_add_ehh
#define ecc_mul_g_itch nettle_ecc_mul_g_itch
#define ecc_mul_g nettle_ecc_mul_g
#define ecc_mul_a_itch nettle_ecc_mul_a_itch
#define ecc_mul_a nettle_ecc_mul_a
+#define ecc_mul_g_eh_itch nettle_ecc_mul_g_eh_itch
+#define ecc_mul_g_eh nettle_ecc_mul_g_eh
+#define ecc_mul_a_eh_itch nettle_ecc_mul_a_eh_itch
+#define ecc_mul_a_eh nettle_ecc_mul_a_eh
struct ecc_curve;
_ecc_*, and provide public ecc_* functions which handle the
infinity points properly? */
-/* Converts the affine coordinates of a point into montgomery form, if
- used for this curve. */
-mp_size_t
-ecc_a_to_a_itch (const struct ecc_curve *ecc);
-void
-ecc_a_to_a (const struct ecc_curve *ecc,
- mp_limb_t *r, const mp_limb_t *p,
- mp_limb_t *scratch);
-
/* Converts a point P in affine coordinates into a point R in jacobian
- coordinates. If INITIAL is non-zero, and the curve uses montgomery
- coordinates, also convert coordinates to montgomery form. */
+ coordinates. */
void
ecc_a_to_j (const struct ecc_curve *ecc,
- int initial,
mp_limb_t *r, const mp_limb_t *p);
/* Converts a point P in jacobian coordinates into a point R in affine
mp_limb_t *r, const mp_limb_t *p,
mp_limb_t *scratch);
-/* Group operations */
+/* Converts a point P on an Edwards curve to affine coordinates on
+ the corresponding Montgomery curve. */
+mp_size_t
+ecc_eh_to_a_itch (const struct ecc_curve *ecc);
+void
+ecc_eh_to_a (const struct ecc_curve *ecc,
+ int flags,
+ mp_limb_t *r, const mp_limb_t *p,
+ mp_limb_t *scratch);
-/* Point doubling, with jacobian output and affine input. Corner
- cases: Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */
mp_size_t
-ecc_dup_ja_itch (const struct ecc_curve *ecc);
+ecc_a_to_eh_itch (const struct ecc_curve *ecc);
void
-ecc_dup_ja (const struct ecc_curve *ecc,
- mp_limb_t *r, const mp_limb_t *p,
- mp_limb_t *scratch);
+ecc_a_to_eh (const struct ecc_curve *ecc,
+ mp_limb_t *r, const mp_limb_t *p,
+ mp_limb_t *scratch);
+
+/* Group operations */
/* Point doubling, with jacobian input and output. Corner cases:
Correctly sets R = 0 (r_Z = 0) if p = 0 or 2p = 0. */
mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
mp_limb_t *scratch);
+/* FIXME: Use a generic ecc_dup, ecc_add, for any type of curve. */
+/* Point doubling on an Edwards curve, with homogeneous
+ cooordinates. */
+mp_size_t
+ecc_dup_eh_itch (const struct ecc_curve *ecc);
+void
+ecc_dup_eh (const struct ecc_curve *ecc,
+ mp_limb_t *r, const mp_limb_t *p,
+ mp_limb_t *scratch);
+
+mp_size_t
+ecc_add_eh_itch (const struct ecc_curve *ecc);
+void
+ecc_add_eh (const struct ecc_curve *ecc,
+ mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
+ mp_limb_t *scratch);
+
+mp_size_t
+ecc_add_ehh_itch (const struct ecc_curve *ecc);
+void
+ecc_add_ehh (const struct ecc_curve *ecc,
+ mp_limb_t *r, const mp_limb_t *p, const mp_limb_t *q,
+ mp_limb_t *scratch);
/* Computes N * the group generator. N is an array of ecc_size()
limbs. It must be in the range 0 < N < group order, then R != 0,
const mp_limb_t *np, mp_limb_t *scratch);
/* Computes N * P. The scalar N is the same as for ecc_mul_g. P is a
- non-zero point on the curve, in affine coordinates. Pass a non-zero
- INITIAL if the point coordinates have not previously been converted
- to Montgomery representation. Output R is a non-zero point, in
- Jacobian coordinates. */
+ non-zero point on the curve, in affine coordinates. Output R is a
+ non-zero point, in Jacobian coordinates. */
mp_size_t
ecc_mul_a_itch (const struct ecc_curve *ecc);
void
ecc_mul_a (const struct ecc_curve *ecc,
- int initial, mp_limb_t *r,
+ mp_limb_t *r,
const mp_limb_t *np, const mp_limb_t *p,
mp_limb_t *scratch);
+mp_size_t
+ecc_mul_g_eh_itch (const struct ecc_curve *ecc);
+void
+ecc_mul_g_eh (const struct ecc_curve *ecc, mp_limb_t *r,
+ const mp_limb_t *np, mp_limb_t *scratch);
+
+mp_size_t
+ecc_mul_a_eh_itch (const struct ecc_curve *ecc);
+void
+ecc_mul_a_eh (const struct ecc_curve *ecc,
+ mp_limb_t *r,
+ const mp_limb_t *np, const mp_limb_t *p,
+ mp_limb_t *scratch);
+
+
#ifdef __cplusplus
}
#endif
Generate compile time constant (but machine dependent) tables.
- Copyright (C) 2013 Niels Möller
+ Copyright (C) 2013, 2014 Niels Möller
This file is part of GNU Nettle.
#include "mini-gmp.c"
-/* Affine coordinates, for simplicity. Infinity point represented as x
- == y == 0. FIXME: Doesn't quite work for Montgomery curves, where
- (0,0) is a normal finite point. Shouldn't occur in these
- computations, though. */
+/* Affine coordinates, for simplicity. Infinity point, i.e., te
+ neutral group element, is represented using the is_zero flag. */
struct ecc_point
{
+ int is_zero;
mpz_t x;
mpz_t y;
};
mpz_t q;
struct ecc_point g;
+ /* Non-zero if we want elements represented as point s(u, v) on an
+ equivalent Edwards curve, using
+
+ u = t x / y
+ v = (x-1) / (x+1)
+ */
+ int use_edwards;
+ mpz_t d;
+ mpz_t t;
+
/* Table for pippenger's algorithm.
Element
static int
ecc_zero_p (const struct ecc_point *p)
{
- return mpz_sgn (p->x) == 0 && mpz_sgn (p->y) == 0;
+ return p->is_zero;
}
static int
ecc_equal_p (const struct ecc_point *p, const struct ecc_point *q)
{
- return mpz_cmp (p->x, q->x) == 0 && mpz_cmp (p->y, q->y) == 0;
+ return p->is_zero ? q->is_zero
+ : !q->is_zero && mpz_cmp (p->x, q->x) == 0 && mpz_cmp (p->y, q->y) == 0;
}
static void
ecc_set_zero (struct ecc_point *r)
{
- mpz_set_ui (r->x, 0);
- mpz_set_ui (r->y, 0);
+ r->is_zero = 1;
}
static void
ecc_set (struct ecc_point *r, const struct ecc_point *p)
{
+ r->is_zero = p->is_zero;
mpz_set (r->x, p->x);
mpz_set (r->y, p->y);
}
mpz_sub (y, y, p->y);
mpz_mod (y, y, ecc->p);
+ r->is_zero = 0;
mpz_swap (x, r->x);
mpz_swap (y, r->y);
-
+
mpz_clear (m);
mpz_clear (t);
mpz_clear (x);
mpz_sub (y, y, p->y);
mpz_mod (y, y, ecc->p);
+ r->is_zero = 0;
mpz_swap (x, r->x);
mpz_swap (y, r->y);
ecc_set_str (struct ecc_point *p,
const char *x, const char *y)
{
+ p->is_zero = 0;
mpz_set_str (p->x, x, 16);
mpz_set_str (p->y, y, 16);
}
static void
ecc_curve_init_str (struct ecc_curve *ecc, enum ecc_type type,
const char *p, const char *b, const char *q,
- const char *gx, const char *gy)
+ const char *gx, const char *gy,
+ const char *d, const char *t)
{
ecc->type = type;
ecc->table = NULL;
ecc->ref = NULL;
+
+ mpz_init (ecc->d);
+ mpz_init (ecc->t);
+
+ ecc->use_edwards = (t != NULL);
+ if (ecc->use_edwards)
+ {
+ mpz_set_str (ecc->t, t, 16);
+ mpz_set_str (ecc->d, d, 16);
+ }
}
static void
"f4ff0afd82ff1012",
"07192b95ffc8da78631011ed6b24cdd5"
- "73f977a11e794811");
+ "73f977a11e794811",
+ NULL, NULL);
ecc->ref = ecc_alloc (3);
ecc_set_str (&ecc->ref[0], /* 2 g */
"dafebf5828783f2ad35534631588a3f629a70fb16982a888",
"56c21122343280d6115c1d21",
"bd376388b5f723fb4c22dfe6cd4375a0"
- "5a07476444d5819985007e34");
+ "5a07476444d5819985007e34",
+ NULL, NULL);
ecc->ref = ecc_alloc (3);
ecc_set_str (&ecc->ref[0], /* 2 g */
"77037D812DEB33A0F4A13945D898C296",
"4FE342E2FE1A7F9B8EE7EB4A7C0F9E16"
- "2BCE33576B315ECECBB6406837BF51F5");
+ "2BCE33576B315ECECBB6406837BF51F5",
+ NULL, NULL);
ecc->ref = ecc_alloc (3);
ecc_set_str (&ecc->ref[0], /* 2 g */
"3617de4a96262c6f5d9e98bf9292dc29"
"f8f41dbd289a147ce9da3113b5f0b8c0"
- "0a60b1ce1d7e819d7a431d7c90ea0e5f");
+ "0a60b1ce1d7e819d7a431d7c90ea0e5f",
+ NULL, NULL);
ecc->ref = ecc_alloc (3);
ecc_set_str (&ecc->ref[0], /* 2 g */
"39296a789a3bc0045c8a5fb42c7d1bd9"
"98f54449579b446817afbd17273e662c"
"97ee72995ef42640c550b9013fad0761"
- "353c7086a272c24088be94769fd16650");
+ "353c7086a272c24088be94769fd16650",
+ NULL, NULL);
ecc->ref = ecc_alloc (3);
ecc_set_str (&ecc->ref[0], /* 2 g */
case 255:
/* curve25519, y^2 = x^3 + 486662 x^2 + x (mod p), with p = 2^{255} - 19.
- Acccording to http://cr.yp.to/papers.html#newelliptic, this
+ According to http://cr.yp.to/papers.html#newelliptic, this
is birationally equivalent to the Edwards curve
x^2 + y^2 = 1 + (121665/121666) x^2 y^2 (mod p).
"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",
x = Mod(9, 2^255-19); sqrt(x^3 + 486662*x^2 + x)
*/
"20ae19a1b8a086b4e01edd2c7748d14c"
- "923d4d7e6d7c61b229e9c5a27eced3d9");
+ "923d4d7e6d7c61b229e9c5a27eced3d9",
+ /* (121665/121666) mod p, from PARI/GP
+ c = Mod(121665, p); c / (c+1)
+ */
+ "2dfc9311d490018c7338bf8688861767"
+ "ff8ff5b2bebe27548a14b235eca6874a",
+ /* sqrt(486664) mod p, from PARI/GP
+ sqrt(Mod(486664, p)) */
+ "141b0b6806563d503de05885280b5910"
+ "9ca5ee38d7b56c9c165db7106377bbd8");
ecc->ref = ecc_alloc (3);
ecc_set_str (&ecc->ref[0], /* 2 g */
"20d342d51873f1b7d9750c687d157114"
mpz_clear (n);
}
+static void
+ecc_point_out (FILE *f, const struct ecc_point *p)
+{
+ if (p->is_zero)
+ fprintf (f, "zero");
+ else
+ {
+ fprintf (stderr, "(");
+ mpz_out_str (stderr, 16, p->x);
+ fprintf (stderr, ",\n ");
+ mpz_out_str (stderr, 16, (p)->y);
+ fprintf (stderr, ")");
+ }
+}
#define ASSERT_EQUAL(p, q) do { \
if (!ecc_equal_p (p, q)) \
{ \
fprintf (stderr, "%s:%d: ASSERT_EQUAL (%s, %s) failed.\n", \
__FILE__, __LINE__, #p, #q); \
- fprintf (stderr, "p = ("); \
- mpz_out_str (stderr, 16, (p)->x); \
- fprintf (stderr, ",\n "); \
- mpz_out_str (stderr, 16, (p)->y); \
- fprintf (stderr, ")\nq = ("); \
- mpz_out_str (stderr, 16, (q)->x); \
- fprintf (stderr, ",\n "); \
- mpz_out_str (stderr, 16, (q)->y); \
- fprintf (stderr, ")\n"); \
+ fprintf (stderr, "p = "); \
+ ecc_point_out (stderr, (p)); \
+ fprintf (stderr, "\nq = "); \
+ ecc_point_out (stderr, (q)); \
+ fprintf (stderr, "\n"); \
abort(); \
} \
} while (0)
{ \
fprintf (stderr, "%s:%d: ASSERT_ZERO (%s) failed.\n", \
__FILE__, __LINE__, #p); \
- fprintf (stderr, "p = ("); \
- mpz_out_str (stderr, 16, (p)->x); \
- fprintf (stderr, ",\n "); \
- mpz_out_str (stderr, 16, (p)->y); \
- fprintf (stderr, ")\n"); \
+ fprintf (stderr, "p = "); \
+ ecc_point_out (stderr, (p)); \
+ fprintf (stderr, "\n"); \
abort(); \
} \
} while (0)
}
static void
-output_point (const char *name, const struct ecc_point *p,
+output_point (const char *name, const struct ecc_curve *ecc,
+ const struct ecc_point *p, int use_redc,
unsigned size, unsigned bits_per_limb)
{
- if (name)
- printf("static const mp_limb_t %s[%u] = {", name, 2*size);
-
- output_digits (p->x, size, bits_per_limb);
- output_digits (p->y, size, bits_per_limb);
+ mpz_t x, y, t;
- if (name)
- printf("\n};\n");
-}
-
-static void
-output_point_redc (const char *name, const struct ecc_curve *ecc,
- const struct ecc_point *p,
- unsigned size, unsigned bits_per_limb)
-{
- mpz_t t;
+ mpz_init (x);
+ mpz_init (y);
mpz_init (t);
-
+
if (name)
printf("static const mp_limb_t %s[%u] = {", name, 2*size);
-
- mpz_mul_2exp (t, p->x, size * bits_per_limb);
- mpz_mod (t, t, ecc->p);
-
- output_digits (t, size, bits_per_limb);
- mpz_mul_2exp (t, p->y, size * bits_per_limb);
- mpz_mod (t, t, ecc->p);
+ if (ecc->use_edwards)
+ {
+ if (ecc_zero_p (p))
+ {
+ mpz_set_si (x, 0);
+ mpz_set_si (y, 1);
+ }
+ else if (!mpz_sgn (p->y))
+ {
+ assert (!mpz_sgn (p->x));
+ mpz_set_si (x, 0);
+ mpz_set_si (y, -1);
+ }
+ else
+ {
+ mpz_invert (x, p->y, ecc->p);
+ mpz_mul (x, x, p->x);
+ mpz_mul (x, x, ecc->t);
+ mpz_mod (x, x, ecc->p);
+
+ mpz_sub_ui (y, p->x, 1);
+ mpz_add_ui (t, p->x, 1);
+ mpz_invert (t, t, ecc->p);
+ mpz_mul (y, y, t);
+ mpz_mod (y, y, ecc->p);
+ }
+ }
+ else
+ {
+ mpz_set (x, p->x);
+ mpz_set (y, p->y);
+ }
+ if (use_redc)
+ {
+ mpz_mul_2exp (x, x, size * bits_per_limb);
+ mpz_mod (x, x, ecc->p);
+ mpz_mul_2exp (y, y, size * bits_per_limb);
+ mpz_mod (y, y, ecc->p);
+ }
- output_digits (t, size, bits_per_limb);
+ output_digits (x, size, bits_per_limb);
+ output_digits (y, size, bits_per_limb);
if (name)
printf("\n};\n");
+ mpz_clear (x);
+ mpz_clear (y);
mpz_clear (t);
}
{
unsigned limb_size = (ecc->bit_size + bits_per_limb - 1)/bits_per_limb;
unsigned i;
- unsigned bits;
+ unsigned bits, e;
int redc_limbs;
mpz_t t;
output_bignum ("ecc_p", ecc->p, limb_size, bits_per_limb);
output_bignum ("ecc_b", ecc->b, limb_size, bits_per_limb);
+ if (ecc->use_edwards)
+ output_bignum ("ecc_d", ecc->d, limb_size, bits_per_limb);
output_bignum ("ecc_q", ecc->q, limb_size, bits_per_limb);
- output_point ("ecc_g", &ecc->g, limb_size, bits_per_limb);
- output_point_redc ("ecc_redc_g", ecc, &ecc->g, limb_size, bits_per_limb);
+ output_point ("ecc_g", ecc, &ecc->g, 0, limb_size, bits_per_limb);
+ output_point ("ecc_redc_g", ecc, &ecc->g, 1, limb_size, bits_per_limb);
bits = output_modulo ("ecc_Bmodp", ecc->p, limb_size, bits_per_limb);
printf ("#define ECC_BMODP_SIZE %u\n",
bits = output_modulo ("ecc_Bmodq", ecc->q, limb_size, bits_per_limb);
printf ("#define ECC_BMODQ_SIZE %u\n",
(bits + bits_per_limb - 1) / bits_per_limb);
+ bits = mpz_sizeinbase (ecc->q, 2);
+ if (bits < ecc->bit_size)
+ {
+ /* for curve25519, with q = 2^k + q', with a much smaller q' */
+ unsigned mbits;
+ unsigned shift;
+
+ /* Shift to align the one bit at B */
+ shift = bits_per_limb * limb_size + 1 - bits;
+
+ mpz_set (t, ecc->q);
+ mpz_clrbit (t, bits-1);
+ mbits = mpz_sizeinbase (t, 2);
+
+ /* The shifted value must be a limb smaller than q. */
+ if (mbits + shift + bits_per_limb <= bits)
+ {
+ /* q of the form 2^k + q', with q' a limb smaller */
+ mpz_mul_2exp (t, t, shift);
+ output_bignum ("ecc_mBmodq_shifted", t, limb_size, bits_per_limb);
+ }
+ }
if (ecc->bit_size < limb_size * bits_per_limb)
{
mpz_add_ui (t, ecc->q, 1);
mpz_fdiv_q_2exp (t, t, 1);
output_bignum ("ecc_qp1h", t, limb_size, bits_per_limb);
-
+
+ if (ecc->use_edwards)
+ output_bignum ("ecc_edwards", ecc->t, limb_size, bits_per_limb);
+
/* Trailing zeros in p+1 correspond to trailing ones in p. */
redc_limbs = mpz_scan0 (ecc->p, 0) / bits_per_limb;
if (redc_limbs > 0)
}
printf ("#define ECC_REDC_SIZE %d\n", redc_limbs);
+ /* For mod p square root computation. */
+ if (mpz_fdiv_ui (ecc->p, 4) == 3)
+ {
+ /* x = a^{(p+1)/4} gives square root of a (if it exists,
+ otherwise the square root of -a). */
+ e = 1;
+ mpz_add_ui (t, ecc->p, 1);
+ mpz_fdiv_q_2exp (t, t, 2);
+ }
+ else
+ {
+ /* p-1 = 2^e s, s odd, t = (s-1)/2*/
+ unsigned g, i;
+ mpz_t s;
+ mpz_t z;
+
+ mpz_init (s);
+ mpz_init (z);
+
+ mpz_sub_ui (s, ecc->p, 1);
+ e = mpz_scan1 (s, 0);
+ assert (e > 1);
+
+ mpz_fdiv_q_2exp (s, s, e);
+
+ /* Find a non-square g, g^{(p-1)/2} = -1,
+ and z = g^{(p-1)/4 */
+ for (g = 2; ; g++)
+ {
+ mpz_set_ui (z, g);
+ mpz_powm (z, z, s, ecc->p);
+ mpz_mul (t, z, z);
+ mpz_mod (t, t, ecc->p);
+
+ for (i = 2; i < e; i++)
+ {
+ mpz_mul (t, t, t);
+ mpz_mod (t, t, ecc->p);
+ }
+ if (mpz_cmp_ui (t, 1) != 0)
+ break;
+ }
+ mpz_add_ui (t, t, 1);
+ assert (mpz_cmp (t, ecc->p) == 0);
+ output_bignum ("ecc_sqrt_z", z, limb_size, bits_per_limb);
+
+ mpz_fdiv_q_2exp (t, s, 1);
+
+ mpz_clear (s);
+ mpz_clear (z);
+ }
+ printf ("#define ECC_SQRT_E %u\n", e);
+ printf ("#define ECC_SQRT_T_BITS %u\n",
+ (unsigned) mpz_sizeinbase (t, 2));
+ output_bignum ("ecc_sqrt_t", t, limb_size, bits_per_limb);
+
printf ("#if USE_REDC\n");
printf ("#define ecc_unit ecc_Bmodp\n");
printf ("static const mp_limb_t ecc_table[%lu] = {",
(unsigned long) (2*ecc->table_size * limb_size));
for (i = 0; i < ecc->table_size; i++)
- output_point_redc (NULL, ecc, &ecc->table[i], limb_size, bits_per_limb);
+ output_point (NULL, ecc, &ecc->table[i], 1, limb_size, bits_per_limb);
printf("\n};\n");
printf ("static const mp_limb_t ecc_table[%lu] = {",
(unsigned long) (2*ecc->table_size * limb_size));
for (i = 0; i < ecc->table_size; i++)
- output_point (NULL, &ecc->table[i], limb_size, bits_per_limb);
+ output_point (NULL, ecc, &ecc->table[i], 0, limb_size, bits_per_limb);
printf("\n};\n");
printf ("#endif\n");
bench_mul_g (void *p)
{
struct ecc_ctx *ctx = (struct ecc_ctx *) p;
- ecc_mul_g (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
+ ctx->ecc->mul_g (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
}
static void
bench_mul_a (void *p)
{
struct ecc_ctx *ctx = (struct ecc_ctx *) p;
- ecc_mul_a (ctx->ecc, 1, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
+ ctx->ecc->mul (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
+}
+
+static void
+bench_dup_eh (void *p)
+{
+ struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+ ecc_dup_eh (ctx->ecc, ctx->rp, ctx->ap, ctx->tp);
+}
+
+static void
+bench_add_eh (void *p)
+{
+ struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+ ecc_add_eh (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
+}
+
+static void
+bench_add_ehh (void *p)
+{
+ struct ecc_ctx *ctx = (struct ecc_ctx *) p;
+ ecc_add_ehh (ctx->ecc, ctx->rp, ctx->ap, ctx->bp, ctx->tp);
}
#if NETTLE_USE_MINI_GMP
#else
modinv_powm = 0;
#endif
- dup_jj = time_function (bench_dup_jj, &ctx);
- add_jja = time_function (bench_add_jja, &ctx);
- add_jjj = time_function (bench_add_jjj, &ctx);
+ if (ecc->bit_size == 255)
+ {
+ /* For now, curve25519 is a special case */
+ dup_jj = time_function (bench_dup_eh, &ctx);
+ add_jja = time_function (bench_add_eh, &ctx);
+ add_jjj = time_function (bench_add_ehh, &ctx);
+ }
+ else
+ {
+ dup_jj = time_function (bench_dup_jj, &ctx);
+ add_jja = time_function (bench_add_jja, &ctx);
+ add_jjj = time_function (bench_add_jjj, &ctx);
+ }
mul_g = time_function (bench_mul_g, &ctx);
mul_a = time_function (bench_mul_a, &ctx);
const struct ecc_curve * const curves[] = {
&nettle_secp_192r1,
&nettle_secp_224r1,
+ &nettle_curve25519,
&nettle_secp_256r1,
&nettle_secp_384r1,
&nettle_secp_521r1,
}
}
+void
+mpn_set_base256_le (mp_limb_t *rp, mp_size_t rn,
+ const uint8_t *xp, size_t xn)
+{
+ size_t xi;
+ mp_limb_t out;
+ unsigned bits;
+ for (xi = 0, out = bits = 0; xi < xn && rn > 0; )
+ {
+ mp_limb_t in = xp[xi++];
+ out |= (in << bits) & GMP_NUMB_MASK;
+ bits += 8;
+ if (bits >= GMP_NUMB_BITS)
+ {
+ *rp++ = out;
+ rn--;
+
+ bits -= GMP_NUMB_BITS;
+ out = in >> (8 - bits);
+ }
+ }
+ if (rn > 0)
+ {
+ *rp++ = out;
+ if (--rn > 0)
+ mpn_zero (rp, rn);
+ }
+}
+
+void
+mpn_get_base256_le (uint8_t *rp, size_t rn,
+ const mp_limb_t *xp, mp_size_t xn)
+{
+ unsigned bits;
+ mp_limb_t in;
+ for (bits = in = 0; xn > 0 && rn > 0; )
+ {
+ if (bits >= 8)
+ {
+ *rp++ = in;
+ rn--;
+ in >>= 8;
+ bits -= 8;
+ }
+ else
+ {
+ uint8_t old = in;
+ in = *xp++;
+ xn--;
+ *rp++ = old | (in << bits);
+ in >>= (8 - bits);
+ bits += GMP_NUMB_BITS - 8;
+ }
+ }
+ while (rn > 0)
+ {
+ *rp++ = in;
+ rn--;
+ in >>= 8;
+ }
+}
+
mp_limb_t *
gmp_alloc_limbs (mp_size_t n)
{
#define mpz_limbs_copy _nettle_mpz_limbs_copy
#define mpz_set_n _nettle_mpz_set_n
#define mpn_set_base256 _nettle_mpn_set_base256
+#define mpn_set_base256_le _nettle_mpn_set_base256_le
+#define mpn_get_base256_le _nettle_mpn_get_base256_le
#define gmp_alloc_limbs _nettle_gmp_alloc_limbs
#define gmp_free_limbs _nettle_gmp_free_limbs
#define gmp_free _nettle_gmp_free
/* Copy limbs, with zero-padding. */
/* FIXME: Reorder arguments, on the theory that the first argument of
- an _mpz_* fucntion should be an mpz_t? Or rename to _mpz_get_limbs,
+ an _mpz_* function should be an mpz_t? Or rename to _mpz_get_limbs,
with argument order consistent with mpz_get_*. */
void
mpz_limbs_copy (mp_limb_t *xp, mpz_srcptr x, mp_size_t n);
mpn_set_base256 (mp_limb_t *rp, mp_size_t rn,
const uint8_t *xp, size_t xn);
+void
+mpn_set_base256_le (mp_limb_t *rp, mp_size_t rn,
+ const uint8_t *xp, size_t xn);
+
+void
+mpn_get_base256_le (uint8_t *rp, size_t rn,
+ const mp_limb_t *xp, mp_size_t xn);
+
mp_limb_t *
gmp_alloc_limbs (mp_size_t n);
gmp_assert_nocarry (mpn_sub_1 (dp + limb_index, dp + limb_index,
dn - limb_index, bit));
- dn -= (dp[dn-1] == 0);
+ dn = mpn_normalized_size (dp, dn);
d->_mp_size = (d->_mp_size < 0) ? - dn : dn;
}
/*.pdf
+/*.dvi
+/*.log
+/*.aux
+/auto
--- /dev/null
+\documentclass[a4paper]{article}
+\usepackage[utf8]{inputenc}
+\usepackage{amsmath}
+\usepackage{url}
+
+\author{Niels Möller}
+\title{Notes on ECC formulas}
+
+\begin{document}
+
+\maketitle
+
+\section{Weierstrass curve}
+
+Consider only the special case
+\begin{equation*}
+ y^2 = x^3 - 3x + b \pmod{p}
+\end{equation*}
+See \url{http://www.hyperelliptic.org/EFD/g1p/auto-shortw.html}.
+
+Affine formulas for duplication, $(x_2, y_2) = 2(x_1, y_1)$:
+\begin{align*}
+ t &= (2y)^{-1} 3 (x_1^2 - 1) \\
+ x_2 &= t^2 - 2 x_1 \\
+ y_2 &= (x_1 - x_2) * t - y_1
+\end{align*}
+Affine formulas for addition, $(x_3, y_3) = (x_1, y_1) + (x_2,
+y_2)$:
+\begin{align*}
+ t &= (x_2 - x_1)^{-1} (y_2 - y_1) \\
+ x_3 &= t^2 - x_1 - x_2 \\
+ y_3 &= (x_1 - x_3) t - y_1
+\end{align*}
+
+\section{Montgomery curve}
+
+Consider the special case
+\begin{equation*}
+ y^2 = x^3 + b x^2 + x
+\end{equation*}
+See \url{http://www.hyperelliptic.org/EFD/g1p/auto-montgom.html}.
+
+Affine formulas for duplication, $(x_2, y_2) = 2(x_1, y_1)$:
+\begin{align*}
+ t &= (2 y_1)^{-1} (3 x_1^2 + 2b x_1 + 1) \\
+ x_2 &= t^2 - b - 2 x_1 \\
+ y_2 &= (3 x_1 + b) t - t^3 - y_1 \\
+ &= (3 x_1 + b - t^2) t - y_1 \\
+ &= (x_1 - x_2) t - y_1
+\end{align*}
+So the computation is very similar to the Weierstraß case, differing
+only in the formula for $t$, and the $b$ term in $x_2$.
+
+Affine formulas for addition, $(x_3, y_3) = (x_1, y_1) + (x_2,
+y_2)$:
+\begin{align*}
+ t &= (x_2 - x_1)^{-1} (y_2 - y_1) \\
+ x_3 &= t^2 - b - x_1 - x_2 \\
+ y_3 &= (2 x_1 + x_2 + b) t - t^3 - y_1 \\
+ &= (2 x_1 + x_2 + b - t^2) t - y_1 \\
+ &= (x_1 - x_3) t - y_1
+\end{align*}
+Again, very similar to the Weierstraß formulas, with only an
+additional $b$ term in the formula for $x_3$.
+
+\section{Edwards curve}
+
+For an Edwards curve, we consider the special case
+\begin{equation*}
+ x^2 + y^2 = 1 + d x^2 y^2
+\end{equation*}
+See \url{http://cr.yp.to/papers.html#newelliptic}.
+
+Affine formulas for addition, $(x_3, y_3) = (x_1, y_1) + (x_2,
+y_2)$:
+\begin{align*}
+ t &= d x_1 x_2 y_1 y_2 \\
+ x_3 &= (1 + t)^{-1} (x_1 y_2 + y_1 x_2) \\
+ y_3 &= (1 - t)^{-1} (y_1 y_2 - x_1 x_2)
+\end{align*}
+With homogeneous coordinates $(X_1, Y_1, Z_1)$ etc., D.~J.~Bernstein
+suggests the formulas
+\begin{align*}
+ A &= Z_1 Z_2 \\
+ B &= A^2 \\
+ C &= X_1 X_2 \\
+ D &= Y_1 Y_2 \\
+ E &= d C D \\
+ F &= B - E \\
+ G &= B + E \\
+ X_3 &= A F [(X_1 + Y_1)(X_2 + Y_2) - C - D] \\
+ Y_3 &= A G (D - C) \\
+ Z_3 &= F G
+\end{align*}
+This works also for doubling, but a more efficient variant is
+\begin{align*}
+ B &= (X_1 + Y_1)^2 \\
+ C &= X_1^2 \\
+ D &= Y_1^2 \\
+ E &= C + D \\
+ H &= Z_1^2 \\
+ J &= E - 2H \\
+ X_3 &= (B - E) J \\
+ Y_3 &= E (C - D) \\
+ Z_3 &= E J
+\end{align*}
+
+\section{EdDSA}
+
+The EdDSA paper (\url{http://ed25519.cr.yp.to/ed25519-20110926.pdf})
+suggests using the twisted Edwards curve,
+\begin{equation*}
+ -x^2 + y^2 = 1 + d x^2 y^2 \pmod{p}
+\end{equation*}
+Assuming -1 has a square root modulo $p$, a point $(x, y)$ lies on
+this curve if and only if $(\sqrt{-1} x, p)$ lies of the non-twisted
+Edwards curve. The point additin formulas for the twisted Edwards
+curve are
+\begin{align*}
+ t &= d x_1 x_2 y_1 y_2 \\
+ x_3 &= (1 + t)^{-1} (x_1 y_2 + y_1 x_2) \\
+ y_3 &= (1 - t)^{-1} (y_1 y_2 + x_1 x_2)
+\end{align*}
+For the other formulas, it should be fine to just switch the sign of
+terms involving $x_1 x_2$ or $x_1^2$. The paper suggests further
+optimizations: For precomputed points, use the representation $(x-y,
+x+y, dxy)$. And for temporary points, maintain an additional redundant
+coordinate $T$, with $Z T = X Y$ (see
+\url{http://eprint.iacr.org/2008/522.pdf}).
+
+\section{Curve25519}
+
+Curve25519 is defined as the Montgomery curve
+\begin{equation*}
+ y^2 = x^3 + b x^2 + x \pmod p
+\end{equation*}
+with $b = 486662$ and $p = 2^{255} -19$. It is equivalent to the
+Edwards curve
+\begin{equation*}
+ u^2 + v^2 = 1 + d u^2 v^2 \pmod p
+\end{equation*}
+with $d = (121665/121666) \bmod p$. The equivalence is given by
+mapping $P = (x,y)$ to $P' = (u, v)$, as follows.
+\begin{itemize}
+\item $P = \infty$ corresponds to $P' = (0, 1)$
+\item $P = (0, 0)$ corresponds to $P' = (0, -1)$
+\item Otherwise, for all other points on the curve. First note that $x
+ \neq -1$ (since then the right hand side is a not a quadratic
+ residue), and that $y \neq 0$ (since $y = 0$ and $x \neq 0$ implies
+ that $x^2 + bx + 1 = 0$, or $(x + b/2)^2 = (b/2)^2 - 1$, which also
+ isn't a quadratic residue). The correspondence is then given by
+ \begin{align*}
+ u &= \sqrt{b+2} \, x / y \\
+ v &= (x-1) / (x+1)
+ \end{align*}
+\end{itemize}
+
+The inverse transformation is
+\begin{align*}
+ x &= (1+v) / (1-v) \\
+ y &= \sqrt{b+2} \, x / u
+\end{align*}
+If the Edwards coordinates are represented using homogeneous
+coordinates, $u = U/W$ and $v = V/W$, then
+\begin{align*}
+ x &= \frac{W+V}{W-V} \\
+ y &= \sqrt{b} \frac{(W+V) W}{(W-V) U}
+\end{align*}
+so we need to invert the value $(W-V) U$.
+
+\subsection{Transforms for the twisted Edwards Curve}
+
+If we use the twisted Edwards curve instead, let $\alpha = \sqrt{-1}
+\pmod{p}$. Then we work with coordinates $(u', v)$, where $u' = \alpha
+u$. The transform from Montgomery form $(x, y)$ is then
+\begin{align*}
+ u &= (\alpha \sqrt{b+2}) \, x / y\\
+ v &= (x-1) / (x+1)
+\end{align*}
+And the inverse transform is similarly
+\begin{align*}
+ x &= (1+v) / (1-v) \\
+ y &= (\alpha \sqrt{b+2}) \, x / u
+\end{align*}
+so it's just a change of the transform constant, effectively using
+$\sqrt{-(b+2)}$ instead.
+
+\subsection{Coordinates outside of the base field}
+
+The curve25519 function is defined with an input point represented by
+the $x$-coordinate only, and is specified as allowing any value. The
+corresponding $y$ coordinate is given by
+\begin{equation*}
+ y = \sqrt{x^3 + b x^2 + x} \pmod p
+\end{equation*}
+whenever this square root exists. But what if it doesn't? Then we work
+with the curve over the extended field $F_{p^2}$. Let $n$ by any
+non-square, then $(x^3 + b x^2 + x) n$ is a square, and we get the
+$y = y' / \sqrt{n}$ with
+\begin{equation*}
+ y' = \sqrt{(x^3 + b x^2 + x) n}
+\end{equation*}
+It happens that for all multiples of such a point, this same factor is
+tacked on to all the $y$-coordinates, while all the $x$-coordinates
+remain in the base field $F_p$. It's the ``twist'' curve $y'^2 / n =
+x^3 + bx^2 + x$. On the corresponding Edwards curve, we
+get $u = \sqrt{n} u'$ with
+\begin{equation*}
+ u' = \sqrt{b+2} \, x / y'
+\end{equation*}
+and the addition formula
+\begin{align*}
+ t &= d n u'_1 u'_2 v_1 v_2 \\
+ u'_3 &= (1+t)^{-1}(u'_1v_2 + v_1 u'_2) \\
+ v_3 &= (1-t)^{-1}(v_1 v_2 - n u'_1 u'_2)
+\end{align*}
+It seems a bit tricky to handle both types of point in a single
+function without speed penalty, due to the conditional factor of $n$
+in the formula for $v_3$.
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% End:
--- /dev/null
+/* Script for pari/gp. Run as gp -q ecc-ref.gp */
+
+out(apriv, A, bpriv, B, S) = print( \
+ "/* a_s */ \"", apriv, "\",\n", \
+ "/* a_x */ \"", component(A[1], 2), "\",\n", \
+ "/* a_y */ \"", component(A[2], 2), "\",\n", \
+ "/* b_s */ \"", bpriv, "\",\n", \
+ "/* b_x */ \"", component(B[1], 2), "\",\n", \
+ "/* b_y */ \"", component(B[2], 2), "\",\n", \
+ "/* s_x */ \"", component(S[1], 2), "\",\n", \
+ "/* s_y */ \"", component(S[2], 2), "\",");
+
+p192 = 2^192 - 2^64 - 1;
+b192 = 2455155546008943817740293915197451784769108058161191238065;
+g = Mod([602046282375688656758213480587526111916698976636884684818, \
+ 174050332293622031404857552280219410364023488927386650641], p192);
+secp192 = ellinit(Mod([0,0,0,-3, b192], p192));
+q = 6277101735386680763835789423176059013767194773182842284081;
+if (ellpow(secp192, g, q) != [0], error("secp192 parameter error"));
+
+a = 1+random(q-1);
+b = 1+random(q-1);
+A = ellpow(secp192, g, a);
+B = ellpow(secp192, g, b);
+S = ellpow(secp192, A, b);
+if (S != ellpow(secp192, B, a), error("secp192 dh error"));
+print("secp192");
+out(a, A, b, B, S);
+
+p224 = 2^224 - 2^96 + 1;
+b224 = 18958286285566608000408668544493926415504680968679321075787234672564;
+g = Mod([19277929113566293071110308034699488026831934219452440156649784352033,\
+ 19926808758034470970197974370888749184205991990603949537637343198772], p224);
+
+secp224 = ellinit(Mod([0,0,0,-3, b224], p224));
+q = 26959946667150639794667015087019625940457807714424391721682722368061;
+if (ellpow(secp224, g, q) != [0], error("secp224 parameter error"));
+
+a = 1+random(q-1);
+b = 1+random(q-1);
+A = ellpow(secp224, g, a);
+B = ellpow(secp224, g, b);
+S = ellpow(secp224, A, b);
+if (S != ellpow(secp224, B, a), error("secp224 dh error"));
+print("secp224");
+out(a, A, b, B, S);
+
+p256 = 2^256 - 2^224 + 2^192 + 2^96 - 1;
+b256 = 41058363725152142129326129780047268409114441015993725554835256314039467401291;
+g = Mod([48439561293906451759052585252797914202762949526041747995844080717082404635286,\
+ 36134250956749795798585127919587881956611106672985015071877198253568414405109], p256);
+
+secp256 = ellinit(Mod([0,0,0,-3, b256], p256));
+q = 115792089210356248762697446949407573529996955224135760342422259061068512044369;
+if (ellpow(secp256, g, q) != [0], error("secp256 parameter error"));
+
+a = 1+random(q-1);
+b = 1+random(q-1);
+A = ellpow(secp256, g, a);
+B = ellpow(secp256, g, b);
+S = ellpow(secp256, A, b);
+if (S != ellpow(secp256, B, a), error("secp256 dh error"));
+print("secp256");
+out(a, A, b, B, S);
+
+p384 = 2^384 - 2^128 - 2^96 + 2^32 - 1;
+b384 = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575;
+g = Mod([26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087,\
+ 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871], p384);
+
+secp384 = ellinit(Mod([0,0,0,-3, b384], p384));
+q = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643;
+if (ellpow(secp384, g, q) != [0], error("secp384 parameter error"));
+
+a = 1+random(q-1);
+b = 1+random(q-1);
+A = ellpow(secp384, g, a);
+B = ellpow(secp384, g, b);
+S = ellpow(secp384, A, b);
+if (S != ellpow(secp384, B, a), error("secp384 dh error"));
+print("secp384");
+out(a, A, b, B, S);
+
+p521 = 2^521 - 1;
+b521 = 1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984;
+g = Mod([2661740802050217063228768716723360960729859168756973147706671368418802944996427808491545080627771902352094241225065558662157113545570916814161637315895999846,\
+ 3757180025770020463545507224491183603594455134769762486694567779615544477440556316691234405012945539562144444537289428522585666729196580810124344277578376784], p521);
+
+secp521 = ellinit(Mod([0,0,0,-3, b521], p521));
+q = 6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449;
+if (ellpow(secp521, g, q) != [0], error("secp521 parameter error"));
+
+a = 1+random(q-1);
+b = 1+random(q-1);
+A = ellpow(secp521, g, a);
+B = ellpow(secp521, g, b);
+S = ellpow(secp521, A, b);
+if (S != ellpow(secp521, B, a), error("secp521 dh error"));
+print("secp521");
+out(a, A, b, B, S);
+
+p25519 = 2^255 - 19;
+b25519 = 486662;
+x = Mod(9, p25519);
+y = sqrt(x^3 + b25519*x^2 + x);
+g = [x, y];
+
+curve25519 = ellinit(Mod([0, b25519, 0, 1, 0], p25519));
+q = 2^252 + 27742317777372353535851937790883648493;
+if (ellpow(curve25519, g, q) != [0], error("curve25519 parameter error"));
+
+a = 1+random(q-1);
+b = 1+random(q-1);
+A = ellpow(curve25519, g, a);
+B = ellpow(curve25519, g, b);
+S = ellpow(curve25519, A, b);
+if (S != ellpow(curve25519, B, a), error("curve25519 dh error"));
+print("curve25519");
+out(a, A, b, B, S);
+
+quit
}
/* Compute a^{-1} mod m, with running time depending only on the size.
+ Returns zero if a == 0 (mod m), to be consistent with a^{phi(m)-1}.
Also needs (m+1)/2, and m must be odd. */
void
sec_modinv (mp_limb_t *vp, mp_limb_t *ap, mp_size_t n,
dsa-keygen-test$(EXEEXT): dsa-keygen-test.$(OBJEXT)
$(LINK) dsa-keygen-test.$(OBJEXT) $(TEST_OBJS) -o dsa-keygen-test$(EXEEXT)
+curve25519-dup-test$(EXEEXT): curve25519-dup-test.$(OBJEXT)
+ $(LINK) curve25519-dup-test.$(OBJEXT) $(TEST_OBJS) -o curve25519-dup-test$(EXEEXT)
+
+curve25519-add-test$(EXEEXT): curve25519-add-test.$(OBJEXT)
+ $(LINK) curve25519-add-test.$(OBJEXT) $(TEST_OBJS) -o curve25519-add-test$(EXEEXT)
+
+curve25519-dh-test$(EXEEXT): curve25519-dh-test.$(OBJEXT)
+ $(LINK) curve25519-dh-test.$(OBJEXT) $(TEST_OBJS) -o curve25519-dh-test$(EXEEXT)
+
ecc-mod-test$(EXEEXT): ecc-mod-test.$(OBJEXT)
$(LINK) ecc-mod-test.$(OBJEXT) $(TEST_OBJS) -o ecc-mod-test$(EXEEXT)
ecdsa-keygen-test$(EXEEXT): ecdsa-keygen-test.$(OBJEXT)
$(LINK) ecdsa-keygen-test.$(OBJEXT) $(TEST_OBJS) -o ecdsa-keygen-test$(EXEEXT)
+ecdh-test$(EXEEXT): ecdh-test.$(OBJEXT)
+ $(LINK) ecdh-test.$(OBJEXT) $(TEST_OBJS) -o ecdh-test$(EXEEXT)
+
sha1-huge-test$(EXEEXT): sha1-huge-test.$(OBJEXT)
$(LINK) sha1-huge-test.$(OBJEXT) $(TEST_OBJS) -o sha1-huge-test$(EXEEXT)
pkcs1-test.c \
rsa-test.c rsa-encrypt-test.c rsa-keygen-test.c \
dsa-test.c dsa-keygen-test.c \
+ curve25519-dup-test.c curve25519-add-test.c \
+ curve25519-dh-test.c \
ecc-mod-test.c ecc-modinv-test.c ecc-redc-test.c \
ecc-mul-g-test.c ecc-mul-a-test.c \
- ecdsa-sign-test.c ecdsa-verify-test.c ecdsa-keygen-test.c
+ ecdsa-sign-test.c ecdsa-verify-test.c \
+ ecdsa-keygen-test.c ecdh-test.c
TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES)
CXX_SOURCES = cxx-test.cxx
--- /dev/null
+#include "testutils.h"
+
+static int
+point_zero_p (const struct ecc_curve *ecc, const mp_limb_t *p)
+{
+ mp_limb_t *d;
+ int ret;
+ mp_size_t i;
+ d = xalloc_limbs (ecc->size);
+ ecc_modp_sub (ecc, d, p + ecc->size, p + 2*ecc->size);
+ while (mpn_cmp (d, ecc->p, ecc->size) >= 0)
+ mpn_sub_n (d, d, ecc->p, ecc->size);
+
+ for (i = 0, ret = 1; i < ecc->size; i++)
+ if (d[i])
+ {
+ ret = 0;
+ break;
+ }
+
+ free (d);
+ return ret;
+}
+
+void
+test_main (void)
+{
+ const struct ecc_curve *ecc = &nettle_curve25519;
+ mp_limb_t *g;
+ mp_limb_t *z;
+ mp_limb_t *g2;
+ mp_limb_t *g3;
+ mp_limb_t *g4;
+ mp_limb_t *pe;
+ mp_limb_t *pa;
+ mp_limb_t *scratch;
+ const struct ecc_ref_point rg =
+ {
+ "9",
+ "20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9"
+ };
+ const struct ecc_ref_point rg2 =
+ { /* In Edwards coordinates:
+ x = 0x1a1c31f8665368131698fecfd54233fcdc638bb46d25cc61d8bc4bcdbfbb4459,
+ y = 0x2260cdf3092329c21da25ee8c9a21f5697390f51643851560e5f46ae6af8a3c9
+ */
+ "20d342d51873f1b7d9750c687d157114"
+ "8f3f5ced1e350b5c5cae469cdd684efb",
+ "13b57e011700e8ae050a00945d2ba2f3"
+ "77659eb28d8d391ebcd70465c72df563"
+ };
+ const struct ecc_ref_point rg3 =
+ {
+ "1c12bc1a6d57abe645534d91c21bba64"
+ "f8824e67621c0859c00a03affb713c12",
+ "2986855cbe387eaeaceea446532c338c"
+ "536af570f71ef7cf75c665019c41222b"
+ };
+ const struct ecc_ref_point rg4 =
+ {
+ "79ce98b7e0689d7de7d1d074a15b315f"
+ "fe1805dfcd5d2a230fee85e4550013ef",
+ "075af5bf4ebdc75c8fe26873427d275d"
+ "73c0fb13da361077a565539f46de1c30"
+ };
+
+ g = xalloc_limbs (ecc_size_j (ecc));
+ z = xalloc_limbs (ecc_size_j (ecc));
+ g2 = xalloc_limbs (ecc_size_j (ecc));
+ g3 = xalloc_limbs (ecc_size_j (ecc));
+ g4 = xalloc_limbs (ecc_size_j (ecc));
+ pe = xalloc_limbs (ecc_size_j (ecc));
+ pa = xalloc_limbs (ecc_size_j (ecc));
+ scratch = xalloc_limbs (ECC_ADD_EHH_ITCH(ecc->size));
+
+ mpn_copyi (g, ecc->g, 2*ecc->size);
+ g[2*ecc->size] = 1;
+ mpn_zero (g+2*ecc->size + 1, ecc->size - 1);
+
+ /* Zero point has x = 0, y = 1, z = 1 */
+ mpn_zero (z, 3*ecc->size);
+ z[ecc->size] = z[2*ecc->size] = 1;
+
+ ecc_add_ehh (ecc, pe, z, z, scratch);
+ if (!point_zero_p (ecc, pe))
+ die ("dup of zero point failed.\n");
+
+ ecc_add_eh (ecc, pe, z, z, scratch);
+ if (!point_zero_p (ecc, pe))
+ die ("dup of zero point failed.\n");
+
+ ecc_add_ehh (ecc, pe, g, pe, scratch);
+ ecc_eh_to_a (ecc, 0, pa, pe, scratch);
+ test_ecc_point (ecc, &rg, pa);
+
+ ecc_add_eh (ecc, pe, z, g, scratch);
+ ecc_eh_to_a (ecc, 0, pa, pe, scratch);
+ test_ecc_point (ecc, &rg, pa);
+
+ ecc_add_ehh (ecc, g2, g, pe, scratch);
+ ecc_eh_to_a (ecc, 0, pa, g2, scratch);
+ test_ecc_point (ecc, &rg2, pa);
+
+ ecc_add_eh (ecc, g2, g, g, scratch);
+ ecc_eh_to_a (ecc, 0, pa, g2, scratch);
+ test_ecc_point (ecc, &rg2, pa);
+
+ ecc_add_ehh (ecc, g3, g, g2, scratch);
+ ecc_eh_to_a (ecc, 0, pa, g3, scratch);
+ test_ecc_point (ecc, &rg3, pa);
+
+ ecc_add_eh (ecc, g3, g2, g, scratch);
+ ecc_eh_to_a (ecc, 0, pa, g3, scratch);
+ test_ecc_point (ecc, &rg3, pa);
+
+ ecc_add_ehh (ecc, g4, g, g3, scratch);
+ ecc_eh_to_a (ecc, 0, pa, g4, scratch);
+ test_ecc_point (ecc, &rg4, pa);
+
+ ecc_add_eh (ecc, g4, g3, g, scratch);
+ ecc_eh_to_a (ecc, 0, pa, g4, scratch);
+ test_ecc_point (ecc, &rg4, pa);
+
+ ecc_add_ehh (ecc, g4, g2, g2, scratch);
+ ecc_eh_to_a (ecc, 0, pa, g4, scratch);
+ test_ecc_point (ecc, &rg4, pa);
+
+ free (g);
+ free (z);
+ free (g2);
+ free (g3);
+ free (g4);
+ free (pe);
+ free (pa);
+ free (scratch);
+}
--- /dev/null
+/* curve25519-dh-test.c
+
+ 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/.
+*/
+
+#include "testutils.h"
+
+#include "curve25519.h"
+
+static void
+test_g (const uint8_t *s, const uint8_t *r)
+{
+ uint8_t p[CURVE25519_SIZE];
+ curve25519_mul_g (p, s);
+ if (!MEMEQ (CURVE25519_SIZE, p, r))
+ {
+ printf ("curve25519_mul_g failure:\ns = ");
+ print_hex (CURVE25519_SIZE, s);
+ printf ("\np = ");
+ print_hex (CURVE25519_SIZE, p);
+ printf (" (bad)\nr = ");
+ print_hex (CURVE25519_SIZE, r);
+ printf (" (expected)\n");
+ abort ();
+ }
+}
+
+static void
+test_a (const uint8_t *s, const uint8_t *b, const uint8_t *r)
+{
+ uint8_t p[CURVE25519_SIZE];
+ if (!curve25519_mul (p, s, b))
+ {
+ printf ("curve25519_mul returned 0:\ns = ");
+ print_hex (CURVE25519_SIZE, s);
+ printf ("\nb = ");
+ print_hex (CURVE25519_SIZE, b);
+ printf ("\n");
+ abort ();
+ }
+
+ if (!MEMEQ (CURVE25519_SIZE, p, r))
+ {
+ printf ("curve25519_mul failure:\ns = ");
+ print_hex (CURVE25519_SIZE, s);
+ printf ("\nb = ");
+ print_hex (CURVE25519_SIZE, b);
+ printf ("\np = ");
+ print_hex (CURVE25519_SIZE, p);
+ printf (" (bad)\nr = ");
+ print_hex (CURVE25519_SIZE, r);
+ printf (" (expected)\n");
+ abort ();
+ }
+}
+
+void
+test_main (void)
+{
+ /* From draft-turner-thecurve25519function-00 (same also in
+ draft-josefsson-tls-curve25519-05, but the latter uses different
+ endianness). */
+ test_g (H("77076d0a7318a57d3c16c17251b26645"
+ "df4c2f87ebc0992ab177fba51db92c2a"),
+ H("8520f0098930a754748b7ddcb43ef75a"
+ "0dbf3a0d26381af4eba4a98eaa9b4e6a"));
+ test_g (H("5dab087e624a8a4b79e17f8b83800ee6"
+ "6f3bb1292618b6fd1c2f8b27ff88e0eb"),
+ H("de9edb7d7b7dc1b4d35b61c2ece43537"
+ "3f8343c85b78674dadfc7e146f882b4f"));
+
+ test_a (H("77076d0a7318a57d3c16c17251b26645"
+ "df4c2f87ebc0992ab177fba51db92c2a"),
+ H("de9edb7d7b7dc1b4d35b61c2ece43537"
+ "3f8343c85b78674dadfc7e146f882b4f"),
+ H("4a5d9d5ba4ce2de1728e3bf480350f25"
+ "e07e21c947d19e3376f09b3c1e161742"));
+
+ test_a (H("5dab087e624a8a4b79e17f8b83800ee6"
+ "6f3bb1292618b6fd1c2f8b27ff88e0eb"),
+ H("8520f0098930a754748b7ddcb43ef75a"
+ "0dbf3a0d26381af4eba4a98eaa9b4e6a"),
+ H("4a5d9d5ba4ce2de1728e3bf480350f25"
+ "e07e21c947d19e3376f09b3c1e161742"));
+}
--- /dev/null
+#include "testutils.h"
+
+static int
+point_zero_p (const struct ecc_curve *ecc, const mp_limb_t *p)
+{
+ mp_limb_t *d;
+ int ret;
+ mp_size_t i;
+ d = xalloc_limbs (ecc->size);
+ ecc_modp_sub (ecc, d, p + ecc->size, p + 2*ecc->size);
+ while (mpn_cmp (d, ecc->p, ecc->size) >= 0)
+ mpn_sub_n (d, d, ecc->p, ecc->size);
+
+ for (i = 0, ret = 1; i < ecc->size; i++)
+ if (d[i])
+ {
+ ret = 0;
+ break;
+ }
+
+ free (d);
+ return ret;
+}
+
+void
+test_main (void)
+{
+ const struct ecc_curve *ecc = &nettle_curve25519;
+ mp_limb_t *g;
+ mp_limb_t *z;
+ mp_limb_t *pe;
+ mp_limb_t *pa;
+ mp_limb_t *scratch;
+ const struct ecc_ref_point g2 =
+ { /* In Edwards coordinates:
+ x = 0x1a1c31f8665368131698fecfd54233fcdc638bb46d25cc61d8bc4bcdbfbb4459,
+ y = 0x2260cdf3092329c21da25ee8c9a21f5697390f51643851560e5f46ae6af8a3c9
+ */
+ "20d342d51873f1b7d9750c687d157114"
+ "8f3f5ced1e350b5c5cae469cdd684efb",
+ "13b57e011700e8ae050a00945d2ba2f3"
+ "77659eb28d8d391ebcd70465c72df563"
+ };
+ const struct ecc_ref_point g4 =
+ {
+ "79ce98b7e0689d7de7d1d074a15b315f"
+ "fe1805dfcd5d2a230fee85e4550013ef",
+ "075af5bf4ebdc75c8fe26873427d275d"
+ "73c0fb13da361077a565539f46de1c30"
+ };
+
+ g = xalloc_limbs (ecc_size_j (ecc));
+ z = xalloc_limbs (ecc_size_j (ecc));
+ pe = xalloc_limbs (ecc_size_j (ecc));
+ pa = xalloc_limbs (ecc_size_j (ecc));
+ scratch = xalloc_limbs (ECC_DUP_EH_ITCH(ecc->size));
+
+ mpn_copyi (g, ecc->g, 2*ecc->size);
+ g[2*ecc->size] = 1;
+ mpn_zero (g+2*ecc->size + 1, ecc->size - 1);
+
+ /* Zero point has x = 0, y = 1, z = 1 */
+ mpn_zero (z, 3*ecc->size);
+ z[ecc->size] = z[2*ecc->size] = 1;
+
+ ecc_dup_eh (ecc, pe, z, scratch);
+ if (!point_zero_p (ecc, pe))
+ die ("dup of zero point failed.\n");
+
+ ecc_dup_eh (ecc, pe, g, scratch);
+
+ ecc_eh_to_a (ecc, 0, pa, pe, scratch);
+ test_ecc_point (ecc, &g2, pa);
+
+ ecc_dup_eh (ecc, pe, pe, scratch);
+
+ ecc_eh_to_a (ecc, 0, pa, pe, scratch);
+ test_ecc_point (ecc, &g4, pa);
+
+ free (g);
+ free (z);
+ free (pe);
+ free (pa);
+ free (scratch);
+}
#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);
+ mpz_limbs_copy (a, r, 2*ecc->size);
- ref_mod (ref, a, ecc->p, ecc->size);
+ ref_mod (ref, a, ecc->p, 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);
+
+ 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);
+ mpn_copyi (m, a, 2*ecc->size);
+ ecc->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->modq 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->Bmodq_size < ecc->size)
+ {
mpn_copyi (m, a, 2*ecc->size);
- ecc->modq (ecc, m);
+ 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->modq 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->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 (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 ();
- }
- }
}
}
-
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 */
#define MAX_ECC_SIZE (1 + 521 / GMP_NUMB_BITS)
#define COUNT 500
+static int
+mpn_zero_p (mp_srcptr ap, mp_size_t n)
+{
+ while (--n >= 0)
+ {
+ if (ap[n] != 0)
+ return 0;
+ }
+ return 1;
+}
+
void
test_main (void)
{
{
const struct ecc_curve *ecc = ecc_curves[i];
unsigned j;
+ /* Check behaviour for zero input */
+ mpn_zero (a, ecc->size);
+ memset (ai, 17, ecc->size * sizeof(*ai));
+ ecc_modp_inv (ecc, ai, a, scratch);
+ if (!mpn_zero_p (ai, ecc->size))
+ {
+ fprintf (stderr, "ecc_modp_inv failed for zero input (bit size %u):\n",
+ ecc->bit_size);
+ gmp_fprintf (stderr, "p = %Nx\n"
+ "t = %Nx (bad)\n",
+ ecc->p, ecc->size,
+ ai, ecc->size);
+ abort ();
+ }
+
+ /* Check behaviour for a = p */
+ mpn_copyi (a, ecc->p, ecc->size);
+ memset (ai, 17, ecc->size * sizeof(*ai));
+ ecc_modp_inv (ecc, ai, a, scratch);
+ if (!mpn_zero_p (ai, ecc->size))
+ {
+ fprintf (stderr, "ecc_modp_inv failed for a = p input (bit size %u):\n",
+ ecc->bit_size);
+ gmp_fprintf (stderr, "p = %Nx\n"
+ "t = %Nx (bad)\n",
+ ecc->p, ecc->size,
+ ai, ecc->size);
+ abort ();
+ }
+
for (j = 0; j < COUNT; j++)
{
if (j & 1)
mpn_zero (n, size);
n[0] = 1;
- ecc_mul_a (ecc, 1, p, n, ecc->g, scratch);
+ ecc_mul_a (ecc, p, n, ecc->g, scratch);
ecc_j_to_a (ecc, 1, p, p, scratch);
if (mpn_cmp (p, ecc->g, 2*size != 0))
die ("curve %d: ecc_mul_a with n = 1 failed.\n", ecc->bit_size);
- if (ecc->use_redc)
- {
- ecc_mul_a (ecc, 0, p, n, ecc->redc_g, scratch);
- ecc_j_to_a (ecc, 1, p, p, scratch);
-
- if (mpn_cmp (p, ecc->g, 2*size != 0))
- die ("curve %d: ecc_mul_a with n = 1 and redc failed.\n", ecc->bit_size);
- }
for (n[0] = 2; n[0] <= 4; n[0]++)
{
- ecc_mul_a (ecc, 1, p, n, ecc->g, scratch);
+ ecc_mul_a (ecc, p, n, ecc->g, scratch);
test_ecc_mul_j (i, n[0], p);
- if (ecc->use_redc)
- {
- ecc_mul_a (ecc, 0, p, n, ecc->redc_g, scratch);
- test_ecc_mul_j (i, n[0], p);
- }
}
/* (order - 1) * g = - g */
mpn_sub_1 (n, ecc->q, size, 1);
- ecc_mul_a (ecc, 1, p, n, ecc->g, scratch);
+ ecc_mul_a (ecc, p, n, ecc->g, scratch);
ecc_j_to_a (ecc, 1, p, p, scratch);
mpn_sub_n (p + size, ecc->p, p + size, size);
if (mpn_cmp (p, ecc->g, 2*size) != 0)
mpz_limbs_copy (n, r, size);
n[size - 1] %= ecc->q[size - 1];
- ecc_mul_a (ecc, 1, p, n, ecc->g, scratch);
+ ecc_mul_a (ecc, p, n, ecc->g, scratch);
ecc_j_to_a (ecc, 1, p, p, scratch);
ecc_mul_g (ecc, q, n, scratch);
--- /dev/null
+/* ecdh-test.c
+
+ 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/.
+*/
+
+#include "testutils.h"
+
+static void
+set_point (struct ecc_point *p,
+ const char *x, const char *y)
+{
+ mpz_t X, Y;
+ mpz_init_set_str (X, x, 0);
+ mpz_init_set_str (Y, y, 0);
+ if (!ecc_point_set (p, X, Y))
+ die ("Test point not on curve!\n");
+
+ mpz_clear (X);
+ mpz_clear (Y);
+}
+
+static void
+set_scalar (struct ecc_scalar *s,
+ const char *x)
+{
+ mpz_t X;
+ mpz_init_set_str (X, x, 0);
+ ecc_scalar_set (s, X);
+ mpz_clear (X);
+}
+
+static void
+check_point (const char *name, const char *label,
+ const struct ecc_point *P,
+ const struct ecc_point *R)
+{
+ mpz_t px, py, rx, ry;
+
+ mpz_init (px);
+ mpz_init (py);
+ mpz_init (rx);
+ mpz_init (ry);
+
+ ecc_point_get (P, px, py);
+ ecc_point_get (R, rx, ry);
+
+ /* FIXME: Should have a public point compare function */
+ if (mpz_cmp (px, rx) != 0 || mpz_cmp (py, ry) != 0)
+ {
+ fprintf (stderr, "Failed %s %s\np_x = ", name, label);
+ mpz_out_str (stderr, 10, px);
+ fprintf (stderr, "\nr_x = ");
+ mpz_out_str (stderr, 10, rx);
+ fprintf (stderr, " (expected)\np_y = ");
+ mpz_out_str (stderr, 10, py);
+ fprintf (stderr, "\nr_y = ");
+ mpz_out_str (stderr, 10, ry);
+ fprintf (stderr, " (expected)\n");
+ abort ();
+ }
+ mpz_clear (px);
+ mpz_clear (py);
+ mpz_clear (rx);
+ mpz_clear (ry);
+}
+
+static void
+test_dh (const char *name, const struct ecc_curve *ecc,
+ const char *a_priv, const char *ax, const char *ay,
+ const char *b_priv, const char *bx, const char *by,
+ const char *sx, const char *sy)
+{
+ struct ecc_point A, B, S, T;
+ struct ecc_scalar A_priv, B_priv;
+
+ ecc_scalar_init (&A_priv, ecc);
+ set_scalar (&A_priv, a_priv);
+ ecc_point_init (&A, ecc);
+ set_point (&A, ax, ay);
+
+ ecc_scalar_init (&B_priv, ecc);
+ set_scalar (&B_priv, b_priv);
+ ecc_point_init (&B, ecc);
+ set_point (&B, bx, by);
+
+ ecc_point_init (&S, ecc);
+ set_point (&S, sx, sy);
+
+ ecc_point_init (&T, ecc);
+
+ ecc_point_mul_g (&T, &A_priv);
+ check_point (name, "a g", &T, &A);
+
+ ecc_point_mul (&T, &B_priv, &T);
+ check_point (name, "b (a g)", &T, &S);
+
+ ecc_point_mul_g (&T, &B_priv);
+ check_point (name, "b g", &T, &B);
+
+ ecc_point_mul (&T, &A_priv, &T);
+ check_point (name, "a (b g)", &T, &S);
+
+ ecc_scalar_clear (&A_priv);
+ ecc_scalar_clear (&B_priv);
+
+ ecc_point_clear (&A);
+ ecc_point_clear (&B);
+ ecc_point_clear (&S);
+ ecc_point_clear (&T);
+}
+
+void
+test_main(void)
+{
+ test_dh ("secp-192r1", &nettle_secp_192r1,
+ "3406157206141798348095184987208239421004566462391397236532",
+ "1050363442265225480786760666329560655512990381040021438562",
+ "5298249600854377235107392014200406283816103564916230704184",
+ "738368960171459956677260317271477822683777845013274506165",
+ "2585840779771604687467445319428618542927556223024046979917",
+ "293088185788565313717816218507714888251468410990708684573",
+ "149293809021051532782730990145509724807636529827149481690",
+ "2891131861147398318714693938158856874319184314120776776192");
+
+ test_dh ("secp-224r1", &nettle_secp_224r1,
+ "1321072106881784386340709783538698930880431939595776773514895067682",
+ "6768311794185371282972144247871764855860666277647541840973645586477",
+ "2880077809069104378181313860274147139049600284805670362929579614547",
+ "13934723037778859565852601874354272638301919827851286722006496784914",
+ "373124771833407982305885866158843810218322878380632071540538232035",
+ "24223309755162432227459925493224336241652868856405241018762887667883",
+ "8330362698029245839097779050425944245826040430538860338085968752913",
+ "24167244512472228715617822000878192535267113543393576038737592837010");
+
+ test_dh ("secp-256r1", &nettle_secp_256r1,
+ "94731533361265297353914491124013058635674217345912524033267198103710636378786",
+ "22441589863306126152768848344973918725077248391248404659242620344938484650846",
+ "8673475622926171928656873398933611700804732317466515884933832073457396747355",
+ "97657865959185011849283028361556797595752581630732610898393589042714626616209",
+ "18453500628354973083413728373777272885280811435138222441593126858566687017580",
+ "14365748655141740924607822284126054269177292284541187981786689038777833170313",
+ "102958799567030688009123101477538973715497039396202015119148334812951370853564",
+ "29188877854984806245046208182450375893010623119030341548941791125497546766367");
+
+ test_dh ("secp-384r1", &nettle_secp_384r1,
+ "39086550219018474560700767788227987514008150214902287969462741484831311917159729009715909108606822193356890811565070",
+ "15536343869384820642787280162462493474000839389760580357050317691132784247078954166759523572989472049798969369413707",
+ "23268351460749985365652822073294615614961429585671989812206213135127969284347174876010177880230302801199500921999966",
+ "36869963309577906178833120963925446333578086292605692048464445726274368063284094788012795873582576522541658781990645",
+ "6571571183519639697971973492227725184968062063941037806786906539419849188357322949908539215960508669158121817812397",
+ "36555212611228586427448926841660565534959679681904941933188284044726925984417589749068550977832780023128545833460008",
+ "27780263733159299625371532605243698753833039933618994121416145881861678645978369807598146716869504289033472077532789",
+ "12327518461490664021199432424728005314646140038116972426756705356672414772151215711157356913456651047992140493843405");
+
+ test_dh ("secp-521r1", &nettle_secp_521r1,
+ "1177787298234877762125077260641419691552146813662613924864132680693789861345339466386194840381422980702458955378518702648732728796955434922249345867267377826",
+ "3168153642368000846168628288850857848098131369578410603904155841373678828215434925507474033105518841999665785152501356092020415699294327720257651796364374116",
+ "278603899104240796379373331240296114411332466119196525390128418935585486485808560319073463912513286987331907013829243645911963547435764718505394265715321106",
+ "4632844957395758597246278843156350179301194123641664447791935593091018103746003967476919616681982477804041933745387575872964923485212972039478646226080044590",
+ "3278857364905061449863537070675297207767865967146919975942590789168732752489407699106980407552332044280575891715425195464227794423128203118286002006478070253",
+ "4488572162727491199625798812850846214916160870437505769058530973184916706326908828109446998319674522651965593412129100088877891410841200092694907512496020182",
+ "2126311732129869456512627735193938710331935978955001830871465201548004444073866677974896970734635601049909886616595755762740651165670628002084824920216966370",
+ "4803556648772727869384704240411011976585308117802975396033423138930126997561438092192867119930177133880625991019440171972612468402200399449807843995563872782");
+
+ /* NOTE: This isn't quite the standard way to do curve25519
+ diffie-hellman, but it tests that the ecc_point interface works
+ also with curve25519. FIXME: Which it doesn't yet do. */
+ test_dh ("curve25519", &nettle_curve25519,
+ "238301186166219052901200372289459967515481170332211409964804596991365959539",
+ "16689431791973914300519294566135927090340942991104989847654071982531922134636",
+ "20308418066388251043787233144732111482161260158474210903552303016733832642783",
+ "3795950278952272509684177709511717492358770264218705926196469999516028451559",
+ "33748673775975978547568270043630771161978032265709185964960751948965332685487",
+ "45040108202870901856797106334440548809561721639881101469282515918034252408802",
+ "12684624775789228333626692483521764247362476074160626230698999100180553618972",
+ "22635121008463339848034566659860493350277619617839914078958064757823336329514");
+}
return res;
}
-struct ecc_ref_point
-{
- const char *x;
- const char *y;
-};
-
void
write_mpn (FILE *f, int base, const mp_limb_t *xp, mp_size_t n)
{
mpz_out_str (f, base, mpz_roinit_n (t,xp, n));
}
-static void
+void
test_ecc_point (const struct ecc_curve *ecc,
const struct ecc_ref_point *ref,
const mp_limb_t *p)
extern const struct ecc_curve * const ecc_curves[];
+struct ecc_ref_point
+{
+ const char *x;
+ const char *y;
+};
+
+void
+test_ecc_point (const struct ecc_curve *ecc,
+ const struct ecc_ref_point *ref,
+ const mp_limb_t *p);
+
void
test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p);
--- /dev/null
+C x86_64/ecc-25519-modp.asm
+
+ifelse(<
+ 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/.
+>)
+
+ .file "ecc-25519-modp.asm"
+
+define(<RP>, <%rsi>)
+define(<U0>, <%rdi>) C Overlaps unused ecc input
+define(<U1>, <%rcx>)
+define(<U2>, <%r8>)
+define(<U3>, <%r9>)
+define(<T0>, <%r10>)
+define(<T1>, <%r11>)
+define(<M>, <%rbx>)
+
+PROLOGUE(nettle_ecc_25519_modp)
+ W64_ENTRY(2, 0)
+ push %rbx
+
+ C First fold the limbs affecting bit 255
+ mov 56(RP), %rax
+ mov $38, M
+ mul M
+ mov 24(RP), U3
+ xor T0, T0
+ add %rax, U3
+ adc %rdx, T0
+
+ mov 40(RP), %rax C Do this early as possible
+ mul M
+
+ add U3, U3
+ adc T0, T0
+ shr U3 C Undo shift, clear high bit
+
+ C Fold the high limb again, together with RP[5]
+ imul $19, T0
+
+ mov (RP), U0
+ mov 8(RP), U1
+ mov 16(RP), U2
+ add T0, U0
+ adc %rax, U1
+ mov 32(RP), %rax
+ adc %rdx, U2
+ adc $0, U3
+
+ C Fold final two limbs, RP[4] and RP[6]
+ mul M
+ mov %rax, T0
+ mov 48(RP), %rax
+ mov %rdx, T1
+ mul M
+ add T0, U0
+ mov U0, (RP)
+ adc T1, U1
+ mov U1, 8(RP)
+ adc %rax, U2
+ mov U2, 16(RP)
+ adc %rdx, U3
+ mov U3, 24(RP)
+
+ pop %rbx
+ W64_EXIT(2, 0)
+ ret
+EPILOGUE(nettle_ecc_25519_modp)
git.samba.org / gd / nettle / commitdiff