ecc: Implement Curve Ed25519 signing and verification.

* cipher/ecc-curves.c (domain_parms): Add curve "Ed25519".
* cipher/ecc.c (reverse_buffer): New.
(eddsa_encodempi): New.
(eddsa_encodepoint): New.
(eddsa_decodepoint): New.
(sign_eddsa): Implement.
(verify_eddsa): Implement.
(ecc_sign): Init unused Q.  Pass public key to sign_eddsa.
(ecc_verify): Init pk.Q if not used.  Pass public key verbatim to
verify_eddsa.
* cipher/pubkey.c (sexp_elements_extract): Add arg OPAQUE.  Change all
callers to pass 0.
(sexp_to_sig): Add arg OPAQUE and pass it to sexp_elements_extract.
(sexp_data_to_mpi): Allow for a zero length "value".
(gcry_pk_verify): Reorder parameter processing.  Pass OPAQUE flag as
required.
* mpi/ec.c (ec_invm): Print a warning if the inverse does not exist.
(_gcry_mpi_ec_get_affine): Implement for our Twisted Edwards curve
model.
(dup_point_twistededwards): Implement.
(add_points_twistededwards): Implement.
(_gcry_mpi_ec_mul_point): Support Twisted Edwards.

* mpi/mpicoder.c (do_get_buffer): Add arg FILL_LE.
(_gcry_mpi_get_buffer): Ditto.  Change all callers.
(_gcry_mpi_get_secure_buffer): Ditto.

* src/sexp.c (_gcry_sexp_nth_opaque_mpi): New.

* tests/t-ed25519.c: New.
* tests/t-ed25519.inp: New.
* tests/t-mpi-point.c (basic_ec_math_simplified): Print some output
only in debug mode.
(twistededwards_math): New test.
(main): Call new test.
--

This is a non optimized version which takes far too long.  On my X220
Thinkpad the 1024 test cases take 14 seconds (12 with --sign-with-pk).
There should be a lot of room for improvements.

Signed-off-by: Werner Koch <wk@gnupg.org>

1 files changed, 32 insertions, 13 deletions

diff --git a/cipher/pubkey.c b/cipher/pubkey.c
index 98e3074f..949c5382 100644
--- a/cipher/pubkey.c
+++ b/cipher/pubkey.c
@@ -1811,7 +1811,7 @@ pss_verify_cmp (void *opaque, gcry_mpi_t tmp)
 /* Internal function.   */
 static gcry_err_code_t
 sexp_elements_extract (gcry_sexp_t key_sexp, const char *element_names,
-		       gcry_mpi_t *elements, const char *algo_name)
+		       gcry_mpi_t *elements, const char *algo_name, int opaque)
 {
   gcry_err_code_t err = 0;
   int i, idx;
@@ -1823,6 +1823,13 @@ sexp_elements_extract (gcry_sexp_t key_sexp, const char *element_names,
       list = gcry_sexp_find_token (key_sexp, name, 1);
       if (!list)
 	elements[idx] = NULL;
+      else if (opaque)
+        {
+	  elements[idx] = _gcry_sexp_nth_opaque_mpi (list, 1);
+	  gcry_sexp_release (list);
+	  if (!elements[idx])
+	    err = GPG_ERR_INV_OBJ;
+        }
       else
 	{
 	  elements[idx] = gcry_sexp_nth_mpi (list, 1, GCRYMPI_FMT_USG);
@@ -2099,7 +2106,7 @@ sexp_to_key (gcry_sexp_t sexp, int want_private, int use,
         err = sexp_elements_extract_ecc (list, elems, array, extraspec,
                                          want_private);
       else
-        err = sexp_elements_extract (list, elems, array, pubkey->name);
+        err = sexp_elements_extract (list, elems, array, pubkey->name, 0);
     }
 
   gcry_sexp_release (list);
@@ -2124,9 +2131,12 @@ sexp_to_key (gcry_sexp_t sexp, int want_private, int use,
 }
 
 
+/* Parse SEXP and store the elements into a newly allocated array of
+   MPIs which will be stored at RETARRAY.  If OPAQUE is set, store the
+   MPI as opaque data.  */
 static gcry_err_code_t
 sexp_to_sig (gcry_sexp_t sexp, gcry_mpi_t **retarray,
-	     gcry_module_t *retalgo)
+	     gcry_module_t *retalgo, int opaque)
 {
   gcry_err_code_t err = 0;
   gcry_sexp_t list, l2;
@@ -2190,7 +2200,7 @@ sexp_to_sig (gcry_sexp_t sexp, gcry_mpi_t **retarray,
     err = gpg_err_code_from_syserror ();
 
   if (!err)
-    err = sexp_elements_extract (list, elems, array, NULL);
+    err = sexp_elements_extract (list, elems, array, NULL, opaque);
 
   gcry_sexp_release (l2);
   gcry_sexp_release (list);
@@ -2452,7 +2462,7 @@ sexp_to_enc (gcry_sexp_t sexp, gcry_mpi_t **retarray, gcry_module_t *retalgo,
       goto leave;
     }
 
-  err = sexp_elements_extract (list, elems, array, NULL);
+  err = sexp_elements_extract (list, elems, array, NULL, 0);
 
  leave:
   gcry_sexp_release (list);
@@ -2616,7 +2626,15 @@ sexp_data_to_mpi (gcry_sexp_t input, gcry_mpi_t *ret_mpi,
       /* Get VALUE.  */
       value = gcry_sexp_nth_buffer (lvalue, 1, &valuelen);
       if (!value)
-        rc = GPG_ERR_INV_OBJ;
+        {
+          /* We assume that a zero length message is meant by
+             "(value)".  This is commonly used by test vectors.  Note
+             that S-expression do not allow zero length items. */
+          valuelen = 0;
+          value = gcry_malloc (1);
+          if (!value)
+            rc = gpg_err_code_from_syserror ();
+        }
       else if ((valuelen * 8) < valuelen)
         {
           gcry_free (value);
@@ -3445,10 +3463,17 @@ gcry_pk_verify (gcry_sexp_t s_sig, gcry_sexp_t s_hash, gcry_sexp_t s_pkey)
   if (rc)
     goto leave;
 
-  rc = sexp_to_sig (s_sig, &sig, &module_sig);
+  /* Get the stuff we want to verify. */
+  init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY, gcry_pk_get_nbits (s_pkey));
+  rc = sexp_data_to_mpi (s_hash, &hash, &ctx);
   if (rc)
     goto leave;
 
+  /* Get the signature.  */
+  rc = sexp_to_sig (s_sig, &sig, &module_sig,
+                    !!(ctx.flags & PUBKEY_FLAG_EDDSA));
+  if (rc)
+    goto leave;
   /* Fixme: Check that the algorithm of S_SIG is compatible to the one
      of S_PKEY.  */
 
@@ -3458,12 +3483,6 @@ gcry_pk_verify (gcry_sexp_t s_sig, gcry_sexp_t s_hash, gcry_sexp_t s_pkey)
       goto leave;
     }
 
-  /* Get the stuff we want to verify. */
-  init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY, gcry_pk_get_nbits (s_pkey));
-  rc = sexp_data_to_mpi (s_hash, &hash, &ctx);
-  if (rc)
-    goto leave;
-
   rc = pubkey_verify (module_key->mod_id, hash, sig, pkey, &ctx);
 
  leave: