ecc: ec_addm/ec_subm improvement

[NIIBE Yutaka]

Hello,

While this patch is not mature yet, I'd like to share the idea.

Large picture is computing curve point with MPI which always has fixed
number of limbs, so that computation can be constant time.

Bonus point is it will be somewhat faster and a bit smaller memory
footprint.


ec_addm/ec_subm doesn't need to be reduced by the prime, and the value
can be somewhat redundant.  When it encounter carry to another limb,
it does something with the prime.

The change in this patch itself includes non-constant-time path,
it should be improved.

It build and works well by 'make check' when applied over the
positive-value-only patch.


diff --git a/mpi/ec.c b/mpi/ec.c
index cd24e87..d51a69b 100644
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -268,17 +268,114 @@ ec_mod (gcry_mpi_t w, mpi_ec_t ec)
 static void
 ec_addm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
 {
-  mpi_add (w, u, v);
-  ec_mod (w, ctx);
+  mpi_ptr_t wp, up, vp;
+  mpi_size_t usize, vsize, wsize;
+  mpi_limb_t cy;
+
+  gcry_assert (u->sign == 0 && v->sign == 0);
+
+  if ( u->nlimbs < v->nlimbs )
+    { /* Swap U and V. */
+      usize = v->nlimbs;
+      vsize = u->nlimbs;
+      wsize = usize;
+      RESIZE_IF_NEEDED (w, wsize);
+      up = v->d;
+      vp = u->d;
+    }
+  else
+    {
+      usize = u->nlimbs;
+      vsize = v->nlimbs;
+      wsize = usize;
+      RESIZE_IF_NEEDED (w, wsize);
+      up = u->d;
+      vp = v->d;
+    }
+  wp = w->d;
+
+  if ( !vsize )
+    {
+      cy = 0;
+      MPN_COPY (wp, up, usize);
+    }
+  else
+    cy = _gcry_mpih_add (wp, up, usize, vp, vsize);
+
+  w->sign = 0;
+  if (wsize == ctx->p->nlimbs)
+    {
+      if (cy)
+        _gcry_mpih_sub_n (wp, wp, ctx->p->d, wsize);
+      w->nlimbs = wsize;
+    }
+  else
+    {
+      if (cy)
+        {
+          wsize++;
+          RESIZE_IF_NEEDED (w, wsize);
+          w->d[usize] = cy;
+        }
+      w->nlimbs = wsize;
+    }
 }

 static void
-ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ec)
+ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx)
 {
-  mpi_sub (w, u, v);
-  while (w->sign)
-    mpi_add (w, w, ec->p);
-  /*ec_mod (w, ec);*/
+  mpi_ptr_t wp, up, vp;
+  mpi_size_t usize, vsize, wsize;
+  mpi_limb_t cy;
+  int sign;
+
+  gcry_assert (u->sign == 0 && v->sign == 0);
+
+  w->sign = 0;
+  wsize = ctx->p->nlimbs;
+  RESIZE_IF_NEEDED (w, wsize);
+  wp = w->d;
+
+  if ( u->nlimbs < v->nlimbs )
+    { /* Swap U and V. */
+      sign = 1;
+      usize = v->nlimbs;
+      vsize = u->nlimbs;
+      up = v->d;
+      vp = u->d;
+    }
+  else
+    {
+      sign = 0;
+      usize = u->nlimbs;
+      vsize = v->nlimbs;
+      up = u->d;
+      vp = v->d;
+    }
+
+  cy = _gcry_mpih_sub (wp, up, usize, vp, vsize);
+  memset (wp + usize, cy?~0:0, (wsize - usize) * BYTES_PER_MPI_LIMB);
+
+  if (cy && !sign)
+    _gcry_mpih_add_n (wp, wp, ctx->p->d, wsize);
+  else if (cy && sign)
+    {
+      size_t i;
+
+      for (i = 0; i < wsize; i++)
+        w->d[i] = ~w->d[i];
+
+      _gcry_mpih_add_1 (wp, wp, wsize, 1);
+    }
+  else if (!cy && !sign)
+    ;
+  else if (!cy && sign)
+    _gcry_mpih_sub_n (wp, ctx->p->d, wp, wsize);
+
+#if 0
+  MPN_NORMALIZE (wp, wsize);
+#endif
+  w->nlimbs = wsize;
 }

 static void
@@ -1463,6 +1560,7 @@ _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
         ec_mulm (w, ctx->a, x, ctx);
         ec_addm (w, w, ctx->b, ctx);
         ec_addm (w, w, xxx, ctx);
+        ec_mod (w, ctx);

         if (!mpi_cmp (y, w))
           res = 1;
@@ -1517,6 +1615,8 @@ _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
         ec_mulm (x, x, y, ctx);
         ec_mulm (x, x, ctx->b, ctx);
         ec_subm (w, w, x, ctx);
+        ec_mod (w, ctx);
+
         if (!mpi_cmp_ui (w, 0))
           res = 1;
       }
--