ecc: Change algorithm for Ed25519 x recovery.

* cipher/ecc-eddsa.c (scanval): Add as temporary hack.
(_gcry_ecc_eddsa_recover_x): Use the algorithm from page 15 of the
paper.  Return an error code.
(_gcry_ecc_eddsa_decodepoint): Take care of the error code.
* mpi/mpi-mul.c (gcry_mpi_mulm): Use truncated division.

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

4 files changed, 111 insertions, 60 deletions

diff --git a/cipher/ecc-common.h b/cipher/ecc-common.h
index e451f8d8..93fd449e 100644
--- a/cipher/ecc-common.h
+++ b/cipher/ecc-common.h
@@ -97,8 +97,8 @@ gpg_err_code_t _gcry_ecc_ecdsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
                                        gcry_mpi_t r, gcry_mpi_t s);
 
 /*-- ecc-eddsa.c --*/
-void _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign,
-                                mpi_ec_t ec);
+gpg_err_code_t _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign,
+                                          mpi_ec_t ec);
 gpg_err_code_t _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ctx,
                                             gcry_mpi_t x, gcry_mpi_t y,
                                             unsigned char **r_buffer,
diff --git a/cipher/ecc-eddsa.c b/cipher/ecc-eddsa.c
index 4a9fe0a5..22f27023 100644
--- a/cipher/ecc-eddsa.c
+++ b/cipher/ecc-eddsa.c
@@ -46,6 +46,20 @@ reverse_buffer (unsigned char *buffer, unsigned int length)
 }
 
 
+/* Helper to scan a hex string. */
+static gcry_mpi_t
+scanval (const char *string)
+{
+  gpg_error_t err;
+  gcry_mpi_t val;
+
+  err = gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL);
+  if (err)
+    log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (err));
+  return val;
+}
+
+
 
 /* Encode MPI using the EdDSA scheme.  MINLEN specifies the required
    length of the buffer in bytes.  On success 0 is returned an a
@@ -122,61 +136,82 @@ _gcry_ecc_eddsa_encodepoint (mpi_point_t point, mpi_ec_t ec,
 }
 
 
-/* Recover X from Y and SIGN .  */
-void
+/* Recover X from Y and SIGN (which actually is a parity bit).  */
+gpg_err_code_t
 _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
 {
-  /* FIXME: This algorithm can be improved - see the paper.
-     sqrt(-1) mod ed255519_p:
-       2B8324804FC1DF0B2B4D00993DFBD7A72F431806AD2FE478C4EE1B274A0EA0B0 */
-  gcry_mpi_t yy, t, p1, p2, p3;
-
-  /* t = (y^2-1) · ((b*y^2+1)^{p-2} mod p) */
-  yy = mpi_new (0);
-  mpi_mul (yy, y, y);
-  t = mpi_copy (yy);
-  mpi_mul (t, t, ec->b);
-  mpi_add_ui (t, t, 1);
-  p2 = mpi_copy (ec->p);
-  mpi_sub_ui (p2, p2, 2);
-  mpi_powm (t, t, p2, ec->p);
-
-  mpi_sub_ui (yy, yy, 1);
-  mpi_mul (t, yy, t);
-
-  /* x = t^{(p+3)/8} mod p */
-  p3 = mpi_copy (ec->p);
-  mpi_add_ui (p3, p3, 3);
-  mpi_fdiv_q (p3, p3, mpi_const (MPI_C_EIGHT));
-  mpi_powm (x, t, p3, ec->p);
-
-  /* (x^2 - t) % p != 0 ? x = (x*(2^{(p-1)/4} mod p)) % p */
-  mpi_mul (yy, x, x);
-  mpi_subm (yy, yy, t, ec->p);
-  if (mpi_cmp_ui (yy, 0))
+  gpg_err_code_t rc = 0;
+  gcry_mpi_t u, v, v3, t;
+  static gcry_mpi_t p58, seven;
+
+  if (ec->dialect != ECC_DIALECT_ED25519)
+    return GPG_ERR_NOT_IMPLEMENTED;
+
+  if (!p58)
+    p58 = scanval ("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+                   "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD");
+  if (!seven)
+    seven = mpi_set_ui (NULL, 7);
+
+  u   = mpi_new (0);
+  v   = mpi_new (0);
+  v3  = mpi_new (0);
+  t   = mpi_new (0);
+
+  /* Compute u and v */
+  /* u = y^2    */
+  mpi_mulm (u, y, y, ec->p);
+  /* v = b*y^2   */
+  mpi_mulm (v, ec->b, u, ec->p);
+  /* u = y^2-1  */
+  mpi_sub_ui (u, u, 1);
+  /* v = b*y^2+1 */
+  mpi_add_ui (v, v, 1);
+
+  /* Compute sqrt(u/v) */
+  /* v3 = v^3 */
+  mpi_powm (v3, v, mpi_const (MPI_C_THREE), ec->p);
+  /* t = v3 * v3 * u * v = u * v^7 */
+  mpi_powm (t, v, seven, ec->p);
+  mpi_mulm (t, t, u, ec->p);
+  /* t = t^((p-5)/8) = (u * v^7)^((p-5)/8)  */
+  mpi_powm (t, t, p58, ec->p);
+  /* x = t * u * v^3 = (u * v^3) * (u * v^7)^((p-5)/8) */
+  mpi_mulm (t, t, u, ec->p);
+  mpi_mulm (x, t, v3, ec->p);
+
+  /* Adjust if needed.  */
+  /* t = v * x^2  */
+  mpi_mulm (t, x, x, ec->p);
+  mpi_mulm (t, t, v, ec->p);
+  /* -t == u ? x = x * sqrt(-1) */
+  gcry_mpi_neg (t, t);
+  if (!mpi_cmp (t, u))
     {
-      p1 = mpi_copy (ec->p);
-      mpi_sub_ui (p1, p1, 1);
-      mpi_fdiv_q (p1, p1, mpi_const (MPI_C_FOUR));
-      mpi_powm (yy, mpi_const (MPI_C_TWO), p1, ec->p);
-      mpi_mulm (x, x, yy, ec->p);
+      static gcry_mpi_t m1;  /* Fixme: this is not thread-safe.  */
+      if (!m1)
+        m1 = scanval ("2B8324804FC1DF0B2B4D00993DFBD7A7"
+                      "2F431806AD2FE478C4EE1B274A0EA0B0");
+      mpi_mulm (x, x, m1, ec->p);
+      /* t = v * x^2  */
+      mpi_mulm (t, x, x, ec->p);
+      mpi_mulm (t, t, v, ec->p);
+      /* -t == u ? x = x * sqrt(-1) */
+      gcry_mpi_neg (t, t);
+      if (!mpi_cmp (t, u))
+        rc = GPG_ERR_INV_OBJ;
     }
-  else
-    p1 = NULL;
 
-  /* is_odd(x) ? x = p-x */
-  if (mpi_test_bit (x, 0))
-    mpi_sub (x, ec->p, x);
+  /* Choose the desired square root according to parity */
+  if (mpi_test_bit (x, 0) != !!sign)
+    gcry_mpi_neg (x, x);
 
-  /* lowbit(x) != sign ?  x = p-x */
-  if (mpi_test_bit (x, 0) != sign)
-    mpi_sub (x, ec->p, x);
+  mpi_free (t);
+  mpi_free (v3);
+  mpi_free (v);
+  mpi_free (u);
 
-  gcry_mpi_release (yy);
-  gcry_mpi_release (t);
-  gcry_mpi_release (p3);
-  gcry_mpi_release (p2);
-  gcry_mpi_release (p1);
+  return rc;
 }
 
 
@@ -278,10 +313,10 @@ _gcry_ecc_eddsa_decodepoint (gcry_mpi_t pk, mpi_ec_t ctx, mpi_point_t result,
   else
     gcry_free (rawmpi);
 
-  _gcry_ecc_eddsa_recover_x (result->x, result->y, sign, ctx);
+  rc = _gcry_ecc_eddsa_recover_x (result->x, result->y, sign, ctx);
   mpi_set_ui (result->z, 1);
 
-  return 0;
+  return rc;
 }
 
 
diff --git a/mpi/mpi-mul.c b/mpi/mpi-mul.c
index ec6aea05..0a687116 100644
--- a/mpi/mpi-mul.c
+++ b/mpi/mpi-mul.c
@@ -208,5 +208,5 @@ void
 gcry_mpi_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, gcry_mpi_t m)
 {
   gcry_mpi_mul (w, u, v);
-  _gcry_mpi_mod (w, w, m);
+  _gcry_mpi_tdiv_r (w, w, m);
 }
diff --git a/tests/t-ed25519.c b/tests/t-ed25519.c
index 0a6ae148..be200fa4 100644
--- a/tests/t-ed25519.c
+++ b/tests/t-ed25519.c
@@ -53,6 +53,7 @@ static int debug;
 static int error_count;
 static int sign_with_pk;
 static int no_verify;
+static int custom_data_file;
 
 static void
 die (const char *format, ...)
@@ -405,9 +406,8 @@ one_test (int testno, const char *sk, const char *pk,
 
 
 static void
-check_ed25519 (void)
+check_ed25519 (const char *fname)
 {
-  char *fname;
   FILE *fp;
   int lineno, ntests;
   char *line;
@@ -416,7 +416,6 @@ check_ed25519 (void)
 
   show ("Checking Ed25519.\n");
 
-  fname = prepend_srcdir ("t-ed25519.inp");
   fp = fopen (fname, "r");
   if (!fp)
     die ("error opening '%s': %s\n", fname, strerror (errno));
@@ -459,13 +458,12 @@ check_ed25519 (void)
   xfree (msg);
   xfree (sig);
 
-  if (ntests != N_TESTS)
+  if (ntests != N_TESTS && !custom_data_file)
     fail ("did %d tests but expected %d", ntests, N_TESTS);
   else if ((ntests % 256))
     show_note ("%d tests done\n", ntests);
 
   fclose (fp);
-  xfree (fname);
 }
 
 
@@ -473,6 +471,7 @@ int
 main (int argc, char **argv)
 {
   int last_argc = -1;
+  char *fname = NULL;
 
   if (argc)
     { argc--; argv++; }
@@ -492,7 +491,8 @@ main (int argc, char **argv)
                  "  --verbose       print timings etc.\n"
                  "  --debug         flyswatter\n"
                  "  --sign-with-pk  also use the public key for signing\n"
-                 "  --no-verify     skip the verify test\n",
+                 "  --no-verify     skip the verify test\n"
+                 "  --data FNAME    take test data from file FNAME\n",
                  stdout);
           exit (0);
         }
@@ -517,11 +517,25 @@ main (int argc, char **argv)
           no_verify = 1;
           argc--; argv++;
         }
+      else if (!strcmp (*argv, "--data"))
+        {
+          argc--; argv++;
+          if (argc)
+            {
+              xfree (fname);
+              fname = xstrdup (*argv);
+              argc--; argv++;
+            }
+        }
       else if (!strncmp (*argv, "--", 2))
         die ("unknown option '%s'", *argv);
 
     }
 
+  if (!fname)
+    fname = prepend_srcdir ("t-ed25519.inp");
+  else
+    custom_data_file = 1;
 
   gcry_control (GCRYCTL_DISABLE_SECMEM, 0);
   if (!gcry_check_version (GCRYPT_VERSION))
@@ -532,9 +546,11 @@ main (int argc, char **argv)
   gcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0);
 
   start_timer ();
-  check_ed25519 ();
+  check_ed25519 (fname);
   stop_timer ();
 
+  xfree (fname);
+
   show ("All tests completed in %s.  Errors: %d\n",
         elapsed_time (), error_count);
   return !!error_count;