Use GMP functions mpn_cnd_add_n, mpn_cnd_sub_n and mpn_cnd_swap.use-mpn_cnd-functions

17 files changed, 105 insertions, 49 deletions

diff --git a/ChangeLog b/ChangeLog
index 983078a6..57d121be 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+2020-10-28  Niels Möller  <nisse@lysator.liu.se>
+
+	* gmp-glue.h (cnd_add_n, cnd_sub_n, cnd_swap): Deleted, use
+	corresponding functions mpn_cnd_add_n, mpn_cnd_sub_n,
+	mpn_cnd_swap, available from GMP version 6.1.0. Update all
+	callers, in particular, mpn_cnd_add_n and mpn_cnd_sub_n has one
+	more argument than the old functions.
+
+	* gmp-glue.c (mpn_cnd_add_n, mpn_cnd_sub_n, mpn_cnd_swap)
+	[NETTLE_USE_MINI_GMP]: Fallback definitions or mini-gmp builds.
+
 2020-10-14  Niels Möller  <nisse@lysator.liu.se>
 
 	* ecc-mod-arith.c (ecc_mod_pow_2k, ecc_mod_pow_2k_mul): Moved
diff --git a/ecc-curve25519.c b/ecc-curve25519.c
index 60ef0540..05e772bc 100644
--- a/ecc-curve25519.c
+++ b/ecc-curve25519.c
@@ -91,13 +91,13 @@ ecc_curve25519_modq (const struct ecc_modulo *q, mp_limb_t *rp)
 			 rp[n + ECC_LIMB_SIZE]);
       /* Top limb of mBmodq_shifted is zero, so we get cy == 0 or 1 */
       assert (cy < 2);
-      cnd_add_n (cy, rp+n, q->m, ECC_LIMB_SIZE);
+      mpn_cnd_add_n (cy, rp+n, rp+n, q->m, ECC_LIMB_SIZE);
     }
 
   cy = mpn_submul_1 (rp, q->m, ECC_LIMB_SIZE,
 		     rp[ECC_LIMB_SIZE-1] >> (GMP_NUMB_BITS - QHIGH_BITS));
   assert (cy < 2);
-  cnd_add_n (cy, rp, q->m, ECC_LIMB_SIZE);
+  mpn_cnd_add_n (cy, rp, rp, q->m, ECC_LIMB_SIZE);
 }
 
 /* Computes a^{(p-5)/8} = a^{2^{252}-3} mod m. Needs 5 * n scratch
@@ -187,7 +187,7 @@ ecc_curve25519_zero_p (const struct ecc_modulo *p, mp_limb_t *xp)
     + sec_add_1 (xp, xp, ECC_LIMB_SIZE - 1, 19 * (hi >> (GMP_NUMB_BITS - PHIGH_BITS)));
 #endif
   cy = mpn_sub_n (xp, xp, p->m, ECC_LIMB_SIZE);
-  cnd_add_n (cy, xp, p->m, ECC_LIMB_SIZE);
+  mpn_cnd_add_n (cy, xp, xp, p->m, ECC_LIMB_SIZE);
 
   for (i = 0, w = 0; i < ECC_LIMB_SIZE; i++)
     w |= xp[i];
diff --git a/ecc-curve448.c b/ecc-curve448.c
index 729ce985..c00faa30 100644
--- a/ecc-curve448.c
+++ b/ecc-curve448.c
@@ -91,7 +91,7 @@ ecc_curve448_modp(const struct ecc_modulo *m, mp_limb_t *rp)
   tp[4] = c4 + (c7 >> 32) + (tp[3] < c3);
   tp[5] = tp[6] = 0;
   c7 = mpn_add_n (rp, rp, tp, 7);
-  c7 = cnd_add_n (c7, rp, m->B, 7);
+  c7 = mpn_cnd_add_n (c7, rp, rp, m->B, 7);
   assert (c7 == 0);
 }
 #else
@@ -165,7 +165,7 @@ ecc_curve448_zero_p (const struct ecc_modulo *p, mp_limb_t *xp)
   mp_limb_t w;
   mp_size_t i;
   cy = mpn_sub_n (xp, xp, p->m, ECC_LIMB_SIZE);
-  cnd_add_n (cy, xp, p->m, ECC_LIMB_SIZE);
+  mpn_cnd_add_n (cy, xp, xp, p->m, ECC_LIMB_SIZE);
 
   for (i = 0, w = 0; i < ECC_LIMB_SIZE; i++)
     w |= xp[i];
diff --git a/ecc-mod-arith.c b/ecc-mod-arith.c
index 0b315552..34a28544 100644
--- a/ecc-mod-arith.c
+++ b/ecc-mod-arith.c
@@ -48,8 +48,8 @@ ecc_mod_add (const struct ecc_modulo *m, mp_limb_t *rp,
 {
   mp_limb_t cy;
   cy = mpn_add_n (rp, ap, bp, m->size);
-  cy = cnd_add_n (cy, rp, m->B, m->size);
-  cy = cnd_add_n (cy, rp, m->B, m->size);
+  cy = mpn_cnd_add_n (cy, rp, rp, m->B, m->size);
+  cy = mpn_cnd_add_n (cy, rp, rp, m->B, m->size);
   assert (cy == 0);  
 }
 
@@ -59,8 +59,8 @@ 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 = cnd_sub_n (cy, rp, m->B, m->size);
-  cy = cnd_sub_n (cy, rp, m->B, m->size);
+  cy = mpn_cnd_sub_n (cy, rp, rp, m->B, m->size);
+  cy = mpn_cnd_sub_n (cy, rp, rp, m->B, m->size);
   assert (cy == 0);  
 }
 
@@ -74,7 +74,7 @@ ecc_mod_mul_1 (const struct ecc_modulo *m, mp_limb_t *rp,
   hi = mpn_mul_1 (rp, ap, m->size, b);
   hi = mpn_addmul_1 (rp, m->B, m->size, hi);
   assert (hi <= 1);
-  hi = cnd_add_n (hi, rp, m->B, m->size);
+  hi = mpn_cnd_add_n (hi, rp, rp, m->B, m->size);
   /* Sufficient if b < B^size / p */
   assert (hi == 0);
 }
@@ -89,7 +89,7 @@ ecc_mod_addmul_1 (const struct ecc_modulo *m, mp_limb_t *rp,
   hi = mpn_addmul_1 (rp, ap, m->size, b);
   hi = mpn_addmul_1 (rp, m->B, m->size, hi);
   assert (hi <= 1);
-  hi = cnd_add_n (hi, rp, m->B, m->size);
+  hi = mpn_cnd_add_n (hi, rp, rp, m->B, m->size);
   /* Sufficient roughly if b < B^size / p */
   assert (hi == 0);
 }
@@ -104,7 +104,7 @@ ecc_mod_submul_1 (const struct ecc_modulo *m, mp_limb_t *rp,
   hi = mpn_submul_1 (rp, ap, m->size, b);
   hi = mpn_submul_1 (rp, m->B, m->size, hi);
   assert (hi <= 1);
-  hi = cnd_sub_n (hi, rp, m->B, m->size);
+  hi = mpn_cnd_sub_n (hi, rp, rp, m->B, m->size);
   /* Sufficient roughly if b < B^size / p */
   assert (hi == 0);
 }
diff --git a/ecc-mod-inv.c b/ecc-mod-inv.c
index f306d7de..e45c230a 100644
--- a/ecc-mod-inv.c
+++ b/ecc-mod-inv.c
@@ -134,19 +134,19 @@ ecc_mod_inv_destructive (const struct ecc_modulo *m,
       assert (bp[0] & 1);
       odd = ap[0] & 1;
 
-      swap = cnd_sub_n (odd, ap, bp, n);
-      cnd_add_n (swap, bp, ap, n);
+      swap = mpn_cnd_sub_n (odd, ap, ap, bp, n);
+      mpn_cnd_add_n (swap, bp, bp, ap, n);
       cnd_neg (swap, ap, ap, n);
 
-      cnd_swap (swap, up, vp, n);
-      cy = cnd_sub_n (odd, up, vp, n);
-      cy -= cnd_add_n (cy, up, m->m, n);
+      mpn_cnd_swap (swap, up, vp, n);
+      cy = mpn_cnd_sub_n (odd, up, up, vp, n);
+      cy -= mpn_cnd_add_n (cy, up, up, m->m, n);
       assert (cy == 0);
 
       cy = mpn_rshift (ap, ap, n, 1);
       assert (cy == 0);
       cy = mpn_rshift (up, up, n, 1);
-      cy = cnd_add_n (cy, up, m->mp1h, n);
+      cy = mpn_cnd_add_n (cy, up, up, m->mp1h, n);
       assert (cy == 0);
     }
   assert ( (ap[0] | ap[n-1]) == 0);
diff --git a/ecc-mod.c b/ecc-mod.c
index 4e77f0c0..fd3b315d 100644
--- a/ecc-mod.c
+++ b/ecc-mod.c
@@ -86,7 +86,7 @@ ecc_mod (const struct ecc_modulo *m, mp_limb_t *rp)
 	    rp[rn+i] = mpn_addmul_1 (rp + rn - mn + i, m->B, bn, rp[rn+i]);
 				     
 	  hi = mpn_add_n (rp + rn - sn, rp + rn - sn, rp + rn, sn);
-	  hi = cnd_add_n (hi, rp + rn - mn, m->B, mn);
+	  hi = mpn_cnd_add_n (hi, rp + rn - mn, rp + rn - mn, m->B, mn);
 	  assert (hi == 0);
 	}
     }
@@ -113,7 +113,7 @@ ecc_mod (const struct ecc_modulo *m, mp_limb_t *rp)
     }
   else
     {
-      hi = cnd_add_n (hi, rp, m->B_shifted, mn);
+      hi = mpn_cnd_add_n (hi, rp, rp, m->B_shifted, mn);
       assert (hi == 0);
     }
 }
diff --git a/ecc-mul-m.c b/ecc-mul-m.c
index 68bdd16e..ce612360 100644
--- a/ecc-mul-m.c
+++ b/ecc-mul-m.c
@@ -87,7 +87,7 @@ ecc_mul_m (const struct ecc_modulo *m,
     {
       int bit = (n[i/8] >> (i & 7)) & 1;
 
-      cnd_swap (bit, x2, x3, 2*m->size);
+      mpn_cnd_swap (bit, x2, x3, 2*m->size);
 
       /* Formulas from RFC 7748. We compute new coordinates in
 	 memory-address order, since mul and sqr clobbers higher
@@ -112,8 +112,8 @@ ecc_mul_m (const struct ecc_modulo *m,
       ecc_mod_sqr (m, DA, C);
       ecc_mod_mul (m, z3, DA, px);
 
-      /* FIXME: Could be combined with the loop's initial cnd_swap. */
-      cnd_swap (bit, x2, x3, 2*m->size);
+      /* FIXME: Could be combined with the loop's initial mpn_cnd_swap. */
+      mpn_cnd_swap (bit, x2, x3, 2*m->size);
     }
   /* Do the low zero bits, just duplicating x2 */
   for (i = 0; i < bit_low; i++)
diff --git a/ecc-pm1-redc.c b/ecc-pm1-redc.c
index 2ed50ca5..1b07b793 100644
--- a/ecc-pm1-redc.c
+++ b/ecc-pm1-redc.c
@@ -53,7 +53,7 @@ ecc_pm1_redc (const struct ecc_modulo *m, mp_limb_t *rp)
     rp[i] = mpn_submul_1 (rp + i + k,
 			  m->redc_mpm1, m->size - k, rp[i]);
   hi = mpn_sub_n (rp, rp + m->size, rp, m->size);
-  cy = cnd_add_n (hi, rp, m->m, m->size);
+  cy = mpn_cnd_add_n (hi, rp, rp, m->m, m->size);
   assert (cy == hi);
 
   if (shift > 0)
diff --git a/ecc-pp1-redc.c b/ecc-pp1-redc.c
index ae5b9669..9f643d97 100644
--- a/ecc-pp1-redc.c
+++ b/ecc-pp1-redc.c
@@ -63,7 +63,7 @@ ecc_pp1_redc (const struct ecc_modulo *m, mp_limb_t *rp)
     }
   else
     {
-      cy = cnd_sub_n (hi, rp, m->m, m->size);
+      cy = mpn_cnd_sub_n (hi, rp, rp, m->m, m->size);
       assert (cy == hi);      
     }
 }
diff --git a/ecc-secp192r1.c b/ecc-secp192r1.c
index 046026f3..05c26408 100644
--- a/ecc-secp192r1.c
+++ b/ecc-secp192r1.c
@@ -78,7 +78,7 @@ ecc_secp192r1_modp (const struct ecc_modulo *m UNUSED, mp_limb_t *rp)
   cy = sec_add_1 (rp + 5, rp + 5, 1, cy);
   
   assert (cy <= 1);
-  cy = cnd_add_n (cy, rp, ecc_Bmodp, 6);
+  cy = mpn_cnd_add_n (cy, rp, rp, ecc_Bmodp, 6);
   assert (cy == 0);  
 }
 #elif GMP_NUMB_BITS == 64
@@ -102,7 +102,7 @@ ecc_secp192r1_modp (const struct ecc_modulo *m UNUSED, mp_limb_t *rp)
   cy += mpn_add_n (rp + 1, rp + 1, rp + 3, 2);
 
   assert (cy <= 1);
-  cy = cnd_add_n (cy, rp, ecc_Bmodp, 3);
+  cy = mpn_cnd_add_n (cy, rp, rp, ecc_Bmodp, 3);
   assert (cy == 0);  
 }
   
diff --git a/ecc-secp256r1.c b/ecc-secp256r1.c
index adab8d90..4b153327 100644
--- a/ecc-secp256r1.c
+++ b/ecc-secp256r1.c
@@ -127,7 +127,7 @@ ecc_secp256r1_modp (const struct ecc_modulo *p, mp_limb_t *rp)
 	 shifts rather than mul.
       */
       t = mpn_submul_1 (rp + n - 4, p->m, 2, q1);
-      t += cnd_sub_n (q2, rp + n - 3, p->m, 1);
+      t += mpn_cnd_sub_n (q2, rp + n - 3, rp + n - 3, p->m, 1);
       t += (-q2) & 0xffffffff;
 
       u0 = rp[n-2];
@@ -136,7 +136,7 @@ ecc_secp256r1_modp (const struct ecc_modulo *p, mp_limb_t *rp)
       t = (u1 < cy);
       u1 -= cy;
 
-      cy = cnd_add_n (t, rp + n - 4, p->m, 2);
+      cy = mpn_cnd_add_n (t, rp + n - 4, rp + n - 4, p->m, 2);
       u0 += cy;
       u1 += (u0 < cy);
       u1 -= (-t) & 0xffffffff;
@@ -210,7 +210,7 @@ ecc_secp256r1_modq (const struct ecc_modulo *q, mp_limb_t *rp)
 
       assert (q2 < 2);
 
-      c0 = cnd_sub_n (q2, rp + n - 3, q->m, 1);
+      c0 = mpn_cnd_sub_n (q2, rp + n - 3, rp + n - 3, q->m, 1);
       c0 += (-q2) & q->m[1];
       t = mpn_submul_1 (rp + n - 4, q->m, 2, q1);
       c0 += t;
@@ -227,7 +227,7 @@ ecc_secp256r1_modq (const struct ecc_modulo *q, mp_limb_t *rp)
       u1 += t;
       u2 += (t<<32) + (u1 < t);
 
-      t = cnd_add_n (t, rp + n - 4, q->m, 2);
+      t = mpn_cnd_add_n (t, rp + n - 4, rp + n - 4, q->m, 2);
       u1 += t;
       u2 += (u1 < t);
     }
diff --git a/ecc-secp384r1.c b/ecc-secp384r1.c
index 54bcd112..317899e4 100644
--- a/ecc-secp384r1.c
+++ b/ecc-secp384r1.c
@@ -99,7 +99,7 @@ ecc_secp384r1_modp (const struct ecc_modulo *p, mp_limb_t *rp)
   assert (cy >= bw);
   cy -= bw;
   assert (cy <= 1);
-  cy = cnd_add_n (cy, rp, p->B, ECC_LIMB_SIZE);
+  cy = mpn_cnd_add_n (cy, rp, rp, p->B, ECC_LIMB_SIZE);
   assert (cy == 0);
 }
 #elif GMP_NUMB_BITS == 64
@@ -140,7 +140,7 @@ ecc_secp384r1_modp (const struct ecc_modulo *p, mp_limb_t *rp)
   cy = sec_add_1 (rp + 5, rp + 5, 1, cy);
   assert (cy <= 1);
 
-  cy = cnd_add_n (cy, rp, p->B, ECC_LIMB_SIZE);
+  cy = mpn_cnd_add_n (cy, rp, rp, p->B, ECC_LIMB_SIZE);
   assert (cy == 0);  
 }
 #else
diff --git a/eddsa-hash.c b/eddsa-hash.c
index e05f6ac1..3f21dac4 100644
--- a/eddsa-hash.c
+++ b/eddsa-hash.c
@@ -71,7 +71,7 @@ _eddsa_hash (const struct ecc_modulo *m,
 
       hi = mpn_addmul_1 (rp + m->size, m->B, m->size, hi);
       assert (hi <= 1);
-      hi = cnd_add_n (hi, rp + m->size, m->B, m->size);
+      hi = mpn_cnd_add_n (hi, rp + m->size, rp + m->size, m->B, m->size);
       assert (hi == 0);
     }
   m->mod (m, rp);
diff --git a/eddsa-sign.c b/eddsa-sign.c
index acb8299b..f8bdf255 100644
--- a/eddsa-sign.c
+++ b/eddsa-sign.c
@@ -117,7 +117,7 @@ _eddsa_sign (const struct ecc_curve *ecc,
 
   cy = mpn_submul_1 (sp, ecc->q.m, ecc->p.size, q);
   assert (cy < 2);
-  cy -= cnd_add_n (cy, sp, ecc->q.m, ecc->p.size);
+  cy -= mpn_cnd_add_n (cy, sp, sp, ecc->q.m, ecc->p.size);
   assert (cy == 0);
 
   mpn_get_base256_le (signature + nbytes, nbytes, sp, ecc->q.size);
diff --git a/gmp-glue.c b/gmp-glue.c
index 8819601f..3bfc6175 100644
--- a/gmp-glue.c
+++ b/gmp-glue.c
@@ -39,10 +39,54 @@
 
 #include "gmp-glue.h"
 
+#if NETTLE_USE_MINI_GMP
+mp_limb_t
+mpn_cnd_add_n (mp_limb_t cnd, mp_limb_t *rp,
+	       const mp_limb_t *ap, const mp_limb_t *bp, mp_size_t n)
+{
+  mp_limb_t cy, mask;
+  mp_size_t  i;
+
+  mask = -(mp_limb_t) (cnd != 0);
+
+  for (i = 0, cy = 0; i < n; i++)
+    {
+      mp_limb_t rl = ap[i] + cy;
+      mp_limb_t bl = bp[i] & mask;
+      cy = (rl < cy);
+      rl += bl;
+      cy += (rl < bl);
+      rp[i] = rl;
+    }
+  return cy;
+}
+
+mp_limb_t
+mpn_cnd_sub_n (mp_limb_t cnd, mp_limb_t *rp,
+	       const mp_limb_t *ap, const mp_limb_t *bp, mp_size_t n)
+{
+  mp_limb_t cy, mask;
+  mp_size_t  i;
+
+  mask = -(mp_limb_t) (cnd != 0);
+
+  for (i = 0, cy = 0; i < n; i++)
+    {
+      mp_limb_t al = ap[i];
+      mp_limb_t bl = bp[i] & mask;
+      mp_limb_t sl;
+      sl = al - cy;
+      cy = (al < cy) + (sl < bl);
+      sl -= bl;
+      rp[i] = sl;
+    }
+  return cy;
+}
+
 void
-cnd_swap (mp_limb_t cnd, mp_limb_t *ap, mp_limb_t *bp, mp_size_t n)
+mpn_cnd_swap (mp_limb_t cnd, volatile mp_limb_t *ap, volatile mp_limb_t *bp, mp_size_t n)
 {
-  mp_limb_t mask = - (mp_limb_t) (cnd != 0);
+  volatile mp_limb_t mask = - (mp_limb_t) (cnd != 0);
   mp_size_t i;
   for (i = 0; i < n; i++)
     {
@@ -55,6 +99,8 @@ cnd_swap (mp_limb_t cnd, mp_limb_t *ap, mp_limb_t *bp, mp_size_t n)
     }
 }
 
+#endif /* NETTLE_USE_MINI_GMP */
+
 /* Additional convenience functions. */
 
 int
diff --git a/gmp-glue.h b/gmp-glue.h
index 4dfcb384..7ebfd782 100644
--- a/gmp-glue.h
+++ b/gmp-glue.h
@@ -35,7 +35,6 @@
 
 #include "bignum.h"
 
-#define cnd_swap _nettle_cnd_swap
 #define mpz_limbs_cmp _nettle_mpz_limbs_cmp
 #define mpz_limbs_read_n _nettle_mpz_limbs_read_n
 #define mpz_limbs_copy _nettle_mpz_limbs_copy
@@ -57,22 +56,22 @@
   } while (0)
 #define TMP_GMP_FREE(name) (gmp_free(name, tmp_##name##_size))
 
+#if NETTLE_USE_MINI_GMP
+mp_limb_t
+mpn_cnd_add_n (mp_limb_t cnd, mp_limb_t *rp,
+	       const mp_limb_t *ap, const mp_limb_t *bp, mp_size_t n);
 
-/* Use only in-place operations, so we can fall back to addmul_1/submul_1 */
-#ifdef mpn_cnd_add_n
-# define cnd_add_n(cnd, rp, ap, n) mpn_cnd_add_n ((cnd), (rp), (rp), (ap), (n))
-# define cnd_sub_n(cnd, rp, ap, n) mpn_cnd_sub_n ((cnd), (rp), (rp), (ap), (n))
-#else
-# define cnd_add_n(cnd, rp, ap, n) mpn_addmul_1 ((rp), (ap), (n), (cnd) != 0)
-# define cnd_sub_n(cnd, rp, ap, n) mpn_submul_1 ((rp), (ap), (n), (cnd) != 0)
+mp_limb_t
+mpn_cnd_sub_n (mp_limb_t cnd, mp_limb_t *rp,
+	       const mp_limb_t *ap, const mp_limb_t *bp, mp_size_t n);
+
+void
+mpn_cnd_swap (mp_limb_t cnd, volatile mp_limb_t *ap, volatile mp_limb_t *bp, mp_size_t n);
 #endif
 
 #define NETTLE_OCTET_SIZE_TO_LIMB_SIZE(n) \
   (((n) * 8 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
 
-void
-cnd_swap (mp_limb_t cnd, mp_limb_t *ap, mp_limb_t *bp, mp_size_t n);
-
 /* Convenience functions */
 int
 mpz_limbs_cmp (mpz_srcptr a, const mp_limb_t *bp, mp_size_t bn);
diff --git a/rsa-sec-compute-root.c b/rsa-sec-compute-root.c
index 98b6c2a5..8e9676b6 100644
--- a/rsa-sec-compute-root.c
+++ b/rsa-sec-compute-root.c
@@ -184,7 +184,7 @@ _rsa_sec_compute_root (const struct rsa_private_key *key,
   sec_mod_mul (scratch_out, r_mod_q, qn, mpz_limbs_read (key->c), cn, pp, pn,
 	       scratch_out + cn + qn);
   cy = mpn_sub_n (r_mod_p, r_mod_p, scratch_out, pn);
-  cnd_add_n (cy, r_mod_p, pp, pn);
+  mpn_cnd_add_n (cy, r_mod_p, r_mod_p, pp, pn);
 
   /* Finally, compute x = r_mod_q + q r_mod_p' */
   sec_mul (scratch_out, qp, qn, r_mod_p, pn, scratch_out + pn + qn);