From 16661a7b6404be359cd5ad4d55f1b5b51e7daa98 Mon Sep 17 00:00:00 2001
From: Jack Lloyd <jack@randombit.net>
Date: Mon, 8 Jul 2019 20:53:47 -0400
Subject: Add constant-time gcd

Previous version leaked some (minimal) information from the loop
bounds.
---
 src/lib/math/mp/mp_core.h             |  5 +--
 src/lib/math/numbertheory/numthry.cpp | 62 +++++++++++++++++++++++++++--------
 src/lib/pubkey/rsa/rsa.cpp            |  1 -
 src/tests/test_bigint.cpp             |  3 +-
 4 files changed, 54 insertions(+), 17 deletions(-)

diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h
index 9de8c375c..e59be0c39 100644
--- a/src/lib/math/mp/mp_core.h
+++ b/src/lib/math/mp/mp_core.h
@@ -656,8 +656,9 @@ bigint_sub_abs(word z[],
    const int32_t relative_size = bigint_cmp(x, x_size, y, y_size);
 
    // Swap if relative_size == -1
-   CT::conditional_swap_ptr(relative_size < 0, x, y);
-   CT::conditional_swap(relative_size < 0, x_size, y_size);
+   const bool need_swap = relative_size < 0;
+   CT::conditional_swap_ptr(need_swap, x, y);
+   CT::conditional_swap(need_swap, x_size, y_size);
 
    /*
    * We know at this point that x >= y so if y_size is larger than
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index a69028189..0d21f0237 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -19,6 +19,21 @@
 
 namespace Botan {
 
+namespace {
+
+void sub_abs(BigInt& z, const BigInt& x, const BigInt& y)
+   {
+   const size_t x_sw = x.sig_words();
+   const size_t y_sw = y.sig_words();
+   z.resize(std::max(x_sw, y_sw));
+
+   bigint_sub_abs(z.mutable_data(),
+                  x.data(), x_sw,
+                  y.data(), y_sw);
+   }
+
+}
+
 /*
 * Return the number of 0 bits at the end of n
 */
@@ -55,27 +70,48 @@ BigInt gcd(const BigInt& a, const BigInt& b)
    if(a == 1 || b == 1)
       return 1;
 
-   BigInt X[2] = { a, b };
-   X[0].set_sign(BigInt::Positive);
-   X[1].set_sign(BigInt::Positive);
+   BigInt f = a;
+   BigInt g = b;
+   f.set_sign(BigInt::Positive);
+   g.set_sign(BigInt::Positive);
 
-   const size_t shift = std::min(low_zero_bits(X[0]), low_zero_bits(X[1]));
+   const size_t common2s = std::min(low_zero_bits(f), low_zero_bits(g));
 
-   X[0] >>= shift;
-   X[1] >>= shift;
+   f >>= common2s;
+   g >>= common2s;
 
-   while(X[0].is_nonzero())
+   f.ct_cond_swap(f.is_even(), g);
+
+   int32_t delta = 1;
+
+   const size_t loop_cnt = 4 + 3*std::max(f.bits(), g.bits());
+
+   BigInt newg, t;
+   for(size_t i = 0; i != loop_cnt; ++i)
       {
-      X[0] >>= low_zero_bits(X[0]);
-      X[1] >>= low_zero_bits(X[1]);
+      g.shrink_to_fit();
+      f.shrink_to_fit();
+      sub_abs(newg, f, g);
+
+      const uint8_t need_swap = (g.is_odd() && delta > 0);
 
-      const uint8_t sel = static_cast<uint8_t>(X[0] >= X[1]);
+      // if(need_swap) delta *= -1
+      delta *= CT::Mask<uint8_t>::expand(need_swap).select(0, 2) - 1;
+      f.ct_cond_swap(need_swap, g);
+      g.ct_cond_swap(need_swap, newg);
 
-      X[sel^1] -= X[sel];
-      X[sel^1] >>= 1;
+      delta += 1;
+
+      t = g;
+      t += f;
+      g.ct_cond_assign(g.is_odd(), t);
+
+      g >>= 1;
       }
 
-   return (X[1] << shift);
+   f <<= common2s;
+
+   return f;
    }
 
 /*
diff --git a/src/lib/pubkey/rsa/rsa.cpp b/src/lib/pubkey/rsa/rsa.cpp
index 5f597b811..830b1a5e8 100644
--- a/src/lib/pubkey/rsa/rsa.cpp
+++ b/src/lib/pubkey/rsa/rsa.cpp
@@ -297,7 +297,6 @@ RSA_PrivateKey::RSA_PrivateKey(RandomNumberGenerator& rng,
    const BigInt p_minus_1 = p - 1;
    const BigInt q_minus_1 = q - 1;
 
-   // FIXME: lcm calls gcd which is not completely const time
    const BigInt phi_n = lcm(p_minus_1, q_minus_1);
    // FIXME: this uses binary ext gcd because phi_n is even
    d = inverse_mod(e, phi_n);
diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp
index 3ea57d584..2e41e0004 100644
--- a/src/tests/test_bigint.cpp
+++ b/src/tests/test_bigint.cpp
@@ -446,7 +446,8 @@ class BigInt_GCD_Test final : public Text_Based_Test
 
          const BigInt g = Botan::gcd(x, y);
 
-         result.test_eq("gcd", expected, g);
+         result.test_eq("gcd", g, expected);
+
          return result;
          }
    };
-- 
cgit v1.2.3