Make ecc modular inversion use redc form, for relevant curves.invert-with-redc

* ecc-mod-inv.c (ecc_mod_inv_destructive): New helper function,
not preserving input argument. Extracted from old ecc_mod_inv.
(ecc_mod_inv): Call ecc_mod_inv_destructive.
(ecc_mod_inv_redc): New inversion function, with input and output
in redc form.

* ecc-secp224r1.c: Select between ecc_mod_inv and ecc_mod_inv_redc.
* ecc-secp256r1.c: Likewise.

* ecc-j-to-a.c (ecc_j_to_a): Simplify redc-related logic, taking
advantage of ecc->p.invert handling redc, when appropriate. Reduce
scratch need from 5n to 4n in the process (assuming inversion
needs 2n).

* testsuite/ecc-modinv-test.c (ref_modinv): Updated to do redc, if
appropriate.

7 files changed, 90 insertions, 53 deletions

diff --git a/ChangeLog b/ChangeLog
index bc70e5f1..42b91357 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,22 @@
+2020-01-29  Niels Möller  <nisse@lysator.liu.se>
+
+	* ecc-mod-inv.c (ecc_mod_inv_destructive): New helper function,
+	not preserving input argument. Extracted from old ecc_mod_inv.
+	(ecc_mod_inv): Call ecc_mod_inv_destructive.
+	(ecc_mod_inv_redc): New inversion function, with input and output
+	in redc form.
+
+	* ecc-secp224r1.c: Select between ecc_mod_inv and ecc_mod_inv_redc.
+	* ecc-secp256r1.c: Likewise.
+
+	* ecc-j-to-a.c (ecc_j_to_a): Simplify redc-related logic, taking
+	advantage of ecc->p.invert handling redc, when appropriate. Reduce
+	scratch need from 5n to 4n in the process (assuming inversion
+	needs 2n).
+
+	* testsuite/ecc-modinv-test.c (ref_modinv): Updated to do redc, if
+	appropriate.
+
 2020-01-26  Niels Möller  <nisse@lysator.liu.se>
 
 	* ecc-internal.h (struct ecc_curve): Delete g, the curve
diff --git a/ecc-internal.h b/ecc-internal.h
index 9516023a..2c1e57e8 100644
--- a/ecc-internal.h
+++ b/ecc-internal.h
@@ -52,6 +52,7 @@
 #define ecc_mod_random _nettle_ecc_mod_random
 #define ecc_mod _nettle_ecc_mod
 #define ecc_mod_inv _nettle_ecc_mod_inv
+#define ecc_mod_inv_redc _nettle_ecc_mod_inv_redc
 #define ecc_hash _nettle_ecc_hash
 #define gost_hash _nettle_gost_hash
 #define ecc_a_to_j _nettle_ecc_a_to_j
@@ -168,6 +169,8 @@ struct ecc_modulo
 
   ecc_mod_func *mod;
   ecc_mod_func *reduce;
+  /* For moduli where we use redc, the invert and sqrt functions work
+     with inputs and outputs in redc form. */
   ecc_mod_inv_func *invert;
   ecc_mod_sqrt_func *sqrt;
 };
@@ -228,6 +231,7 @@ ecc_mod_func ecc_pp1_redc;
 ecc_mod_func ecc_pm1_redc;
 
 ecc_mod_inv_func ecc_mod_inv;
+ecc_mod_inv_func ecc_mod_inv_redc;
 
 void
 ecc_mod_add (const struct ecc_modulo *m, mp_limb_t *rp,
@@ -432,7 +436,8 @@ curve448_eh_to_x (mp_limb_t *xp, const mp_limb_t *p,
 
 /* Current scratch needs: */
 #define ECC_MOD_INV_ITCH(size) (2*(size))
-#define ECC_J_TO_A_ITCH(size) (5*(size))
+/* Only valid when using the general ecc_mod_inv/ecc_mod_inv_redc ! */
+#define ECC_J_TO_A_ITCH(size) (4*(size))
 #define ECC_EH_TO_A_ITCH(size, inv) (2*(size)+(inv))
 #define ECC_DUP_JJ_ITCH(size) (5*(size))
 #define ECC_DUP_EH_ITCH(size) (5*(size))
diff --git a/ecc-j-to-a.c b/ecc-j-to-a.c
index eca10f0f..faaaa717 100644
--- a/ecc-j-to-a.c
+++ b/ecc-j-to-a.c
@@ -45,47 +45,24 @@ ecc_j_to_a (const struct ecc_curve *ecc,
 	    mp_limb_t *scratch)
 {
 #define izp   scratch
-#define up   (scratch + 2*ecc->p.size)
 #define iz2p (scratch + ecc->p.size)
 #define iz3p (scratch + 2*ecc->p.size)
-#define izBp (scratch + 3*ecc->p.size)
 #define tp    scratch
 
   mp_limb_t cy;
 
-  if (ecc->use_redc)
-    {
-      /* Set v = (r_z / B^2)^-1,
-
-	 r_x = p_x v^2 / B^3 =  ((v/B * v)/B * p_x)/B
-	 r_y = p_y v^3 / B^4 = (((v/B * v)/B * v)/B * p_y)/B
-      */
-
-      mpn_copyi (up, p + 2*ecc->p.size, ecc->p.size);
-      mpn_zero (up + ecc->p.size, ecc->p.size);
-      ecc->p.reduce (&ecc->p, up);
-      mpn_zero (up + ecc->p.size, ecc->p.size);
-      ecc->p.reduce (&ecc->p, up);
-
-      ecc->p.invert (&ecc->p, izp, up, up + ecc->p.size);
+  ecc->p.invert (&ecc->p, izp, p+2*ecc->p.size, izp + 2 * ecc->p.size);
+  ecc_modp_sqr (ecc, iz2p, izp);
 
-      /* Divide this common factor by B */
-      mpn_copyi (izBp, izp, ecc->p.size);
-      mpn_zero (izBp + ecc->p.size, ecc->p.size);
-      ecc->p.reduce (&ecc->p, izBp);
-
-      ecc_modp_mul (ecc, iz2p, izp, izBp);
-    }
-  else
+  if (ecc->use_redc)
     {
-      /* Set s = p_z^{-1}, r_x = p_x s^2, r_y = p_y s^3 */
-
-      mpn_copyi (up, p+2*ecc->p.size, ecc->p.size); /* p_z */
-      ecc->p.invert (&ecc->p, izp, up, up + ecc->p.size);
-
-      ecc_modp_sqr (ecc, iz2p, izp);
+      /* Divide this common factor by B, instead of applying redc to
+	 both x and y outputs. */
+      mpn_zero (iz2p + ecc->p.size, ecc->p.size);
+      ecc->p.reduce (&ecc->p, iz2p);
     }
 
+  /* r_x <-- x / z^2 */
   ecc_modp_mul (ecc, iz3p, iz2p, p);
   /* ecc_modp (and ecc_modp_mul) may return a value up to 2p - 1, so
      do a conditional subtraction. */
@@ -112,7 +89,6 @@ ecc_j_to_a (const struct ecc_curve *ecc,
   cnd_copy (cy, r + ecc->p.size, tp, ecc->p.size);
 
 #undef izp
-#undef up
 #undef iz2p
 #undef iz3p
 #undef tp
diff --git a/ecc-mod-inv.c b/ecc-mod-inv.c
index 8cfd2e3b..f306d7de 100644
--- a/ecc-mod-inv.c
+++ b/ecc-mod-inv.c
@@ -54,22 +54,19 @@ cnd_neg (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n)
     }
 }
 
-/* Compute a^{-1} mod m, with running time depending only on the size.
-   Returns zero if a == 0 (mod m), to be consistent with a^{phi(m)-1}.
-   Also needs (m+1)/2, and m must be odd.
-
-   Needs 2n limbs available at rp, and 2n additional scratch limbs.
+/* Compute v = a^{-1} mod m, with running time depending only on the
+   size. Returns zero if a == 0 (mod m), to be consistent with
+   a^{phi(m)-1}. Also needs (m+1)/2, and m must be odd. The value at
+   ap is destroyed in the process.
 */
 
 /* FIXME: Could use mpn_sec_invert (in GMP-6), but with a bit more
    scratch need since it doesn't precompute (m+1)/2. */
-void
-ecc_mod_inv (const struct ecc_modulo *m,
-	     mp_limb_t *vp, const mp_limb_t *in_ap,
-	     mp_limb_t *scratch)
+static void
+ecc_mod_inv_destructive (const struct ecc_modulo *m,
+			 mp_limb_t *vp, mp_limb_t *ap)
 {
-#define ap scratch
-#define bp (scratch + n)
+#define bp (ap + n)
 #define up (vp + n)
 
   mp_size_t n = m->size;
@@ -94,7 +91,6 @@ ecc_mod_inv (const struct ecc_modulo *m,
   mpn_zero (up+1, n - 1);
   mpn_copyi (bp, m->m, n);
   mpn_zero (vp, n);
-  mpn_copyi (ap, in_ap, n);
 
   for (i = m->bit_size + GMP_NUMB_BITS * n; i-- > 0; )
     {
@@ -158,3 +154,36 @@ ecc_mod_inv (const struct ecc_modulo *m,
 #undef bp
 #undef up
 }
+
+/* Needs 2n limbs available at rp, and 2n additional scratch
+   limbs. */
+void
+ecc_mod_inv (const struct ecc_modulo *m,
+	     mp_limb_t *vp, const mp_limb_t *ap,
+	     mp_limb_t *scratch)
+{
+  mpn_copyi (scratch, ap, m->size);
+  ecc_mod_inv_destructive (m, vp, scratch);
+}
+
+/* Inversion, with input and output in redc form. I.e., we want v =
+   a^-1 (mod m), but inputs and outputs are v' = vB, a' = aB. Then
+   v' a' = B^2 (mod b), and we do the inversion as
+
+     v' = (a / B^2)^-1 (mod m)
+*/
+
+void
+ecc_mod_inv_redc (const struct ecc_modulo *m,
+		  mp_limb_t *vp, const mp_limb_t *ap,
+		  mp_limb_t *scratch)
+{
+  mpn_copyi (scratch, ap, m->size);
+
+  mpn_zero (scratch + m->size, m->size);
+  m->reduce (m, scratch);
+  mpn_zero (scratch + m->size, m->size);
+  m->reduce (m, scratch);
+
+  ecc_mod_inv_destructive (m, vp, scratch);
+}
diff --git a/ecc-secp224r1.c b/ecc-secp224r1.c
index 05d84017..c8d4d40e 100644
--- a/ecc-secp224r1.c
+++ b/ecc-secp224r1.c
@@ -80,7 +80,7 @@ const struct ecc_curve _nettle_secp_224r1 =
 
     ecc_secp224r1_modp,
     USE_REDC ? ecc_secp224r1_redc : ecc_secp224r1_modp,
-    ecc_mod_inv,
+    USE_REDC ? ecc_mod_inv_redc : ecc_mod_inv,
     NULL,
   },
   {
diff --git a/ecc-secp256r1.c b/ecc-secp256r1.c
index d3996424..adab8d90 100644
--- a/ecc-secp256r1.c
+++ b/ecc-secp256r1.c
@@ -257,7 +257,7 @@ const struct ecc_curve _nettle_secp_256r1 =
 
     ecc_secp256r1_modp,
     USE_REDC ? ecc_secp256r1_redc : ecc_secp256r1_modp,
-    ecc_mod_inv,
+    USE_REDC ? ecc_mod_inv_redc : ecc_mod_inv,
     NULL,
   },
   {
diff --git a/testsuite/ecc-modinv-test.c b/testsuite/ecc-modinv-test.c
index c46c69f5..e991485a 100644
--- a/testsuite/ecc-modinv-test.c
+++ b/testsuite/ecc-modinv-test.c
@@ -1,7 +1,8 @@
 #include "testutils.h"
 
 static int
-ref_modinv (mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *mp, mp_size_t mn)
+ref_modinv (mp_limb_t *rp, const mp_limb_t *ap,
+	    const mp_limb_t *mp, mp_size_t mn, int use_redc)
 {
   mpz_t g, s, a, m;
   int res;
@@ -19,12 +20,18 @@ ref_modinv (mp_limb_t *rp, const mp_limb_t *ap, const mp_limb_t *mp, mp_size_t m
 	  mpz_add (s, s, m);
 	  ASSERT (mpz_sgn (s) > 0);
 	}
-      mpz_limbs_copy (rp, s, mn);
       res = 1;
     }
   else
     res = 0;
 
+  if (use_redc)
+    {
+      mpz_mul_2exp (s, s, 2 * mn * GMP_NUMB_BITS);
+      mpz_mod (s, s, m);
+    }
+
+  mpz_limbs_copy (rp, s, mn);
   mpz_clear (g);
   mpz_clear (s);
   return res;
@@ -42,7 +49,7 @@ zero_p (const struct ecc_modulo *m, const mp_limb_t *xp)
 
 static void
 test_modulo (gmp_randstate_t rands, const char *name,
-	     const struct ecc_modulo *m)
+	     const struct ecc_modulo *m, int use_redc)
 {
   mp_limb_t *a;
   mp_limb_t *ai;
@@ -99,7 +106,7 @@ test_modulo (gmp_randstate_t rands, const char *name,
 
       mpz_limbs_copy (a, r, m->size);
 
-      if (!ref_modinv (ref, a, m->m, m->size))
+      if (!ref_modinv (ref, a, m->m, m->size, use_redc))
 	{
 	  if (verbose)
 	    fprintf (stderr, "Test %u (bit size %u) not invertible mod %s.\n",
@@ -107,6 +114,7 @@ test_modulo (gmp_randstate_t rands, const char *name,
 	  continue;
 	}
       m->invert (m, ai, a, scratch);
+      /* FIXME: Allow non-canonical representation, ai > m */
       if (mpn_cmp (ref, ai, m->size))
 	{
 	  fprintf (stderr, "%s->invert failed (test %u, bit size %u):\n",
@@ -141,8 +149,8 @@ test_main (void)
 
   for (i = 0; ecc_curves[i]; i++)
     {
-      test_modulo (rands, "p", &ecc_curves[i]->p);
-      test_modulo (rands, "q", &ecc_curves[i]->q);
+      test_modulo (rands, "p", &ecc_curves[i]->p, ecc_curves[i]->use_redc);
+      test_modulo (rands, "q", &ecc_curves[i]->q, 0);
     }
   gmp_randclear (rands);
 }