nettle-bugs January 2020

nettle-bugs@lists.lysator.liu.se

9 participants
19 discussions

[PATCH v5 1/3] Add GOST DSA according to GOST R 34.10-2001/-2012
by dbaryshkov＠gmail.com 17 Jan '20

17 Jan '20

From: Dmitry Baryshkov <dbaryshkov(a)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 Baryshkov <dbaryshkov(a)gmail.com> --- Makefile.in | 4 +- ecc-gostdsa-sign.c | 101 +++++++++++++++++++++ ecc-gostdsa-verify.c | 130 +++++++++++++++++++++++++++ ecc-hash.c | 11 +++ ecc-internal.h | 7 ++ gostdsa-sign.c | 74 +++++++++++++++ gostdsa-verify.c | 78 ++++++++++++++++ gostdsa.h | 100 +++++++++++++++++++++ testsuite/.gitignore | 3 + testsuite/.test-rules.make | 9 ++ testsuite/Makefile.in | 4 +- testsuite/gostdsa-keygen-test.c | 155 ++++++++++++++++++++++++++++++++ testsuite/gostdsa-sign-test.c | 88 ++++++++++++++++++ testsuite/gostdsa-verify-test.c | 111 +++++++++++++++++++++++ 14 files changed, 873 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 eb1c6c335c39..f876e5e82197 100644 --- a/Makefile.in +++ b/Makefile.in @@ -189,6 +189,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 \ @@ -205,7 +207,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..00eeef81f659 --- /dev/null +++ b/ecc-gostdsa-sign.c @@ -0,0 +1,101 @@ +/* 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/. +*/ + +#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..4358132b2bf6 --- /dev/null +++ b/ecc-gostdsa-verify.c @@ -0,0 +1,130 @@ +/* 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/. +*/ + +#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 cef1366545e0..0022e0ab6cc2 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 @@ -288,6 +289,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 @@ -456,6 +462,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..892c0742c898 --- /dev/null +++ b/gostdsa-sign.c @@ -0,0 +1,74 @@ +/* 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/. +*/ + +#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..7dc1bec1ef62 --- /dev/null +++ b/gostdsa-verify.c @@ -0,0 +1,78 @@ +/* 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/. +*/ + +#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..c92dfd1e1dd6 --- /dev/null +++ b/gostdsa.h @@ -0,0 +1,100 @@ +/* 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/. +*/ + +#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 dea6c28d2f20..73a61685dfc1 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..ebeabc860bca --- /dev/null +++ b/testsuite/gostdsa-keygen-test.c @@ -0,0 +1,155 @@ +#include "testutils.h" +#include "gostdsa.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..0e2e0420a313 --- /dev/null +++ b/testsuite/gostdsa-sign-test.c @@ -0,0 +1,88 @@ +#include "testutils.h" +#include "gostdsa.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_gost_gc256b(), + "BFCF1D623E5CDD3032A7C6EABB4A923C46E43D640FFEAAF2C3ED39A8FA399924", /* z */ + + "5782C53F110C596F9155D35EBD25A06A89C50391850A8FEFE33B0E270318857C", /* k */ + + SHEX("1C067E20EA6CB183F22EFB0F3C6FD2A4E6A02821CB7A1B17FACD5E1F7AA76F70"), /* h */ + + "E9323A5E88DD87FB7C724383BFFE7CECD4B9FFA2AC33BEEF73A5A1F743404F6B", /* r */ + + "5E5B9B805B01147A8492C4A162643AC615DC777B9174108F3DC276A41F987AF3"); /* s */ + + test_gostdsa (nettle_get_gost_gc512a(), + "3FC01CDCD4EC5F972EB482774C41E66DB7F380528DFE9E67992BA05AEE462435" + "757530E641077CE587B976C8EEB48C48FD33FD175F0C7DE6A44E014E6BCB074B", /* z */ + + "72ABB44536656BF1618CE10BF7EADD40582304A51EE4E2A25A0A32CB0E773ABB" + "23B7D8FDD8FA5EEE91B4AE452F2272C86E1E2221215D405F51B5D5015616E1F6", /* k */ + + SHEX("EDC257BED45FDDE4F1457B7F5B19017A8F204184366689D938532CDBAA5CB29A" + "1D369DA57F8B983BE272219BD2C9A4FC57ECF7A77F34EE2E8AA553976A4766C0"), /* h */ + + "891AA75C2A6F3B4DE27E3903F61CBB0F3F85A4E3C62F39A6E4E84A7477679C6E" + "45008DC2774CA2FF64C12C0606FF918CAE3A50115440E9BF2971B627A882A1E8", /* r */ + + "31065479996DDBDEE180AFE22CA3CDC44B45CE4C6C83909D1D3B702922A32441" + "A9E11DCFBEA3D847C06B1A8A38EB1671D6C82FA21B79C99BE2EA809B10DAA5DF"); /* s */ +} diff --git a/testsuite/gostdsa-verify-test.c b/testsuite/gostdsa-verify-test.c new file mode 100644 index 000000000000..7279f5f46c5b --- /dev/null +++ b/testsuite/gostdsa-verify-test.c @@ -0,0 +1,111 @@ +#include "testutils.h" +#include "gostdsa.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_gost_gc256b(), + "971566CEDA436EE7678F7E07E84EBB7217406C0B4747AA8FD2AB1453C3D0DFBA", /* x */ + + "AD58736965949F8E59830F8DE20FC6C0D177F6AB599874F1E2E24FF71F9CE643", /* y */ + + SHEX("1C067E20EA6CB183F22EFB0F3C6FD2A4E6A02821CB7A1B17FACD5E1F7AA76F70"), /* h */ + + "E9323A5E88DD87FB7C724383BFFE7CECD4B9FFA2AC33BEEF73A5A1F743404F6B", /* r */ + + "5E5B9B805B01147A8492C4A162643AC615DC777B9174108F3DC276A41F987AF3"); /* s */ + + test_gostdsa (nettle_get_gost_gc512a(), + "03A36340A95BB5F93D131961B5B1C1B3213DF7FF3B5A30376407E2A65C441BC6" + "D1B34662317083243F007B15A8512B526606D3B172B606DCE86DBD6F82DA3D40", /* x */ + + "DEAD76318012FED79507809C89CC44848743640EAC9A3C847DA9082E050760A1" + "0679F4B707ABC1872640AD20D7441F66C7A8B3BFF1B8E11B4A076F0A86749F73", /* y */ + + SHEX("EDC257BED45FDDE4F1457B7F5B19017A8F204184366689D938532CDBAA5CB29A" + "1D369DA57F8B983BE272219BD2C9A4FC57ECF7A77F34EE2E8AA553976A4766C0"), /* h */ + + "891AA75C2A6F3B4DE27E3903F61CBB0F3F85A4E3C62F39A6E4E84A7477679C6E" + "45008DC2774CA2FF64C12C0606FF918CAE3A50115440E9BF2971B627A882A1E8", /* r */ + + "31065479996DDBDEE180AFE22CA3CDC44B45CE4C6C83909D1D3B702922A32441" + "A9E11DCFBEA3D847C06B1A8A38EB1671D6C82FA21B79C99BE2EA809B10DAA5DF"); /* s */ +} -- 2.24.1

1 2

Require GNU make?
by nisse＠lysator.liu.se 16 Jan '20

16 Jan '20

Hi, it's been pointed out to me that GNU make documentation of old-fashioned suffix rules say : Suffix rules cannot have any prerequisites of their own. If they : have any, they are treated as normal files with funny names, not as : suffix rules. Thus, the rule: : : .c.o: foo.h : $(CC) -c $(CFLAGS) $(CPPFLAGS) -o $@ $< : : tells how to make the file '.c.o' from the prerequisite file 'foo.h', Nettle's Makefile.in has a rule .asm.$(OBJEXT): $(srcdir)/asm.m4 machine.m4 config.m4 which is broken according to these docs. I haven't seen any problems in practice (not entirely sure why), but it reportedly fails with some GNU make prerelease. To change this to a %-pattern rule, I wonder: Should we just drop support for non-GNU make programs? Requiring GNU make makes a few things easier: We can use %-patterns everywhere. We can use -include unconditionally for dep-files, dropping the @DEP_INCLUDE@ variable and the dummy-dep-files configure step. We can most likely also drop all logic for the testsuite/.test-rules.make file. Current status of make compatibility is that it's supposed to work with Solaris make (but likely not tested for a long time), and it should kind-of work with BSD make, provided one configures with --disable-dependency-tracking. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance.

3 4

Gitlab merge requests
by nisse＠lysator.liu.se 16 Jan '20

16 Jan '20

Hi, After some off-list discussions and encouragement, I've reenabled the "merge request" feature on git.lysator.liu.se/nettle. I don't know yet precisely how I will want to use it, but feel free to create merge requests if you think that helps us keep track of ongoing work. For the time being, please also write to the mailinglist whenever some action is done or desired on a merge request. I intend the mailinglist to remain the main forum for discussing new features and implementation choices, while detailed patch review might gradually move to the web interface. Advice on how to use and configure gitlab is welcome. Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance.

5 9

[PATCH v2 1/3] Add support for GOST GC256B curve
by dbaryshkov＠gmail.com 15 Jan '20

15 Jan '20

From: Dmitry Eremin-Solenikov <dbaryshkov(a)gmail.com> Add support for GC256B curve ("TLS Supported Groups" registry, draft-smyshlyaev-tls12-gost-suites) also known as GostR3410-2001-CryptoPro-A and GostR3410-2001-CryptoPro-XchA (RFC 4357). Signed-off-by: Dmitry Eremin-Solenikov <dbaryshkov(a)gmail.com> --- .gitignore | 1 + Makefile.in | 11 +++ ecc-curve.h | 1 + ecc-gc256b.c | 140 +++++++++++++++++++++++++++++++++++++++ ecc-internal.h | 3 + eccdata.c | 34 +++++++++- examples/ecc-benchmark.c | 1 + testsuite/testutils.c | 12 +++- 8 files changed, 200 insertions(+), 3 deletions(-) create mode 100644 ecc-gc256b.c diff --git a/.gitignore b/.gitignore index ea264107fa40..4454ade5a950 100644 --- a/.gitignore +++ b/.gitignore @@ -45,6 +45,7 @@ core /rotors.h /ecc-curve25519.h /ecc-curve448.h +/ecc-gc256b.h /ecc-secp192r1.h /ecc-secp224r1.h /ecc-secp256r1.h diff --git a/Makefile.in b/Makefile.in index 38160bb40fe1..8815e7b76dea 100644 --- a/Makefile.in +++ b/Makefile.in @@ -176,6 +176,7 @@ 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-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 +397,21 @@ 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 $@ + 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-secp192r1.$(OBJEXT): ecc-secp192r1.h ecc-secp224r1.$(OBJEXT): ecc-secp224r1.h ecc-secp256r1.$(OBJEXT): ecc-secp256r1.h @@ -660,6 +670,7 @@ distcheck: dist clean-here: -rm -f $(TARGETS) *.$(OBJEXT) *.s *.so *.dll *.a \ ecc-curve25519.h ecc-curve448.h \ + ecc-gc256b.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..b378c8489839 100644 --- a/ecc-curve.h +++ b/ecc-curve.h @@ -43,6 +43,7 @@ extern "C" { /* The contents of this struct is internal. */ struct ecc_curve; +const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_gc256b(void); const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_192r1(void); const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_224r1(void); const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_256r1(void); diff --git a/ecc-gc256b.c b/ecc-gc256b.c new file mode 100644 index 000000000000..755759a8fd38 --- /dev/null +++ b/ecc-gc256b.c @@ -0,0 +1,140 @@ +/* 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, + }, + { + 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, + }, + + 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-internal.h b/ecc-internal.h index c918632df292..0972efaf10d1 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -91,6 +91,9 @@ 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; + #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..3820e150125b 100644 --- a/eccdata.c +++ b/eccdata.c @@ -674,6 +674,38 @@ ecc_curve_init (struct ecc_curve *ecc, const char *curve) "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, "curve448")) { /* curve448, y^2 = x^3 + 156326 x^2 + x (mod p), with p = 2^{448} - 2^{224} - 1. @@ -1316,7 +1348,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..497c76c3e550 100644 --- a/examples/ecc-benchmark.c +++ b/examples/ecc-benchmark.c @@ -314,6 +314,7 @@ const struct ecc_curve * const curves[] = { &_nettle_secp_384r1, &_nettle_curve448, &_nettle_secp_521r1, + &_nettle_gc256b, }; #define numberof(x) (sizeof (x) / sizeof ((x)[0])) diff --git a/testsuite/testutils.c b/testsuite/testutils.c index 7772d2b01661..e4e7c23dcc1b 100644 --- a/testsuite/testutils.c +++ b/testsuite/testutils.c @@ -1677,6 +1677,7 @@ const struct ecc_curve * const ecc_curves[] = { &_nettle_secp_521r1, &_nettle_curve25519, &_nettle_curve448, + &_nettle_gc256b, NULL }; @@ -1728,7 +1729,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[8][3] = { { { "dafebf5828783f2ad35534631588a3f629a70fb16982a888", "dd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab" }, { "76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da", @@ -1796,9 +1797,16 @@ test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p) "e005a8dbd5125cf706cbda7ad43aa6449a4a8d952356c3b9fce43c82ec4e1d58bb3a331bdb6767f0bffa9a68fed02dafb822ac13588ed6fc" }, { "49dcbc5c6c0cce2c1419a17226f929ea255a09cf4e0891c693fda4be70c74cc301b7bdf1515dd8ba21aee1798949e120e2ce42ac48ba7f30", "d49077e4accde527164b33a5de021b979cb7c02f0457d845c90dc3227b8a5bc1c0d8f97ea1ca9472b5d444285d0d4f5b32e236f86de51839" }, + }, + { { "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd95", + "726e1b8e1f676325d820afa5bac0d489cad6b0d220dc1c4edd5336636160df83" }, + { "8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38d2c", + "76bcd1ca9a23b041d4d9baf507a6cd821267a94c838768e8486117796b788a51" }, + { "f7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e4b7", + "83ccf17ba6706d73625cc3534c7a2b9d6ec1ee6a9a7e07c10d84b388de59f741" }, } }; - assert (curve < 7); + assert (curve < 8); assert (n <= 4); if (n == 0) { -- 2.24.1

3 7

[PATCH v3 1/3] Add support for GOST GC256B curve
by dbaryshkov＠gmail.com 13 Jan '20

13 Jan '20

From: Dmitry Eremin-Solenikov <dbaryshkov(a)gmail.com> Add support for GC256B curve ("TLS Supported Groups" registry, draft-smyshlyaev-tls12-gost-suites) also known as GostR3410-2001-CryptoPro-A and GostR3410-2001-CryptoPro-XchA (RFC 4357). Signed-off-by: Dmitry Eremin-Solenikov <dbaryshkov(a)gmail.com> --- .gitignore | 1 + Makefile.in | 11 ++++ ecc-curve.h | 1 + ecc-gc256b.c | 128 +++++++++++++++++++++++++++++++++++++++ ecc-internal.h | 3 + eccdata.c | 34 ++++++++++- examples/ecc-benchmark.c | 1 + testsuite/testutils.c | 12 +++- 8 files changed, 188 insertions(+), 3 deletions(-) create mode 100644 ecc-gc256b.c diff --git a/.gitignore b/.gitignore index ea264107fa40..4454ade5a950 100644 --- a/.gitignore +++ b/.gitignore @@ -45,6 +45,7 @@ core /rotors.h /ecc-curve25519.h /ecc-curve448.h +/ecc-gc256b.h /ecc-secp192r1.h /ecc-secp224r1.h /ecc-secp256r1.h diff --git a/Makefile.in b/Makefile.in index 38160bb40fe1..8815e7b76dea 100644 --- a/Makefile.in +++ b/Makefile.in @@ -176,6 +176,7 @@ 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-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 +397,21 @@ 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 $@ + 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-secp192r1.$(OBJEXT): ecc-secp192r1.h ecc-secp224r1.$(OBJEXT): ecc-secp224r1.h ecc-secp256r1.$(OBJEXT): ecc-secp256r1.h @@ -660,6 +670,7 @@ distcheck: dist clean-here: -rm -f $(TARGETS) *.$(OBJEXT) *.s *.so *.dll *.a \ ecc-curve25519.h ecc-curve448.h \ + ecc-gc256b.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..b378c8489839 100644 --- a/ecc-curve.h +++ b/ecc-curve.h @@ -43,6 +43,7 @@ extern "C" { /* The contents of this struct is internal. */ struct ecc_curve; +const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_gc256b(void); const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_192r1(void); const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_224r1(void); const struct ecc_curve * _NETTLE_ATTRIBUTE_PURE nettle_get_secp_256r1(void); diff --git a/ecc-gc256b.c b/ecc-gc256b.c new file mode 100644 index 000000000000..b2d12d0bdf7c --- /dev/null +++ b/ecc-gc256b.c @@ -0,0 +1,128 @@ +/* ecc-gc256b.c + + Copyright (C) 2016-2020 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/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <assert.h> + +#include "ecc.h" +#include "ecc-internal.h" + +#define USE_REDC 0 + +#include "ecc-gc256b.h" + +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, + ecc_gc256b_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_gc256b_modq, + ecc_gc256b_modq, + ecc_mod_inv, + 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-internal.h b/ecc-internal.h index c918632df292..0972efaf10d1 100644 --- a/ecc-internal.h +++ b/ecc-internal.h @@ -91,6 +91,9 @@ 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; + #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..3820e150125b 100644 --- a/eccdata.c +++ b/eccdata.c @@ -674,6 +674,38 @@ ecc_curve_init (struct ecc_curve *ecc, const char *curve) "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, "curve448")) { /* curve448, y^2 = x^3 + 156326 x^2 + x (mod p), with p = 2^{448} - 2^{224} - 1. @@ -1316,7 +1348,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..497c76c3e550 100644 --- a/examples/ecc-benchmark.c +++ b/examples/ecc-benchmark.c @@ -314,6 +314,7 @@ const struct ecc_curve * const curves[] = { &_nettle_secp_384r1, &_nettle_curve448, &_nettle_secp_521r1, + &_nettle_gc256b, }; #define numberof(x) (sizeof (x) / sizeof ((x)[0])) diff --git a/testsuite/testutils.c b/testsuite/testutils.c index 7772d2b01661..e4e7c23dcc1b 100644 --- a/testsuite/testutils.c +++ b/testsuite/testutils.c @@ -1677,6 +1677,7 @@ const struct ecc_curve * const ecc_curves[] = { &_nettle_secp_521r1, &_nettle_curve25519, &_nettle_curve448, + &_nettle_gc256b, NULL }; @@ -1728,7 +1729,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[8][3] = { { { "dafebf5828783f2ad35534631588a3f629a70fb16982a888", "dd6bda0d993da0fa46b27bbc141b868f59331afa5c7e93ab" }, { "76e32a2557599e6edcd283201fb2b9aadfd0d359cbb263da", @@ -1796,9 +1797,16 @@ test_ecc_mul_a (unsigned curve, unsigned n, const mp_limb_t *p) "e005a8dbd5125cf706cbda7ad43aa6449a4a8d952356c3b9fce43c82ec4e1d58bb3a331bdb6767f0bffa9a68fed02dafb822ac13588ed6fc" }, { "49dcbc5c6c0cce2c1419a17226f929ea255a09cf4e0891c693fda4be70c74cc301b7bdf1515dd8ba21aee1798949e120e2ce42ac48ba7f30", "d49077e4accde527164b33a5de021b979cb7c02f0457d845c90dc3227b8a5bc1c0d8f97ea1ca9472b5d444285d0d4f5b32e236f86de51839" }, + }, + { { "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd95", + "726e1b8e1f676325d820afa5bac0d489cad6b0d220dc1c4edd5336636160df83" }, + { "8e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38d2c", + "76bcd1ca9a23b041d4d9baf507a6cd821267a94c838768e8486117796b788a51" }, + { "f7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e7063e4b7", + "83ccf17ba6706d73625cc3534c7a2b9d6ec1ee6a9a7e07c10d84b388de59f741" }, } }; - assert (curve < 7); + assert (curve < 8); assert (n <= 4); if (n == 0) { -- 2.24.1

1 2

[PATCH 1/3] Change ecc_mod_*mul_1 to be per-module callbacks
by dbaryshkov＠gmail.com 11 Jan '20

11 Jan '20

From: Dmitry Eremin-Solenikov <dbaryshkov(a)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(a)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, -- 2.24.1

2 4

[PATCH v3 0/3] ecc: rename to contain full curve name
by dbaryshkov＠gmail.com 11 Jan '20

11 Jan '20

Next iteration of renaming patchset. The only change since v2 is rebasing on top of current master to fix conflicts due to ed448 addition. -- With best wishes Dmitry

3 7

update CI to latest fedora image
by Nikos Mavrogiannopoulos 07 Jan '20

07 Jan '20

Hi, This patch updates the CI to the latest fedora image. It also includes some minor changes to tools, to pass the new clang analyser. I will remove the f29 image once this is applied. A test run passes: https://gitlab.com/nmav/nettle/pipelines/106785682 regards, Nikos

3 4

[PATCH 0/8] Implement Curve448 ECDH and Ed448
by Daiki Ueno 03 Jan '20

03 Jan '20

Hello, This patch series implements the Curve448 Diffie-Hellman protocol (RFC 7748) and the Ed448 signature scheme (RFC 8032). Although I tried to make it as close as possible to the Curve25519 and Ed25519 implementations, I had to add a few special cases, namely: - for Curve448, eccdata directly calculates points on the Edwards curve instead of the equivalent Montgomery curve - untwisted versions of ecc_add_eh* and ecc_dup_eh are added - the point decoding for Ed448 uses a different formula to recover u and v Also, optimized implementation of modular reduction is currently missing, which is beyond my expertise. I would appreciate any suggestions regarding that. The patches are also available on: https://gitlab.com/dueno/nettle/commits/wip/dueno/ed448 Thanks to Hubert Kario and Nikos Mavrogiannopoulos for initial reviews. Daiki Ueno (8): ecc-mul-test: Fix mpn_cmp calls eccdata: Emit correct ecc_Bmodq_shifted for curve448 eccdata: Redirect ecc_point_out to given stream, instead of stderr ecc: Add add_hh and dup members to ecc_curve ecc-eh-to-a, eddsa-sign: Parameterize hard-coded value Implement curve448 primitives Implement SHAKE128/256 functions Implement Ed448 signature scheme .gitignore | 1 + Makefile.in | 18 +- curve448-eh-to-x.c | 73 + curve448-mul-g.c | 74 + curve448-mul.c | 148 + curve448.h | 58 + ecc-192.c | 5 + ecc-224.c | 5 + ecc-25519.c | 5 + ecc-256.c | 5 + ecc-384.c | 5 + ecc-448.c | 273 ++ ecc-521.c | 5 + ecc-add-eh.c | 74 +- ecc-add-ehh.c | 77 +- ecc-dup-eh.c | 55 +- ecc-eh-to-a.c | 4 +- ecc-internal.h | 57 +- ecc-mul-a-eh.c | 12 +- ecc-mul-g-eh.c | 4 +- ecc-point-mul-g.c | 7 +- ecc-point-mul.c | 2 +- ecc-point.c | 15 + eccdata.c | 183 +- ecdsa-keygen.c | 4 +- ed25519-sha512-sign.c | 15 + ed448-shake256-pubkey.c | 60 + ed448-shake256-sign.c | 92 + ed448-shake256-verify.c | 66 + eddsa-compress.c | 11 +- eddsa-decompress.c | 15 +- eddsa-expand.c | 20 +- eddsa-hash.c | 35 + eddsa-pubkey.c | 2 +- eddsa-sign.c | 18 +- eddsa-verify.c | 16 +- eddsa.h | 24 + examples/ecc-benchmark.c | 1 + nettle-internal.h | 2 +- nettle-meta-hashes.c | 2 + nettle-meta.h | 2 + nettle.texinfo | 152 +- sha3.c | 13 + sha3.h | 56 + shake128-meta.c | 42 + shake128.c | 84 + shake256-meta.c | 42 + shake256.c | 84 + testsuite/.test-rules.make | 12 + testsuite/Makefile.in | 5 +- testsuite/curve448-dh-test.c | 100 + testsuite/ecc-add-test.c | 48 +- testsuite/ecc-dup-test.c | 12 +- testsuite/ecc-mul-a-test.c | 6 +- testsuite/ecc-mul-g-test.c | 6 +- testsuite/ecdh-test.c | 16 +- testsuite/ecdsa-keygen-test.c | 16 + testsuite/ed448-test.c | 240 ++ testsuite/eddsa-compress-test.c | 137 +- testsuite/eddsa-sign-test.c | 66 +- testsuite/eddsa-verify-test.c | 49 +- testsuite/meta-hash-test.c | 2 + testsuite/shake.awk | 14 + testsuite/shake128-test.c | 6183 +++++++++++++++++++++++++++++++++++++++ testsuite/shake256-test.c | 6183 +++++++++++++++++++++++++++++++++++++++ testsuite/testutils.c | 57 +- 66 files changed, 14976 insertions(+), 199 deletions(-) create mode 100644 curve448-eh-to-x.c create mode 100644 curve448-mul-g.c create mode 100644 curve448-mul.c create mode 100644 curve448.h create mode 100644 ecc-448.c create mode 100644 ed448-shake256-pubkey.c create mode 100644 ed448-shake256-sign.c create mode 100644 ed448-shake256-verify.c create mode 100644 shake128-meta.c create mode 100644 shake128.c create mode 100644 shake256-meta.c create mode 100644 shake256.c create mode 100644 testsuite/curve448-dh-test.c create mode 100644 testsuite/ed448-test.c create mode 100755 testsuite/shake.awk create mode 100644 testsuite/shake128-test.c create mode 100644 testsuite/shake256-test.c -- 2.13.3

2 35

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

nettle-bugs January 2020