From: Dmitry Eremin-Solenikov dbaryshkov@gmail.com
GOST curves will require different "fixups" for fast (mul X mod p) operations. Move these operations to ecc_modulo structure and call them via function pointer.
Signed-off-by: Dmitry Eremin-Solenikov dbaryshkov@gmail.com --- ecc-curve25519.c | 8 ++++++++ ecc-curve448.c | 8 ++++++++ ecc-internal.h | 32 ++++++++++++++++++++------------ ecc-mod-arith.c | 12 ++++++------ ecc-mul-m.c | 6 +++--- ecc-secp192r1.c | 8 ++++++++ ecc-secp224r1.c | 8 ++++++++ ecc-secp256r1.c | 8 ++++++++ ecc-secp384r1.c | 8 ++++++++ ecc-secp521r1.c | 8 ++++++++ 10 files changed, 85 insertions(+), 21 deletions(-)
diff --git a/ecc-curve25519.c b/ecc-curve25519.c index 0ad3017c9ebc..4ee80c8d4463 100644 --- a/ecc-curve25519.c +++ b/ecc-curve25519.c @@ -310,6 +310,10 @@ const struct ecc_curve _nettle_curve25519 = ecc_curve25519_modp, ecc_curve25519_inv, ecc_curve25519_sqrt, + + ecc_mod_mul_1_std, + ecc_mod_addmul_1_std, + ecc_mod_submul_1_std, }, { 253, @@ -329,6 +333,10 @@ const struct ecc_curve _nettle_curve25519 = ecc_curve25519_modq, ecc_mod_inv, NULL, + + NULL, + NULL, + NULL, },
0, /* No redc */ diff --git a/ecc-curve448.c b/ecc-curve448.c index c31a0eb26ba4..71634b855af8 100644 --- a/ecc-curve448.c +++ b/ecc-curve448.c @@ -288,6 +288,10 @@ const struct ecc_curve _nettle_curve448 = ecc_curve448_modp, ecc_curve448_inv, ecc_curve448_sqrt, + + ecc_mod_mul_1_std, + ecc_mod_addmul_1_std, + ecc_mod_submul_1_std, }, { 446, @@ -307,6 +311,10 @@ const struct ecc_curve _nettle_curve448 = ecc_mod, /* FIXME: Implement optimized reduce function */ ecc_mod_inv, NULL, + + NULL, + NULL, + NULL, },
0, /* No redc */ diff --git a/ecc-internal.h b/ecc-internal.h index c918632df292..105b67b2990e 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -44,9 +44,9 @@ #define ecc_pm1_redc _nettle_ecc_pm1_redc #define ecc_mod_add _nettle_ecc_mod_add #define ecc_mod_sub _nettle_ecc_mod_sub -#define ecc_mod_mul_1 _nettle_ecc_mod_mul_1 -#define ecc_mod_addmul_1 _nettle_ecc_mod_addmul_1 -#define ecc_mod_submul_1 _nettle_ecc_mod_submul_1 +#define ecc_mod_mul_1_std _nettle_ecc_mod_mul_1_std +#define ecc_mod_addmul_1_std _nettle_ecc_mod_addmul_1_std +#define ecc_mod_submul_1_std _nettle_ecc_mod_submul_1_std #define ecc_mod_mul _nettle_ecc_mod_mul #define ecc_mod_sqr _nettle_ecc_mod_sqr #define ecc_mod_random _nettle_ecc_mod_random @@ -141,6 +141,10 @@ typedef void ecc_h_to_a_func (const struct ecc_curve *ecc, mp_limb_t *r, const mp_limb_t *p, mp_limb_t *scratch);
+typedef void ecc_mod_mul_1_func (const struct ecc_modulo *m, + mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b); + struct ecc_modulo { unsigned short bit_size; @@ -165,6 +169,10 @@ struct ecc_modulo ecc_mod_func *reduce; ecc_mod_inv_func *invert; ecc_mod_sqrt_func *sqrt; + + ecc_mod_mul_1_func *mul_1; + ecc_mod_mul_1_func *addmul_1; + ecc_mod_mul_1_func *submul_1; };
/* Represents an elliptic curve of the form @@ -235,15 +243,15 @@ ecc_mod_sub (const struct ecc_modulo *m, mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *bp);
void -ecc_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp, - const mp_limb_t *ap, const mp_limb_t b); +ecc_mod_mul_1_std (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, const mp_limb_t b);
void -ecc_mod_addmul_1 (const struct ecc_modulo *m, mp_limb_t *rp, - const mp_limb_t *ap, mp_limb_t b); +ecc_mod_addmul_1_std (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b); void -ecc_mod_submul_1 (const struct ecc_modulo *m, mp_limb_t *rp, - const mp_limb_t *ap, mp_limb_t b); +ecc_mod_submul_1_std (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b);
/* The mul and sqr functions need 2*m->size limbs at rp */ void @@ -259,11 +267,11 @@ ecc_mod_sqr (const struct ecc_modulo *m, mp_limb_t *rp, #define ecc_modp_sub(ecc, r, a, b) \ ecc_mod_sub (&(ecc)->p, (r), (a), (b)) #define ecc_modp_mul_1(ecc, r, a, b) \ - ecc_mod_mul_1 (&(ecc)->p, (r), (a), (b)) + (ecc)->p.mul_1 (&(ecc)->p, (r), (a), (b)) #define ecc_modp_addmul_1(ecc, r, a, b) \ - ecc_mod_addmul_1 (&(ecc)->p, (r), (a), (b)) + (ecc)->p.addmul_1 (&(ecc)->p, (r), (a), (b)) #define ecc_modp_submul_1(ecc, r, a, b) \ - ecc_mod_submul_1 (&(ecc)->p, (r), (a), (b)) + (ecc)->p.submul_1 (&(ecc)->p, (r), (a), (b)) #define ecc_modp_mul(ecc, r, a, b) \ ecc_mod_mul (&(ecc)->p, (r), (a), (b)) #define ecc_modp_sqr(ecc, r, a) \ diff --git a/ecc-mod-arith.c b/ecc-mod-arith.c index f2e47f6747c1..0399a2cdd7c5 100644 --- a/ecc-mod-arith.c +++ b/ecc-mod-arith.c @@ -65,8 +65,8 @@ ecc_mod_sub (const struct ecc_modulo *m, mp_limb_t *rp, }
void -ecc_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp, - const mp_limb_t *ap, mp_limb_t b) +ecc_mod_mul_1_std (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b) { mp_limb_t hi;
@@ -80,8 +80,8 @@ ecc_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp, }
void -ecc_mod_addmul_1 (const struct ecc_modulo *m, mp_limb_t *rp, - const mp_limb_t *ap, mp_limb_t b) +ecc_mod_addmul_1_std (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b) { mp_limb_t hi;
@@ -95,8 +95,8 @@ ecc_mod_addmul_1 (const struct ecc_modulo *m, mp_limb_t *rp, }
void -ecc_mod_submul_1 (const struct ecc_modulo *m, mp_limb_t *rp, - const mp_limb_t *ap, mp_limb_t b) +ecc_mod_submul_1_std (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b) { mp_limb_t hi;
diff --git a/ecc-mul-m.c b/ecc-mul-m.c index 68bdd16e8e94..770350162da1 100644 --- a/ecc-mul-m.c +++ b/ecc-mul-m.c @@ -80,7 +80,7 @@ ecc_mul_m (const struct ecc_modulo *m, ecc_mod_sqr (m, BB, B); ecc_mod_mul (m, x3, AA, BB); ecc_mod_sub (m, E, AA, BB); - ecc_mod_addmul_1 (m, AA, E, a24); + m->addmul_1 (m, AA, E, a24); ecc_mod_mul (m, z3, E, AA);
for (i = bit_high; i >= bit_low; i--) @@ -98,7 +98,7 @@ ecc_mul_m (const struct ecc_modulo *m, ecc_mod_sqr (m, BB, B); ecc_mod_mul (m, x2, AA, BB); /* Last use of BB */ ecc_mod_sub (m, E, AA, BB); - ecc_mod_addmul_1 (m, AA, E, a24); + m->addmul_1 (m, AA, E, a24); ecc_mod_add (m, C, x3, z3); ecc_mod_sub (m, D, x3, z3); ecc_mod_mul (m, z2, E, AA); /* Last use of E and AA */ @@ -124,7 +124,7 @@ ecc_mul_m (const struct ecc_modulo *m, ecc_mod_sqr (m, BB, B); ecc_mod_mul (m, x2, AA, BB); ecc_mod_sub (m, E, AA, BB); - ecc_mod_addmul_1 (m, AA, E, a24); + m->addmul_1 (m, AA, E, a24); ecc_mod_mul (m, z2, E, AA); } assert (m->invert_itch <= 7 * m->size); diff --git a/ecc-secp192r1.c b/ecc-secp192r1.c index 094074d73ed7..d36be63d7b3a 100644 --- a/ecc-secp192r1.c +++ b/ecc-secp192r1.c @@ -130,6 +130,10 @@ const struct ecc_curve _nettle_secp_192r1 = ecc_secp192r1_modp, ecc_mod_inv, NULL, + + ecc_mod_mul_1_std, + ecc_mod_addmul_1_std, + ecc_mod_submul_1_std, }, { 192, @@ -149,6 +153,10 @@ const struct ecc_curve _nettle_secp_192r1 = ecc_mod, ecc_mod_inv, NULL, + + NULL, + NULL, + NULL, },
USE_REDC, diff --git a/ecc-secp224r1.c b/ecc-secp224r1.c index e6b43fa61f42..cde02a01fd6d 100644 --- a/ecc-secp224r1.c +++ b/ecc-secp224r1.c @@ -82,6 +82,10 @@ const struct ecc_curve _nettle_secp_224r1 = USE_REDC ? ecc_secp224r1_redc : ecc_secp224r1_modp, ecc_mod_inv, NULL, + + ecc_mod_mul_1_std, + ecc_mod_addmul_1_std, + ecc_mod_submul_1_std, }, { 224, @@ -101,6 +105,10 @@ const struct ecc_curve _nettle_secp_224r1 = ecc_mod, ecc_mod_inv, NULL, + + NULL, + NULL, + NULL, },
USE_REDC, diff --git a/ecc-secp256r1.c b/ecc-secp256r1.c index 6c776a729aea..e17061ab761c 100644 --- a/ecc-secp256r1.c +++ b/ecc-secp256r1.c @@ -259,6 +259,10 @@ const struct ecc_curve _nettle_secp_256r1 = USE_REDC ? ecc_secp256r1_redc : ecc_secp256r1_modp, ecc_mod_inv, NULL, + + ecc_mod_mul_1_std, + ecc_mod_addmul_1_std, + ecc_mod_submul_1_std, }, { 256, @@ -278,6 +282,10 @@ const struct ecc_curve _nettle_secp_256r1 = ecc_secp256r1_modq, ecc_mod_inv, NULL, + + NULL, + NULL, + NULL, },
USE_REDC, diff --git a/ecc-secp384r1.c b/ecc-secp384r1.c index c4a75564bf58..cf0cd25e32fb 100644 --- a/ecc-secp384r1.c +++ b/ecc-secp384r1.c @@ -167,6 +167,10 @@ const struct ecc_curve _nettle_secp_384r1 = ecc_secp384r1_modp, ecc_mod_inv, NULL, + + ecc_mod_mul_1_std, + ecc_mod_addmul_1_std, + ecc_mod_submul_1_std, }, { 384, @@ -186,6 +190,10 @@ const struct ecc_curve _nettle_secp_384r1 = ecc_mod, ecc_mod_inv, NULL, + + NULL, + NULL, + NULL, },
USE_REDC, diff --git a/ecc-secp521r1.c b/ecc-secp521r1.c index 74688008959b..2241e542f927 100644 --- a/ecc-secp521r1.c +++ b/ecc-secp521r1.c @@ -95,6 +95,10 @@ const struct ecc_curve _nettle_secp_521r1 = ecc_secp521r1_modp, ecc_mod_inv, NULL, + + ecc_mod_mul_1_std, + ecc_mod_addmul_1_std, + ecc_mod_submul_1_std, }, { 521, @@ -114,6 +118,10 @@ const struct ecc_curve _nettle_secp_521r1 = ecc_mod, ecc_mod_inv, NULL, + + NULL, + NULL, + NULL, },
USE_REDC,
From: Dmitry Eremin-Solenikov dbaryshkov@gmail.com
Add three 256-bit curves from RFC 4357 (Section 11.4) and two 512-bit curves from RFC 7836 (Section A.1).
Curves are named accrording to the "TLS Supported Groups" registry.
Signed-off-by: Dmitry Eremin-Solenikov dbaryshkov@gmail.com --- .gitignore | 5 + Makefile.in | 49 +++++++++ ecc-curve.h | 5 + ecc-gc256b.c | 148 +++++++++++++++++++++++++++ ecc-gc256c.c | 210 +++++++++++++++++++++++++++++++++++++++ ecc-gc256d.c | 184 ++++++++++++++++++++++++++++++++++ ecc-gc512a.c | 148 +++++++++++++++++++++++++++ ecc-gc512b.c | 204 +++++++++++++++++++++++++++++++++++++ ecc-internal.h | 7 ++ eccdata.c | 174 +++++++++++++++++++++++++++++++- examples/ecc-benchmark.c | 5 + testsuite/testutils.c | 56 ++++++++++- 12 files changed, 1192 insertions(+), 3 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 ea264107fa40..a0642b1b6c2f 100644 --- a/.gitignore +++ b/.gitignore @@ -45,6 +45,11 @@ core /rotors.h /ecc-curve25519.h /ecc-curve448.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 38160bb40fe1..d9b76d8d5354 100644 --- a/Makefile.in +++ b/Makefile.in @@ -176,6 +176,8 @@ hogweed_SOURCES = sexp.c sexp-format.c \ ecc-mod.c ecc-mod-inv.c \ ecc-mod-arith.c ecc-pp1-redc.c ecc-pm1-redc.c \ ecc-curve25519.c ecc-curve448.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 \ @@ -396,12 +398,57 @@ ecc-curve25519.h: eccdata.stamp ecc-curve448.h: eccdata.stamp ./eccdata$(EXEEXT_FOR_BUILD) curve448 38 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-curve448.$(OBJEXT): ecc-curve448.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 @@ -660,6 +707,8 @@ distcheck: dist clean-here: -rm -f $(TARGETS) *.$(OBJEXT) *.s *.so *.dll *.a \ ecc-curve25519.h ecc-curve448.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) \ diff --git a/ecc-curve.h b/ecc-curve.h index 76024a19d24f..6a53506ea815 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_gc256b(void); +const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_gc256c(void); +const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_gc256d(void); +const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_gc512a(void); +const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_gc512b(void);
#ifdef __cplusplus } diff --git a/ecc-gc256b.c b/ecc-gc256b.c new file mode 100644 index 000000000000..9fa818d8c330 --- /dev/null +++ b/ecc-gc256b.c @@ -0,0 +1,148 @@ +/* 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_gc256b_redc ecc_pp1_redc +#elif ECC_REDC_SIZE == 0 +# define ecc_gc256b_redc NULL +#else +# error Configuration error +#endif + +static void +ecc_gc256b_modp (const struct ecc_modulo *m, mp_limb_t *rp) +{ + mp_size_t mn = m->size; + mp_limb_t hi; + + hi = mpn_addmul_1(rp, rp + mn, mn, 0x269); + hi = sec_add_1 (rp, rp, mn, hi * 0x269); + hi = sec_add_1 (rp, rp, mn, hi * 0x269); + assert(hi == 0); +} + +#define ecc_gc256b_modp ecc_gc256b_modp +#define ecc_gc256b_modq ecc_mod + +const struct ecc_curve _nettle_gc256b = +{ + { + 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_gc256b_modp, + USE_REDC ? ecc_gc256b_redc : ecc_gc256b_modp, + ecc_mod_inv, + NULL, + + ecc_mod_mul_1_std, + ecc_mod_addmul_1_std, + ecc_mod_submul_1_std, + }, + { + 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_gc256b_modq, + ecc_gc256b_modq, + ecc_mod_inv, + NULL, + + NULL, + NULL, + NULL, + }, + + USE_REDC, + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + + ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE), + ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_DUP_JJ_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_jja, + ecc_add_jjj, + ecc_dup_jj, + ecc_mul_a, + ecc_mul_g, + ecc_j_to_a, + + ecc_b, + ecc_g, + ecc_unit, + ecc_table +}; + +const struct ecc_curve *nettle_get_gc256b(void) +{ + return &_nettle_gc256b; +} diff --git a/ecc-gc256c.c b/ecc-gc256c.c new file mode 100644 index 000000000000..9feacd32bfa2 --- /dev/null +++ b/ecc-gc256c.c @@ -0,0 +1,210 @@ +/* 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_gc256c_redc +# define ecc_gc256c_redc nettle_ecc_gc256c_redc +void +ecc_gc256c_redc (const struct ecc_modulo *p, mp_limb_t *rp); +#else /* !HAVE_NATIVE_ecc_gc256c_redc */ +# if ECC_REDC_SIZE > 0 +# define ecc_gc256c_redc ecc_pp1_redc +# elif ECC_REDC_SIZE == 0 +# define ecc_gc256c_redc NULL +# else +# error Configuration error +# endif +#endif /* !HAVE_NATIVE_ecc_gc256c_redc */ + +static void +ecc_gc256c_modp (const struct ecc_modulo *m, mp_limb_t *rp) +{ + mp_size_t mn = m->size; + mp_limb_t hi; + + hi = mpn_submul_1(rp, rp + mn, mn, 0xc99 * 2); + hi = sec_add_1 (rp, rp, mn, hi * 0xc99 * 2); + hi = sec_sub_1 (rp, rp, mn, hi * 0xc99 * 2); + assert(hi <= 1); + hi = cnd_sub_n (hi, rp, m->B, mn); + assert(hi == 0); +} + +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); +} + +static void +ecc_gc256c_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b) +{ + mp_limb_t hi; + + assert (b <= 0xffffffff); + hi = mpn_mul_1 (rp, ap, m->size, b); + hi = mpn_sub_1 (rp, rp, m->size, hi * 0xc99 * 2); + assert(hi <= 1); + hi = cnd_add_n (hi, rp, m->B, m->size); + assert(hi == 0); +} + +static void +ecc_gc256c_mod_addmul_1 (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b) +{ + mp_limb_t hi; + + assert (b <= 0xffffffff); + hi = mpn_addmul_1 (rp, ap, m->size, b); + hi = mpn_sub_1 (rp, rp, m->size, hi * 0xc99 * 2); + assert(hi <= 1); + hi = cnd_add_n (hi, rp, m->B, m->size); + assert(hi == 0); +} + +static void +ecc_gc256c_mod_submul_1 (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b) +{ + mp_limb_t hi; + + assert (b <= 0xffffffff); + hi = mpn_submul_1 (rp, ap, m->size, b); + hi = mpn_add_1 (rp, rp, m->size, hi * 0xc99 * 2); + assert(hi <= 1); + hi = cnd_sub_n (hi, rp, m->B, m->size); + assert(hi == 0); +} + +#define ecc_gc256c_modp ecc_gc256c_modp +#define ecc_gc256c_modq ecc_gost256_mod + +const struct ecc_curve _nettle_gc256c = +{ + { + 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_gc256c_modp, + USE_REDC ? ecc_gc256c_redc : ecc_gc256c_modp, + ecc_mod_inv, + NULL, + + ecc_gc256c_mod_mul_1, + ecc_gc256c_mod_addmul_1, + ecc_gc256c_mod_submul_1, + }, + { + 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_gc256c_modq, + ecc_gc256c_modq, + ecc_mod_inv, + NULL, + + NULL, + NULL, + NULL, + }, + + USE_REDC, + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + + ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE), + ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_DUP_JJ_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_jja, + ecc_add_jjj, + ecc_dup_jj, + ecc_mul_a, + ecc_mul_g, + ecc_j_to_a, + + ecc_b, + ecc_g, + ecc_unit, + ecc_table +}; + +const struct ecc_curve *nettle_get_gc256c(void) +{ + return &_nettle_gc256c; +} diff --git a/ecc-gc256d.c b/ecc-gc256d.c new file mode 100644 index 000000000000..19971f2bda2a --- /dev/null +++ b/ecc-gc256d.c @@ -0,0 +1,184 @@ +/* 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_gc256d_redc ecc_pp1_redc +#elif ECC_REDC_SIZE == 0 +# define ecc_gc256d_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); +} + +static void +ecc_gc256d_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b) +{ + mp_limb_t hi; + + assert (b <= 0xffffffff); + hi = mpn_mul_1 (rp, ap, m->size, b); + while (hi != 0) + hi = mpn_addmul_1 (rp, m->B, m->size, hi); +} + +static void +ecc_gc256d_mod_addmul_1 (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b) +{ + mp_limb_t hi; + + assert (b <= 0xffffffff); + hi = mpn_addmul_1 (rp, ap, m->size, b); + while (hi != 0) + hi = mpn_addmul_1 (rp, m->B, m->size, hi); +} + +static void +ecc_gc256d_mod_submul_1 (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b) +{ + mp_limb_t hi; + + assert (b <= 0xffffffff); + hi = mpn_submul_1 (rp, ap, m->size, b); + while (hi != 0) + hi = mpn_submul_1 (rp, m->B, m->size, hi); +} + +#define ecc_gc256d_modp ecc_gost256_mod +#define ecc_gc256d_modq ecc_gost256_mod + +const struct ecc_curve _nettle_gc256d = +{ + { + 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_gc256d_modp, + USE_REDC ? ecc_gc256d_redc : ecc_gc256d_modp, + ecc_mod_inv, + NULL, + + ecc_gc256d_mod_mul_1, + ecc_gc256d_mod_addmul_1, + ecc_gc256d_mod_submul_1, + }, + { + 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_gc256d_modq, + ecc_gc256d_modq, + ecc_mod_inv, + NULL, + + NULL, + NULL, + NULL, + }, + + USE_REDC, + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + + ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE), + ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_DUP_JJ_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_jja, + ecc_add_jjj, + ecc_dup_jj, + ecc_mul_a, + ecc_mul_g, + ecc_j_to_a, + + ecc_b, + ecc_g, + ecc_unit, + ecc_table +}; + +const struct ecc_curve *nettle_get_gc256d(void) +{ + return &_nettle_gc256d; +} diff --git a/ecc-gc512a.c b/ecc-gc512a.c new file mode 100644 index 000000000000..1e814236b57b --- /dev/null +++ b/ecc-gc512a.c @@ -0,0 +1,148 @@ +/* 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_gc512a_redc ecc_pp1_redc +#elif ECC_REDC_SIZE == 0 +# define ecc_gc512a_redc NULL +#else +# error Configuration error +#endif + +static void +ecc_gc512a_modp (const struct ecc_modulo *m, mp_limb_t *rp) +{ + mp_size_t mn = m->size; + mp_limb_t hi; + + hi = mpn_addmul_1(rp, rp + mn, mn, 0x239); + hi = sec_add_1 (rp, rp, mn, hi * 0x239); + hi = sec_add_1 (rp, rp, mn, hi * 0x239); + assert(hi == 0); +} + +#define ecc_gc512a_modp ecc_gc512a_modp +#define ecc_gc512a_modq ecc_mod + +const struct ecc_curve _nettle_gc512a = +{ + { + 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_gc512a_modp, + USE_REDC ? ecc_gc512a_redc : ecc_gc512a_modp, + ecc_mod_inv, + NULL, + + ecc_mod_mul_1_std, + ecc_mod_addmul_1_std, + ecc_mod_submul_1_std, + }, + { + 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_gc512a_modq, + ecc_gc512a_modq, + ecc_mod_inv, + NULL, + + NULL, + NULL, + NULL, + }, + + USE_REDC, + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + + ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE), + ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_DUP_JJ_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_jja, + ecc_add_jjj, + ecc_dup_jj, + ecc_mul_a, + ecc_mul_g, + ecc_j_to_a, + + ecc_b, + ecc_g, + ecc_unit, + ecc_table +}; + +const struct ecc_curve *nettle_get_gc512a(void) +{ + return &_nettle_gc512a; +} diff --git a/ecc-gc512b.c b/ecc-gc512b.c new file mode 100644 index 000000000000..ac2064dde1f3 --- /dev/null +++ b/ecc-gc512b.c @@ -0,0 +1,204 @@ +/* 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_gc512b_redc ecc_pp1_redc +#elif ECC_REDC_SIZE == 0 +# define ecc_gc512b_redc NULL +#else +# error Configuration error +#endif + +static void +ecc_gc512b_modp (const struct ecc_modulo *m, mp_limb_t *rp) +{ + mp_size_t mn = m->size; + mp_limb_t hi; + + hi = mpn_submul_1(rp, rp + mn, mn, 0x6f * 2); + hi = sec_add_1 (rp, rp, mn, hi * 0x6f * 2); + hi = sec_sub_1 (rp, rp, mn, hi * 0x6f * 2); + assert(hi <= 1); + hi = cnd_sub_n (hi, rp, m->B, mn); + assert(hi == 0); +} + +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); +} + +static void +ecc_gc512b_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b) +{ + mp_limb_t hi; + + assert (b <= 0xffffffff); + hi = mpn_mul_1 (rp, ap, m->size, b); + hi = mpn_sub_1 (rp, rp, m->size, hi * 0x6f * 2); + assert(hi <= 1); + hi = cnd_add_n (hi, rp, m->B, m->size); + assert(hi == 0); +} + +static void +ecc_gc512b_mod_addmul_1 (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b) +{ + mp_limb_t hi; + + assert (b <= 0xffffffff); + hi = mpn_addmul_1 (rp, ap, m->size, b); + hi = mpn_sub_1 (rp, rp, m->size, hi * 0x6f * 2); + assert(hi <= 1); + hi = cnd_add_n (hi, rp, m->B, m->size); + assert(hi == 0); +} + +static void +ecc_gc512b_mod_submul_1 (const struct ecc_modulo *m, mp_limb_t *rp, + const mp_limb_t *ap, mp_limb_t b) +{ + mp_limb_t hi; + + assert (b <= 0xffffffff); + hi = mpn_submul_1 (rp, ap, m->size, b); + hi = mpn_add_1 (rp, rp, m->size, hi * 0x6f * 2); + assert(hi <= 1); + hi = cnd_sub_n (hi, rp, m->B, m->size); + assert(hi == 0); +} + +#define ecc_gc512b_modp ecc_gc512b_modp +#define ecc_gc512b_modq ecc_gc512_mod + +const struct ecc_curve _nettle_gc512b = +{ + { + 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_gc512b_modp, + USE_REDC ? ecc_gc512b_redc : ecc_gc512b_modp, + ecc_mod_inv, + NULL, + + ecc_gc512b_mod_mul_1, + ecc_gc512b_mod_addmul_1, + ecc_gc512b_mod_submul_1, + }, + { + 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_gc512b_modq, + ecc_gc512b_modq, + ecc_mod_inv, + NULL, + + NULL, + NULL, + NULL, + }, + + USE_REDC, + ECC_PIPPENGER_K, + ECC_PIPPENGER_C, + + ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE), + ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), + ECC_DUP_JJ_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_jja, + ecc_add_jjj, + ecc_dup_jj, + ecc_mul_a, + ecc_mul_g, + ecc_j_to_a, + + ecc_b, + ecc_g, + ecc_unit, + ecc_table +}; + +const struct ecc_curve *nettle_get_gc512b(void) +{ + return &_nettle_gc512b; +} diff --git a/ecc-internal.h b/ecc-internal.h index 105b67b2990e..99e711a5b38d 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -91,6 +91,13 @@ extern const struct ecc_curve _nettle_secp_521r1; extern const struct ecc_curve _nettle_curve25519; extern const struct ecc_curve _nettle_curve448;
+/* GOST curves, visible with underscore prefix for now */ +extern const struct ecc_curve _nettle_gc256b; +extern const struct ecc_curve _nettle_gc256c; +extern const struct ecc_curve _nettle_gc256d; +extern const struct ecc_curve _nettle_gc512a; +extern const struct ecc_curve _nettle_gc512b; + #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 d76a42bcde6f..6facbace8698 100644 --- a/eccdata.c +++ b/eccdata.c @@ -673,6 +673,178 @@ ecc_curve_init (struct ecc_curve *ecc, const char *curve) "1a739ec193ce1547493aa657c4c9f870", "47d0e827cb1595e1470eb88580d5716c" "4cf22832ea2f0ff0df38ab61ca32112f"); + + } + else if (!strcmp (curve, "gc256b")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "ffffffffffffffffffffffffffffffff" + "fffffffffffffffffffffffffffffd97", + + "00000000000000000000000000000000" + "000000000000000000000000000000a6", + + "ffffffffffffffffffffffffffffffff" + "6c611070995ad10045841b09b761b893", + + "00000000000000000000000000000000" + "00000000000000000000000000000001", + + "8d91e471e0989cda27df505a453f2b76" + "35294f2ddf23e3b122acc99c9e9f1e14"); + + 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"); + + 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"); + 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, + "ffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffff" + "fffffffffffffffffffffffffffffdc7", + "e8c2505dedfc86ddc1bd0b2b6667f1da" + "34b82574761cb0e879bd081cfd0b6265" + "ee3cb090f30d27614cb4574010da90dd" + "862ef9d4ebee4761503190785a71c760", + "ffffffffffffffffffffffffffffffff" + "ffffffffffffffffffffffffffffffff" + "27e69532f48d89116ff22b8d4e056060" + "9b4b38abfad2b85dcacdb1411f10b275", + "00000000000000000000000000000000" + "00000000000000000000000000000000" + "00000000000000000000000000000000" + "00000000000000000000000000000003", + "7503cfe87a836ae3a61b8816e25450e6" + "ce5e1c93acf1abc1778064fdcbefa921" + "df1626be4fd036e93d75e6a50e3a41e9" + "8028fe5fc235f5b889a589cb5215f2a4"); + + 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, + "80000000000000000000000000000000" + "00000000000000000000000000000000" + "00000000000000000000000000000000" + "0000000000000000000000000000006f", + "687d1b459dc841457e3e06cf6f5e2517" + "b97c7d614af138bcbf85dc806c4b289f" + "3e965d2db1416d217f8b276fad1ab69c" + "50f78bee1fa3106efb8ccbc7c5140116", + "80000000000000000000000000000000" + "00000000000000000000000000000001" + "49a1ec142565a545acfdb77bd9d40cfa" + "8b996712101bea0ec6346c54374f25bd", + "00000000000000000000000000000000" + "00000000000000000000000000000000" + "00000000000000000000000000000000" + "00000000000000000000000000000002", + "1a8f7eda389b094c2c071e3647a8940f" + "3c123b697578c213be6dd9e6c8ec7335" + "dcb228fd1edf4a39152cbcaaf8c03988" + "28041055f94ceeec7e21340780fe41bd"); + + 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 if (!strcmp (curve, "curve448")) { @@ -1316,7 +1488,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 d36d46b77bc1..21e3e24dcef5 100644 --- a/examples/ecc-benchmark.c +++ b/examples/ecc-benchmark.c @@ -314,6 +314,11 @@ const struct ecc_curve * const curves[] = { &_nettle_secp_384r1, &_nettle_curve448, &_nettle_secp_521r1, + &_nettle_gc256b, + &_nettle_gc256c, + &_nettle_gc256d, + &_nettle_gc512a, + &_nettle_gc512b, };
#define numberof(x) (sizeof (x) / sizeof ((x)[0])) diff --git a/testsuite/testutils.c b/testsuite/testutils.c index 7772d2b01661..10f2ef915e38 100644 --- a/testsuite/testutils.c +++ b/testsuite/testutils.c @@ -1677,6 +1677,11 @@ const struct ecc_curve * const ecc_curves[] = { &_nettle_secp_521r1, &_nettle_curve25519, &_nettle_curve448, + &_nettle_gc256b, + &_nettle_gc256c, + &_nettle_gc256d, + &_nettle_gc512a, + &_nettle_gc512b, NULL };
@@ -1728,7 +1733,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[7][3] = { + static const struct ecc_ref_point ref[12][3] = { { { "dafebf5828783f2ad35534631588a3f629a70fb16982a888", "dd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab" }, { "76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da", @@ -1796,9 +1801,56 @@ test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p) "e005a8dbd5125cf706cbda7ad43aa6449a4a8d952356c3b9fce43c82ec4e1d58bb3a331bdb6767f0bffa9a68fed02dafb822ac13588ed6fc" }, { "49dcbc5c6c0cce2c1419a17226f929ea255a09cf4e0891c693fda4be70c74cc301b7bdf1515dd8ba21aee1798949e120e2ce42ac48ba7f30", "d49077e4accde527164b33a5de021b979cb7c02f0457d845c90dc3227b8a5bc1c0d8f97ea1ca9472b5d444285d0d4f5b32e236f86de51839" }, + }, + { { "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 < 7); + assert (curve < 12); assert (n <= 4); if (n == 0) {
dbaryshkov@gmail.com writes:
From: Dmitry Eremin-Solenikov dbaryshkov@gmail.com
Add three 256-bit curves from RFC 4357 (Section 11.4) and two 512-bit curves from RFC 7836 (Section A.1).
To easy review, please do one patch or merge-request per curve. We can do the easiest ones first, which I think are gc256b and gc512a.
Regards, /Niels
From: Dmitry Eremin-Solenikov dbaryshkov@gmail.com
Add GOST Digital Signature Algorithms support according to GOST R 34.10-2001/-2012. English translations of these standards are provided as RFC 5832 and RFC 7091.
Signed-off-by: Dmitry Eremin-Solenikov dbaryshkov@gmail.com --- Makefile.in | 4 +- ecc-gostdsa-sign.c | 103 +++++++++++++++++++++ ecc-gostdsa-verify.c | 132 +++++++++++++++++++++++++++ ecc-hash.c | 11 +++ ecc-internal.h | 7 ++ gostdsa-sign.c | 76 ++++++++++++++++ gostdsa-verify.c | 80 +++++++++++++++++ gostdsa.h | 102 +++++++++++++++++++++ testsuite/.gitignore | 3 + testsuite/.test-rules.make | 9 ++ testsuite/Makefile.in | 4 +- testsuite/gostdsa-keygen-test.c | 154 ++++++++++++++++++++++++++++++++ testsuite/gostdsa-sign-test.c | 125 ++++++++++++++++++++++++++ testsuite/gostdsa-verify-test.c | 148 ++++++++++++++++++++++++++++++ testsuite/testutils.h | 1 + 15 files changed, 957 insertions(+), 2 deletions(-) create mode 100644 ecc-gostdsa-sign.c create mode 100644 ecc-gostdsa-verify.c create mode 100644 gostdsa-sign.c create mode 100644 gostdsa-verify.c create mode 100644 gostdsa.h create mode 100644 testsuite/gostdsa-keygen-test.c create mode 100644 testsuite/gostdsa-sign-test.c create mode 100644 testsuite/gostdsa-verify-test.c
diff --git a/Makefile.in b/Makefile.in index d9b76d8d5354..3efc41f5ea04 100644 --- a/Makefile.in +++ b/Makefile.in @@ -190,6 +190,8 @@ hogweed_SOURCES = sexp.c sexp-format.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 \ + ecc-gostdsa-sign.c gostdsa-sign.c \ + ecc-gostdsa-verify.c gostdsa-verify.c \ curve25519-mul-g.c curve25519-mul.c curve25519-eh-to-x.c \ curve448-mul-g.c curve448-mul.c curve448-eh-to-x.c \ eddsa-compress.c eddsa-decompress.c eddsa-expand.c \ @@ -206,7 +208,7 @@ HEADERS = aes.h arcfour.h arctwo.h asn1.h blowfish.h \ cbc.h ccm.h cfb.h chacha.h chacha-poly1305.h ctr.h \ curve25519.h curve448.h des.h dsa.h dsa-compat.h eax.h \ ecc-curve.h ecc.h ecdsa.h eddsa.h \ - gcm.h gost28147.h gosthash94.h hmac.h \ + gcm.h gost28147.h gostdsa.h gosthash94.h hmac.h \ knuth-lfib.h hkdf.h \ macros.h \ cmac.h siv-cmac.h \ diff --git a/ecc-gostdsa-sign.c b/ecc-gostdsa-sign.c new file mode 100644 index 000000000000..0b8671d382ec --- /dev/null +++ b/ecc-gostdsa-sign.c @@ -0,0 +1,103 @@ +/* ecc-gostdsa-sign.c + + Copyright (C) 2015 Dmitry Eremin-Solenikov + 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 <stdlib.h> + +#include "gostdsa.h" +#include "ecc-internal.h" + +/* Low-level GOST DSA signing */ + +mp_size_t +ecc_gostdsa_sign_itch (const struct ecc_curve *ecc) +{ + /* Needs 3*ecc->p.size + scratch for ecc->mul_g. Currently same for + ecc_mul_g and ecc_mul_g_eh. */ + return ECC_GOSTDSA_SIGN_ITCH (ecc->p.size); +} + +/* NOTE: Caller should check if r or s is zero. */ +void +ecc_gostdsa_sign (const struct ecc_curve *ecc, + const mp_limb_t *zp, + const mp_limb_t *kp, + size_t length, const uint8_t *digest, + mp_limb_t *rp, mp_limb_t *sp, + mp_limb_t *scratch) +{ +#define P scratch +#define hp (scratch + 4*ecc->p.size) +#define tp (scratch + 2*ecc->p.size) +#define t2p scratch + /* Procedure, according to GOST 34.10. q denotes the group + order. + + 1. k <-- uniformly random, 0 < k < q + + 2. C <-- (c_x, c_y) = k g + + 3. r <-- c_x mod q + + 4. s <-- (r*z + k*h) mod q. + */ + + ecc->mul_g (ecc, P, kp, P + 3*ecc->p.size); + /* x coordinate only, modulo q */ + ecc->h_to_a (ecc, 2, rp, P, P + 3*ecc->p.size); + + /* Process hash digest */ + gost_hash (&ecc->q, hp, length, digest); + if (mpn_zero_p (hp, ecc->p.size)) + mpn_add_1 (hp, hp, ecc->p.size, 1); + + ecc_modq_mul (ecc, tp, rp, zp); + ecc_modq_mul (ecc, t2p, kp, hp); + ecc_modq_add (ecc, sp, tp, t2p); + + /* Also reduce mod ecc->q. It should already be < 2*ecc->q, + * so one subtraction should suffice. */ + + *scratch = mpn_sub_n (tp, sp, ecc->q.m, ecc->p.size); + cnd_copy (*scratch == 0, sp, tp, ecc->p.size); + +#undef P +#undef hp +#undef tp +#undef t2p +} diff --git a/ecc-gostdsa-verify.c b/ecc-gostdsa-verify.c new file mode 100644 index 000000000000..44f87b892f75 --- /dev/null +++ b/ecc-gostdsa-verify.c @@ -0,0 +1,132 @@ +/* ecc-gostdsa-verify.c + + Copyright (C) 2015 Dmitry Eremin-Solenikov + 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 <stdlib.h> + +#include "gostdsa.h" +#include "ecc-internal.h" + +/* Low-level GOST DSA verify */ + +static int +ecdsa_in_range (const struct ecc_curve *ecc, const mp_limb_t *xp) +{ + return !mpn_zero_p (xp, ecc->p.size) + && mpn_cmp (xp, ecc->q.m, ecc->p.size) < 0; +} + +mp_size_t +ecc_gostdsa_verify_itch (const struct ecc_curve *ecc) +{ + /* Largest storage need is for the ecc->mul call. */ + return 5*ecc->p.size + ecc->mul_itch; +} + +/* FIXME: Use faster primitives, not requiring side-channel silence. */ +int +ecc_gostdsa_verify (const struct ecc_curve *ecc, + const mp_limb_t *pp, /* Public key */ + size_t length, const uint8_t *digest, + const mp_limb_t *rp, const mp_limb_t *sp, + mp_limb_t *scratch) +{ + /* Procedure, according to GOST R 34.10. q denotes the group + order. + + 1. Check 0 < r, s < q. + + 2. v <-- h^{-1} (mod q) + + 3. z1 <-- s * v (mod q) + + 4. z2 <-- -r * v (mod q) + + 5. R = u1 G + u2 Y + + 6. Signature is valid if R_x = r (mod q). + */ + +#define hp (scratch) +#define vp (scratch + ecc->p.size) +#define z1 (scratch + 3*ecc->p.size) +#define z2 (scratch + 4*ecc->p.size) + +#define P1 (scratch + 4*ecc->p.size) +#define P2 (scratch) + + + if (! (ecdsa_in_range (ecc, rp) + && ecdsa_in_range (ecc, sp))) + return 0; + + gost_hash (&ecc->q, hp, length, digest); + + if (mpn_zero_p (hp, ecc->p.size)) + mpn_add_1 (hp, hp, ecc->p.size, 1); + + /* Compute v */ + ecc->q.invert (&ecc->q, vp, hp, vp + 2*ecc->p.size); + + /* z1 = s / h, P1 = z1 * G */ + ecc_modq_mul (ecc, z1, sp, vp); + + /* z2 = - r / h, P2 = z2 * Y */ + ecc_modq_mul (ecc, z2, rp, vp); + mpn_sub_n (z2, ecc->q.m, z2, ecc->p.size); + + /* Total storage: 5*ecc->p.size + ecc->mul_itch */ + ecc->mul (ecc, P2, z2, pp, z2 + ecc->p.size); + + /* Total storage: 7*ecc->p.size + ecc->mul_g_itch (ecc->p.size) */ + ecc->mul_g (ecc, P1, z1, P1 + 3*ecc->p.size); + + /* Total storage: 6*ecc->p.size + ecc->add_hhh_itch */ + ecc->add_hhh (ecc, P1, P1, P2, P1 + 3*ecc->p.size); + + /* x coordinate only, modulo q */ + ecc->h_to_a (ecc, 2, P2, P1, P1 + 3*ecc->p.size); + + return (mpn_cmp (rp, P2, ecc->p.size) == 0); +#undef P2 +#undef P1 +#undef z2 +#undef z1 +#undef hp +#undef vp +} diff --git a/ecc-hash.c b/ecc-hash.c index 4e830a514ac4..07877110263f 100644 --- a/ecc-hash.c +++ b/ecc-hash.c @@ -62,3 +62,14 @@ ecc_hash (const struct ecc_modulo *m, /* We got a few extra bits, at the low end. Discard them. */ mpn_rshift (hp, hp, m->size + 1, 8*length - m->bit_size); } + +void +gost_hash (const struct ecc_modulo *m, + mp_limb_t *hp, + size_t length, const uint8_t *digest) +{ + if (length > ((size_t) m->bit_size + 7) / 8) + length = (m->bit_size + 7) / 8; + + mpn_set_base256_le (hp, m->size + 1, digest, length); +} diff --git a/ecc-internal.h b/ecc-internal.h index 99e711a5b38d..680e82258be7 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -53,6 +53,7 @@ #define ecc_mod _nettle_ecc_mod #define ecc_mod_inv _nettle_ecc_mod_inv #define ecc_hash _nettle_ecc_hash +#define gost_hash _nettle_gost_hash #define ecc_a_to_j _nettle_ecc_a_to_j #define ecc_j_to_a _nettle_ecc_j_to_a #define ecc_eh_to_a _nettle_ecc_eh_to_a @@ -299,6 +300,11 @@ ecc_hash (const struct ecc_modulo *m, mp_limb_t *hp, size_t length, const uint8_t *digest);
+void +gost_hash (const struct ecc_modulo *m, + mp_limb_t *hp, + size_t length, const uint8_t *digest); + /* Converts a point P in affine coordinates into a point R in jacobian coordinates. */ void @@ -467,6 +473,7 @@ curve448_eh_to_x (mp_limb_t *xp, const mp_limb_t *p, #endif #define ECC_MUL_M_ITCH(size) (11*(size)) #define ECC_ECDSA_SIGN_ITCH(size) (12*(size)) +#define ECC_GOSTDSA_SIGN_ITCH(size) (12*(size)) #define ECC_MOD_RANDOM_ITCH(size) (size) #define ECC_HASH_ITCH(size) (1+(size))
diff --git a/gostdsa-sign.c b/gostdsa-sign.c new file mode 100644 index 000000000000..598654ac34f1 --- /dev/null +++ b/gostdsa-sign.c @@ -0,0 +1,76 @@ +/* gostdsa-sign.c + + Copyright (C) 2015 Dmitry Eremin-Solenikov + Copyright (C) 2013 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 <stdlib.h> + +#include "gostdsa.h" +#include "ecc-internal.h" +#include "nettle-internal.h" + +void +gostdsa_sign (const struct ecc_scalar *key, + void *random_ctx, nettle_random_func *random, + size_t digest_length, + const uint8_t *digest, + struct dsa_signature *signature) +{ + /* At most 936 bytes. */ + TMP_DECL(k, mp_limb_t, ECC_MAX_SIZE + ECC_GOSTDSA_SIGN_ITCH (ECC_MAX_SIZE)); + mp_limb_t size = key->ecc->p.size; + mp_limb_t *rp = mpz_limbs_write (signature->r, size); + mp_limb_t *sp = mpz_limbs_write (signature->s, size); + + TMP_ALLOC (k, size + ECC_GOSTDSA_SIGN_ITCH (size)); + + /* Timing reveals the number of rounds through this loop, but the + timing is still independent of the secret k finally used. */ + do + { + do + { + ecc_mod_random (&key->ecc->q, k, random_ctx, random, k + size); + } + while (mpn_zero_p(k, size)); + ecc_gostdsa_sign (key->ecc, key->p, k, digest_length, digest, + rp, sp, k + size); + mpz_limbs_finish (signature->r, size); + mpz_limbs_finish (signature->s, size); + } + while (mpz_sgn (signature->r) == 0 || mpz_sgn (signature->s) == 0); +} diff --git a/gostdsa-verify.c b/gostdsa-verify.c new file mode 100644 index 000000000000..cdf87d6ba18d --- /dev/null +++ b/gostdsa-verify.c @@ -0,0 +1,80 @@ +/* gostdsa-verify.c + + Copyright (C) 2015 Dmitry Eremin-Solenikov + Copyright (C) 2013 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 <stdlib.h> + +#include "gostdsa.h" + +#include "gmp-glue.h" + +int +gostdsa_verify (const struct ecc_point *pub, + size_t length, const uint8_t *digest, + const struct dsa_signature *signature) +{ + mp_limb_t size = ecc_size (pub->ecc); + mp_size_t itch = 2*size + ecc_gostdsa_verify_itch (pub->ecc); + /* For ECC_MUL_A_WBITS == 0, at most 1512 bytes. With + ECC_MUL_A_WBITS == 4, currently needs 67 * ecc->size, at most + 4824 bytes. Don't use stack allocation for this. */ + mp_limb_t *scratch; + int res; + +#define rp scratch +#define sp (scratch + size) +#define scratch_out (scratch + 2*size) + + if (mpz_sgn (signature->r) <= 0 || mpz_size (signature->r) > size + || mpz_sgn (signature->s) <= 0 || mpz_size (signature->s) > size) + return 0; + + scratch = gmp_alloc_limbs (itch); + + mpz_limbs_copy (rp, signature->r, size); + mpz_limbs_copy (sp, signature->s, size); + + res = ecc_gostdsa_verify (pub->ecc, pub->p, length, digest, rp, sp, scratch_out); + + gmp_free_limbs (scratch, itch); + + return res; +#undef rp +#undef sp +#undef scratch_out +} diff --git a/gostdsa.h b/gostdsa.h new file mode 100644 index 000000000000..b34533436f72 --- /dev/null +++ b/gostdsa.h @@ -0,0 +1,102 @@ +/* gostdsa.h + + Copyright (C) 2015 Dmity Eremin-Solenikov + Copyright (C) 2013 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. */ + +#ifndef NETTLE_GOSTDSA_H_INCLUDED +#define NETTLE_GOSTDSA_H_INCLUDED + +#include "ecc.h" +#include "dsa.h" +#include "ecdsa.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* Name mangling */ +#define gostdsa_sign nettle_gostdsa_sign +#define gostdsa_verify nettle_gostdsa_verify +#define ecc_gostdsa_sign nettle_ecc_gostdsa_sign +#define ecc_gostdsa_sign_itch nettle_ecc_gostdsa_sign_itch +#define ecc_gostdsa_verify nettle_ecc_gostdsa_verify +#define ecc_gostdsa_verify_itch nettle_ecc_gostdsa_verify_itch + +/* Just use ECDSA function for key generation */ +#define gostdsa_generate_keypair ecdsa_generate_keypair + +/* High level GOST DSA functions. + * + * A public key is represented as a struct ecc_point, and a private + * key as a struct ecc_scalar. FIXME: Introduce some aliases? */ +void +gostdsa_sign (const struct ecc_scalar *key, + void *random_ctx, nettle_random_func *random, + size_t digest_length, + const uint8_t *digest, + struct dsa_signature *signature); + +int +gostdsa_verify (const struct ecc_point *pub, + size_t length, const uint8_t *digest, + const struct dsa_signature *signature); + +/* Low-level GOSTDSA functions. */ +mp_size_t +ecc_gostdsa_sign_itch (const struct ecc_curve *ecc); + +void +ecc_gostdsa_sign (const struct ecc_curve *ecc, + const mp_limb_t *zp, + /* Random nonce, must be invertible mod ecc group + order. */ + const mp_limb_t *kp, + size_t length, const uint8_t *digest, + mp_limb_t *rp, mp_limb_t *sp, + mp_limb_t *scratch); + +mp_size_t +ecc_gostdsa_verify_itch (const struct ecc_curve *ecc); + +int +ecc_gostdsa_verify (const struct ecc_curve *ecc, + const mp_limb_t *pp, /* Public key */ + size_t length, const uint8_t *digest, + const mp_limb_t *rp, const mp_limb_t *sp, + mp_limb_t *scratch); + + +#ifdef __cplusplus +} +#endif + +#endif /* NETTLE_GOSTDSA_H_INCLUDED */ diff --git a/testsuite/.gitignore b/testsuite/.gitignore index 1e2a69a60c13..be3a48707580 100644 --- a/testsuite/.gitignore +++ b/testsuite/.gitignore @@ -43,6 +43,9 @@ /eddsa-sign-test /eddsa-verify-test /gcm-test +/gostdsa-keygen-test +/gostdsa-sign-test +/gostdsa-verify-test /gosthash94-test /hkdf-test /hmac-test diff --git a/testsuite/.test-rules.make b/testsuite/.test-rules.make index 6dbef7e24a27..9fd11fd6d126 100644 --- a/testsuite/.test-rules.make +++ b/testsuite/.test-rules.make @@ -289,6 +289,15 @@ ed25519-test$(EXEEXT): ed25519-test.$(OBJEXT) ed448-test$(EXEEXT): ed448-test.$(OBJEXT) $(LINK) ed448-test.$(OBJEXT) $(TEST_OBJS) -o ed448-test$(EXEEXT)
+gostdsa-sign-test$(EXEEXT): gostdsa-sign-test.$(OBJEXT) + $(LINK) gostdsa-sign-test.$(OBJEXT) $(TEST_OBJS) -o gostdsa-sign-test$(EXEEXT) + +gostdsa-verify-test$(EXEEXT): gostdsa-verify-test.$(OBJEXT) + $(LINK) gostdsa-verify-test.$(OBJEXT) $(TEST_OBJS) -o gostdsa-verify-test$(EXEEXT) + +gostdsa-keygen-test$(EXEEXT): gostdsa-keygen-test.$(OBJEXT) + $(LINK) gostdsa-keygen-test.$(OBJEXT) $(TEST_OBJS) -o gostdsa-keygen-test$(EXEEXT) + sha1-huge-test$(EXEEXT): sha1-huge-test.$(OBJEXT) $(LINK) sha1-huge-test.$(OBJEXT) $(TEST_OBJS) -o sha1-huge-test$(EXEEXT)
diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in index 97128040912e..860394d3bea5 100644 --- a/testsuite/Makefile.in +++ b/testsuite/Makefile.in @@ -53,7 +53,9 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \ ecdsa-sign-test.c ecdsa-verify-test.c \ ecdsa-keygen-test.c ecdh-test.c \ eddsa-compress-test.c eddsa-sign-test.c \ - eddsa-verify-test.c ed25519-test.c ed448-test.c + eddsa-verify-test.c ed25519-test.c ed448-test.c \ + gostdsa-sign-test.c gostdsa-verify-test.c \ + gostdsa-keygen-test.c
TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES) CXX_SOURCES = cxx-test.cxx diff --git a/testsuite/gostdsa-keygen-test.c b/testsuite/gostdsa-keygen-test.c new file mode 100644 index 000000000000..f34ff485ad6b --- /dev/null +++ b/testsuite/gostdsa-keygen-test.c @@ -0,0 +1,154 @@ +#include "testutils.h" +#include "knuth-lfib.h" + +/* Check if y^2 = x^3 - 3x + b */ +static int +ecc_valid_p (struct ecc_point *pub) +{ + mpz_t t, x, y; + mpz_t lhs, rhs; + int res; + mp_size_t size; + + size = pub->ecc->p.size; + + /* First check range */ + if (mpn_cmp (pub->p, pub->ecc->p.m, size) >= 0 + || mpn_cmp (pub->p + size, pub->ecc->p.m, size) >= 0) + return 0; + + mpz_init (lhs); + mpz_init (rhs); + + mpz_roinit_n (x, pub->p, size); + mpz_roinit_n (y, pub->p + size, size); + + mpz_mul (lhs, y, y); + + if (pub->ecc->p.bit_size == 255) + { + /* Check that + 121666 (1 + x^2 - y^2) = 121665 x^2 y^2 */ + mpz_t x2; + mpz_init (x2); + mpz_mul (x2, x, x); /* x^2 */ + mpz_mul (rhs, x2, lhs); /* x^2 y^2 */ + mpz_sub (lhs, x2, lhs); /* x^2 - y^2 */ + mpz_add_ui (lhs, lhs, 1); /* 1 + x^2 - y^2 */ + mpz_mul_ui (lhs, lhs, 121666); + mpz_mul_ui (rhs, rhs, 121665); + + mpz_clear (x2); + } + else if (pub->ecc->p.bit_size == 448) + { + /* Check that + x^2 + y^2 = 1 - 39081 x^2 y^2 */ + mpz_t x2, d; + mpz_init (x2); + mpz_init_set_ui (d, 39081); + mpz_mul (x2, x, x); /* x^2 */ + mpz_mul (d, d, x2); /* 39081 x^2 */ + mpz_set_ui (rhs, 1); + mpz_submul (rhs, d, lhs); /* 1 - 39081 x^2 y^2 */ + mpz_add (lhs, x2, lhs); /* x^2 + y^2 */ + + mpz_clear (d); + mpz_clear (x2); + } + else + { + /* Check y^2 = x^3 - 3 x + b */ + mpz_mul (rhs, x, x); + mpz_sub_ui (rhs, rhs, 3); + mpz_mul (rhs, rhs, x); + mpz_add (rhs, rhs, mpz_roinit_n (t, pub->ecc->b, size)); + } + res = mpz_congruent_p (lhs, rhs, mpz_roinit_n (t, pub->ecc->p.m, size)); + + mpz_clear (lhs); + mpz_clear (rhs); + + return res; +} + +void +test_main (void) +{ + unsigned i; + struct knuth_lfib_ctx rctx; + struct dsa_signature signature; + + struct tstring *digest; + + knuth_lfib_init (&rctx, 4711); + dsa_signature_init (&signature); + + digest = SHEX (/* sha256("abc") */ + "BA7816BF 8F01CFEA 414140DE 5DAE2223" + "B00361A3 96177A9C B410FF61 F20015AD"); + + for (i = 0; ecc_curves[i]; i++) + { + const struct ecc_curve *ecc = ecc_curves[i]; + struct ecc_point pub; + struct ecc_scalar key; + + if (ecc->p.bit_size == 255 || ecc->p.bit_size == 448) + /* Exclude curve25519 and curve448, not supported with GOSTDSA. */ + continue; + + if (verbose) + fprintf (stderr, "Curve %d\n", ecc->p.bit_size); + + ecc_point_init (&pub, ecc); + ecc_scalar_init (&key, ecc); + + ecdsa_generate_keypair (&pub, &key, + &rctx, + (nettle_random_func *) knuth_lfib_random); + + if (verbose) + { + fprintf (stderr, "Public key:\nx = "); + write_mpn (stderr, 16, pub.p, ecc->p.size); + fprintf (stderr, "\ny = "); + write_mpn (stderr, 16, pub.p + ecc->p.size, ecc->p.size); + fprintf (stderr, "\nPrivate key: "); + write_mpn (stderr, 16, key.p, ecc->p.size); + fprintf (stderr, "\n"); + } + if (!ecc_valid_p (&pub)) + die ("gostdsa_generate_keypair produced an invalid point.\n"); + + gostdsa_sign (&key, + &rctx, (nettle_random_func *) knuth_lfib_random, + digest->length, digest->data, + &signature); + + if (!gostdsa_verify (&pub, digest->length, digest->data, + &signature)) + die ("gostdsa_verify failed.\n"); + + digest->data[3] ^= 17; + if (gostdsa_verify (&pub, digest->length, digest->data, + &signature)) + die ("gostdsa_verify returned success with invalid digest.\n"); + digest->data[3] ^= 17; + + mpz_combit (signature.r, 117); + if (gostdsa_verify (&pub, digest->length, digest->data, + &signature)) + die ("gostdsa_verify returned success with invalid signature.r.\n"); + + mpz_combit (signature.r, 117); + mpz_combit (signature.s, 93); + if (gostdsa_verify (&pub, digest->length, digest->data, + &signature)) + die ("gostdsa_verify returned success with invalid signature.s.\n"); + + ecc_point_clear (&pub); + ecc_scalar_clear (&key); + } + dsa_signature_clear (&signature); +} diff --git a/testsuite/gostdsa-sign-test.c b/testsuite/gostdsa-sign-test.c new file mode 100644 index 000000000000..989621536b4b --- /dev/null +++ b/testsuite/gostdsa-sign-test.c @@ -0,0 +1,125 @@ +#include "testutils.h" + +static void +test_gostdsa (const struct ecc_curve *ecc, + /* Private key */ + const char *sz, + /* Random nonce */ + const char *sk, + /* Hash */ + const struct tstring *h, + /* Expected signature */ + const char *r, const char *s) +{ + struct dsa_signature ref; + mpz_t z; + mpz_t k; + mp_limb_t *rp = xalloc_limbs (ecc->p.size); + mp_limb_t *sp = xalloc_limbs (ecc->p.size); + mp_limb_t *scratch = xalloc_limbs (ecc_gostdsa_sign_itch (ecc)); + + dsa_signature_init (&ref); + + mpz_init_set_str (z, sz, 16); + mpz_init_set_str (k, sk, 16); + + ecc_gostdsa_sign (ecc, mpz_limbs_read_n (z, ecc->p.size), + mpz_limbs_read_n (k, ecc->p.size), + h->length, h->data, rp, sp, scratch); + + mpz_set_str (ref.r, r, 16); + mpz_set_str (ref.s, s, 16); + + if (mpz_limbs_cmp (ref.r, rp, ecc->p.size) != 0 + || mpz_limbs_cmp (ref.s, sp, ecc->p.size) != 0) + { + fprintf (stderr, "_gostdsa_sign failed, bit_size = %u\n", ecc->p.bit_size); + fprintf (stderr, "r = "); + write_mpn (stderr, 16, rp, ecc->p.size); + fprintf (stderr, "\ns = "); + write_mpn (stderr, 16, sp, ecc->p.size); + fprintf (stderr, "\nref.r = "); + mpz_out_str (stderr, 16, ref.r); + fprintf (stderr, "\nref.s = "); + mpz_out_str (stderr, 16, ref.s); + fprintf (stderr, "\n"); + abort(); + } + + free (rp); + free (sp); + free (scratch); + + dsa_signature_clear (&ref); + mpz_clear (k); + mpz_clear (z); +} + +void +test_main (void) +{ + test_gostdsa (nettle_get_gc256b(), + "BFCF1D623E5CDD3032A7C6EABB4A923C46E43D640FFEAAF2C3ED39A8FA399924", /* z */ + + "5782C53F110C596F9155D35EBD25A06A89C50391850A8FEFE33B0E270318857C", /* k */ + + SHEX("1C067E20EA6CB183F22EFB0F3C6FD2A4E6A02821CB7A1B17FACD5E1F7AA76F70"), /* h */ + + "E9323A5E88DD87FB7C724383BFFE7CECD4B9FFA2AC33BEEF73A5A1F743404F6B", /* r */ + + "5E5B9B805B01147A8492C4A162643AC615DC777B9174108F3DC276A41F987AF3"); /* s */ + + test_gostdsa (nettle_get_gc256c(), + "3FCF1D623E5CDD3032A7C6EABB4A923C46E43D640FFEAAF2C3ED39A8FA399924", /* z */ + + "5782C53F110C596F9155D35EBD25A06A89C50391850A8FEFE33B0E270318857C", /* k */ + + SHEX("1C067E20EA6CB183F22EFB0F3C6FD2A4E6A02821CB7A1B17FACD5E1F7AA76F70"), /* h */ + + "4E8F9973B31A134CE0942421573B0529B07EC96B835A07856C16CE8070C62547", /* r */ + + "10CE0EFA72741D5EB24837563AAB9369781D6F487ACF88BBEE3E49EC239F6A90"); /* s */ + + test_gostdsa (nettle_get_gc256d(), + "3FCF1D623E5CDD3032A7C6EABB4A923C46E43D640FFEAAF2C3ED39A8FA399924", /* z */ + + "5782C53F110C596F9155D35EBD25A06A89C50391850A8FEFE33B0E270318857C", /* k */ + + SHEX("1C067E20EA6CB183F22EFB0F3C6FD2A4E6A02821CB7A1B17FACD5E1F7AA76F70"), /* h */ + + "7A03B527F916AF43DB655362A54AA9EBAF1A02B5776B5EBD8F00484EE8FD4AC6", /* r */ + + "7D21C2C0D9AD2D03B5D0EF47AE85AB8861067C1FF5394A755BD4A30B5591F8C4"); /* s */ + + test_gostdsa (nettle_get_gc512a(), + "3FC01CDCD4EC5F972EB482774C41E66DB7F380528DFE9E67992BA05AEE462435" + "757530E641077CE587B976C8EEB48C48FD33FD175F0C7DE6A44E014E6BCB074B", /* z */ + + "72ABB44536656BF1618CE10BF7EADD40582304A51EE4E2A25A0A32CB0E773ABB" + "23B7D8FDD8FA5EEE91B4AE452F2272C86E1E2221215D405F51B5D5015616E1F6", /* k */ + + SHEX("EDC257BED45FDDE4F1457B7F5B19017A8F204184366689D938532CDBAA5CB29A" + "1D369DA57F8B983BE272219BD2C9A4FC57ECF7A77F34EE2E8AA553976A4766C0"), /* h */ + + "891AA75C2A6F3B4DE27E3903F61CBB0F3F85A4E3C62F39A6E4E84A7477679C6E" + "45008DC2774CA2FF64C12C0606FF918CAE3A50115440E9BF2971B627A882A1E8", /* r */ + + "31065479996DDBDEE180AFE22CA3CDC44B45CE4C6C83909D1D3B702922A32441" + "A9E11DCFBEA3D847C06B1A8A38EB1671D6C82FA21B79C99BE2EA809B10DAA5DF"); /* s */ + + test_gostdsa (nettle_get_gc512b(), + "3FC01CDCD4EC5F972EB482774C41E66DB7F380528DFE9E67992BA05AEE462435" + "757530E641077CE587B976C8EEB48C48FD33FD175F0C7DE6A44E014E6BCB074B", /* z */ + + "72ABB44536656BF1618CE10BF7EADD40582304A51EE4E2A25A0A32CB0E773ABB" + "23B7D8FDD8FA5EEE91B4AE452F2272C86E1E2221215D405F51B5D5015616E1F6", /* k */ + + SHEX("EDC257BED45FDDE4F1457B7F5B19017A8F204184366689D938532CDBAA5CB29A" + "1D369DA57F8B983BE272219BD2C9A4FC57ECF7A77F34EE2E8AA553976A4766C0"), /* h */ + + "5DBF2F4C2D6A7705880FB1458CC58335065BEA5621FC9FBC176C4ACA5BC1E672" + "25459A8EA3779434590DC872704029365A83A53B5EB3C06936B5D287E0A983E7", /* r */ + + "4E6D2EE8A693D35F31F2551D43B4F6BC6F9EE7B9D27323873386C7DE5F91C39E" + "D3AAE39B7D07FA92B3C742E9E1B16E11D9F7308E485B715987668346AEF1723D"); /* s */ +} diff --git a/testsuite/gostdsa-verify-test.c b/testsuite/gostdsa-verify-test.c new file mode 100644 index 000000000000..347f19fd277b --- /dev/null +++ b/testsuite/gostdsa-verify-test.c @@ -0,0 +1,148 @@ +#include "testutils.h" + +static void +test_gostdsa (const struct ecc_curve *ecc, + /* Public key */ + const char *xs, const char *ys, + /* Hash */ + struct tstring *h, + /* Valid signature */ + const char *r, const char *s) +{ + struct ecc_point pub; + struct dsa_signature signature; + mpz_t x, y; + + ecc_point_init (&pub, ecc); + dsa_signature_init (&signature); + + mpz_init_set_str (x, xs, 16); + mpz_init_set_str (y, ys, 16); + + if (!ecc_point_set (&pub, x, y)) + die ("ecc_point_set failed.\n"); + + mpz_set_str (signature.r, r, 16); + mpz_set_str (signature.s, s, 16); + + if (!gostdsa_verify (&pub, h->length, h->data, &signature)) + { + fprintf (stderr, "gostdsa_verify failed with valid signature.\n"); + fail: + fprintf (stderr, "bit_size = %u\nx = ", ecc->p.bit_size); + mpz_out_str (stderr, 16, x); + fprintf (stderr, "\ny = "); + mpz_out_str (stderr, 16, y); + fprintf (stderr, "\ndigest "); + print_hex (h->length, h->data); + fprintf (stderr, "r = "); + mpz_out_str (stderr, 16, signature.r); + fprintf (stderr, "\ns = "); + mpz_out_str (stderr, 16, signature.s); + fprintf (stderr, "\n"); + abort(); + } + + mpz_combit (signature.r, ecc->p.bit_size / 3); + if (gostdsa_verify (&pub, h->length, h->data, &signature)) + { + fprintf (stderr, "gostdsa_verify unexpectedly succeeded with invalid signature.\n"); + goto fail; + } + mpz_combit (signature.r, ecc->p.bit_size / 3); + + mpz_combit (signature.s, 4*ecc->p.bit_size / 5); + if (gostdsa_verify (&pub, h->length, h->data, &signature)) + { + fprintf (stderr, "gostdsa_verify unexpectedly succeeded with invalid signature.\n"); + goto fail; + } + mpz_combit (signature.s, 4*ecc->p.bit_size / 5); + + h->data[2*h->length / 3] ^= 0x40; + if (gostdsa_verify (&pub, h->length, h->data, &signature)) + { + fprintf (stderr, "gostdsa_verify unexpectedly succeeded with invalid signature.\n"); + goto fail; + } + h->data[2*h->length / 3] ^= 0x40; + if (!gostdsa_verify (&pub, h->length, h->data, &signature)) + { + fprintf (stderr, "gostdsa_verify failed, internal testsuite error.\n"); + goto fail; + } + + ecc_point_clear (&pub); + dsa_signature_clear (&signature); + mpz_clear (x); + mpz_clear (y); +} + +void +test_main (void) +{ + test_gostdsa (nettle_get_gc256b(), + "971566CEDA436EE7678F7E07E84EBB7217406C0B4747AA8FD2AB1453C3D0DFBA", /* x */ + + "AD58736965949F8E59830F8DE20FC6C0D177F6AB599874F1E2E24FF71F9CE643", /* y */ + + SHEX("1C067E20EA6CB183F22EFB0F3C6FD2A4E6A02821CB7A1B17FACD5E1F7AA76F70"), /* h */ + + "E9323A5E88DD87FB7C724383BFFE7CECD4B9FFA2AC33BEEF73A5A1F743404F6B", /* r */ + + "5E5B9B805B01147A8492C4A162643AC615DC777B9174108F3DC276A41F987AF3"); /* s */ + + test_gostdsa (nettle_get_gc256c(), + "347E354F60B8DA8DE659B432600418C7D0E70F01622477579FAB36A066B9B8FD", /* x */ + + "1DD2E31CF7840A5109DFAB561E15D42BC3CE2E64995FB70F3B86679655A1BAA1", /* y */ + + SHEX("1C067E20EA6CB183F22EFB0F3C6FD2A4E6A02821CB7A1B17FACD5E1F7AA76F70"), /* h */ + + "4E8F9973B31A134CE0942421573B0529B07EC96B835A07856C16CE8070C62547", /* r */ + + "10CE0EFA72741D5EB24837563AAB9369781D6F487ACF88BBEE3E49EC239F6A90"); /* s */ + + test_gostdsa (nettle_get_gc256d(), + "1F737CC71E43E3FB35B886383714CA5E1226ECDF21F6063E6EA2E40DD04C44EC", /* x */ + + "7DD94CE1044CCEAD21E4E985E281034058A5B11F37B5F96F31DDCF7D513D164E", /* y */ + + SHEX("1C067E20EA6CB183F22EFB0F3C6FD2A4E6A02821CB7A1B17FACD5E1F7AA76F70"), /* h */ + + "7A03B527F916AF43DB655362A54AA9EBAF1A02B5776B5EBD8F00484EE8FD4AC6", /* r */ + + "7D21C2C0D9AD2D03B5D0EF47AE85AB8861067C1FF5394A755BD4A30B5591F8C4"); /* s */ + + test_gostdsa (nettle_get_gc512a(), + "03A36340A95BB5F93D131961B5B1C1B3213DF7FF3B5A30376407E2A65C441BC6" + "D1B34662317083243F007B15A8512B526606D3B172B606DCE86DBD6F82DA3D40", /* x */ + + "DEAD76318012FED79507809C89CC44848743640EAC9A3C847DA9082E050760A1" + "0679F4B707ABC1872640AD20D7441F66C7A8B3BFF1B8E11B4A076F0A86749F73", /* y */ + + SHEX("EDC257BED45FDDE4F1457B7F5B19017A8F204184366689D938532CDBAA5CB29A" + "1D369DA57F8B983BE272219BD2C9A4FC57ECF7A77F34EE2E8AA553976A4766C0"), /* h */ + + "891AA75C2A6F3B4DE27E3903F61CBB0F3F85A4E3C62F39A6E4E84A7477679C6E" + "45008DC2774CA2FF64C12C0606FF918CAE3A50115440E9BF2971B627A882A1E8", /* r */ + + "31065479996DDBDEE180AFE22CA3CDC44B45CE4C6C83909D1D3B702922A32441" + "A9E11DCFBEA3D847C06B1A8A38EB1671D6C82FA21B79C99BE2EA809B10DAA5DF"); /* s */ + + test_gostdsa (nettle_get_gc512b(), + "07134627CE7FC6770953ABA4714B38AF8DE764B8870A502C2F4CC2D05541459A" + "18DA3B9D4EBC09BC06CB2EA1856A03747561CF04C34382111539230A550F1913", /* x */ + + "7E08A434CB2FA300F8974E3FF69A4BCDF36B6308E1D7A56144693A35E11CBD14" + "D502916E680E35FE1E6ABBA85BD4DAE7065308B16B1CCABFE3D91CE0655B0FFD", /* y */ + + SHEX("EDC257BED45FDDE4F1457B7F5B19017A8F204184366689D938532CDBAA5CB29A" + "1D369DA57F8B983BE272219BD2C9A4FC57ECF7A77F34EE2E8AA553976A4766C0"), /* h */ + + "5DBF2F4C2D6A7705880FB1458CC58335065BEA5621FC9FBC176C4ACA5BC1E672" + "25459A8EA3779434590DC872704029365A83A53B5EB3C06936B5D287E0A983E7", /* r */ + + "4E6D2EE8A693D35F31F2551D43B4F6BC6F9EE7B9D27323873386C7DE5F91C39E" + "D3AAE39B7D07FA92B3C742E9E1B16E11D9F7308E485B715987668346AEF1723D"); /* s */ +} diff --git a/testsuite/testutils.h b/testsuite/testutils.h index f4ea38da9deb..cef7f4011a7c 100644 --- a/testsuite/testutils.h +++ b/testsuite/testutils.h @@ -22,6 +22,7 @@ # include "ecc.h" # include "ecc-internal.h" # include "ecdsa.h" +# include "gostdsa.h" # include "gmp-glue.h" # if NETTLE_USE_MINI_GMP # include "knuth-lfib.h"
dbaryshkov@gmail.com writes:
GOST curves will require different "fixups" for fast (mul X mod p) operations. Move these operations to ecc_modulo structure and call them via function pointer.
Can you explain what methods you intend to use? I had a quick look at the prime definitions in the next patch,
+ else if (!strcmp (curve, "gc256b")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "ffffffffffffffffffffffffffffffff" + "fffffffffffffffffffffffffffffd97",
Should work fine with the current functions.
+ else if (!strcmp (curve, "gc256c")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "80000000000000000000000000000000" + "00000000000000000000000000000c99",
Could use special tricks. Structure is similar to the q for curve25519.
+ else if (!strcmp (curve, "gc256d")) + { + ecc_curve_init_str (ecc, ECC_TYPE_WEIERSTRASS, + "9b9f605f5a858107ab1ec85e6b41c8aa" + "cf846e86789051d37998f7b9022d759b",
This has no visible structure. One could maybe use some variant of the 3/2 division in https://gmplib.org/~tege/division-paper.pdf to find a good enough quotient, and divide without any bignum adjustment step. The result should then be a non-canonical remainder, in the range 0 <= r < 2^256. Everything needs to be side-channel silent.
Another option is to premultiply, and do computations mod k p for some smallish k. With k = 0x1a51f176161f1d734 (same as the 3/2 reciprocal, I think),
k p = ffffffffffffffffd8e5627c0706fb8dc4f73162b7fca65ab59cdb66ec652b2787ac757f10ec107c
with friendly structure (but one word larger). I think this trick is known as Svoboda division. But for the main operations, it is likely more efficient to use plain unstructured redc, precomputing p^{-1} mod B (where B is word size, 2^32 or 2^64 depending on architecture).
Regards, /Niels
nettle-bugs@lists.lysator.liu.se
-
dbaryshkov＠gmail.com -
nisse＠lysator.liu.se