aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJack Lloyd <[email protected]>2019-07-08 20:53:47 -0400
committerJack Lloyd <[email protected]>2019-10-12 03:02:24 -0400
commit16661a7b6404be359cd5ad4d55f1b5b51e7daa98 (patch)
tree134bcc4b4be36306b42f017c8ae82d9b1d0400d5
parentabdcd9f87c07308f89aa4ac449460823286fbf74 (diff)
Add constant-time gcd
Previous version leaked some (minimal) information from the loop bounds.
-rw-r--r--src/lib/math/mp/mp_core.h5
-rw-r--r--src/lib/math/numbertheory/numthry.cpp62
-rw-r--r--src/lib/pubkey/rsa/rsa.cpp1
-rw-r--r--src/tests/test_bigint.cpp3
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;
}
};