From 87099691e752f25e3c044ed59ae47224599291bf Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Niels=20M=C3=B6ller?= <nisse@lysator.liu.se>
Date: Wed, 29 Jan 2020 17:16:03 +0100
Subject: Make ecc modular inversion use redc form, for relevant curves.

* 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.
---
 ecc-j-to-a.c | 40 ++++++++--------------------------------
 1 file changed, 8 insertions(+), 32 deletions(-)

(limited to 'ecc-j-to-a.c')

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
-- 
cgit v1.2.1