[email protected] writes: > From: Dmitry Eremin-Solenikov <[email protected]> > > 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.
I've merged the first two patches to a branch ecc-gost. A few comments on the signature implementation. > Signed-off-by: Dmitry Eremin-Solenikov <[email protected]> > Signed-off-by: Dmitry Baryshkov <[email protected]> > --- > 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 | 102 +++++++++++++++++++++ > testsuite/.gitignore | 3 + > testsuite/.test-rules.make | 9 ++ > testsuite/Makefile.in | 4 +- > testsuite/gostdsa-keygen-test.c | 154 ++++++++++++++++++++++++++++++++ > testsuite/gostdsa-sign-test.c | 87 ++++++++++++++++++ > testsuite/gostdsa-verify-test.c | 110 +++++++++++++++++++++++ > testsuite/testutils.h | 1 + > 15 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 a08dfe4da481..1396e2fe2808 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 > +/* 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. > + */ So no modular inversion in the signature operation? That's an improvement over NIST's DSA and ECDSA. > 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 > +/* 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); Comment about faster primitives applies particularly to this modular inversion. Using mpn_gcdext, which isn't side-channel silent, is likely significantly faster (but a bit different interface). Would be interesting to add to hogweed-benchmark, to compare to other ecc signatures. > 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); > +} It looks a bit strange to truncate the digest in this function, but I see that's the same as ecc_hash just above. Do you need to also handle the case of left-over bits, 8*length > m->bit_size? Are the details very specific to gost, or could the helper be renamed ecc_hash_le ? What are typical values of length, compared to the prime size? > --- /dev/null > +++ b/gostdsa.h > @@ -0,0 +1,102 @@ [...] > + > +/* Development of Nettle's ECC support was funded by the .SE Internet Fund. > */ Left-over note? > 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" Drop include, if nothing in testutils.h or testutils.c need gostdsa types. Regard, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677. Internet email is subject to wholesale government surveillance. _______________________________________________ nettle-bugs mailing list [email protected] http://lists.lysator.liu.se/mailman/listinfo/nettle-bugs
