[PATCH 3/3] Add support for GOST R 34.10-2001/-2012 signatures
Dmitry Eremin-Solenikov
dbaryshkov at gmail.com
Thu Sep 26 14:07:43 CEST 2013
* src/cipher.h: define PUBKEY_FLAG_GOST
* cipher/ecc-curves.c: add GOST2001-test and GOST2012-test curves
defined in standards. Typical applications would use either those
curves, or curves defined in RFC 4357 (will be added later).
* cipher/ecc.c (sign_gost, verify_gost): New.
(ecc_sign, ecc_verify): use sign_gost/verify_gost if PUBKEY_FLAG_GOST
is set.
(ecc_names): add "gost" for gost signatures.
* cipher/pubkey.c (sexp_data_to_mpi): set PUBKEY_FLAG_GOST if gost flag
is present in s-exp.
* tests/benchmark.c (ecc_bench): also benchmark GOST signatures.
* tests/basic.c (check_pubkey): add two public keys from
GOST R 34.10-2012 standard.
(check_pubkey_sign_ecdsa): add two data sets to check gost signatures.
Signed-off-by: Dmitry Eremin-Solenikov <dbaryshkov at gmail.com>
---
cipher/ecc-curves.c | 28 +++++++
cipher/ecc.c | 218 ++++++++++++++++++++++++++++++++++++++++++++++++++++
cipher/pubkey.c | 5 ++
src/cipher.h | 1 +
tests/basic.c | 75 ++++++++++++++++++
tests/benchmark.c | 17 +++-
6 files changed, 343 insertions(+), 1 deletion(-)
diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index 7447340..05fca05 100644
--- a/cipher/ecc-curves.c
+++ b/cipher/ecc-curves.c
@@ -263,6 +263,34 @@ static const ecc_domain_parms_t domain_parms[] =
"0x7dde385d566332ecc0eabfa9cf7822fdf209f70024a57b1aa000c55b881f8111"
"b2dcde494a5f485e5bca4bd88a2763aed1ca2b2fa8f0540678cd1e0f3ad80892"
},
+ {
+ "GOST2001-test", 256, 0,
+ MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD,
+ "0x8000000000000000000000000000000000000000000000000000000000000431", /* p */
+ "0x0000000000000000000000000000000000000000000000000000000000000007", /* a */
+ "0x5fbff498aa938ce739b8e022fbafef40563f6e6a3472fc2a514c0ce9dae23b7e", /* b */
+ "0x8000000000000000000000000000000150fe8a1892976154c59cfc193accf5b3", /* q */
+
+ "0x0000000000000000000000000000000000000000000000000000000000000002", /* x */
+ "0x08e2a8a0e65147d4bd6316030e16d19c85c97f0a9ca267122b96abbcea7e8fc8", /* y */
+ },
+
+ {
+ "GOST2012-test", 511, 0,
+ MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD,
+ "0x4531acd1fe0023c7550d267b6b2fee80922b14b2ffb90f04d4eb7c09b5d2d15d"
+ "f1d852741af4704a0458047e80e4546d35b8336fac224dd81664bbf528be6373", /* p */
+ "0x0000000000000000000000000000000000000000000000000000000000000007", /* a */
+ "0x1cff0806a31116da29d8cfa54e57eb748bc5f377e49400fdd788b649eca1ac4"
+ "361834013b2ad7322480a89ca58e0cf74bc9e540c2add6897fad0a3084f302adc", /* b */
+ "0x4531acd1fe0023c7550d267b6b2fee80922b14b2ffb90f04d4eb7c09b5d2d15d"
+ "a82f2d7ecb1dbac719905c5eecc423f1d86e25edbe23c595d644aaf187e6e6df", /* q */
+
+ "0x24d19cc64572ee30f396bf6ebbfd7a6c5213b3b3d7057cc825f91093a68cd762"
+ "fd60611262cd838dc6b60aa7eee804e28bc849977fac33b4b530f1b120248a9a", /* x */
+ "0x2bb312a43bd2ce6e0d020613c857acddcfbf061e91e5f2c3f32447c259f39b2"
+ "c83ab156d77f1496bf7eb3351e1ee4e43dc1a18b91b24640b6dbb92cb1add371e", /* y */
+ },
{ NULL, 0, 0, 0, 0, NULL, NULL, NULL, NULL }
};
diff --git a/cipher/ecc.c b/cipher/ecc.c
index abd501f..68a5a89 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -567,6 +567,203 @@ verify_ecdsa (gcry_mpi_t input, ECC_public_key *pkey,
return err;
}
+/* Compute an GOST R 34.10-01/-12 signature.
+ * Return the signature struct (r,s) from the message hash. The caller
+ * must have allocated R and S.
+ */
+static gpg_err_code_t
+sign_gost (gcry_mpi_t input, ECC_secret_key *skey, gcry_mpi_t r, gcry_mpi_t s)
+{
+ gpg_err_code_t err = 0;
+ gcry_mpi_t k, dr, sum, ke, x, e;
+ mpi_point_struct I;
+ gcry_mpi_t hash;
+ const void *abuf;
+ unsigned int abits, qbits;
+ mpi_ec_t ctx;
+
+ if (DBG_CIPHER)
+ log_mpidump ("gost sign hash ", input );
+
+ qbits = mpi_get_nbits (skey->E.n);
+
+ /* Convert the INPUT into an MPI if needed. */
+ if (mpi_is_opaque (input))
+ {
+ abuf = gcry_mpi_get_opaque (input, &abits);
+ err = gpg_err_code (gcry_mpi_scan (&hash, GCRYMPI_FMT_USG,
+ abuf, (abits+7)/8, NULL));
+ if (err)
+ return err;
+ if (abits > qbits)
+ gcry_mpi_rshift (hash, hash, abits - qbits);
+ }
+ else
+ hash = input;
+
+
+ k = NULL;
+ dr = mpi_alloc (0);
+ sum = mpi_alloc (0);
+ ke = mpi_alloc (0);
+ e = mpi_alloc (0);
+ x = mpi_alloc (0);
+ point_init (&I);
+
+ ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect,
+ skey->E.p, skey->E.a, skey->E.b);
+
+ mpi_mod (e, input, skey->E.n); /* e = hash mod n */
+
+ if (!mpi_cmp_ui (e, 0))
+ mpi_set_ui (e, 1);
+
+ /* Two loops to avoid R or S are zero. This is more of a joke than
+ a real demand because the probability of them being zero is less
+ than any hardware failure. Some specs however require it. */
+ do
+ {
+ do
+ {
+ mpi_free (k);
+ k = _gcry_dsa_gen_k (skey->E.n, GCRY_STRONG_RANDOM);
+
+ _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
+ if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
+ {
+ if (DBG_CIPHER)
+ log_debug ("ecc sign: Failed to get affine coordinates\n");
+ err = GPG_ERR_BAD_SIGNATURE;
+ goto leave;
+ }
+ mpi_mod (r, x, skey->E.n); /* r = x mod n */
+ }
+ while (!mpi_cmp_ui (r, 0));
+ mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n */
+ mpi_mulm (ke, k, e, skey->E.n); /* ke = k*e mod n */
+ mpi_addm (s, ke, dr, skey->E.n); /* sum = (k*e+ d*r) mod n */
+ }
+ while (!mpi_cmp_ui (s, 0));
+
+ if (DBG_CIPHER)
+ {
+ log_mpidump ("gost sign result r ", r);
+ log_mpidump ("gost sign result s ", s);
+ }
+
+ leave:
+ _gcry_mpi_ec_free (ctx);
+ point_free (&I);
+ mpi_free (x);
+ mpi_free (e);
+ mpi_free (ke);
+ mpi_free (sum);
+ mpi_free (dr);
+ mpi_free (k);
+
+ if (hash != input)
+ mpi_free (hash);
+
+ return err;
+}
+
+/* Verify a GOST R 34.10-01/-12 signature.
+ * Check if R and S verifies INPUT.
+ */
+static gpg_err_code_t
+verify_gost (gcry_mpi_t input, ECC_public_key *pkey,
+ gcry_mpi_t r, gcry_mpi_t s)
+{
+ gpg_err_code_t err = 0;
+ gcry_mpi_t e, x, z1, z2, v, rv, zero;
+ mpi_point_struct Q, Q1, Q2;
+ mpi_ec_t ctx;
+
+ if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
+ return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < r < n failed. */
+ if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
+ return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < s < n failed. */
+
+ x = mpi_alloc (0);
+ e = mpi_alloc (0);
+ z1 = mpi_alloc (0);
+ z2 = mpi_alloc (0);
+ v = mpi_alloc (0);
+ rv = mpi_alloc (0);
+ zero = mpi_alloc (0);
+
+ point_init (&Q);
+ point_init (&Q1);
+ point_init (&Q2);
+
+ ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect,
+ pkey->E.p, pkey->E.a, pkey->E.b);
+
+ mpi_mod (e, input, pkey->E.n); /* e = hash mod n */
+ if (!mpi_cmp_ui (e, 0))
+ mpi_set_ui (e, 1);
+ mpi_invm (v, e, pkey->E.n); /* v = e^(-1) (mod n) */
+ mpi_mulm (z1, s, v, pkey->E.n); /* z1 = s*v (mod n) */
+ mpi_mulm (rv, r, v, pkey->E.n); /* rv = s*v (mod n) */
+ mpi_subm (z2, zero, rv, pkey->E.n); /* z2 = -r*v (mod n) */
+
+ _gcry_mpi_ec_mul_point (&Q1, z1, &pkey->E.G, ctx);
+/* log_mpidump ("Q1.x", Q1.x); */
+/* log_mpidump ("Q1.y", Q1.y); */
+/* log_mpidump ("Q1.z", Q1.z); */
+ _gcry_mpi_ec_mul_point (&Q2, z2, &pkey->Q, ctx);
+/* log_mpidump ("Q2.x", Q2.x); */
+/* log_mpidump ("Q2.y", Q2.y); */
+/* log_mpidump ("Q2.z", Q2.z); */
+ _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
+/* log_mpidump (" Q.x", Q.x); */
+/* log_mpidump (" Q.y", Q.y); */
+/* log_mpidump (" Q.z", Q.z); */
+
+ if (!mpi_cmp_ui (Q.z, 0))
+ {
+ if (DBG_CIPHER)
+ log_debug ("ecc verify: Rejected\n");
+ err = GPG_ERR_BAD_SIGNATURE;
+ goto leave;
+ }
+ if (_gcry_mpi_ec_get_affine (x, NULL, &Q, ctx))
+ {
+ if (DBG_CIPHER)
+ log_debug ("ecc verify: Failed to get affine coordinates\n");
+ err = GPG_ERR_BAD_SIGNATURE;
+ goto leave;
+ }
+ mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
+ if (mpi_cmp (x, r)) /* x != r */
+ {
+ if (DBG_CIPHER)
+ {
+ log_mpidump (" x", x);
+ log_mpidump (" r", r);
+ log_mpidump (" s", s);
+ log_debug ("ecc verify: Not verified\n");
+ }
+ err = GPG_ERR_BAD_SIGNATURE;
+ goto leave;
+ }
+ if (DBG_CIPHER)
+ log_debug ("ecc verify: Accepted\n");
+
+ leave:
+ _gcry_mpi_ec_free (ctx);
+ point_free (&Q2);
+ point_free (&Q1);
+ point_free (&Q);
+ mpi_free (zero);
+ mpi_free (rv);
+ mpi_free (v);
+ mpi_free (z2);
+ mpi_free (z1);
+ mpi_free (x);
+ mpi_free (e);
+ return err;
+}
static void
@@ -1511,6 +1708,13 @@ ecc_sign (int algo, gcry_sexp_t *r_result, gcry_mpi_t data, gcry_mpi_t *skey,
rc = gcry_sexp_build (r_result, NULL,
"(sig-val(eddsa(r%M)(s%M)))", r, s);
}
+ else if ((flags & PUBKEY_FLAG_GOST))
+ {
+ rc = sign_gost (data, &sk, r, s);
+ if (!rc)
+ rc = gcry_sexp_build (r_result, NULL,
+ "(sig-val(gost(r%M)(s%M)))", r, s);
+ }
else
{
rc = sign_ecdsa (data, &sk, r, s, flags, hashalgo);
@@ -1578,6 +1782,19 @@ ecc_verify (int algo, gcry_mpi_t hash, gcry_mpi_t *data, gcry_mpi_t *pkey,
err = verify_eddsa (hash, &pk, data[0], data[1], hashalgo, pkey[5]);
}
+ else if ((flags & PUBKEY_FLAG_GOST))
+ {
+ point_init (&pk.Q);
+ err = _gcry_ecc_os2ec (&pk.Q, pkey[5]);
+ if (err)
+ {
+ point_free (&pk.E.G);
+ point_free (&pk.Q);
+ return err;
+ }
+
+ err = verify_gost (hash, &pk, data[0], data[1]);
+ }
else
{
point_init (&pk.Q);
@@ -2085,6 +2302,7 @@ static const char *ecc_names[] =
"ecdsa",
"ecdh",
"eddsa",
+ "gost",
NULL,
};
diff --git a/cipher/pubkey.c b/cipher/pubkey.c
index 4738c29..d247a67 100644
--- a/cipher/pubkey.c
+++ b/cipher/pubkey.c
@@ -1001,6 +1001,11 @@ sexp_data_to_mpi (gcry_sexp_t input, gcry_mpi_t *ret_mpi,
ctx->encoding = PUBKEY_ENC_RAW;
parsed_flags |= PUBKEY_FLAG_EDDSA;
}
+ else if (n == 4 && !memcmp (s, "gost", 4))
+ {
+ ctx->encoding = PUBKEY_ENC_RAW;
+ parsed_flags |= PUBKEY_FLAG_GOST;
+ }
else if ( n == 3 && !memcmp (s, "raw", 3)
&& ctx->encoding == PUBKEY_ENC_UNKNOWN)
{
diff --git a/src/cipher.h b/src/cipher.h
index ea7a141..fcd43a8 100644
--- a/src/cipher.h
+++ b/src/cipher.h
@@ -31,6 +31,7 @@
#define PUBKEY_FLAG_EDDSA (1 << 2)
#define PUBKEY_FLAG_FIXEDLEN (1 << 3)
#define PUBKEY_FLAG_LEGACYRESULT (1 << 4)
+#define PUBKEY_FLAG_GOST (1 << 5)
enum pk_operation
{
diff --git a/tests/basic.c b/tests/basic.c
index 9ce684b..b664de5 100644
--- a/tests/basic.c
+++ b/tests/basic.c
@@ -3438,6 +3438,30 @@ check_pubkey_sign_ecdsa (int n, gcry_sexp_t skey, gcry_sexp_t pkey)
/* */ "000102030405060708090A0B0C0D0E0F#))",
0
},
+ { 256,
+ "(data (flags gost)\n"
+ " (value #00112233445566778899AABBCCDDEEFF"
+ /* */ "000102030405060708090A0B0C0D0E0F#))",
+ 0,
+ "(data (flags gost)\n"
+ " (value #80112233445566778899AABBCCDDEEFF"
+ /* */ "000102030405060708090A0B0C0D0E0F#))",
+ 0
+ },
+ { 512,
+ "(data (flags gost)\n"
+ " (value #00112233445566778899AABBCCDDEEFF"
+ /* */ "000102030405060708090A0B0C0D0E0F"
+ /* */ "000102030405060708090A0B0C0D0E0F"
+ /* */ "000102030405060708090A0B0C0D0E0F#))",
+ 0,
+ "(data (flags gost)\n"
+ " (value #80112233445566778899AABBCCDDEEFF"
+ /* */ "000102030405060708090A0B0C0D0E0F"
+ /* */ "000102030405060708090A0B0C0D0E0F"
+ /* */ "000102030405060708090A0B0C0D0E0F#))",
+ 0
+ },
{ 0, NULL }
};
@@ -4023,6 +4047,57 @@ check_pubkey (void)
"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
"\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00" }
+ },
+ { /* GOST R 34.10-2001/2012 test 256 bit. */
+ GCRY_PK_ECDSA, FLAG_SIGN,
+ {
+ "(private-key\n"
+ " (ecc\n"
+ " (curve GOST2001-test)\n"
+ " (q #047F2B49E270DB6D90D8595BEC458B50C58585BA1D4E9B78"
+ " 8F6689DBD8E56FD80B26F1B489D6701DD185C8413A977B3C"
+ " BBAF64D1C593D26627DFFB101A87FF77DA#)\n"
+ " (d #7A929ADE789BB9BE10ED359DD39A72C11B60961F49397EEE"
+ " 1D19CE9891EC3B28#)))\n",
+
+ "(public-key\n"
+ " (ecc\n"
+ " (curve GOST2001-test)\n"
+ " (q #047F2B49E270DB6D90D8595BEC458B50C58585BA1D4E9B78"
+ " 8F6689DBD8E56FD80B26F1B489D6701DD185C8413A977B3C"
+ " BBAF64D1C593D26627DFFB101A87FF77DA#)))\n",
+
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00" }
+ },
+ { /* GOST R 34.10-2012 test 512 bit. */
+ GCRY_PK_ECDSA, FLAG_SIGN,
+ {
+ "(private-key\n"
+ " (ecc\n"
+ " (curve GOST2012-test)\n"
+ " (q #04115DC5BC96760C7B48598D8AB9E740D4C4A85A65BE33C1"
+ " 815B5C320C854621DD5A515856D13314AF69BC5B924C8B"
+ " 4DDFF75C45415C1D9DD9DD33612CD530EFE137C7C90CD4"
+ " 0B0F5621DC3AC1B751CFA0E2634FA0503B3D52639F5D7F"
+ " B72AFD61EA199441D943FFE7F0C70A2759A3CDB84C114E"
+ " 1F9339FDF27F35ECA93677BEEC#)\n"
+ " (d #0BA6048AADAE241BA40936D47756D7C93091A0E851466970"
+ " 0EE7508E508B102072E8123B2200A0563322DAD2827E2714"
+ " A2636B7BFD18AADFC62967821FA18DD4#)))\n",
+
+ "(public-key\n"
+ " (ecc\n"
+ " (curve GOST2001-test)\n"
+ " (q #04115DC5BC96760C7B48598D8AB9E740D4C4A85A65BE33C1"
+ " 815B5C320C854621DD5A515856D13314AF69BC5B924C8B"
+ " 4DDFF75C45415C1D9DD9DD33612CD530EFE137C7C90CD4"
+ " 0B0F5621DC3AC1B751CFA0E2634FA0503B3D52639F5D7F"
+ " B72AFD61EA199441D943FFE7F0C70A2759A3CDB84C114E"
+ " 1F9339FDF27F35ECA93677BEEC#)))\n"
+
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"
+ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00" }
}
};
int i;
diff --git a/tests/benchmark.c b/tests/benchmark.c
index 5d1434a..ecda0d3 100644
--- a/tests/benchmark.c
+++ b/tests/benchmark.c
@@ -883,7 +883,8 @@ ecc_bench (int iterations, int print_header)
{
#if USE_ECC
gpg_error_t err;
- const char *p_sizes[] = { "192", "224", "256", "384", "521", "Ed25519" };
+ const char *p_sizes[] = { "192", "224", "256", "384", "521", "Ed25519",
+ "gost256", "gost512" };
int testno;
if (print_header)
@@ -899,14 +900,22 @@ ecc_bench (int iterations, int print_header)
int count;
int p_size;
int is_ed25519;
+ int is_gost;
is_ed25519 = !strcmp (p_sizes[testno], "Ed25519");
+ is_gost = !strncmp (p_sizes[testno], "gost", 4);
if (is_ed25519)
{
p_size = 256;
printf ("EdDSA Ed25519 ");
fflush (stdout);
}
+ else if (is_gost)
+ {
+ p_size = atoi (p_sizes[testno] + 4);
+ printf ("GOST %3d bit ", p_size);
+ fflush (stdout);
+ }
else
{
p_size = atoi (p_sizes[testno]);
@@ -917,6 +926,10 @@ ecc_bench (int iterations, int print_header)
if (is_ed25519)
err = gcry_sexp_build (&key_spec, NULL,
"(genkey (ecdsa (curve \"Ed25519\")))");
+ else if (is_gost)
+ err = gcry_sexp_build (&key_spec, NULL,
+ "(genkey (ecdsa (curve %s)))",
+ p_size == 256 ? "GOST2001-test" : "GOST2012-test");
else
err = gcry_sexp_build (&key_spec, NULL,
"(genkey (ECDSA (nbits %d)))", p_size);
@@ -950,6 +963,8 @@ ecc_bench (int iterations, int print_header)
err = gcry_sexp_build (&data, NULL,
"(data (flags eddsa)(hash-algo sha512)"
" (value %m))", x);
+ else if (is_gost)
+ err = gcry_sexp_build (&data, NULL, "(data (flags gost) (value %m))", x);
else
err = gcry_sexp_build (&data, NULL, "(data (flags raw) (value %m))", x);
gcry_mpi_release (x);
--
1.8.4.rc3
More information about the Gcrypt-devel
mailing list