Add support for several GOST curves as defined by RFC 4357 and RFC 7836. Names for these curves are taken from TLS Supported Groups registry.
-- With best wishes Dmitry
In preparation to adding GOST curves support, rename source files and use curve name as eccdata parameter.
Signed-off-by: Dmitry Eremin-Solenikov dbaryshkov@gmail.com --- .gitignore | 12 ++--- Makefile.in | 45 ++++++++++--------- ...cc-192-modp.asm => ecc-secp192r1-modp.asm} | 0 ...cc-224-modp.asm => ecc-secp224r1-modp.asm} | 0 ...cc-256-redc.asm => ecc-secp256r1-redc.asm} | 0 ...cc-384-modp.asm => ecc-secp384r1-modp.asm} | 0 ...cc-521-modp.asm => ecc-secp521r1-modp.asm} | 0 configure.ac | 5 ++- ecc-25519.c => ecc-curve25519.c | 4 +- ecc-192.c => ecc-secp192r1.c | 4 +- ecc-224.c => ecc-secp224r1.c | 4 +- ecc-256.c => ecc-secp256r1.c | 4 +- ecc-384.c => ecc-secp384r1.c | 4 +- ecc-521.c => ecc-secp521r1.c | 4 +- eccdata.c | 45 ++++++++++--------- ...25519-modp.asm => ecc-curve25519-modp.asm} | 0 ...cc-192-modp.asm => ecc-secp192r1-modp.asm} | 0 ...cc-224-modp.asm => ecc-secp224r1-modp.asm} | 0 ...cc-256-redc.asm => ecc-secp256r1-redc.asm} | 0 ...cc-384-modp.asm => ecc-secp384r1-modp.asm} | 0 ...cc-521-modp.asm => ecc-secp521r1-modp.asm} | 0 21 files changed, 68 insertions(+), 63 deletions(-) rename arm/{ecc-192-modp.asm => ecc-secp192r1-modp.asm} (100%) rename arm/{ecc-224-modp.asm => ecc-secp224r1-modp.asm} (100%) rename arm/{ecc-256-redc.asm => ecc-secp256r1-redc.asm} (100%) rename arm/{ecc-384-modp.asm => ecc-secp384r1-modp.asm} (100%) rename arm/{ecc-521-modp.asm => ecc-secp521r1-modp.asm} (100%) rename ecc-25519.c => ecc-curve25519.c (99%) rename ecc-192.c => ecc-secp192r1.c (98%) rename ecc-224.c => ecc-secp224r1.c (98%) rename ecc-256.c => ecc-secp256r1.c (99%) rename ecc-384.c => ecc-secp384r1.c (99%) rename ecc-521.c => ecc-secp521r1.c (98%) rename x86_64/{ecc-25519-modp.asm => ecc-curve25519-modp.asm} (100%) rename x86_64/{ecc-192-modp.asm => ecc-secp192r1-modp.asm} (100%) rename x86_64/{ecc-224-modp.asm => ecc-secp224r1-modp.asm} (100%) rename x86_64/{ecc-256-redc.asm => ecc-secp256r1-redc.asm} (100%) rename x86_64/{ecc-384-modp.asm => ecc-secp384r1-modp.asm} (100%) rename x86_64/{ecc-521-modp.asm => ecc-secp521r1-modp.asm} (100%)
diff --git a/.gitignore b/.gitignore index b79c53f535ff..be10fbe959cc 100644 --- a/.gitignore +++ b/.gitignore @@ -43,12 +43,12 @@ core /keymap.h /parity.h /rotors.h -/ecc-192.h -/ecc-224.h -/ecc-256.h -/ecc-384.h -/ecc-521.h -/ecc-25519.h +/ecc-curve25519.h +/ecc-secp192r1.h +/ecc-secp224r1.h +/ecc-secp256r1.h +/ecc-secp384r1.h +/ecc-secp521r1.h /version.h /nettle.aux /nettle.cp diff --git a/Makefile.in b/Makefile.in index 440de9f7bb59..8d8da40c1911 100644 --- a/Makefile.in +++ b/Makefile.in @@ -171,8 +171,8 @@ hogweed_SOURCES = sexp.c sexp-format.c \ gmp-glue.c cnd-copy.c \ ecc-mod.c ecc-mod-inv.c \ ecc-mod-arith.c ecc-pp1-redc.c ecc-pm1-redc.c \ - ecc-192.c ecc-224.c ecc-256.c ecc-384.c ecc-521.c \ - ecc-25519.c \ + ecc-curve25519.c ecc-secp192r1.c ecc-secp224r1.c \ + ecc-secp256r1.c ecc-secp384r1.c ecc-secp521r1.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-eh-to-a.c \ @@ -341,24 +341,24 @@ des.$(OBJEXT): des.c des.h $(des_headers) # k = 14, c = 7, S = 256, T = 42 ( 28 A + 14 D) 12 KB # k = 11, c = 6, S = 192, T = 44 ( 33 A + 11 D) 9 KB # k = 16, c = 6, S = 128, T = 48 ( 32 A + 16 D) 6 KB -ecc-192.h: eccdata.stamp - ./eccdata$(EXEEXT_FOR_BUILD) 192 8 6 $(NUMB_BITS) > $@T && mv $@T $@ +ecc-secp192r1.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) secp192r1 8 6 $(NUMB_BITS) > $@T && mv $@T $@
# Some reasonable choices for 224: # k = 16, c = 7, S = 256, T = 48 ( 32 A + 16 D) ~16 KB # k = 10, c = 6, S = 256, T = 50 ( 40 A + 10 D) ~16 KB # k = 13, c = 6, S = 192, T = 52 ( 39 A + 13 D) ~12 KB # k = 9, c = 5, S = 160, T = 54 ( 45 A + 9 D) ~10 KB -ecc-224.h: eccdata.stamp - ./eccdata$(EXEEXT_FOR_BUILD) 224 16 7 $(NUMB_BITS) > $@T && mv $@T $@ +ecc-secp224r1.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) secp224r1 16 7 $(NUMB_BITS) > $@T && mv $@T $@
# Some reasonable choices for 256: # k = 9, c = 6, S = 320, T = 54 ( 45 A + 9 D) 20 KB # k = 11, c = 6, S = 256, T = 55 ( 44 A + 11 D) 16 KB # k = 19, c = 7, S = 256, T = 57 ( 38 A + 19 D) 16 KB # k = 15, c = 6, S = 192, T = 60 ( 45 A + 15 D) 12 KB -ecc-256.h: eccdata.stamp - ./eccdata$(EXEEXT_FOR_BUILD) 256 11 6 $(NUMB_BITS) > $@T && mv $@T $@ +ecc-secp256r1.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) secp256r1 11 6 $(NUMB_BITS) > $@T && mv $@T $@
# Some reasonable choices for 384: # k = 16, c = 6, S = 256, T = 80 ( 64 A + 16 D) 24 KB @@ -368,31 +368,31 @@ ecc-256.h: eccdata.stamp # k = 13, c = 5, S = 192, T = 91 ( 78 A + 13 D) 18 KB # k = 16, c = 5, S = 160, T = 96 ( 80 A + 16 D) 15 KB # k = 32, c = 6, S = 128, T = 96 ( 64 A + 32 D) 12 KB -ecc-384.h: eccdata.stamp - ./eccdata$(EXEEXT_FOR_BUILD) 384 32 6 $(NUMB_BITS) > $@T && mv $@T $@ +ecc-secp384r1.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) secp384r1 32 6 $(NUMB_BITS) > $@T && mv $@T $@
# Some reasonable choices for 521: # k = 29, c = 6, S = 192, T = 116 ( 87 A + 29 D) ~27 KB # k = 21, c = 5, S = 160, T = 126 (105 A + 21 D) ~23 KB # k = 44, c = 6, S = 128, T = 132 ( 88 A + 44 D) ~18 KB # k = 35, c = 5, S = 96, T = 140 (105 A + 35 D) ~14 KB -ecc-521.h: eccdata.stamp - ./eccdata$(EXEEXT_FOR_BUILD) 521 44 6 $(NUMB_BITS) > $@T && mv $@T $@ +ecc-secp521r1.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) secp521r1 44 6 $(NUMB_BITS) > $@T && mv $@T $@
-# Parameter choices mostly the same as for ecc-256.h. -ecc-25519.h: eccdata.stamp - ./eccdata$(EXEEXT_FOR_BUILD) 255 11 6 $(NUMB_BITS) > $@T && mv $@T $@ +# Parameter choices mostly the same as for ecc-secp256r1.h. +ecc-curve25519.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) curve25519 11 6 $(NUMB_BITS) > $@T && mv $@T $@
eccdata.stamp: eccdata.c $(MAKE) eccdata$(EXEEXT_FOR_BUILD) echo stamp > eccdata.stamp
-ecc-192.$(OBJEXT): ecc-192.h -ecc-224.$(OBJEXT): ecc-224.h -ecc-256.$(OBJEXT): ecc-256.h -ecc-384.$(OBJEXT): ecc-384.h -ecc-521.$(OBJEXT): ecc-521.h -ecc-25519.$(OBJEXT): ecc-25519.h +ecc-curve25519.$(OBJEXT): ecc-curve25519.h +ecc-secp192r1.$(OBJEXT): ecc-secp192r1.h +ecc-secp224r1.$(OBJEXT): ecc-secp224r1.h +ecc-secp256r1.$(OBJEXT): ecc-secp256r1.h +ecc-secp384r1.$(OBJEXT): ecc-secp384r1.h +ecc-secp521r1.$(OBJEXT): ecc-secp521r1.h
.asm.$(OBJEXT): $(srcdir)/asm.m4 machine.m4 config.m4 $(M4) $(srcdir)/asm.m4 machine.m4 config.m4 $< >$*.s @@ -645,7 +645,8 @@ distcheck: dist
clean-here: -rm -f $(TARGETS) *.$(OBJEXT) *.s *.so *.dll *.a \ - ecc-192.h ecc-224.h ecc-256.h ecc-384.h ecc-521.h ecc-25519.h \ + ecc-curve25519.h ecc-secp192r1.h ecc-secp224r1.h ecc-secp256r1.h \ + ecc-secp384r1.h ecc-secp521r1.h \ aesdata$(EXEEXT_FOR_BUILD) \ desdata$(EXEEXT_FOR_BUILD) \ twofishdata$(EXEEXT_FOR_BUILD) \ diff --git a/arm/ecc-192-modp.asm b/arm/ecc-secp192r1-modp.asm similarity index 100% rename from arm/ecc-192-modp.asm rename to arm/ecc-secp192r1-modp.asm diff --git a/arm/ecc-224-modp.asm b/arm/ecc-secp224r1-modp.asm similarity index 100% rename from arm/ecc-224-modp.asm rename to arm/ecc-secp224r1-modp.asm diff --git a/arm/ecc-256-redc.asm b/arm/ecc-secp256r1-redc.asm similarity index 100% rename from arm/ecc-256-redc.asm rename to arm/ecc-secp256r1-redc.asm diff --git a/arm/ecc-384-modp.asm b/arm/ecc-secp384r1-modp.asm similarity index 100% rename from arm/ecc-384-modp.asm rename to arm/ecc-secp384r1-modp.asm diff --git a/arm/ecc-521-modp.asm b/arm/ecc-secp521r1-modp.asm similarity index 100% rename from arm/ecc-521-modp.asm rename to arm/ecc-secp521r1-modp.asm diff --git a/configure.ac b/configure.ac index 00d2bf5dcd40..ade9c919abcb 100644 --- a/configure.ac +++ b/configure.ac @@ -475,8 +475,9 @@ asm_nettle_optional_list="gcm-hash8.asm cpuid.asm \
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-25519-modp.asm ecc-256-redc.asm ecc-384-modp.asm ecc-521-modp.asm" + asm_hogweed_optional_list="ecc-curve25519-modp.asm \ + ecc-secp192r1-modp.asm ecc-secp224r1-modp.asm \ + ecc-secp256r1-redc.asm ecc-secp384r1-modp.asm ecc-secp521r1-modp.asm" fi
OPT_NETTLE_OBJS="" diff --git a/ecc-25519.c b/ecc-curve25519.c similarity index 99% rename from ecc-25519.c rename to ecc-curve25519.c index bb71a36b3cd5..9e77a4ca9aef 100644 --- a/ecc-25519.c +++ b/ecc-curve25519.c @@ -1,4 +1,4 @@ -/* ecc-25519.c +/* ecc-curve25519.c
Arithmetic and tables for curve25519,
@@ -42,7 +42,7 @@
#define USE_REDC 0
-#include "ecc-25519.h" +#include "ecc-curve25519.h"
#define PHIGH_BITS (GMP_NUMB_BITS * ECC_LIMB_SIZE - 255)
diff --git a/ecc-192.c b/ecc-secp192r1.c similarity index 98% rename from ecc-192.c rename to ecc-secp192r1.c index 4f428113674e..8919f85bcfb5 100644 --- a/ecc-192.c +++ b/ecc-secp192r1.c @@ -1,4 +1,4 @@ -/* ecc-192.c +/* ecc-secp192r1.c
Compile time constant (but machine dependent) tables.
@@ -46,7 +46,7 @@
#define USE_REDC 0
-#include "ecc-192.h" +#include "ecc-secp192r1.h"
#if HAVE_NATIVE_ecc_192_modp
diff --git a/ecc-224.c b/ecc-secp224r1.c similarity index 98% rename from ecc-224.c rename to ecc-secp224r1.c index 5962e1b863bf..cc15a7470e75 100644 --- a/ecc-224.c +++ b/ecc-secp224r1.c @@ -1,4 +1,4 @@ -/* ecc-224.c +/* ecc-secp224r1.c
Compile time constant (but machine dependent) tables.
@@ -52,7 +52,7 @@ ecc_224_modp (const struct ecc_modulo *m, mp_limb_t *rp); #define ecc_224_modp ecc_mod #endif
-#include "ecc-224.h" +#include "ecc-secp224r1.h"
#if ECC_REDC_SIZE < 0 # define ecc_224_redc ecc_pm1_redc diff --git a/ecc-256.c b/ecc-secp256r1.c similarity index 99% rename from ecc-256.c rename to ecc-secp256r1.c index 7eed2835c08a..611d6d7c7d42 100644 --- a/ecc-256.c +++ b/ecc-secp256r1.c @@ -1,4 +1,4 @@ -/* ecc-256.c +/* ecc-secp256r1.c
Compile time constant (but machine dependent) tables.
@@ -48,7 +48,7 @@ # define USE_REDC (ECC_REDC_SIZE != 0) #endif
-#include "ecc-256.h" +#include "ecc-secp256r1.h"
#if HAVE_NATIVE_ecc_256_redc # define ecc_256_redc nettle_ecc_256_redc diff --git a/ecc-384.c b/ecc-secp384r1.c similarity index 99% rename from ecc-384.c rename to ecc-secp384r1.c index 94b8af91354e..6ffed8473c36 100644 --- a/ecc-384.c +++ b/ecc-secp384r1.c @@ -1,4 +1,4 @@ -/* ecc-384.c +/* ecc-secp384r1.c
Compile time constant (but machine dependent) tables.
@@ -44,7 +44,7 @@
#define USE_REDC 0
-#include "ecc-384.h" +#include "ecc-secp384r1.h"
#if HAVE_NATIVE_ecc_384_modp #define ecc_384_modp nettle_ecc_384_modp diff --git a/ecc-521.c b/ecc-secp521r1.c similarity index 98% rename from ecc-521.c rename to ecc-secp521r1.c index 52a018dd7c9c..753208c6b47d 100644 --- a/ecc-521.c +++ b/ecc-secp521r1.c @@ -1,4 +1,4 @@ -/* ecc-521.c +/* ecc-secp521r1.c
Compile time constant (but machine dependent) tables.
@@ -42,7 +42,7 @@
#define USE_REDC 0
-#include "ecc-521.h" +#include "ecc-secp521r1.h"
#if HAVE_NATIVE_ecc_521_modp #define ecc_521_modp nettle_ecc_521_modp diff --git a/eccdata.c b/eccdata.c index fa7a11c5f0af..12b2455d4058 100644 --- a/eccdata.c +++ b/eccdata.c @@ -345,11 +345,10 @@ ecc_curve_init_str (struct ecc_curve *ecc, enum ecc_type type, }
static void -ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) +ecc_curve_init (struct ecc_curve *ecc, const char *curve) { - switch (bit_size) + if (!strcmp (curve, "secp192r1")) { - case 192: ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, /* p = 2^{192} - 2^{64} - 1 */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE" @@ -380,8 +379,9 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) "35433907297cc378b0015703374729d7a4fe46647084e4ba", "a2649984f2135c301ea3acb0776cd4f125389b311db3be32");
- break; - case 224: + } + else if (!strcmp (curve, "secp224r1")) + { ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, /* p = 2^{224} - 2^{96} + 1 */ "ffffffffffffffffffffffffffffffff" @@ -413,8 +413,9 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) "ae99feebb5d26945b54892092a8aee02912930fa41cd114e40447301", "482580a0ec5bc47e88bc8c378632cd196cb3fa058a7114eb03054c9");
- break; - case 256: + } + else if (!strcmp (curve, "secp256r1")) + { ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, /* p = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1 */ "FFFFFFFF000000010000000000000000" @@ -446,8 +447,9 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) "e2534a3532d08fbba02dde659ee62bd0031fe2db785596ef509302446b030852", "e0f1575a4c633cc719dfee5fda862d764efc96c3f30ee0055c42c23f184ed8c6");
- break; - case 384: + } + else if (!strcmp (curve, "secp384r1")) + { ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, /* p = 2^{384} - 2^{128} - 2^{96} + 2^{32} - 1 */ "ffffffffffffffffffffffffffffffff" @@ -484,8 +486,9 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) "138251cd52ac9298c1c8aad977321deb97e709bd0b4ca0aca55dc8ad51dcfc9d1589a1597e3a5120e1efd631c63e1835", "cacae29869a62e1631e8a28181ab56616dc45d918abc09f3ab0e63cf792aa4dced7387be37bba569549f1c02b270ed67");
- break; - case 521: + } + else if (!strcmp (curve, "secp521r1")) + { ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, "1ff" /* p = 2^{521} - 1 */ "ffffffffffffffffffffffffffffffff" @@ -531,8 +534,9 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) "35b5df64ae2ac204c354b483487c9070cdc61c891c5ff39afc06c5d55541d3ceac8659e24afe3d0750e8b88e9f078af066a1d5025b08e5a5e2fbc87412871902f3", "82096f84261279d2b673e0178eb0b4abb65521aef6e6e32e1b5ae63fe2f19907f279f283e54ba385405224f750a95b85eebb7faef04699d1d9e21f47fc346e4d0d");
- break; - case 255: + } + else if (!strcmp (curve, "curve25519")) + { /* curve25519, y^2 = x^3 + 486662 x^2 + x (mod p), with p = 2^{255} - 19.
According to http://cr.yp.to/papers.html#newelliptic, this @@ -601,14 +605,13 @@ ecc_curve_init (struct ecc_curve *ecc, unsigned bit_size) "fe1805dfcd5d2a230fee85e4550013ef", "75af5bf4ebdc75c8fe26873427d275d7" "3c0fb13da361077a565539f46de1c30"); - - break; - - default: - fprintf (stderr, "No known curve for size %d\n", bit_size); - exit(EXIT_FAILURE); } - ecc->bit_size = bit_size; + else + { + fprintf (stderr, "No known curve with name %s\n", curve); + exit(EXIT_FAILURE); + } + ecc->bit_size = mpz_sizeinbase (ecc->p, 2); }
static void @@ -1204,7 +1207,7 @@ main (int argc, char **argv) return EXIT_FAILURE; }
- ecc_curve_init (&ecc, atoi(argv[1])); + ecc_curve_init (&ecc, argv[1]);
ecc_pippenger_precompute (&ecc, atoi(argv[2]), atoi(argv[3]));
diff --git a/x86_64/ecc-25519-modp.asm b/x86_64/ecc-curve25519-modp.asm similarity index 100% rename from x86_64/ecc-25519-modp.asm rename to x86_64/ecc-curve25519-modp.asm diff --git a/x86_64/ecc-192-modp.asm b/x86_64/ecc-secp192r1-modp.asm similarity index 100% rename from x86_64/ecc-192-modp.asm rename to x86_64/ecc-secp192r1-modp.asm diff --git a/x86_64/ecc-224-modp.asm b/x86_64/ecc-secp224r1-modp.asm similarity index 100% rename from x86_64/ecc-224-modp.asm rename to x86_64/ecc-secp224r1-modp.asm diff --git a/x86_64/ecc-256-redc.asm b/x86_64/ecc-secp256r1-redc.asm similarity index 100% rename from x86_64/ecc-256-redc.asm rename to x86_64/ecc-secp256r1-redc.asm diff --git a/x86_64/ecc-384-modp.asm b/x86_64/ecc-secp384r1-modp.asm similarity index 100% rename from x86_64/ecc-384-modp.asm rename to x86_64/ecc-secp384r1-modp.asm diff --git a/x86_64/ecc-521-modp.asm b/x86_64/ecc-secp521r1-modp.asm similarity index 100% rename from x86_64/ecc-521-modp.asm rename to x86_64/ecc-secp521r1-modp.asm
Signed-off-by: Dmitry Eremin-Solenikov dbaryshkov@gmail.com --- .gitignore | 5 ++ Makefile.in | 55 +++++++++++++- ecc-curve.h | 5 ++ ecc-gc256b.c | 125 ++++++++++++++++++++++++++++++ ecc-gc256c.c | 143 +++++++++++++++++++++++++++++++++++ ecc-gc256d.c | 137 +++++++++++++++++++++++++++++++++ ecc-gc512a.c | 125 ++++++++++++++++++++++++++++++ ecc-gc512b.c | 137 +++++++++++++++++++++++++++++++++ ecc-internal.h | 7 ++ eccdata.c | 159 ++++++++++++++++++++++++++++++++++++++- examples/ecc-benchmark.c | 5 ++ testsuite/testutils.c | 56 +++++++++++++- 12 files changed, 954 insertions(+), 5 deletions(-) create mode 100644 ecc-gc256b.c create mode 100644 ecc-gc256c.c create mode 100644 ecc-gc256d.c create mode 100644 ecc-gc512a.c create mode 100644 ecc-gc512b.c
diff --git a/.gitignore b/.gitignore index be10fbe959cc..4edcc8726448 100644 --- a/.gitignore +++ b/.gitignore @@ -44,6 +44,11 @@ core /parity.h /rotors.h /ecc-curve25519.h +/ecc-gc256b.h +/ecc-gc256c.h +/ecc-gc256d.h +/ecc-gc512a.h +/ecc-gc512b.h /ecc-secp192r1.h /ecc-secp224r1.h /ecc-secp256r1.h diff --git a/Makefile.in b/Makefile.in index 8d8da40c1911..98bcad33f866 100644 --- a/Makefile.in +++ b/Makefile.in @@ -171,7 +171,10 @@ hogweed_SOURCES = sexp.c sexp-format.c \ gmp-glue.c cnd-copy.c \ ecc-mod.c ecc-mod-inv.c \ ecc-mod-arith.c ecc-pp1-redc.c ecc-pm1-redc.c \ - ecc-curve25519.c ecc-secp192r1.c ecc-secp224r1.c \ + ecc-curve25519.c \ + ecc-gc256b.c ecc-gc256c.c ecc-gc256d.c \ + ecc-gc512a.c ecc-gc512b.c \ + ecc-secp192r1.c ecc-secp224r1.c \ ecc-secp256r1.c ecc-secp384r1.c ecc-secp521r1.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 \ @@ -382,12 +385,57 @@ ecc-secp521r1.h: eccdata.stamp # Parameter choices mostly the same as for ecc-secp256r1.h. ecc-curve25519.h: eccdata.stamp ./eccdata$(EXEEXT_FOR_BUILD) curve25519 11 6 $(NUMB_BITS) > $@T && mv $@T $@ + # +# Some reasonable choices for 256: +# k = 9, c = 6, S = 320, T = 54 ( 45 A + 9 D) 20 KB +# k = 11, c = 6, S = 256, T = 55 ( 44 A + 11 D) 16 KB +# k = 19, c = 7, S = 256, T = 57 ( 38 A + 19 D) 16 KB +# k = 15, c = 6, S = 192, T = 60 ( 45 A + 15 D) 12 KB +ecc-gc256b.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) gc256b 11 6 $(NUMB_BITS) > $@T && mv $@T $@ + +# Some reasonable choices for 256: +# k = 9, c = 6, S = 320, T = 54 ( 45 A + 9 D) 20 KB +# k = 11, c = 6, S = 256, T = 55 ( 44 A + 11 D) 16 KB +# k = 19, c = 7, S = 256, T = 57 ( 38 A + 19 D) 16 KB +# k = 15, c = 6, S = 192, T = 60 ( 45 A + 15 D) 12 KB +ecc-gc256c.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) gc256c 11 6 $(NUMB_BITS) > $@T && mv $@T $@ + +# Some reasonable choices for 256: +# k = 9, c = 6, S = 320, T = 54 ( 45 A + 9 D) 20 KB +# k = 11, c = 6, S = 256, T = 55 ( 44 A + 11 D) 16 KB +# k = 19, c = 7, S = 256, T = 57 ( 38 A + 19 D) 16 KB +# k = 15, c = 6, S = 192, T = 60 ( 45 A + 15 D) 12 KB +ecc-gc256d.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) gc256d 11 6 $(NUMB_BITS) > $@T && mv $@T $@ + +# Some reasonable choices for 512: +# k = 29, c = 6, S = 192, T = 116 ( 87 A + 29 D) +# k = 21, c = 5, S = 160, T = 126 (105 A + 21 D) +# k = 43, c = 6, S = 128, T = 129 ( 86 A + 43 D) +# k = 35, c = 5, S = 96, T = 140 (105 A + 35 D) +ecc-gc512a.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) gc512a 43 6 $(NUMB_BITS) > $@T && mv $@T $@ + +# Some reasonable choices for 512: +# k = 29, c = 6, S = 192, T = 116 ( 87 A + 29 D) +# k = 21, c = 5, S = 160, T = 126 (105 A + 21 D) +# k = 43, c = 6, S = 128, T = 129 ( 86 A + 43 D) +# k = 35, c = 5, S = 96, T = 140 (105 A + 35 D) +ecc-gc512b.h: eccdata.stamp + ./eccdata$(EXEEXT_FOR_BUILD) gc512b 43 6 $(NUMB_BITS) > $@T && mv $@T $@
eccdata.stamp: eccdata.c $(MAKE) eccdata$(EXEEXT_FOR_BUILD) echo stamp > eccdata.stamp
ecc-curve25519.$(OBJEXT): ecc-curve25519.h +ecc-gc256b.$(OBJEXT): ecc-gc256b.h +ecc-gc256c.$(OBJEXT): ecc-gc256c.h +ecc-gc256d.$(OBJEXT): ecc-gc256d.h +ecc-gc512a.$(OBJEXT): ecc-gc512a.h +ecc-gc512b.$(OBJEXT): ecc-gc512b.h ecc-secp192r1.$(OBJEXT): ecc-secp192r1.h ecc-secp224r1.$(OBJEXT): ecc-secp224r1.h ecc-secp256r1.$(OBJEXT): ecc-secp256r1.h @@ -645,7 +693,10 @@ distcheck: dist
clean-here: -rm -f $(TARGETS) *.$(OBJEXT) *.s *.so *.dll *.a \ - ecc-curve25519.h ecc-secp192r1.h ecc-secp224r1.h ecc-secp256r1.h \ + ecc-curve25519.h \ + ecc-gc256b.h ecc-gc256c.h ecc-gc256d.h \ + ecc-gc512a.h ecc-gc512b.h \ + ecc-secp192r1.h ecc-secp224r1.h ecc-secp256r1.h \ ecc-secp384r1.h ecc-secp521r1.h \ aesdata$(EXEEXT_FOR_BUILD) \ desdata$(EXEEXT_FOR_BUILD) \ diff --git a/ecc-curve.h b/ecc-curve.h index 76024a19d24f..e0aafae4e996 100644 --- a/ecc-curve.h +++ b/ecc-curve.h @@ -48,6 +48,11 @@ const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_224r1(void); const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_256r1(void); const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_384r1(void); const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_521r1(void); +const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_gc_256b(void); +const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_gc_256c(void); +const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_gc_256d(void); +const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_gc_512a(void); +const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_gc_512b(void);
#ifdef __cplusplus } diff --git a/ecc-gc256b.c b/ecc-gc256b.c new file mode 100644 index 000000000000..af6dcaa3264d --- /dev/null +++ b/ecc-gc256b.c @@ -0,0 +1,125 @@ +/* ecc-gc256b.c + + Compile time constant (but machine dependent) tables. + + Copyright (C) 2016, 2019 Dmitry Eremin-Solenikov + + 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" + +#define USE_REDC (ECC_REDC_SIZE != 0) + +#include "ecc-gc256b.h" + +#if ECC_REDC_SIZE > 0 +# define ecc_256_redc ecc_pp1_redc +#elif ECC_REDC_SIZE == 0 +# define ecc_256_redc NULL +#else +# error Configuration error +#endif + +#define ecc_256_modp ecc_mod +#define ecc_256_modq ecc_mod + +const struct ecc_curve _nettle_gc_256b = +{ + { + 256, + ECC_LIMB_SIZE, + ECC_BMODP_SIZE, + ECC_REDC_SIZE, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_p, + ecc_Bmodp, + ecc_Bmodp_shifted, + ecc_redc_ppm1, + + ecc_pp1h, + ecc_256_modp, + USE_REDC ? ecc_256_redc : ecc_256_modp, + ecc_mod_inv, + NULL, + }, + { + 256, + ECC_LIMB_SIZE, + ECC_BMODQ_SIZE, + 0, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_q, + ecc_Bmodq, + ecc_Bmodq_shifted, + NULL, + ecc_qp1h, + + ecc_256_modq, + ecc_256_modq, + ecc_mod_inv, + NULL, + }, + + USE_REDC, + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + + ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_MUL_A_ITCH (ECC_LIMB_SIZE), + ECC_MUL_G_ITCH (ECC_LIMB_SIZE), + ECC_J_TO_A_ITCH (ECC_LIMB_SIZE), + + ecc_add_jjj, + ecc_mul_a, + ecc_mul_g, + ecc_j_to_a, + + ecc_b, + ecc_g, + NULL, + ecc_unit, + ecc_table +}; + +const struct ecc_curve *nettle_get_gc_256b(void) +{ + return &_nettle_gc_256b; +} diff --git a/ecc-gc256c.c b/ecc-gc256c.c new file mode 100644 index 000000000000..8018d1426150 --- /dev/null +++ b/ecc-gc256c.c @@ -0,0 +1,143 @@ +/* ecc-gc256c.c + + Compile time constant (but machine dependent) tables. + + Copyright (C) 2016, 2019 Dmitry Eremin-Solenikov + + 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" + +#define USE_REDC (ECC_REDC_SIZE != 0) + +#include "ecc-gc256c.h" + +#if HAVE_NATIVE_ecc_256_redc +# define ecc_256_redc nettle_ecc_256_redc +void +ecc_256_redc (const struct ecc_modulo *p, mp_limb_t *rp); +#else /* !HAVE_NATIVE_ecc_256_redc */ +# if ECC_REDC_SIZE > 0 +# define ecc_256_redc ecc_pp1_redc +# elif ECC_REDC_SIZE == 0 +# define ecc_256_redc NULL +# else +# error Configuration error +# endif +#endif /* !HAVE_NATIVE_ecc_256_redc */ + +static void +ecc_gost256_mod (const struct ecc_modulo *p, mp_limb_t *rp) +{ + mp_size_t mn = p->size; + mpz_t r, a, m; + mpz_init (r); + mpz_mod (r, mpz_roinit_n (a, rp, 2*mn), mpz_roinit_n (m, p->m, mn)); + mpz_limbs_copy (rp, r, mn); + + mpz_clear (r); +} + +#define ecc_256_modp ecc_gost256_mod +#define ecc_256_modq ecc_gost256_mod + +const struct ecc_curve _nettle_gc_256c = +{ + { + 256, + ECC_LIMB_SIZE, + ECC_BMODP_SIZE, + ECC_REDC_SIZE, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_p, + ecc_Bmodp, + ecc_Bmodp_shifted, + ecc_redc_ppm1, + + ecc_pp1h, + ecc_256_modp, + USE_REDC ? ecc_256_redc : ecc_256_modp, + ecc_mod_inv, + NULL, + }, + { + 256, + ECC_LIMB_SIZE, + ECC_BMODQ_SIZE, + 0, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_q, + ecc_Bmodq, + ecc_Bmodq_shifted, + NULL, + ecc_qp1h, + + ecc_256_modq, + ecc_256_modq, + ecc_mod_inv, + NULL, + }, + + USE_REDC, + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + + ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_MUL_A_ITCH (ECC_LIMB_SIZE), + ECC_MUL_G_ITCH (ECC_LIMB_SIZE), + ECC_J_TO_A_ITCH (ECC_LIMB_SIZE), + + ecc_add_jjj, + ecc_mul_a, + ecc_mul_g, + ecc_j_to_a, + + ecc_b, + ecc_g, + NULL, + ecc_unit, + ecc_table +}; + +const struct ecc_curve *nettle_get_gc_256c(void) +{ + return &_nettle_gc_256c; +} diff --git a/ecc-gc256d.c b/ecc-gc256d.c new file mode 100644 index 000000000000..bbd0b406cc91 --- /dev/null +++ b/ecc-gc256d.c @@ -0,0 +1,137 @@ +/* ecc-gc256d.c + + Compile time constant (but machine dependent) tables. + + Copyright (C) 2016, 2019 Dmitry Eremin-Solenikov + + 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" + +#define USE_REDC (ECC_REDC_SIZE != 0) + +#include "ecc-gc256d.h" + +#if ECC_REDC_SIZE > 0 +# define ecc_256_redc ecc_pp1_redc +#elif ECC_REDC_SIZE == 0 +# define ecc_256_redc NULL +#else +# error Configuration error +#endif + +static void +ecc_gost256_mod (const struct ecc_modulo *p, mp_limb_t *rp) +{ + mp_size_t mn = p->size; + mpz_t r, a, m; + mpz_init (r); + mpz_mod (r, mpz_roinit_n (a, rp, 2*mn), mpz_roinit_n (m, p->m, mn)); + mpz_limbs_copy (rp, r, mn); + + mpz_clear (r); +} + +#define ecc_256_modp ecc_gost256_mod +#define ecc_256_modq ecc_gost256_mod + +const struct ecc_curve _nettle_gc_256d = +{ + { + 256, + ECC_LIMB_SIZE, + ECC_BMODP_SIZE, + ECC_REDC_SIZE, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_p, + ecc_Bmodp, + ecc_Bmodp_shifted, + ecc_redc_ppm1, + + ecc_pp1h, + ecc_256_modp, + USE_REDC ? ecc_256_redc : ecc_256_modp, + ecc_mod_inv, + NULL, + }, + { + 256, + ECC_LIMB_SIZE, + ECC_BMODQ_SIZE, + 0, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_q, + ecc_Bmodq, + ecc_Bmodq_shifted, + NULL, + ecc_qp1h, + + ecc_256_modq, + ecc_256_modq, + ecc_mod_inv, + NULL, + }, + + USE_REDC, + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + + ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_MUL_A_ITCH (ECC_LIMB_SIZE), + ECC_MUL_G_ITCH (ECC_LIMB_SIZE), + ECC_J_TO_A_ITCH (ECC_LIMB_SIZE), + + ecc_add_jjj, + ecc_mul_a, + ecc_mul_g, + ecc_j_to_a, + + ecc_b, + ecc_g, + NULL, + ecc_unit, + ecc_table +}; + +const struct ecc_curve *nettle_get_gc_256d(void) +{ + return &_nettle_gc_256d; +} diff --git a/ecc-gc512a.c b/ecc-gc512a.c new file mode 100644 index 000000000000..26ff83451944 --- /dev/null +++ b/ecc-gc512a.c @@ -0,0 +1,125 @@ +/* ecc-gc512a.c + + Compile time constant (but machine dependent) tables. + + Copyright (C) 2016, 2019 Dmitry Eremin-Solenikov + + 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" + +#define USE_REDC (ECC_REDC_SIZE != 0) + +#include "ecc-gc512a.h" + +#if ECC_REDC_SIZE > 0 +# define ecc_512_redc ecc_pp1_redc +#elif ECC_REDC_SIZE == 0 +# define ecc_512_redc NULL +#else +# error Configuration error +#endif + +#define ecc_512_modp ecc_mod +#define ecc_512_modq ecc_mod + +const struct ecc_curve _nettle_gc_512a = +{ + { + 512, + ECC_LIMB_SIZE, + ECC_BMODP_SIZE, + ECC_REDC_SIZE, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_p, + ecc_Bmodp, + ecc_Bmodp_shifted, + ecc_redc_ppm1, + + ecc_pp1h, + ecc_512_modp, + USE_REDC ? ecc_512_redc : ecc_512_modp, + ecc_mod_inv, + NULL, + }, + { + 512, + ECC_LIMB_SIZE, + ECC_BMODQ_SIZE, + 0, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_q, + ecc_Bmodq, + ecc_Bmodq_shifted, + NULL, + ecc_qp1h, + + ecc_512_modq, + ecc_512_modq, + ecc_mod_inv, + NULL, + }, + + USE_REDC, + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + + ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_MUL_A_ITCH (ECC_LIMB_SIZE), + ECC_MUL_G_ITCH (ECC_LIMB_SIZE), + ECC_J_TO_A_ITCH (ECC_LIMB_SIZE), + + ecc_add_jjj, + ecc_mul_a, + ecc_mul_g, + ecc_j_to_a, + + ecc_b, + ecc_g, + NULL, + ecc_unit, + ecc_table +}; + +const struct ecc_curve *nettle_get_gc_512a(void) +{ + return &_nettle_gc_512a; +} diff --git a/ecc-gc512b.c b/ecc-gc512b.c new file mode 100644 index 000000000000..b36ea83da415 --- /dev/null +++ b/ecc-gc512b.c @@ -0,0 +1,137 @@ +/* ecc-gc512b.c + + Compile time constant (but machine dependent) tables. + + Copyright (C) 2016, 2019 Dmitry Eremin-Solenikov + + 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" + +#define USE_REDC (ECC_REDC_SIZE != 0) + +#include "ecc-gc512b.h" + +#if ECC_REDC_SIZE > 0 +# define ecc_512_redc ecc_pp1_redc +#elif ECC_REDC_SIZE == 0 +# define ecc_512_redc NULL +#else +# error Configuration error +#endif + +static void +ecc_gc512_mod (const struct ecc_modulo *p, mp_limb_t *rp) +{ + mp_size_t mn = p->size; + mpz_t r, a, m; + mpz_init (r); + mpz_mod (r, mpz_roinit_n (a, rp, 2*mn), mpz_roinit_n (m, p->m, mn)); + mpz_limbs_copy (rp, r, mn); + + mpz_clear (r); +} + +#define ecc_512_modp ecc_gc512_mod +#define ecc_512_modq ecc_gc512_mod + +const struct ecc_curve _nettle_gc_512b = +{ + { + 512, + ECC_LIMB_SIZE, + ECC_BMODP_SIZE, + ECC_REDC_SIZE, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_p, + ecc_Bmodp, + ecc_Bmodp_shifted, + ecc_redc_ppm1, + + ecc_pp1h, + ecc_512_modp, + USE_REDC ? ecc_512_redc : ecc_512_modp, + ecc_mod_inv, + NULL, + }, + { + 512, + ECC_LIMB_SIZE, + ECC_BMODQ_SIZE, + 0, + ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), + 0, + + ecc_q, + ecc_Bmodq, + ecc_Bmodq_shifted, + NULL, + ecc_qp1h, + + ecc_512_modq, + ecc_512_modq, + ecc_mod_inv, + NULL, + }, + + USE_REDC, + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + + ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_MUL_A_ITCH (ECC_LIMB_SIZE), + ECC_MUL_G_ITCH (ECC_LIMB_SIZE), + ECC_J_TO_A_ITCH (ECC_LIMB_SIZE), + + ecc_add_jjj, + ecc_mul_a, + ecc_mul_g, + ecc_j_to_a, + + ecc_b, + ecc_g, + NULL, + ecc_unit, + ecc_table +}; + +const struct ecc_curve *nettle_get_gc_512b(void) +{ + return &_nettle_gc_512b; +} diff --git a/ecc-internal.h b/ecc-internal.h index 94fc218b1809..8509c717ad3a 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -85,6 +85,13 @@ extern const struct ecc_curve _nettle_secp_521r1; general ecc operations over an arbitrary type of curve. */ extern const struct ecc_curve _nettle_curve25519;
+/* GOST curves, visible with underscore prefix for now */ +extern const struct ecc_curve _nettle_gc_256b; +extern const struct ecc_curve _nettle_gc_256c; +extern const struct ecc_curve _nettle_gc_256d; +extern const struct ecc_curve _nettle_gc_512a; +extern const struct ecc_curve _nettle_gc_512b; + #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, diff --git a/eccdata.c b/eccdata.c index 12b2455d4058..cbb187d1a2fa 100644 --- a/eccdata.c +++ b/eccdata.c @@ -605,6 +605,163 @@ ecc_curve_init (struct ecc_curve *ecc, const char *curve) "fe1805dfcd5d2a230fee85e4550013ef", "75af5bf4ebdc75c8fe26873427d275d7" "3c0fb13da361077a565539f46de1c30"); + + } + else if (!strcmp (curve, "gc256b")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "ffffffffffffffffffffffffffffffff" + "fffffffffffffffffffffffffffffd97", + + "00000000000000000000000000000000" + "000000000000000000000000000000a6", + + "ffffffffffffffffffffffffffffffff" + "6c611070995ad10045841b09b761b893", + + "00000000000000000000000000000000" + "00000000000000000000000000000001", + + "8d91e471e0989cda27df505a453f2b76" + "35294f2ddf23e3b122acc99c9e9f1e14", + NULL, NULL); + + ecc->ref = ecc_alloc (3); + ecc_set_str (&ecc->ref[0], /* 2 g */ + "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd95", + "726e1b8e1f676325d820afa5bac0d489cad6b0d220dc1c4edd5336636160df83"); + + ecc_set_str (&ecc->ref[1], /* 3 g */ + "8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38d2c", + "76bcd1ca9a23b041d4d9baf507a6cd821267a94c838768e8486117796b788a51"); + + ecc_set_str (&ecc->ref[2], /* 4 g */ + "f7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e4b7", + "83ccf17ba6706d73625cc3534c7a2b9d6ec1ee6a9a7e07c10d84b388de59f741"); + + } + else if (!strcmp (curve, "gc256c")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "80000000000000000000000000000000" + "00000000000000000000000000000c99", + + "3e1af419a269a5f866a7d3c25c3df80a" + "e979259373ff2b182f49d4ce7e1bbc8b", + + "80000000000000000000000000000001" + "5f700cfff1a624e5e497161bcc8a198f", + + "00000000000000000000000000000000" + "00000000000000000000000000000001", + + "3fa8124359f96680b83d1c3eb2c070e5" + "c545c9858d03ecfb744bf8d717717efc", + NULL, NULL); + + ecc->ref = ecc_alloc (3); + ecc_set_str (&ecc->ref[0], /* 2 g */ + "8000000000000000000000000000000000000000000000000000000000000c97", + "4057edbca606997f47c2e3c14d3f8f1a3aba367a72fc13048bb40728e88e8d9d"); + + ecc_set_str (&ecc->ref[1], /* 3 g */ + "1b9a33999d8449c3bbd8cfe49ac6355a2ee0827a6c71687c86cb7b0670efe205", + "1876d998a19da37a120e76cb42f4f5225197279b612f712171a4648fe4a3ff12"); + + ecc_set_str (&ecc->ref[2], /* 4 g */ + "5fa13ecfadd7ae00c2e65d0ac6cac1deda6d60e577afe90915671b08bbb9065e", + "1b3c2859166129ac6dafee570ab9d40d33fdc25c7253c72f4e3fa77223ab016a"); + + } + else if (!strcmp (curve, "gc256d")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "9b9f605f5a858107ab1ec85e6b41c8aa" + "cf846e86789051d37998f7b9022d759b", + + "00000000000000000000000000000000" + "0000000000000000000000000000805a", + + "9b9f605f5a858107ab1ec85e6b41c8aa" + "582ca3511eddfb74f02f3a6598980bb9", + + "00000000000000000000000000000000" + "00000000000000000000000000000000", + + "41ece55743711a8c3cbf3783cd08c0ee" + "4d4dc440d4641a8f366e550dfdb3bb67", + NULL, NULL); + ecc->ref = ecc_alloc (3); + ecc_set_str (&ecc->ref[0], /* 2 g */ + "74ab1ac14e9ed5cda1af70308c897ebf3d91d913a7bf377833c436bf0f8aa40e", + "7d223beab738ba52a65ffbfe585d2807bfaed5ea9cd651a63a775b4182f562e3"); + + ecc_set_str (&ecc->ref[1], /* 3 g */ + "771e56689775fda0bbdeac54e9cd379f30391edf06f335269c48f06446cd037a", + "8430215fbee8a09c5e38bda64b50bbef41392d6afa5ced73652c83cb5221d02b"); + + ecc_set_str (&ecc->ref[2], /* 4 g */ + "4fe44356aded59b4b661e9da15fe79dbcb1d7346770919c5c99090e5ae4db8a6", + "24f0222027a3d2577cca5aefb5411c88f92f5f4b8febddebc71c12180640ebfd"); + + } + else if (!strcmp (curve, "gc512a")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffdc7", + "e8c2505dedfc86ddc1bd0b2b6667f1da34b82574761cb0e879bd081cfd0b6265" + "ee3cb090f30d27614cb4574010da90dd862ef9d4ebee4761503190785a71c760", + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "27e69532f48d89116ff22b8d4e0560609b4b38abfad2b85dcacdb1411f10b275", + "0000000000000000000000000000000000000000000000000000000000000000" + "0000000000000000000000000000000000000000000000000000000000000003", + "7503cfe87a836ae3a61b8816e25450e6ce5e1c93acf1abc1778064fdcbefa921" + "df1626be4fd036e93d75e6a50e3a41e98028fe5fc235f5b889a589cb5215f2a4", + NULL, NULL); + + ecc->ref = ecc_alloc (3); + ecc_set_str (&ecc->ref[0], /* 2 g */ + "3b89dcfc622996ab97a5869dbff15cf51db00954f43a58a5e5f6b0470a132b2f4434bbcd405d2a9516151d2a6a04f2e4375bf48de1fdb21fb982afd9d2ea137c", + "c813c4e2e2e0a8a391774c7903da7a6f14686e98e183e670ee6fb784809a3e92ca209dc631d85b1c7534ed3b37fddf64d854d7e01f91f18bb3fd307591afc051"); + + ecc_set_str (&ecc->ref[1], /* 3 g */ + "a1ff1ab2712a267eb53935ddb5a567f84db156cc096168a1174291d5f488fba543d2840b4d2dd35d764b2f57b308907aec55cfba10544e8416e134687ccb87c3", + "3cb5c4417ec4637f30374f189bb5b984c41e3a48d7f84fbfa3819e3f333f7eb311d3af7e67c4c16eeacfac2fe94c6dd4c6366f711a4fb6c7125cd7ec518d90d6"); + + ecc_set_str (&ecc->ref[2], /* 4 g */ + "b7bfb80956c8670031ba191929f64e301d681634236d47a60e571a4bedc0ef257452ef78b5b98dbb3d9f3129d9349433ce2a3a35cb519c91e2d633d7b373ae16", + "3bee95e29eecc5d5ad2beba941abcbf9f1cad478df0fecf614f63aeebef77850da7efdb93de8f3df80bc25eac09239c14175f5c29704ce9a3e383f1b3ec0e929"); + + } + else if (!strcmp (curve, "gc512b")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "8000000000000000000000000000000000000000000000000000000000000000" + "000000000000000000000000000000000000000000000000000000000000006f", + "687d1b459dc841457e3e06cf6f5e2517b97c7d614af138bcbf85dc806c4b289f" + "3e965d2db1416d217f8b276fad1ab69c50f78bee1fa3106efb8ccbc7c5140116", + "8000000000000000000000000000000000000000000000000000000000000001" + "49a1ec142565a545acfdb77bd9d40cfa8b996712101bea0ec6346c54374f25bd", + "0000000000000000000000000000000000000000000000000000000000000000" + "0000000000000000000000000000000000000000000000000000000000000002", + "1a8f7eda389b094c2c071e3647a8940f3c123b697578c213be6dd9e6c8ec7335" + "dcb228fd1edf4a39152cbcaaf8c0398828041055f94ceeec7e21340780fe41bd", + NULL, NULL); + + ecc->ref = ecc_alloc (3); + ecc_set_str (&ecc->ref[0], /* 2 g */ + "73729fb3c0d629ae5dc9bf88ca05d518bce91e502150f5e5822fa0293bc0e3ca31145f3b0e1831d8bb1f20b28780011473339e581a403c676b47c1f9ab764602", + "35d62c90549f2c17e16c6ea99d3c3dbe610f2c543fc1d0ca5bd48a5ea1d3ec11c3cec5e7fcd74b5306e73b6a8e40c818714f02b25997ee2b54f65432d3f0741e"); + + ecc_set_str (&ecc->ref[1], /* 3 g */ + "1826b56c8dc1d5779b76354070e744f2c9c82755a921142b528f2fe04f5fd0dbdc178314c4546270b423d9fe819ba4c82625b02004bfdf90a08317dceb9309b7", + "4f6882f8f6422d693f8313bb7b121117ad9ee6b8874135f3e4bff91b01141fdb35d29bc3cf15ab8a3b751050e58392a8eeae790ea5d198eab642dc520fd1713f"); + + ecc_set_str (&ecc->ref[2], /* 4 g */ + "5af069b1624dba4513c303b66b90543d97dbec20b5ba013e4f43ed9e2b88bdc5ac69701b626a8a546d03d52f8510d50df944978b0d33565ab75599b0d0a18563", + "19eb28c4ee08a66894ca5cb76e160478a4f94c061b1115357557dacd5370bfc22bd1d0faa2e9d72af11ae65cb2335c53f617052331eb56050a972da4efe55eb7"); + } else { @@ -1203,7 +1360,7 @@ main (int argc, char **argv)
if (argc < 4) { - fprintf (stderr, "Usage: %s CURVE-BITS K C [BITS-PER-LIMB]\n", argv[0]); + fprintf (stderr, "Usage: %s CURVE K C [BITS-PER-LIMB]\n", argv[0]); return EXIT_FAILURE; }
diff --git a/examples/ecc-benchmark.c b/examples/ecc-benchmark.c index ea0be17368fb..8d49c1a6f1d8 100644 --- a/examples/ecc-benchmark.c +++ b/examples/ecc-benchmark.c @@ -336,6 +336,11 @@ const struct ecc_curve * const curves[] = { &_nettle_secp_256r1, &_nettle_secp_384r1, &_nettle_secp_521r1, + &_nettle_gc_256b, + &_nettle_gc_256c, + &_nettle_gc_256d, + &_nettle_gc_512a, + &_nettle_gc_512b, };
#define numberof(x) (sizeof (x) / sizeof ((x)[0])) diff --git a/testsuite/testutils.c b/testsuite/testutils.c index 337e4c4c7cd1..dea864ac3417 100644 --- a/testsuite/testutils.c +++ b/testsuite/testutils.c @@ -1583,6 +1583,11 @@ const struct ecc_curve * const ecc_curves[] = { &_nettle_secp_384r1, &_nettle_secp_521r1, &_nettle_curve25519, + &_nettle_gc_256b, + &_nettle_gc_256c, + &_nettle_gc_256d, + &_nettle_gc_512a, + &_nettle_gc_512b, NULL };
@@ -1634,7 +1639,7 @@ void test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p) { /* For each curve, the points 2 g, 3 g and 4 g */ - static const struct ecc_ref_point ref[6][3] = { + static const struct ecc_ref_point ref[11][3] = { { { "dafebf5828783f2ad35534631588a3f629a70fb16982a888", "dd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab" }, { "76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da", @@ -1695,9 +1700,56 @@ test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p) "1267b1d177ee69aba126a18e60269ef79f16ec176724030402c3684878f5b4d4" }, { "203da8db56cff1468325d4b87a3520f91a739ec193ce1547493aa657c4c9f870", "47d0e827cb1595e1470eb88580d5716c4cf22832ea2f0ff0df38ab61ca32112f" }, + }, + { { "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd95", + "726e1b8e1f676325d820afa5bac0d489cad6b0d220dc1c4edd5336636160df83" }, + { "8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38d2c", + "76bcd1ca9a23b041d4d9baf507a6cd821267a94c838768e8486117796b788a51" }, + { "f7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e4b7", + "83ccf17ba6706d73625cc3534c7a2b9d6ec1ee6a9a7e07c10d84b388de59f741" }, + }, + { { "8000000000000000000000000000000000000000000000000000000000000c97", + "4057edbca606997f47c2e3c14d3f8f1a3aba367a72fc13048bb40728e88e8d9d" }, + { "1b9a33999d8449c3bbd8cfe49ac6355a2ee0827a6c71687c86cb7b0670efe205", + "1876d998a19da37a120e76cb42f4f5225197279b612f712171a4648fe4a3ff12" }, + { "5fa13ecfadd7ae00c2e65d0ac6cac1deda6d60e577afe90915671b08bbb9065e", + "1b3c2859166129ac6dafee570ab9d40d33fdc25c7253c72f4e3fa77223ab016a" }, + }, + { { "74ab1ac14e9ed5cda1af70308c897ebf3d91d913a7bf377833c436bf0f8aa40e", + "7d223beab738ba52a65ffbfe585d2807bfaed5ea9cd651a63a775b4182f562e3" }, + { "771e56689775fda0bbdeac54e9cd379f30391edf06f335269c48f06446cd037a", + "8430215fbee8a09c5e38bda64b50bbef41392d6afa5ced73652c83cb5221d02b" }, + { "4fe44356aded59b4b661e9da15fe79dbcb1d7346770919c5c99090e5ae4db8a6", + "24f0222027a3d2577cca5aefb5411c88f92f5f4b8febddebc71c12180640ebfd" }, + }, + { { "3b89dcfc622996ab97a5869dbff15cf51db00954f43a58a5e5f6b0470a132b2f" + "4434bbcd405d2a9516151d2a6a04f2e4375bf48de1fdb21fb982afd9d2ea137c", + "c813c4e2e2e0a8a391774c7903da7a6f14686e98e183e670ee6fb784809a3e92" + "ca209dc631d85b1c7534ed3b37fddf64d854d7e01f91f18bb3fd307591afc051" }, + { "a1ff1ab2712a267eb53935ddb5a567f84db156cc096168a1174291d5f488fba5" + "43d2840b4d2dd35d764b2f57b308907aec55cfba10544e8416e134687ccb87c3", + "3cb5c4417ec4637f30374f189bb5b984c41e3a48d7f84fbfa3819e3f333f7eb3" + "11d3af7e67c4c16eeacfac2fe94c6dd4c6366f711a4fb6c7125cd7ec518d90d6" }, + { "b7bfb80956c8670031ba191929f64e301d681634236d47a60e571a4bedc0ef25" + "7452ef78b5b98dbb3d9f3129d9349433ce2a3a35cb519c91e2d633d7b373ae16", + "3bee95e29eecc5d5ad2beba941abcbf9f1cad478df0fecf614f63aeebef77850" + "da7efdb93de8f3df80bc25eac09239c14175f5c29704ce9a3e383f1b3ec0e929" }, + }, + { { "73729fb3c0d629ae5dc9bf88ca05d518bce91e502150f5e5822fa0293bc0e3ca" + "31145f3b0e1831d8bb1f20b28780011473339e581a403c676b47c1f9ab764602", + "35d62c90549f2c17e16c6ea99d3c3dbe610f2c543fc1d0ca5bd48a5ea1d3ec11" + "c3cec5e7fcd74b5306e73b6a8e40c818714f02b25997ee2b54f65432d3f0741e" }, + { "1826b56c8dc1d5779b76354070e744f2c9c82755a921142b528f2fe04f5fd0db" + "dc178314c4546270b423d9fe819ba4c82625b02004bfdf90a08317dceb9309b7", + "4f6882f8f6422d693f8313bb7b121117ad9ee6b8874135f3e4bff91b01141fdb" + "35d29bc3cf15ab8a3b751050e58392a8eeae790ea5d198eab642dc520fd1713f" }, + { "5af069b1624dba4513c303b66b90543d97dbec20b5ba013e4f43ed9e2b88bdc5" + "ac69701b626a8a546d03d52f8510d50df944978b0d33565ab75599b0d0a18563", + "19eb28c4ee08a66894ca5cb76e160478a4f94c061b1115357557dacd5370bfc2" + "2bd1d0faa2e9d72af11ae65cb2335c53f617052331eb56050a972da4efe55eb7" }, } }; - assert (curve < 6); + assert (curve < 11); assert (n <= 4); if (n == 0) {
Signed-off-by: Dmitry Eremin-Solenikov dbaryshkov@gmail.com --- ecc-mod-arith.c | 30 ++++++++++++++++++------------ 1 file changed, 18 insertions(+), 12 deletions(-)
diff --git a/ecc-mod-arith.c b/ecc-mod-arith.c index f2e47f6747c1..571680a98dc3 100644 --- a/ecc-mod-arith.c +++ b/ecc-mod-arith.c @@ -73,10 +73,12 @@ ecc_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp, assert (b <= 0xffffffff); hi = mpn_mul_1 (rp, ap, m->size, b); hi = mpn_addmul_1 (rp, m->B, m->size, hi); - assert (hi <= 1); - hi = cnd_add_n (hi, rp, m->B, m->size); - /* Sufficient if b < B^size / p */ - assert (hi == 0); + do { + if (hi > 1) /* This is necessary for some of GOST curves */ + hi = mpn_addmul_1 (rp, m->B, m->size, hi); + else + hi = cnd_add_n (hi, rp, m->B, m->size); + } while (hi != 0); }
void @@ -88,10 +90,12 @@ ecc_mod_addmul_1 (const struct ecc_modulo *m, mp_limb_t *rp, assert (b <= 0xffffffff); hi = mpn_addmul_1 (rp, ap, m->size, b); hi = mpn_addmul_1 (rp, m->B, m->size, hi); - assert (hi <= 1); - hi = cnd_add_n (hi, rp, m->B, m->size); - /* Sufficient roughly if b < B^size / p */ - assert (hi == 0); + do { + if (hi > 1) /* This is necessary for some of GOST curves */ + hi = mpn_addmul_1 (rp, m->B, m->size, hi); + else + hi = cnd_add_n (hi, rp, m->B, m->size); + } while (hi != 0); }
void @@ -103,10 +107,12 @@ ecc_mod_submul_1 (const struct ecc_modulo *m, mp_limb_t *rp, assert (b <= 0xffffffff); hi = mpn_submul_1 (rp, ap, m->size, b); hi = mpn_submul_1 (rp, m->B, m->size, hi); - assert (hi <= 1); - hi = cnd_sub_n (hi, rp, m->B, m->size); - /* Sufficient roughly if b < B^size / p */ - assert (hi == 0); + do { + if (hi > 1) /* This is necessary for some of GOST curves */ + hi = mpn_submul_1 (rp, m->B, m->size, hi); + else + hi = cnd_sub_n (hi, rp, m->B, m->size); + } while (hi != 0); }
/* NOTE: mul and sqr needs 2*m->size limbs at rp */
Dmitry Eremin-Solenikov dbaryshkov@gmail.com writes:
Signed-off-by: Dmitry Eremin-Solenikov dbaryshkov@gmail.com
ecc-mod-arith.c | 30 ++++++++++++++++++------------ 1 file changed, 18 insertions(+), 12 deletions(-)
diff --git a/ecc-mod-arith.c b/ecc-mod-arith.c index f2e47f6747c1..571680a98dc3 100644 --- a/ecc-mod-arith.c +++ b/ecc-mod-arith.c @@ -73,10 +73,12 @@ ecc_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp, assert (b <= 0xffffffff); hi = mpn_mul_1 (rp, ap, m->size, b); hi = mpn_addmul_1 (rp, m->B, m->size, hi);
- assert (hi <= 1);
- hi = cnd_add_n (hi, rp, m->B, m->size);
- /* Sufficient if b < B^size / p */
- assert (hi == 0);
- do {
- if (hi > 1) /* This is necessary for some of GOST curves */
hi = mpn_addmul_1 (rp, m->B, m->size, hi);- else
hi = cnd_add_n (hi, rp, m->B, m->size);- } while (hi != 0);
}
Is it the condition b < B^size / p that is not valid for the GOST curves? What are the problematic values of b and p?
To keep the ecc code side-channel silent, there must be no conditional jumps depending on hi (except for asserts, since they always branch the same way in a non-crashing program). The adjustmenst can only do unconditional calls to functions like mpn_add_mul_1 and cnd_add_1.
Regards, /Niels
Hello,
сб, 11 мая 2019 г. в 11:26, Niels Möller nisse@lysator.liu.se:
Dmitry Eremin-Solenikov dbaryshkov@gmail.com writes:
Signed-off-by: Dmitry Eremin-Solenikov dbaryshkov@gmail.com
ecc-mod-arith.c | 30 ++++++++++++++++++------------ 1 file changed, 18 insertions(+), 12 deletions(-)
diff --git a/ecc-mod-arith.c b/ecc-mod-arith.c index f2e47f6747c1..571680a98dc3 100644 --- a/ecc-mod-arith.c +++ b/ecc-mod-arith.c @@ -73,10 +73,12 @@ ecc_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp, assert (b <= 0xffffffff); hi = mpn_mul_1 (rp, ap, m->size, b); hi = mpn_addmul_1 (rp, m->B, m->size, hi);
- assert (hi <= 1);
- hi = cnd_add_n (hi, rp, m->B, m->size);
- /* Sufficient if b < B^size / p */
- assert (hi == 0);
- do {
- if (hi > 1) /* This is necessary for some of GOST curves */
hi = mpn_addmul_1 (rp, m->B, m->size, hi);- else
hi = cnd_add_n (hi, rp, m->B, m->size);- } while (hi != 0);
}
Is it the condition b < B^size / p that is not valid for the GOST curves? What are the problematic values of b and p?
I did not try debugging maths part of this issue. Basically you can apply first two patches and then observe asserts failing when running ecc-benchmark example. Problematic module looks like 80000.......something. Bmodp then looks like 7fffffff.....something.
Any help at this point is appreciated.
To keep the ecc code side-channel silent, there must be no conditional jumps depending on hi (except for asserts, since they always branch the same way in a non-crashing program). The adjustmenst can only do unconditional calls to functions like mpn_add_mul_1 and cnd_add_1.
Yes, thus I've tried adding a loop which should nearly always terminate with just single compare after cnd_add_1.
Dmitry Eremin-Solenikov dbaryshkov@gmail.com writes:
Is it the condition b < B^size / p that is not valid for the GOST curves? What are the problematic values of b and p?
I did not try debugging maths part of this issue. Basically you can apply first two patches and then observe asserts failing when running ecc-benchmark example. Problematic module looks like 80000.......something. Bmodp then looks like 7fffffff.....something.
Any help at this point is appreciated.
If p is close to B^size / 2, then I think a reduction like
r <-- r - 2 * hi * p
will get you close. I.e.,
hi -= mpn_submul_1(..., 2*hi)
should almost cancel the most significant limb. After this, the common case is hi == 0, with possible error case being hi == -1 if p starts with 8000..., or hi == +1 if p starts with 7ffff...
It might be useful to precompute |2p - B^size|.
For the larger reductions, does p have form suitable for redc, ending with ...00001 of ...fffff? Current non-redc reduction code probably won't support p close to B^size / 2.
To keep the ecc code side-channel silent, there must be no conditional jumps depending on hi (except for asserts, since they always branch the same way in a non-crashing program). The adjustmenst can only do unconditional calls to functions like mpn_add_mul_1 and cnd_add_1.
Yes, thus I've tried adding a loop which should nearly always terminate with just single compare after cnd_add_1.
Unfortunately, "nearly always" isn't enough; it means that some inputs will result in a value of hi making the code branch differently, and that information then leaks through cache and/or timing. If it's likely to be exploitable, I can't say, but current ecc code is written to avoid that risk.
Regards, /Niels
сб, 11 мая 2019 г. в 12:53, Niels Möller nisse@lysator.liu.se:
Dmitry Eremin-Solenikov dbaryshkov@gmail.com writes:
Is it the condition b < B^size / p that is not valid for the GOST curves? What are the problematic values of b and p?
I did not try debugging maths part of this issue. Basically you can apply first two patches and then observe asserts failing when running ecc-benchmark example. Problematic module looks like 80000.......something. Bmodp then looks like 7fffffff.....something.
Any help at this point is appreciated.
If p is close to B^size / 2, then I think a reduction like
Yes, it is.
As an overflow happens in low level code, do you suggest duplicating ecc-dup-jj/ecc-add-jja/ecc-add-jjj for GOST curves?
r <-- r - 2 * hi * p
will get you close. I.e.,
hi -= mpn_submul_1(..., 2*hi)
should almost cancel the most significant limb. After this, the common case is hi == 0, with possible error case being hi == -1 if p starts with 8000..., or hi == +1 if p starts with 7ffff...
It might be useful to precompute |2p - B^size|.
For the larger reductions, does p have form suitable for redc, ending with ...00001 of ...fffff?
No, it does not. p is 80.....0c99 for 256-bit curve and 800...06f for 512-bit curve. Another problem might be another 256-bit curve, where p is semi-random (9b9f605f5a858107ab1ec85e6b41c8aacf846e86789051d37998f7b9022d759b).
Current non-redc reduction code probably won't support p close to B^size / 2.
To keep the ecc code side-channel silent, there must be no conditional jumps depending on hi (except for asserts, since they always branch the same way in a non-crashing program). The adjustmenst can only do unconditional calls to functions like mpn_add_mul_1 and cnd_add_1.
Yes, thus I've tried adding a loop which should nearly always terminate with just single compare after cnd_add_1.
Unfortunately, "nearly always" isn't enough; it means that some inputs will result in a value of hi making the code branch differently, and that information then leaks through cache and/or timing. If it's likely to be exploitable, I can't say, but current ecc code is written to avoid that risk.
Dmitry Eremin-Solenikov dbaryshkov@gmail.com writes:
If p is close to B^size / 2, then I think a reduction like
Yes, it is.
As an overflow happens in low level code, do you suggest duplicating ecc-dup-jj/ecc-add-jja/ecc-add-jjj for GOST curves?
I'd prefer not to duplicate the point functions. Could consider doing these operations (or part of them) using indirection via some new function pointer in struct ecc_modulo.
Regards, /Niels
сб, 11 мая 2019 г. в 21:55, Niels Möller nisse@lysator.liu.se:
Dmitry Eremin-Solenikov dbaryshkov@gmail.com writes:
If p is close to B^size / 2, then I think a reduction like
Yes, it is.
As an overflow happens in low level code, do you suggest duplicating ecc-dup-jj/ecc-add-jja/ecc-add-jjj for GOST curves?
I'd prefer not to duplicate the point functions. Could consider doing these operations (or part of them) using indirection via some new function pointer in struct ecc_modulo.
This patch makes things work for me. Does it stand a chance to be applied? I'll run GnuTLS tests against it later. For now I'm running ecc-mul-a-test and ecc-mul-g-test in a loop without any errors.
diff --git a/ecc-mod-arith.c b/ecc-mod-arith.c index f2e47f6747c1..a70ee1228c78 100644 --- a/ecc-mod-arith.c +++ b/ecc-mod-arith.c @@ -103,8 +103,10 @@ ecc_mod_submul_1 (const struct ecc_modulo *m, mp_limb_t *rp, assert (b <= 0xffffffff); hi = mpn_submul_1 (rp, ap, m->size, b); hi = mpn_submul_1 (rp, m->B, m->size, hi); + hi = mpn_submul_1 (rp, m->B, m->size, hi); assert (hi <= 1); hi = cnd_sub_n (hi, rp, m->B, m->size); + hi = cnd_sub_n (hi, rp, m->B, m->size); /* Sufficient roughly if b < B^size / p */ assert (hi == 0); }
Regards, /Niels
-- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance.
Dmitry Eremin-Solenikov dbaryshkov@gmail.com writes:
This patch makes things work for me.
Is it only ecc_mod_submul_1 that you need to change? It's used via the ecc_modp_submul_1 macro.
Does it stand a chance to be applied?
To accept the patch, I'd like to understand the mathematics and document what's required of the modulo to make it correct. And I'd also like to know if there's any measurable slowdown in examples/hogweed-benchmark or ecc-benchmark for the other curves.
For now I'm running ecc-mul-a-test and ecc-mul-g-test in a loop without any errors.
To make running in a loop useful, you need to add random seeding, see ecc-mod-test.c for an example to how to do it, enabled by the NETTLE_TEST_SEED environment variable. Used like
while NETTLE_TEST_SEED=0 ./testsuite/ecc-mod-test ; do : ; done
Regards, /Niels
Hi,
For now I'm running ecc-mul-a-test and ecc-mul-g-test in a loop without any errors.
To make running in a loop useful, you need to add random seeding, see ecc-mod-test.c for an example to how to do it, enabled by the NETTLE_TEST_SEED environment variable. Used like
while NETTLE_TEST_SEED=0 ./testsuite/ecc-mod-test ; do : ; done
I see that NETTLE_TEST_SEED is used only in ecc-mod-test (and rsa-compute-root-test). Other tests do gmp_rrandomb/urandomb unconditionally.
Regards, /Niels
-- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance.
nettle-bugs@lists.lysator.liu.se
-
Dmitry Eremin-Solenikov -
nisse＠lysator.liu.se