aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/math')
-rw-r--r--src/lib/math/mp/mp_karat.cpp43
-rw-r--r--src/lib/math/numbertheory/def_powm.h1
-rw-r--r--src/lib/math/numbertheory/numthry.cpp3
-rw-r--r--src/lib/math/numbertheory/pow_mod.cpp21
-rw-r--r--src/lib/math/numbertheory/pow_mod.h36
-rw-r--r--src/lib/math/numbertheory/powm_fw.cpp2
-rw-r--r--src/lib/math/numbertheory/powm_mnt.cpp7
7 files changed, 79 insertions, 34 deletions
diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp
index 7a763e2a9..62a52b88c 100644
--- a/src/lib/math/mp/mp_karat.cpp
+++ b/src/lib/math/mp/mp_karat.cpp
@@ -255,53 +255,58 @@ size_t karatsuba_size(size_t z_size, size_t x_size, size_t x_sw)
*/
void bigint_mul(BigInt& z, const BigInt& x, const BigInt& y, word workspace[])
{
- if(x.sig_words() == 1)
+ const size_t x_sig_words = x.sig_words();
+ const size_t y_sig_words = y.sig_words();
+
+ clear_mem(z.mutable_data(), z.size());
+
+ if(x_sig_words == 1)
{
- bigint_linmul3(z.mutable_data(), y.data(), y.sig_words(), x.data()[0]);
+ bigint_linmul3(z.mutable_data(), y.data(), y_sig_words, x.data()[0]);
}
- else if(y.sig_words() == 1)
+ else if(y_sig_words == 1)
{
- bigint_linmul3(z.mutable_data(), x.data(), x.sig_words(), y.data()[0]);
+ bigint_linmul3(z.mutable_data(), x.data(), x_sig_words, y.data()[0]);
}
- else if(x.sig_words() <= 4 && x.size() >= 4 &&
- y.sig_words() <= 4 && y.size() >= 4 && z.size() >= 8)
+ else if(x_sig_words <= 4 && x.size() >= 4 &&
+ y_sig_words <= 4 && y.size() >= 4 && z.size() >= 8)
{
bigint_comba_mul4(z.mutable_data(), x.data(), y.data());
}
- else if(x.sig_words() <= 6 && x.size() >= 6 &&
- y.sig_words() <= 6 && y.size() >= 6 && z.size() >= 12)
+ else if(x_sig_words <= 6 && x.size() >= 6 &&
+ y_sig_words <= 6 && y.size() >= 6 && z.size() >= 12)
{
bigint_comba_mul6(z.mutable_data(), x.data(), y.data());
}
- else if(x.sig_words() <= 8 && x.size() >= 8 &&
- y.sig_words() <= 8 && y.size() >= 8 && z.size() >= 16)
+ else if(x_sig_words <= 8 && x.size() >= 8 &&
+ y_sig_words <= 8 && y.size() >= 8 && z.size() >= 16)
{
bigint_comba_mul8(z.mutable_data(), x.data(), y.data());
}
- else if(x.sig_words() <= 9 && x.size() >= 9 &&
- y.sig_words() <= 9 && y.size() >= 9 && z.size() >= 18)
+ else if(x_sig_words <= 9 && x.size() >= 9 &&
+ y_sig_words <= 9 && y.size() >= 9 && z.size() >= 18)
{
bigint_comba_mul9(z.mutable_data(), x.data(), y.data());
}
- else if(x.sig_words() <= 16 && x.size() >= 16 &&
- y.sig_words() <= 16 && y.size() >= 16 && z.size() >= 32)
+ else if(x_sig_words <= 16 && x.size() >= 16 &&
+ y_sig_words <= 16 && y.size() >= 16 && z.size() >= 32)
{
bigint_comba_mul16(z.mutable_data(), x.data(), y.data());
}
- else if(x.sig_words() < KARATSUBA_MULTIPLY_THRESHOLD ||
- y.sig_words() < KARATSUBA_MULTIPLY_THRESHOLD ||
+ else if(x_sig_words < KARATSUBA_MULTIPLY_THRESHOLD ||
+ y_sig_words < KARATSUBA_MULTIPLY_THRESHOLD ||
!workspace)
{
- basecase_mul(z.mutable_data(), x.data(), x.sig_words(), y.data(), y.sig_words());
+ basecase_mul(z.mutable_data(), x.data(), x_sig_words, y.data(), y_sig_words);
}
else
{
- const size_t N = karatsuba_size(z.size(), x.size(), x.sig_words(), y.size(), y.sig_words());
+ const size_t N = karatsuba_size(z.size(), x.size(), x_sig_words, y.size(), y_sig_words);
if(N)
karatsuba_mul(z.mutable_data(), x.data(), y.data(), N, workspace);
else
- basecase_mul(z.mutable_data(), x.data(), x.sig_words(), y.data(), y.sig_words());
+ basecase_mul(z.mutable_data(), x.data(), x_sig_words, y.data(), y_sig_words);
}
}
diff --git a/src/lib/math/numbertheory/def_powm.h b/src/lib/math/numbertheory/def_powm.h
index d60ca8173..10ae8aa5b 100644
--- a/src/lib/math/numbertheory/def_powm.h
+++ b/src/lib/math/numbertheory/def_powm.h
@@ -52,6 +52,7 @@ class Montgomery_Exponentiator : public Modular_Exponentiator
Montgomery_Exponentiator(const BigInt&, Power_Mod::Usage_Hints);
private:
BigInt m_exp, m_modulus, m_R_mod, m_R2_mod;
+ Modular_Reducer m_reducer;
word m_mod_prime;
size_t m_mod_words, m_exp_bits, m_window_bits;
Power_Mod::Usage_Hints m_hints;
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 6c3d2c931..71dbf6aba 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -358,6 +358,9 @@ word monty_inverse(word input)
y1 = y;
}
+ const word check = y2 * input;
+ BOTAN_ASSERT_EQUAL(check, 1, "monty_inverse result is inverse of input");
+
// Now invert in addition space
y2 = (MP_WORD_MAX - y2) + 1;
diff --git a/src/lib/math/numbertheory/pow_mod.cpp b/src/lib/math/numbertheory/pow_mod.cpp
index 5503f313c..9f7459ac5 100644
--- a/src/lib/math/numbertheory/pow_mod.cpp
+++ b/src/lib/math/numbertheory/pow_mod.cpp
@@ -13,10 +13,10 @@ namespace Botan {
/*
* Power_Mod Constructor
*/
-Power_Mod::Power_Mod(const BigInt& n, Usage_Hints hints)
+Power_Mod::Power_Mod(const BigInt& n, Usage_Hints hints, bool disable_monty)
{
m_core = nullptr;
- set_modulus(n, hints);
+ set_modulus(n, hints, disable_monty);
}
/*
@@ -58,14 +58,21 @@ Power_Mod::~Power_Mod()
/*
* Set the modulus
*/
-void Power_Mod::set_modulus(const BigInt& n, Usage_Hints hints) const
+void Power_Mod::set_modulus(const BigInt& n, Usage_Hints hints, bool disable_monty) const
{
+ // Allow set_modulus(0) to mean "drop old state"
+
delete m_core;
+ m_core = nullptr;
+ disable_monty =true;
+ if(n != 0)
+ {
+ if(n.is_odd() && disable_monty == false)
+ m_core = new Montgomery_Exponentiator(n, hints);
- if(n.is_odd())
- m_core = new Montgomery_Exponentiator(n, hints);
- else if(n != 0)
- m_core = new Fixed_Window_Exponentiator(n, hints);
+ if(!m_core)
+ m_core = new Fixed_Window_Exponentiator(n, hints);
+ }
}
/*
diff --git a/src/lib/math/numbertheory/pow_mod.h b/src/lib/math/numbertheory/pow_mod.h
index 4f94fd62d..194d00ec8 100644
--- a/src/lib/math/numbertheory/pow_mod.h
+++ b/src/lib/math/numbertheory/pow_mod.h
@@ -51,15 +51,43 @@ class BOTAN_DLL Power_Mod
static size_t window_bits(size_t exp_bits, size_t base_bits,
Power_Mod::Usage_Hints hints);
- void set_modulus(const BigInt&, Usage_Hints = NO_HINTS) const;
- void set_base(const BigInt&) const;
- void set_exponent(const BigInt&) const;
+ /**
+ * @param modulus the modulus
+ * @param hints Passed to set_modulus if modulus > 0
+ * @param disable_montgomery_arith Disables use of Montgomery
+ * representation. Likely only useful for testing.
+ */
+ void set_modulus(const BigInt& modulus,
+ Usage_Hints = NO_HINTS,
+ bool disable_montgomery_arith = false) const;
+
+ /**
+ * Set the base
+ */
+ void set_base(const BigInt& base) const;
+ /**
+ * Set the exponent
+ */
+ void set_exponent(const BigInt& exponent) const;
+
+ /**
+ * All three of the above functions must have already been called.
+ * @return result of g^x%p
+ */
BigInt execute() const;
Power_Mod& operator=(const Power_Mod&);
- Power_Mod(const BigInt& = 0, Usage_Hints = NO_HINTS);
+ /**
+ * @param modulus Optionally call set_modulus
+ * @param hints Passed to set_modulus if modulus > 0
+ * @param disable_montgomery_arith Disables use of Montgomery
+ * representation. Likely only useful for testing.
+ */
+ Power_Mod(const BigInt& modulus = 0,
+ Usage_Hints hints = NO_HINTS,
+ bool disable_montgomery_arith = false);
Power_Mod(const Power_Mod&);
virtual ~Power_Mod();
private:
diff --git a/src/lib/math/numbertheory/powm_fw.cpp b/src/lib/math/numbertheory/powm_fw.cpp
index 7369959a9..7d69a2602 100644
--- a/src/lib/math/numbertheory/powm_fw.cpp
+++ b/src/lib/math/numbertheory/powm_fw.cpp
@@ -31,7 +31,7 @@ void Fixed_Window_Exponentiator::set_base(const BigInt& base)
m_g[1] = base;
for(size_t i = 2; i != m_g.size(); ++i)
- m_g[i] = m_reducer.multiply(m_g[i-1], m_g[0]);
+ m_g[i] = m_reducer.multiply(m_g[i-1], m_g[1]);
}
/*
diff --git a/src/lib/math/numbertheory/powm_mnt.cpp b/src/lib/math/numbertheory/powm_mnt.cpp
index 572f0de98..546a2739a 100644
--- a/src/lib/math/numbertheory/powm_mnt.cpp
+++ b/src/lib/math/numbertheory/powm_mnt.cpp
@@ -41,7 +41,7 @@ void Montgomery_Exponentiator::set_base(const BigInt& base)
workspace.data());
m_g[0] = z;
- m_g[1] = (base >= m_modulus) ? (base % m_modulus) : base;
+ m_g[1] = m_reducer.reduce(base);
bigint_monty_mul(z, m_g[1], m_R2_mod,
m_modulus.data(), m_mod_words, m_mod_prime,
@@ -112,6 +112,7 @@ BigInt Montgomery_Exponentiator::execute() const
Montgomery_Exponentiator::Montgomery_Exponentiator(const BigInt& mod,
Power_Mod::Usage_Hints hints) :
m_modulus(mod),
+ m_reducer(m_modulus),
m_mod_words(m_modulus.sig_words()),
m_window_bits(1),
m_hints(hints)
@@ -123,8 +124,8 @@ Montgomery_Exponentiator::Montgomery_Exponentiator(const BigInt& mod,
m_mod_prime = monty_inverse(mod.word_at(0));
const BigInt r = BigInt::power_of_2(m_mod_words * BOTAN_MP_WORD_BITS);
- m_R_mod = r % m_modulus;
- m_R2_mod = (m_R_mod * m_R_mod) % m_modulus;
+ m_R_mod = m_reducer.reduce(r);
+ m_R2_mod = m_reducer.square(m_R_mod);
m_exp_bits = 0;
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-01 22:32:32 +0000