Got stuck with Ed25519

[NIIBE Yutaka]

On 2013-09-11 at 09:35 +0200, Werner Koch wrote:
> On Wed, 11 Sep 2013 02:44, gniibe at fsij.org said:
> 
> > Besides, it seems for me that mpi-pow.c has a bug when it is called
> > with negative base and expo is even (result is positive).  I don't
> > test it though.
> 
> I first thought the same but actually the sign is implementation
> defined.  http://en.wikipedia.org/wiki/Modulo_operation has a table
> describing this.  We should not change that because that would be an ABI
> change.  Instead I cleared the sign in ec_powm.

Thanks for the reference for modulo operation.  That's useful for me.

However, it is BASE (not MOD), which we are talking about, now.

Well, I wrote a test case to share the issue.  Here is a possible
patch.  In the test case, it calculates (-17)^6 mod 19.  Result should
be 7.  Mathematically, it's also correct for powm to return -12 in
this case, but it checks against positive 7.

In the current implementation it returns -7, which is wrong.


diff --git a/tests/mpitests.c b/tests/mpitests.c
index e1c51d1..ae206d7 100644
--- a/tests/mpitests.c
+++ b/tests/mpitests.c
@@ -379,6 +379,25 @@ test_powm (void)
   if (gcry_mpi_cmp (res, base))
     die ("test_powm failed at %d\n", __LINE__);
 
+  /* Check for a case: base is negative and expo is even.  */
+  gcry_mpi_set_ui (base, b_int);
+  gcry_mpi_neg (base, base);
+  gcry_mpi_set_ui (exp, e_int * 2);
+  gcry_mpi_set_ui(mod, m_int);
+  gcry_mpi_powm (res, base, exp, mod);
+  /* Result should be positive and it's 7 = (-17)^6 mod 19.  */
+  if (gcry_mpi_is_neg (res) || gcry_mpi_cmp_ui (res, 7))
+    {
+      if (verbose)
+	{
+	  fprintf (stderr, "is_neg: %d\n", gcry_mpi_is_neg (res));
+	  fprintf (stderr, "mpi: ");
+	  gcry_mpi_dump (res);
+	  putc ('\n', stderr);
+	}
+      die ("test_powm failed for negative base at %d\n", __LINE__);
+    }
+
   gcry_mpi_release (base);
   gcry_mpi_release (exp);
   gcry_mpi_release (mod);
diff --git a/mpi/mpi-pow.c b/mpi/mpi-pow.c
index 85d6fd8..4955fa5 100644
--- a/mpi/mpi-pow.c
+++ b/mpi/mpi-pow.c
@@ -169,7 +169,7 @@ gcry_mpi_powm (gcry_mpi_t res,
     }
   MPN_COPY ( rp, bp, bsize );
   rsize = bsize;
-  rsign = bsign;
+  rsign = 0;
 
   /* Main processing.  */
   {
@@ -184,7 +184,7 @@ gcry_mpi_powm (gcry_mpi_t res,
     xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec );
 
     memset( &karactx, 0, sizeof karactx );
-    negative_result = (ep[0] & 1) && base->sign;
+    negative_result = (ep[0] & 1) && bsign;
 
     i = esize - 1;
     e = ep[i];
--