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) {