ecc: Add support for GOST R 34.10-2001/-2012 signatures
authorDmitry Eremin-Solenikov <dbaryshkov@gmail.com>
Tue, 15 Oct 2013 19:56:44 +0000 (23:56 +0400)
committerWerner Koch <wk@gnupg.org>
Wed, 16 Oct 2013 14:31:07 +0000 (16:31 +0200)
* 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-util.c (_gcry_pk_util_parse_flaglist,
  _gcry_pk_util_preparse_sigval): 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.
* tests/curves.c: correct N_CURVES as we now have 2 more curves.

Signed-off-by: Dmitry Eremin-Solenikov <dbaryshkov@gmail.com>
Removed some comments from the new curve definitions in ecc-curves.c
to avoid line wrapping.  Eventually we will develop a precompiler to
avoid parsing those hex strings. -wk

cipher/ecc-curves.c
cipher/ecc.c
cipher/pubkey-util.c
src/cipher.h
tests/basic.c
tests/benchmark.c
tests/curves.c

index 2cdb9b4..fb0db3b 100644 (file)
@@ -267,6 +267,34 @@ static const ecc_domain_parms_t domain_parms[] =
       "0x7dde385d566332ecc0eabfa9cf7822fdf209f70024a57b1aa000c55b881f8111"
       "b2dcde494a5f485e5bca4bd88a2763aed1ca2b2fa8f0540678cd1e0f3ad80892"
     },
+    {
+      "GOST2001-test", 256, 0,
+      MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD,
+      "0x8000000000000000000000000000000000000000000000000000000000000431",
+      "0x0000000000000000000000000000000000000000000000000000000000000007",
+      "0x5fbff498aa938ce739b8e022fbafef40563f6e6a3472fc2a514c0ce9dae23b7e",
+      "0x8000000000000000000000000000000150fe8a1892976154c59cfc193accf5b3",
+
+      "0x0000000000000000000000000000000000000000000000000000000000000002",
+      "0x08e2a8a0e65147d4bd6316030e16d19c85c97f0a9ca267122b96abbcea7e8fc8",
+    },
+
+    {
+      "GOST2012-test", 511, 0,
+      MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD,
+      "0x4531acd1fe0023c7550d267b6b2fee80922b14b2ffb90f04d4eb7c09b5d2d15d"
+      "f1d852741af4704a0458047e80e4546d35b8336fac224dd81664bbf528be6373",
+      "0x0000000000000000000000000000000000000000000000000000000000000007",
+      "0x1cff0806a31116da29d8cfa54e57eb748bc5f377e49400fdd788b649eca1ac4"
+      "361834013b2ad7322480a89ca58e0cf74bc9e540c2add6897fad0a3084f302adc",
+      "0x4531acd1fe0023c7550d267b6b2fee80922b14b2ffb90f04d4eb7c09b5d2d15d"
+      "a82f2d7ecb1dbac719905c5eecc423f1d86e25edbe23c595d644aaf187e6e6df",
+
+      "0x24d19cc64572ee30f396bf6ebbfd7a6c5213b3b3d7057cc825f91093a68cd762"
+      "fd60611262cd838dc6b60aa7eee804e28bc849977fac33b4b530f1b120248a9a",
+      "0x2bb312a43bd2ce6e0d020613c857acddcfbf061e91e5f2c3f32447c259f39b2"
+      "c83ab156d77f1496bf7eb3351e1ee4e43dc1a18b91b24640b6dbb92cb1add371e",
+    },
 
     { NULL, 0, 0, 0, 0, NULL, NULL, NULL, NULL }
   };
index 1323d00..8b61ae4 100644 (file)
@@ -71,6 +71,7 @@ static const char *ecc_names[] =
     "ecdsa",
     "ecdh",
     "eddsa",
+    "gost",
     NULL,
   };
 
@@ -575,6 +576,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;
+}
 
 \f
 static void
@@ -1623,6 +1821,13 @@ ecc_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms)
         rc = gcry_sexp_build (r_sig, NULL,
                               "(sig-val(eddsa(r%M)(s%M)))", sig_r, sig_s);
     }
+  else if ((ctx.flags & PUBKEY_FLAG_GOST))
+    {
+      rc = sign_gost (data, &sk, sig_r, sig_s);
+      if (!rc)
+        rc = gcry_sexp_build (r_sig, NULL,
+                              "(sig-val(gost(r%M)(s%M)))", sig_r, sig_s);
+    }
   else
     {
       rc = sign_ecdsa (data, &sk, sig_r, sig_s, ctx.flags, ctx.hash_algo);
@@ -1773,6 +1978,15 @@ ecc_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t s_keyparms)
     {
       rc = verify_eddsa (data, &pk, sig_r, sig_s, ctx.hash_algo, mpi_q);
     }
+  else if ((sigflags & PUBKEY_FLAG_GOST))
+    {
+      point_init (&pk.Q);
+      rc = _gcry_ecc_os2ec (&pk.Q, mpi_q);
+      if (rc)
+        goto leave;
+
+      rc = verify_gost (data, &pk, sig_r, sig_s);
+    }
   else
     {
       point_init (&pk.Q);
index 0b90054..0db5840 100644 (file)
@@ -79,6 +79,11 @@ _gcry_pk_util_parse_flaglist (gcry_sexp_t list,
         {
           flags |= PUBKEY_FLAG_ECDSA;
         }
+      else if (n == 4 && !memcmp (s, "gost", 4))
+        {
+          encoding = PUBKEY_ENC_RAW;
+          flags |= PUBKEY_FLAG_GOST;
+        }
       else if (n == 3 && !memcmp (s, "raw", 3)
                && encoding == PUBKEY_ENC_UNKNOWN)
         {
@@ -347,6 +352,8 @@ _gcry_pk_util_preparse_sigval (gcry_sexp_t s_sig, const char **algo_names,
     {
       if (!strcmp (name, "eddsa"))
         *r_eccflags = PUBKEY_FLAG_EDDSA;
+      if (!strcmp (name, "gost"))
+        *r_eccflags = PUBKEY_FLAG_GOST;
     }
 
   *r_parms = l2;
index 077af98..20818ba 100644 (file)
@@ -37,6 +37,7 @@
 #define PUBKEY_FLAG_USE_FIPS186_2  (1 << 8)
 #define PUBKEY_FLAG_ECDSA          (1 << 9)
 #define PUBKEY_FLAG_EDDSA          (1 << 10)
+#define PUBKEY_FLAG_GOST           (1 << 11)
 
 
 enum pk_operation
index 991309a..1d6e637 100644 (file)
@@ -3439,6 +3439,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 }
     };
 
@@ -4021,6 +4045,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;
index 5d1434a..ecda0d3 100644 (file)
@@ -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);
index 2c3ae53..198693e 100644 (file)
@@ -29,7 +29,7 @@
 #include "../src/gcrypt-int.h"
 
 /* Number of curves defined in ../cipger/ecc.c */
-#define N_CURVES 13
+#define N_CURVES 15
 
 /* A real world sample public key.  */
 static char const sample_key_1[] =