Improve scratch usage in ecc_mod_inv.

* ecc-mod-inv.c (ecc_mod_inv): Use passed in scratch for all
scratch needs, don't use memory after the result area.
* ecc-ecdsa-sign.c (ecc_ecdsa_sign): Update invert call.
* ecc-ecdsa-verify.c (ecc_ecdsa_verify): Likewise.
* ecc-eh-to-a.c (ecc_eh_to_a): Likewise.
* ecc-j-to-a.c (ecc_j_to_a): Likewise.
* ecc-gostdsa-verify.c (ecc_gostdsa_verify): Likewise.
* ecc-internal.h (ECC_MOD_INV_ITCH, ECC_J_TO_A_ITCH)
(ECC_EH_TO_A_ITCH): Update accordingly, but no change in total
scratch need.

8 files changed, 26 insertions, 12 deletions

diff --git a/ChangeLog b/ChangeLog
index 1d4699b1..5d774a5f 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,16 @@
+2020-11-14  Niels Möller  <nisse@lysator.liu.se>
+
+	* ecc-mod-inv.c (ecc_mod_inv): Use passed in scratch for all
+	scratch needs, don't use memory after the result area.
+	* ecc-ecdsa-sign.c (ecc_ecdsa_sign): Update invert call.
+	* ecc-ecdsa-verify.c (ecc_ecdsa_verify): Likewise.
+	* ecc-eh-to-a.c (ecc_eh_to_a): Likewise.
+	* ecc-j-to-a.c (ecc_j_to_a): Likewise.
+	* ecc-gostdsa-verify.c (ecc_gostdsa_verify): Likewise.
+	* ecc-internal.h (ECC_MOD_INV_ITCH, ECC_J_TO_A_ITCH)
+	(ECC_EH_TO_A_ITCH): Update accordingly, but no change in total
+	scratch need.
+
 2020-11-13  Niels Möller  <nisse@lysator.liu.se>
 
 	* ecc-internal.h (ECC_J_TO_A_ITCH): Generalize, and take invert
diff --git a/ecc-ecdsa-sign.c b/ecc-ecdsa-sign.c
index 10e1de22..93cbbe7e 100644
--- a/ecc-ecdsa-sign.c
+++ b/ecc-ecdsa-sign.c
@@ -48,6 +48,7 @@ ecc_ecdsa_sign_itch (const struct ecc_curve *ecc)
 {
   /* Needs 3*ecc->p.size + scratch for ecc->mul_g. Currently same for
      ecc_mul_g. */
+  assert (ecc->p.size + ecc->p.invert_itch <= 3*ecc->p.size + ecc->mul_g_itch);
   return ECC_ECDSA_SIGN_ITCH (ecc->p.size);
 }
 
@@ -82,8 +83,8 @@ ecc_ecdsa_sign (const struct ecc_curve *ecc,
   /* x coordinate only, modulo q */
   ecc->h_to_a (ecc, 2, rp, P, P + 3*ecc->p.size);
 
-  /* Invert k, uses 4 * ecc->p.size including scratch */
-  ecc->q.invert (&ecc->q, kinv, kp, tp); /* NOTE: Also clobbers hp */
+  /* Invert k, uses up to 7 * ecc->p.size including scratch (for secp384). */
+  ecc->q.invert (&ecc->q, kinv, kp, tp);
   
   /* Process hash digest */
   ecc_hash (&ecc->q, hp, length, digest);
diff --git a/ecc-ecdsa-verify.c b/ecc-ecdsa-verify.c
index d88bf64c..2b5b6921 100644
--- a/ecc-ecdsa-verify.c
+++ b/ecc-ecdsa-verify.c
@@ -98,7 +98,7 @@ ecc_ecdsa_verify (const struct ecc_curve *ecc,
      division, I think), and write an ecc_add_ppp. */
 
   /* Compute sinv */
-  ecc->q.invert (&ecc->q, sinv, sp, sinv + 2*ecc->p.size);
+  ecc->q.invert (&ecc->q, sinv, sp, sinv + ecc->p.size);
 
   /* u1 = h / s, P1 = u1 * G */
   ecc_hash (&ecc->q, hp, length, digest);
diff --git a/ecc-eh-to-a.c b/ecc-eh-to-a.c
index ce71e93f..24f6d0c0 100644
--- a/ecc-eh-to-a.c
+++ b/ecc-eh-to-a.c
@@ -58,8 +58,8 @@ ecc_eh_to_a (const struct ecc_curve *ecc,
 
   assert(op == 0);
 
-  /* Needs 2*size + scratch for the invert call. */
-  ecc->p.invert (&ecc->p, izp, zp, tp + ecc->p.size);
+  /* Needs size + scratch for the invert call. */
+  ecc->p.invert (&ecc->p, izp, zp, tp);
 
   ecc_mod_mul (&ecc->p, tp, xp, izp, tp);
   cy = mpn_sub_n (r, tp, ecc->p.m, ecc->p.size);
diff --git a/ecc-gostdsa-verify.c b/ecc-gostdsa-verify.c
index 1c02d41c..c0613f4f 100644
--- a/ecc-gostdsa-verify.c
+++ b/ecc-gostdsa-verify.c
@@ -99,7 +99,7 @@ ecc_gostdsa_verify (const struct ecc_curve *ecc,
     mpn_add_1 (hp, hp, ecc->p.size, 1);
 
   /* Compute v */
-  ecc->q.invert (&ecc->q, vp, hp, vp + 2*ecc->p.size);
+  ecc->q.invert (&ecc->q, vp, hp, vp + ecc->p.size);
 
   /* z1 = s / h, P1 = z1 * G */
   ecc_mod_mul (&ecc->q, z1, sp, vp, z1);
diff --git a/ecc-internal.h b/ecc-internal.h
index 2b059914..55c9be27 100644
--- a/ecc-internal.h
+++ b/ecc-internal.h
@@ -438,9 +438,9 @@ curve448_eh_to_x (mp_limb_t *xp, const mp_limb_t *p,
 		  mp_limb_t *scratch);
 
 /* Current scratch needs: */
-#define ECC_MOD_INV_ITCH(size) (2*(size))
-#define ECC_J_TO_A_ITCH(size, inv) (2*(size)+(inv))
-#define ECC_EH_TO_A_ITCH(size, inv) (2*(size)+(inv))
+#define ECC_MOD_INV_ITCH(size) (3*(size))
+#define ECC_J_TO_A_ITCH(size, inv) ((size)+(inv))
+#define ECC_EH_TO_A_ITCH(size, inv) ((size)+(inv))
 #define ECC_DUP_JJ_ITCH(size) (4*(size))
 #define ECC_DUP_EH_ITCH(size) (3*(size))
 #define ECC_DUP_TH_ITCH(size) (3*(size))
diff --git a/ecc-j-to-a.c b/ecc-j-to-a.c
index 882830c4..2d55b3a5 100644
--- a/ecc-j-to-a.c
+++ b/ecc-j-to-a.c
@@ -51,7 +51,7 @@ ecc_j_to_a (const struct ecc_curve *ecc,
 
   mp_limb_t cy;
 
-  ecc->p.invert (&ecc->p, izp, p+2*ecc->p.size, izp + 2 * ecc->p.size);
+  ecc->p.invert (&ecc->p, izp, p+2*ecc->p.size, izp + ecc->p.size);
   ecc_mod_sqr (&ecc->p, iz2p, izp, iz2p);
 
   if (ecc->use_redc)
diff --git a/ecc-mod-inv.c b/ecc-mod-inv.c
index a0c1097e..254fb697 100644
--- a/ecc-mod-inv.c
+++ b/ecc-mod-inv.c
@@ -58,7 +58,7 @@ cnd_neg (int cnd, mp_limb_t *rp, const mp_limb_t *ap, mp_size_t n)
    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.
+   Needs 3n limbs of scratch space.
 */
 
 /* FIXME: Could use mpn_sec_invert (in GMP-6), but with a bit more
@@ -70,7 +70,7 @@ ecc_mod_inv (const struct ecc_modulo *m,
 {
 #define ap scratch
 #define bp (scratch + n)
-#define up (vp + n)
+#define up (scratch + 2*n)
 
   mp_size_t n = m->size;
   /* Avoid the mp_bitcnt_t type for compatibility with older GMP