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.

1 files changed, 14 insertions, 6 deletions

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