ecc: effort so that we can enable barret reduction

[NIIBE Yutaka]

Hello,

Following patch is the one which allow a user to enable
GCRYPT_BARRETT.  With this patch, it goes well for make check.

IIUC, the implementation of Barrett reduction assumes positive MPI.

It would be worth to consider applying this when someone claims it
doesn't work with GCRYPT_BARRETT.


diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c
index a74501d..0394646 100644
--- a/cipher/ecc-curves.c
+++ b/cipher/ecc-curves.c
@@ -123,8 +123,8 @@ static const ecc_domain_parms_t domain_parms[] =
       "Ed25519", 256, 0,
       MPI_EC_EDWARDS, ECC_DIALECT_ED25519,
       "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED",
-      "-0x01",
-      "-0x2DFC9311D490018C7338BF8688861767FF8FF5B2BEBE27548A14B235ECA6874A",
+      "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC",
+      "0x52036CEE2B6FFE738CC740797779E89800700A4D4141D8AB75EB4DCA135978A3",
       "0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED",
       "0x216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A",
       "0x6666666666666666666666666666666666666666666666666666666666666658",
diff --git a/cipher/ecc-eddsa.c b/cipher/ecc-eddsa.c
index 2a52b78..f91f848 100644
--- a/cipher/ecc-eddsa.c
+++ b/cipher/ecc-eddsa.c
@@ -251,7 +251,7 @@ _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
   mpi_mulm (t, x, x, ec->p);
   mpi_mulm (t, t, v, ec->p);
   /* -t == u ? x = x * sqrt(-1) */
-  mpi_neg (t, t);
+  mpi_sub (t, ec->p, t);
   if (!mpi_cmp (t, u))
     {
       static gcry_mpi_t m1;  /* Fixme: this is not thread-safe.  */
@@ -263,7 +263,7 @@ _gcry_ecc_eddsa_recover_x (gcry_mpi_t x, gcry_mpi_t y, int sign, mpi_ec_t ec)
       mpi_mulm (t, x, x, ec->p);
       mpi_mulm (t, t, v, ec->p);
       /* -t == u ? x = x * sqrt(-1) */
-      mpi_neg (t, t);
+      mpi_sub (t, ec->p, t);
       if (!mpi_cmp (t, u))
         rc = GPG_ERR_INV_OBJ;
     }
@@ -835,7 +835,7 @@ _gcry_ecc_eddsa_verify (gcry_mpi_t input, ECC_public_key *pkey,

   _gcry_mpi_ec_mul_point (&Ia, s, &pkey->E.G, ctx);
   _gcry_mpi_ec_mul_point (&Ib, h, &Q, ctx);
-  _gcry_mpi_neg (Ib.x, Ib.x);
+  _gcry_mpi_sub (Ib.x, ctx->p, Ib.x);
   _gcry_mpi_ec_add_points (&Ia, &Ia, &Ib, ctx);
   rc = _gcry_ecc_eddsa_encodepoint (&Ia, ctx, s, h, 0, &tbuf, &tlen);
   if (rc)
diff --git a/cipher/ecc.c b/cipher/ecc.c
index 1933978..6ea77e5 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -1765,6 +1765,12 @@ compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparms)
                                              &values[3], &values[4], &values[5]);
           if (rc)
             goto leave;
+
+          if (!strcmp (curvename, "Ed25519"))
+            {
+              mpi_sub (values[1], values[1], values[0]);
+              mpi_sub (values[2], values[2], values[0]);
+            }
         }
     }

diff --git a/mpi/ec.c b/mpi/ec.c
index 40e09be..cd24e87 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -275,8 +275,9 @@ ec_addm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
 static void
 ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ec)
 {
-  (void)ec;
   mpi_sub (w, u, v);
+  while (w->sign)
+    mpi_add (w, w, ec->p);
   /*ec_mod (w, ec);*/
 }

@@ -790,10 +791,7 @@ dup_point_edwards (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx)

   /* E = aC */
   if (ctx->dialect == ECC_DIALECT_ED25519)
-    {
-      mpi_set (E, C);
-      _gcry_mpi_neg (E, E);
-    }
+    mpi_sub (E, ctx->p, C);
   else
     ec_mulm (E, ctx->a, C, ctx);

@@ -1071,11 +1069,7 @@ add_points_edwards (mpi_point_t result,
   /* Y_3 = A · G · (D - aC) */
   if (ctx->dialect == ECC_DIALECT_ED25519)
     {
-      /* Using ec_addm (Y3, D, C, ctx) is possible but a litte bit
-         slower because a subm does currently skip the mod step.  */
-      mpi_set (Y3, C);
-      _gcry_mpi_neg (Y3, Y3);
-      ec_subm (Y3, D, Y3, ctx);
+      ec_addm (Y3, D, C, ctx);
     }
   else
     {
@@ -1197,7 +1191,7 @@ sub_points_edwards (mpi_point_t result,
 {
   mpi_point_t p2i = _gcry_mpi_point_new (0);
   point_set (p2i, p2);
-  _gcry_mpi_neg (p2i->x, p2i->x);
+  mpi_sub (p2i->x, ctx->p, p2i->x);
   add_points_edwards (result, p1, p2i, ctx);
   _gcry_mpi_point_release (p2i);
 }
@@ -1515,10 +1509,7 @@ _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
         ec_pow2 (x, x, ctx);
         ec_pow2 (y, y, ctx);
         if (ctx->dialect == ECC_DIALECT_ED25519)
-          {
-            mpi_set (w, x);
-            _gcry_mpi_neg (w, w);
-          }
+          mpi_sub (w, ctx->p, x);
         else
           ec_mulm (w, ctx->a, x, ctx);
         ec_addm (w, w, y, ctx);
diff --git a/tests/t-mpi-point.c b/tests/t-mpi-point.c
index d72cd27..ccf9cc4 100644
--- a/tests/t-mpi-point.c
+++ b/tests/t-mpi-point.c
@@ -130,8 +130,8 @@ static struct
     {
       "Ed25519",
       "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED",
-      "-0x01",
-      "-0x2DFC9311D490018C7338BF8688861767FF8FF5B2BEBE27548A14B235ECA6874A",
+      "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC",
+      "0x52036CEE2B6FFE738CC740797779E89800700A4D4141D8AB75EB4DCA135978A3",
       "0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED",
       "0x216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A",
       "0x6666666666666666666666666666666666666666666666666666666666666658",
--