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>

1 files changed, 85 insertions, 50 deletions

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;
 }