dbaryshkov@gmail.com writes:
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.
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 dbaryshkov@gmail.com Signed-off-by: Dmitry Baryshkov dbaryshkov@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 | 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 \@@ -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 \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 < q2. C <-- (c_x, c_y) = k g3. r <-- c_x mod q4. 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 Y6. 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