Reduce output range of ecc_mod_sub.

* ecc-mod-arith.c (ecc_mod_sub): Ensure that if inputs are in the
range 0 <= a, b < 2m, then output is in the same range.
* eccdata.c (output_curve): New outputs ecc_Bm2p and ecc_Bm2q.
* ecc-internal.h (struct ecc_modulo): New member Bm2m (B^size -
2m), needed by ecc_mod_sub. Update all curves.
* testsuite/ecc-mod-arith-test.c: New tests for ecc_mod_add and
ecc_mod_sub.

15 files changed, 226 insertions, 8 deletions

diff --git a/ChangeLog b/ChangeLog
index 15ad3384..083d443a 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,13 @@
 2022-08-16  Niels Möller  <nisse@lysator.liu.se>
 
+	* ecc-mod-arith.c (ecc_mod_sub): Ensure that if inputs are in the
+	range 0 <= a, b < 2m, then output is in the same range.
+	* eccdata.c (output_curve): New outputs ecc_Bm2p and ecc_Bm2q.
+	* ecc-internal.h (struct ecc_modulo): New member Bm2m (B^size -
+	2m), needed by ecc_mod_sub. Update all curves.
+	* testsuite/ecc-mod-arith-test.c: New tests for ecc_mod_add and
+	ecc_mod_sub.
+
 	* eccdata.c (output_modulo): Output the limb size, delete return
 	value.
 	(output_curve): Update calls to output_modulo, other minor cleanup.
diff --git a/ecc-curve25519.c b/ecc-curve25519.c
index 56abcf23..539bff22 100644
--- a/ecc-curve25519.c
+++ b/ecc-curve25519.c
@@ -266,6 +266,7 @@ const struct ecc_curve _nettle_curve25519 =
     ecc_p,
     ecc_Bmodp,
     ecc_Bmodp_shifted,
+    ecc_Bm2p,
     NULL,
     ecc_pp1h,
 
@@ -287,6 +288,7 @@ const struct ecc_curve _nettle_curve25519 =
     ecc_q,
     ecc_Bmodq,  
     ecc_mBmodq_shifted, /* Use q - 2^{252} instead. */
+    ecc_Bm2q,
     NULL,
     ecc_qp1h,
 
diff --git a/ecc-curve448.c b/ecc-curve448.c
index 1bd4e11f..daef56cc 100644
--- a/ecc-curve448.c
+++ b/ecc-curve448.c
@@ -220,6 +220,7 @@ const struct ecc_curve _nettle_curve448 =
     ecc_p,
     ecc_Bmodp,
     ecc_Bmodp_shifted,
+    ecc_Bm2p,
     NULL,
     ecc_pp1h,
 
@@ -241,6 +242,7 @@ const struct ecc_curve _nettle_curve448 =
     ecc_q,
     ecc_Bmodq,
     ecc_Bmodq_shifted,
+    ecc_Bm2q,
     NULL,
     ecc_qp1h,
 
diff --git a/ecc-gost-gc256b.c b/ecc-gost-gc256b.c
index 0cf753e4..df9cbb58 100644
--- a/ecc-gost-gc256b.c
+++ b/ecc-gost-gc256b.c
@@ -71,6 +71,7 @@ const struct ecc_curve _nettle_gost_gc256b =
     ecc_p,
     ecc_Bmodp,
     ecc_Bmodp_shifted,
+    ecc_Bm2p,
     ecc_redc_ppm1,
 
     ecc_pp1h,
@@ -92,6 +93,7 @@ const struct ecc_curve _nettle_gost_gc256b =
     ecc_q,
     ecc_Bmodq,
     ecc_Bmodq_shifted,
+    ecc_Bm2q,
     NULL,
     ecc_qp1h,
 
diff --git a/ecc-gost-gc512a.c b/ecc-gost-gc512a.c
index 338ed001..3807b57e 100644
--- a/ecc-gost-gc512a.c
+++ b/ecc-gost-gc512a.c
@@ -71,6 +71,7 @@ const struct ecc_curve _nettle_gost_gc512a =
     ecc_p,
     ecc_Bmodp,
     ecc_Bmodp_shifted,
+    ecc_Bm2p,
     ecc_redc_ppm1,
 
     ecc_pp1h,
@@ -92,6 +93,7 @@ const struct ecc_curve _nettle_gost_gc512a =
     ecc_q,
     ecc_Bmodq,
     ecc_Bmodq_shifted,
+    ecc_Bm2q,
     NULL,
     ecc_qp1h,
 
diff --git a/ecc-internal.h b/ecc-internal.h
index eb53a9b3..b04d80ce 100644
--- a/ecc-internal.h
+++ b/ecc-internal.h
@@ -178,6 +178,10 @@ struct ecc_modulo
      interest, usually B has trailing zeros and this is B shifted
      right. */
   const mp_limb_t *B_shifted;
+  /* For ecc_mod_sub: B^size - 2m, if that doesn't underflow.
+     Otherwise, same as B */
+  const mp_limb_t *Bm2m;
+
   /* m +/- 1, for redc, excluding redc_size low limbs. */
   const mp_limb_t *redc_mpm1;
   /* (m+1)/2 */
@@ -260,6 +264,8 @@ ecc_mod_equal_p (const struct ecc_modulo *m, const mp_limb_t *a,
 void
 ecc_mod_add (const struct ecc_modulo *m, mp_limb_t *rp,
 	     const mp_limb_t *ap, const mp_limb_t *bp);
+
+/* If inputs are in the range 0 <= a, b < 2m, then so is the output. */
 void
 ecc_mod_sub (const struct ecc_modulo *m, mp_limb_t *rp,
 	     const mp_limb_t *ap, const mp_limb_t *bp);
diff --git a/ecc-mod-arith.c b/ecc-mod-arith.c
index 310cbb1d..d0137864 100644
--- a/ecc-mod-arith.c
+++ b/ecc-mod-arith.c
@@ -85,7 +85,20 @@ ecc_mod_sub (const struct ecc_modulo *m, mp_limb_t *rp,
 {
   mp_limb_t cy;
   cy = mpn_sub_n (rp, ap, bp, m->size);
-  cy = mpn_cnd_sub_n (cy, rp, rp, m->B, m->size);
+  /* The adjustments for this function work differently depending on
+     the value of the most significant bit of m.
+
+     If m has a most significant bit of zero, then the first
+     adjustment step conditionally adds 2m. If in addition, inputs are
+     in the 0 <= a,b < 2m range, then the first adjustment guarantees
+     that result is in that same range. The second adjustment step is
+     needed only if b > 2m, it then ensures output is correct modulo
+     m, but nothing more.
+
+     If m has a most significant bit of one, Bm2m and B are the same,
+     and this function works analogously to ecc_mod_add.
+   */
+  cy = mpn_cnd_sub_n (cy, rp, rp, m->Bm2m, m->size);
   cy = mpn_cnd_sub_n (cy, rp, rp, m->B, m->size);
   assert (cy == 0);  
 }
diff --git a/ecc-secp192r1.c b/ecc-secp192r1.c
index 391ba528..4a07bca3 100644
--- a/ecc-secp192r1.c
+++ b/ecc-secp192r1.c
@@ -247,7 +247,8 @@ const struct ecc_curve _nettle_secp_192r1 =
 
     ecc_p,
     ecc_Bmodp,
-    ecc_Bmodp_shifted,    
+    ecc_Bmodp_shifted,
+    ecc_Bm2p,
     ecc_redc_ppm1,
     ecc_pp1h,
 
@@ -269,6 +270,7 @@ const struct ecc_curve _nettle_secp_192r1 =
     ecc_q,
     ecc_Bmodq,
     ecc_Bmodq_shifted,
+    ecc_Bm2q,
     NULL,
     ecc_qp1h,
 
diff --git a/ecc-secp224r1.c b/ecc-secp224r1.c
index bb321298..b2a335ec 100644
--- a/ecc-secp224r1.c
+++ b/ecc-secp224r1.c
@@ -223,6 +223,7 @@ const struct ecc_curve _nettle_secp_224r1 =
     ecc_p,
     ecc_Bmodp,
     ecc_Bmodp_shifted,
+    ecc_Bm2p,
     ecc_redc_ppm1,
     ecc_pp1h,
 
@@ -244,6 +245,7 @@ const struct ecc_curve _nettle_secp_224r1 =
     ecc_q,
     ecc_Bmodq,
     ecc_Bmodq_shifted,
+    ecc_Bm2q,
     NULL,
     ecc_qp1h,
 
diff --git a/ecc-secp256r1.c b/ecc-secp256r1.c
index e1a14b90..4848dfe3 100644
--- a/ecc-secp256r1.c
+++ b/ecc-secp256r1.c
@@ -343,6 +343,7 @@ const struct ecc_curve _nettle_secp_256r1 =
     ecc_p,
     ecc_Bmodp,
     ecc_Bmodp_shifted,
+    ecc_Bm2p,
     ecc_redc_ppm1,
     ecc_pp1h,
 
@@ -364,6 +365,7 @@ const struct ecc_curve _nettle_secp_256r1 =
     ecc_q,
     ecc_Bmodq,
     ecc_Bmodq_shifted,
+    ecc_Bm2q,
     NULL,
     ecc_qp1h,
 
diff --git a/ecc-secp384r1.c b/ecc-secp384r1.c
index 39716dff..abac5e6d 100644
--- a/ecc-secp384r1.c
+++ b/ecc-secp384r1.c
@@ -314,6 +314,7 @@ const struct ecc_curve _nettle_secp_384r1 =
     ecc_p,
     ecc_Bmodp,
     ecc_Bmodp_shifted,
+    ecc_Bm2p,
     ecc_redc_ppm1,
     ecc_pp1h,
 
@@ -335,6 +336,7 @@ const struct ecc_curve _nettle_secp_384r1 =
     ecc_q,
     ecc_Bmodq,
     ecc_Bmodq_shifted,
+    ecc_Bm2q,
     NULL,
     ecc_qp1h,
 
diff --git a/ecc-secp521r1.c b/ecc-secp521r1.c
index 24d0b53a..8ab7b4bf 100644
--- a/ecc-secp521r1.c
+++ b/ecc-secp521r1.c
@@ -169,6 +169,7 @@ const struct ecc_curve _nettle_secp_521r1 =
     ecc_p,
     ecc_Bmodp,
     ecc_Bmodp_shifted,
+    ecc_Bm2p,
     ecc_redc_ppm1,
     ecc_pp1h,
 
@@ -190,6 +191,7 @@ const struct ecc_curve _nettle_secp_521r1 =
     ecc_q,
     ecc_Bmodq,
     ecc_Bmodq_shifted,
+    ecc_Bm2q,
     NULL,
     ecc_qp1h,
 
diff --git a/eccdata.c b/eccdata.c
index f9b2f402..4459f5d2 100644
--- a/eccdata.c
+++ b/eccdata.c
@@ -1227,6 +1227,11 @@ output_curve (const struct ecc_curve *ecc, unsigned bits_per_limb)
       int shift;
 
       mpz_set_ui (t, 0);
+      mpz_setbit (t, limb_size * bits_per_limb);
+      mpz_submul_ui (t, ecc->p, 2);
+      output_bignum ("ecc_Bm2p", t, limb_size, bits_per_limb);
+
+      mpz_set_ui (t, 0);
       mpz_setbit (t, ecc->bit_size);
       mpz_sub (t, t, ecc->p);      
       output_bignum ("ecc_Bmodp_shifted", t, limb_size, bits_per_limb);
@@ -1258,18 +1263,28 @@ output_curve (const struct ecc_curve *ecc, unsigned bits_per_limb)
 	}
     }
   else
-    printf ("#define ecc_Bmodp_shifted ecc_Bmodp\n");
+    {
+      printf ("#define ecc_Bmodp_shifted ecc_Bmodp\n");
+      printf ("#define ecc_Bm2p ecc_Bmodp\n");
+    }
 
   if (qbits < limb_size * bits_per_limb)
     {
       mpz_set_ui (t, 0);
+      mpz_setbit (t, limb_size * bits_per_limb);
+      mpz_submul_ui (t, ecc->q, 2);
+      output_bignum ("ecc_Bm2q", t, limb_size, bits_per_limb);
+
+      mpz_set_ui (t, 0);
       mpz_setbit (t, qbits);
       mpz_sub (t, t, ecc->q);      
-      output_bignum ("ecc_Bmodq_shifted", t, limb_size, bits_per_limb);      
+      output_bignum ("ecc_Bmodq_shifted", t, limb_size, bits_per_limb);
     }
   else
-    printf ("#define ecc_Bmodq_shifted ecc_Bmodq\n");
-
+    {
+      printf ("#define ecc_Bmodq_shifted ecc_Bmodq\n");
+      printf ("#define ecc_Bm2q ecc_Bmodq\n");
+    }
   mpz_add_ui (t, ecc->p, 1);
   mpz_fdiv_q_2exp (t, t, 1);
   output_bignum ("ecc_pp1h", t, limb_size, bits_per_limb);      
diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in
index 6734d3e6..4e20c7a1 100644
--- a/testsuite/Makefile.in
+++ b/testsuite/Makefile.in
@@ -47,8 +47,8 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \
 		     rsa-compute-root-test.c \
 		     dsa-test.c dsa-keygen-test.c \
 		     curve25519-dh-test.c curve448-dh-test.c \
-		     ecc-mod-test.c ecc-modinv-test.c ecc-redc-test.c \
-		     ecc-sqrt-test.c \
+		     ecc-mod-arith-test.c ecc-mod-test.c ecc-modinv-test.c \
+		     ecc-redc-test.c ecc-sqrt-test.c \
 		     ecc-dup-test.c ecc-add-test.c \
 		     ecc-mul-g-test.c ecc-mul-a-test.c \
 		     ecdsa-sign-test.c ecdsa-verify-test.c \
diff --git a/testsuite/ecc-mod-arith-test.c b/testsuite/ecc-mod-arith-test.c
new file mode 100644
index 00000000..5692f584
--- /dev/null
+++ b/testsuite/ecc-mod-arith-test.c
@@ -0,0 +1,158 @@
+#include "testutils.h"
+
+#define MAX_SIZE (1 + 521 / GMP_NUMB_BITS)
+#define COUNT 50000
+
+static void
+test_add(const char *name,
+	 const struct ecc_modulo *m,
+	 const mpz_t az, const mpz_t bz)
+{
+  mp_limb_t a[MAX_SIZE];
+  mp_limb_t b[MAX_SIZE];
+  mp_limb_t t[MAX_SIZE];
+  mpz_t mz;
+  mpz_t tz;
+  mpz_t ref;
+
+  mpz_init (ref);
+  mpz_add (ref, az, bz);
+  mpz_mod (ref, ref, mpz_roinit_n (mz, m->m, m->size));
+
+  mpz_limbs_copy (a, az, m->size);
+  mpz_limbs_copy (b, bz, m->size);
+  ecc_mod_add (m, t, a, b);
+
+  if (!mpz_congruent_p (ref, mpz_roinit_n (tz, t, m->size), mz))
+    {
+      fprintf (stderr, "ecc_mod_add %s failed: bit_size = %u\n",
+	       name, m->bit_size);
+
+      fprintf (stderr, "a   = ");
+      mpn_out_str (stderr, 16, a, m->size);
+      fprintf (stderr, "\nb   = ");
+      mpn_out_str (stderr, 16, b, m->size);
+      fprintf (stderr, "\nt   = ");
+      mpn_out_str (stderr, 16, t, m->size);
+      fprintf (stderr, " (bad)\nref = ");
+      mpz_out_str (stderr, 16, ref);
+      fprintf (stderr, "\n");
+      abort ();
+    }
+}
+
+static void
+test_sub(const char *name,
+	 const struct ecc_modulo *m,
+	 /* If range is non-null, check that 0 <= r < range. */
+	 const mp_limb_t *range,
+	 const mpz_t az, const mpz_t bz)
+{
+  mp_limb_t a[MAX_SIZE];
+  mp_limb_t b[MAX_SIZE];
+  mp_limb_t t[MAX_SIZE];
+  mpz_t mz;
+  mpz_t tz;
+  mpz_t ref;
+
+  mpz_init (ref);
+  mpz_sub (ref, az, bz);
+  mpz_mod (ref, ref, mpz_roinit_n (mz, m->m, m->size));
+
+  mpz_limbs_copy (a, az, m->size);
+  mpz_limbs_copy (b, bz, m->size);
+  ecc_mod_sub (m, t, a, b);
+
+  if (!mpz_congruent_p (ref, mpz_roinit_n (tz, t, m->size), mz))
+    {
+      fprintf (stderr, "ecc_mod_sub %s failed: bit_size = %u\n",
+	       name, m->bit_size);
+
+      fprintf (stderr, "a   = ");
+      mpn_out_str (stderr, 16, a, m->size);
+      fprintf (stderr, "\nb   = ");
+      mpn_out_str (stderr, 16, b, m->size);
+      fprintf (stderr, "\nt   = ");
+      mpn_out_str (stderr, 16, t, m->size);
+      fprintf (stderr, " (bad)\nref = ");
+      mpz_out_str (stderr, 16, ref);
+      fprintf (stderr, "\n");
+      abort ();
+    }
+
+  if (range && mpn_cmp (t, range, m->size) >= 0)
+    {
+      fprintf (stderr, "ecc_mod_sub %s out of range: bit_size = %u\n",
+	       name, m->bit_size);
+
+      fprintf (stderr, "a   = ");
+      mpn_out_str (stderr, 16, a, m->size);
+      fprintf (stderr, "\nb   = ");
+      mpn_out_str (stderr, 16, b, m->size);
+      fprintf (stderr, "\nt   = ");
+      mpn_out_str (stderr, 16, t, m->size);
+      fprintf (stderr, " \nrange = ");
+      mpn_out_str (stderr, 16, range, m->size);
+      fprintf (stderr, "\n");
+      abort ();
+    }
+}
+
+static void
+test_modulo (gmp_randstate_t rands, const char *name,
+	     const struct ecc_modulo *m, unsigned count)
+{
+  mpz_t a, b;
+  unsigned j;
+
+  mpz_init (a);
+  mpz_init (b);
+
+  for (j = 0; j < count; j++)
+    {
+      if (j & 1)
+	{
+	  mpz_rrandomb (a, rands, m->size * GMP_NUMB_BITS);
+	  mpz_rrandomb (b, rands, m->size * GMP_NUMB_BITS);
+	}
+      else
+	{
+	  mpz_urandomb (a, rands, m->size * GMP_NUMB_BITS);
+	  mpz_urandomb (b, rands, m->size * GMP_NUMB_BITS);
+	}
+      test_add (name, m, a, b);
+      test_sub (name, m, NULL, a, b);
+    }
+  if (m->bit_size < m->size * GMP_NUMB_BITS)
+    {
+      mp_limb_t two_p[MAX_SIZE];
+      mpn_lshift (two_p, m->m, m->size, 1);
+      mpz_t range;
+      mpz_roinit_n (range, two_p, m->size);
+      mpz_urandomm (a, rands, range);
+      mpz_urandomm (b, rands, range);
+      test_sub (name, m, two_p, a, b);
+    }
+  mpz_clear (a);
+  mpz_clear (b);
+}
+
+void
+test_main (void)
+{
+  gmp_randstate_t rands;
+  unsigned count = COUNT;
+  unsigned i;
+
+  gmp_randinit_default (rands);
+
+  if (test_randomize(rands))
+    count *= 20;
+
+  for (i = 0; ecc_curves[i]; i++)
+    {
+      test_modulo (rands, "p", &ecc_curves[i]->p, count);
+      test_modulo (rands, "q", &ecc_curves[i]->q, count);
+    }
+  gmp_randclear (rands);
+}