aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/math')
-rw-r--r--src/lib/math/bigint/big_ops3.cpp6
-rw-r--r--src/lib/math/numbertheory/def_powm.h11
-rw-r--r--src/lib/math/numbertheory/info.txt1
-rw-r--r--src/lib/math/numbertheory/monty_exp.cpp153
-rw-r--r--src/lib/math/numbertheory/monty_exp.h36
-rw-r--r--src/lib/math/numbertheory/numthry.cpp6
-rw-r--r--src/lib/math/numbertheory/powm_mnt.cpp115
7 files changed, 213 insertions, 115 deletions
diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp
index 48d84c8b4..eed8a29a0 100644
--- a/src/lib/math/bigint/big_ops3.cpp
+++ b/src/lib/math/bigint/big_ops3.cpp
@@ -107,6 +107,9 @@ BigInt operator*(const BigInt& x, const BigInt& y)
*/
BigInt operator/(const BigInt& x, const BigInt& y)
{
+ if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
+ return (x >> (y.bits() - 1));
+
BigInt q, r;
divide(x, y, q, r);
return q;
@@ -137,6 +140,9 @@ word operator%(const BigInt& n, word mod)
if(mod == 0)
throw BigInt::DivideByZero();
+ if(mod == 1)
+ return 0;
+
if(is_power_of_2(mod))
return (n.word_at(0) & (mod - 1));
diff --git a/src/lib/math/numbertheory/def_powm.h b/src/lib/math/numbertheory/def_powm.h
index 826ffb49f..fe705bf96 100644
--- a/src/lib/math/numbertheory/def_powm.h
+++ b/src/lib/math/numbertheory/def_powm.h
@@ -36,6 +36,8 @@ class Fixed_Window_Exponentiator final : public Modular_Exponentiator
Power_Mod::Usage_Hints m_hints;
};
+class Montgomery_Exponentation_State;
+
/**
* Montgomery Exponentiator
*/
@@ -51,12 +53,11 @@ class Montgomery_Exponentiator final : 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;
+ std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
+ BigInt m_p;
+ Modular_Reducer m_mod_p;
+ BigInt m_e;
Power_Mod::Usage_Hints m_hints;
- std::vector<BigInt> m_g;
};
}
diff --git a/src/lib/math/numbertheory/info.txt b/src/lib/math/numbertheory/info.txt
index 0a386b9f3..01adb7345 100644
--- a/src/lib/math/numbertheory/info.txt
+++ b/src/lib/math/numbertheory/info.txt
@@ -12,6 +12,7 @@ reducer.h
<header:internal>
def_powm.h
+monty_exp.h
</header:internal>
<requires>
diff --git a/src/lib/math/numbertheory/monty_exp.cpp b/src/lib/math/numbertheory/monty_exp.cpp
new file mode 100644
index 000000000..35d4cd668
--- /dev/null
+++ b/src/lib/math/numbertheory/monty_exp.cpp
@@ -0,0 +1,153 @@
+/*
+* Montgomery Exponentiation
+* (C) 1999-2010,2012,2018 Jack Lloyd
+* 2016 Matthias Gierlings
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/internal/monty_exp.h>
+#include <botan/numthry.h>
+#include <botan/reducer.h>
+#include <botan/internal/mp_core.h>
+
+namespace Botan {
+
+class Montgomery_Exponentation_State
+ {
+ public:
+ Montgomery_Exponentation_State(const BigInt& g,
+ const BigInt& p,
+ const Modular_Reducer& mod_p,
+ size_t window_bits);
+
+ BigInt exponentiation(const BigInt& k) const;
+ private:
+ BigInt m_p;
+ BigInt m_R_mod;
+ BigInt m_R2_mod;
+ word m_mod_prime;
+ size_t m_p_words;
+ size_t m_window_bits;
+ std::vector<BigInt> m_g;
+ };
+
+Montgomery_Exponentation_State::Montgomery_Exponentation_State(const BigInt& g,
+ const BigInt& p,
+ const Modular_Reducer& mod_p,
+ size_t window_bits) :
+ m_p(p),
+ m_p_words(p.sig_words()),
+ m_window_bits(window_bits)
+ {
+ if(p.is_positive() == false || p.is_even())
+ throw Invalid_Argument("Cannot use Montgomery reduction on even or negative integer");
+
+ if(window_bits > 12) // really even 8 is too large ...
+ throw Invalid_Argument("Montgomery window bits too large");
+
+ m_mod_prime = monty_inverse(m_p.word_at(0));
+
+ const BigInt r = BigInt::power_of_2(m_p_words * BOTAN_MP_WORD_BITS);
+ m_R_mod = mod_p.reduce(r);
+ m_R2_mod = mod_p.square(m_R_mod);
+
+ m_g.resize(1U << m_window_bits);
+
+ BigInt z(BigInt::Positive, 2 * (m_p_words + 1));
+ secure_vector<word> workspace(z.size());
+
+ m_g[0] = 1;
+
+ bigint_monty_mul(z, m_g[0], m_R2_mod,
+ m_p.data(), m_p_words, m_mod_prime,
+ workspace.data());
+ m_g[0] = z;
+
+ m_g[1] = mod_p.reduce(g);
+
+ bigint_monty_mul(z, m_g[1], m_R2_mod,
+ m_p.data(), m_p_words, m_mod_prime,
+ workspace.data());
+
+ m_g[1] = z;
+
+ const BigInt& x = m_g[1];
+
+ for(size_t i = 2; i != m_g.size(); ++i)
+ {
+ const BigInt& y = m_g[i-1];
+
+ bigint_monty_mul(z, x, y, m_p.data(), m_p_words, m_mod_prime,
+ workspace.data());
+
+ m_g[i] = z;
+ m_g[i].shrink_to_fit();
+ m_g[i].grow_to(m_p_words);
+ }
+ }
+
+BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& k) const
+ {
+ const size_t exp_nibbles = (k.bits() + m_window_bits - 1) / m_window_bits;
+
+ BigInt x = m_R_mod;
+
+ const size_t z_size = 2*(m_p_words + 1);
+
+ BigInt z(BigInt::Positive, z_size);
+ secure_vector<word> workspace(z.size());
+ secure_vector<word> e(m_p_words);
+
+ for(size_t i = exp_nibbles; i > 0; --i)
+ {
+ for(size_t j = 0; j != m_window_bits; ++j)
+ {
+ bigint_monty_sqr(z, x, m_p.data(), m_p_words, m_mod_prime,
+ workspace.data());
+
+ x = z;
+ }
+
+ const uint32_t nibble = k.get_substring(m_window_bits*(i-1), m_window_bits);
+
+ BigInt::const_time_lookup(e, m_g, nibble);
+
+ bigint_mul(z.mutable_data(), z.size(),
+ x.data(), x.size(), x.sig_words(),
+ e.data(), m_p_words, m_p_words,
+ workspace.data());
+
+ bigint_monty_redc(z.mutable_data(),
+ m_p.data(), m_p_words, m_mod_prime,
+ workspace.data());
+
+ x = z;
+ }
+
+ x.grow_to(2*m_p_words + 1);
+
+ bigint_monty_redc(x.mutable_data(),
+ m_p.data(), m_p_words, m_mod_prime,
+ workspace.data());
+
+ return x;
+ }
+
+std::shared_ptr<const Montgomery_Exponentation_State>
+monty_precompute(const BigInt& g,
+ const BigInt& p,
+ const Modular_Reducer& mod_p,
+ size_t window_bits)
+ {
+ return std::make_shared<const Montgomery_Exponentation_State>(g, p, mod_p, window_bits);
+ }
+
+BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
+ const BigInt& k)
+ {
+ return precomputed_state.exponentiation(k);
+ }
+
+}
+
diff --git a/src/lib/math/numbertheory/monty_exp.h b/src/lib/math/numbertheory/monty_exp.h
new file mode 100644
index 000000000..65fc9ce4b
--- /dev/null
+++ b/src/lib/math/numbertheory/monty_exp.h
@@ -0,0 +1,36 @@
+/*
+* (C) 2018 Jack Lloyd
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#ifndef BOTAN_MONTY_EXP_H_
+#define BOTAN_MONTY_EXP_H_
+
+#include <memory>
+
+namespace Botan {
+
+class BigInt;
+class Modular_Reducer;
+
+class Montgomery_Exponentation_State;
+
+/*
+* Precompute for calculating values g^x mod p
+*/
+std::shared_ptr<const Montgomery_Exponentation_State>
+monty_precompute(const BigInt& g,
+ const BigInt& p,
+ const Modular_Reducer& mod_p,
+ size_t window_bits);
+
+/*
+* Return g^x mod p
+*/
+BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
+ const BigInt& k);
+
+}
+
+#endif
diff --git a/src/lib/math/numbertheory/numthry.cpp b/src/lib/math/numbertheory/numthry.cpp
index 12ac51953..e80ae43ab 100644
--- a/src/lib/math/numbertheory/numthry.cpp
+++ b/src/lib/math/numbertheory/numthry.cpp
@@ -473,15 +473,15 @@ bool is_prime(const BigInt& n, RandomNumberGenerator& rng,
const BigInt n_minus_1 = n - 1;
const size_t s = low_zero_bits(n_minus_1);
- Fixed_Exponent_Power_Mod pow_mod(n_minus_1 >> s, n);
- Modular_Reducer reducer(n);
+ const Modular_Reducer mod_n(n);
+ const Fixed_Exponent_Power_Mod pow_mod(n_minus_1 >> s, n);
for(size_t i = 0; i != test_iterations; ++i)
{
const BigInt a = BigInt::random_integer(rng, 2, n_minus_1);
BigInt y = pow_mod(a);
- if(mr_witness(std::move(y), reducer, n_minus_1, s))
+ if(mr_witness(std::move(y), mod_n, n_minus_1, s))
return false;
}
diff --git a/src/lib/math/numbertheory/powm_mnt.cpp b/src/lib/math/numbertheory/powm_mnt.cpp
index d3b5805e4..81102188b 100644
--- a/src/lib/math/numbertheory/powm_mnt.cpp
+++ b/src/lib/math/numbertheory/powm_mnt.cpp
@@ -1,6 +1,6 @@
/*
* Montgomery Exponentiation
-* (C) 1999-2010,2012 Jack Lloyd
+* (C) 1999-2010,2012,2018 Jack Lloyd
* 2016 Matthias Gierlings
*
* Botan is released under the Simplified BSD License (see license.txt)
@@ -9,131 +9,32 @@
#include <botan/internal/def_powm.h>
#include <botan/numthry.h>
#include <botan/internal/mp_core.h>
+#include <botan/internal/monty_exp.h>
namespace Botan {
-/*
-* Set the exponent
-*/
void Montgomery_Exponentiator::set_exponent(const BigInt& exp)
{
- m_exp = exp;
- m_exp_bits = exp.bits();
+ m_e = exp;
}
-/*
-* Set the base
-*/
void Montgomery_Exponentiator::set_base(const BigInt& base)
{
- m_window_bits = Power_Mod::window_bits(m_exp.bits(), base.bits(), m_hints);
-
- m_g.resize(1U << m_window_bits);
-
- BigInt z(BigInt::Positive, 2 * (m_mod_words + 1));
- secure_vector<word> workspace(z.size());
-
- m_g[0] = 1;
-
- bigint_monty_mul(z, m_g[0], m_R2_mod,
- m_modulus.data(), m_mod_words, m_mod_prime,
- workspace.data());
- m_g[0] = z;
-
- 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,
- workspace.data());
-
- m_g[1] = z;
-
- const BigInt& x = m_g[1];
-
- for(size_t i = 2; i != m_g.size(); ++i)
- {
- const BigInt& y = m_g[i-1];
-
- bigint_monty_mul(z, x, y, m_modulus.data(), m_mod_words, m_mod_prime,
- workspace.data());
-
- m_g[i] = z;
- m_g[i].shrink_to_fit();
- m_g[i].grow_to(m_mod_words);
- }
+ size_t window_bits = Power_Mod::window_bits(m_e.bits(), base.bits(), m_hints);
+ m_monty = monty_precompute(base, m_p, m_mod_p, window_bits);
}
-/*
-* Compute the result
-*/
BigInt Montgomery_Exponentiator::execute() const
{
- const size_t exp_nibbles = (m_exp_bits + m_window_bits - 1) / m_window_bits;
-
- BigInt x = m_R_mod;
-
- const size_t z_size = 2*(m_mod_words + 1);
-
- BigInt z(BigInt::Positive, z_size);
- secure_vector<word> workspace(z.size());
- secure_vector<word> e(m_mod_words);
-
- for(size_t i = exp_nibbles; i > 0; --i)
- {
- for(size_t k = 0; k != m_window_bits; ++k)
- {
- bigint_monty_sqr(z, x, m_modulus.data(), m_mod_words, m_mod_prime,
- workspace.data());
-
- x = z;
- }
-
- const uint32_t nibble = m_exp.get_substring(m_window_bits*(i-1), m_window_bits);
-
- BigInt::const_time_lookup(e, m_g, nibble);
-
- bigint_mul(z.mutable_data(), z.size(),
- x.data(), x.size(), x.sig_words(),
- e.data(), m_mod_words, m_mod_words,
- workspace.data());
-
- bigint_monty_redc(z.mutable_data(),
- m_modulus.data(), m_mod_words, m_mod_prime,
- workspace.data());
-
- x = z;
- }
-
- x.grow_to(2*m_mod_words + 1);
-
- bigint_monty_redc(x.mutable_data(),
- m_modulus.data(), m_mod_words, m_mod_prime,
- workspace.data());
-
- return x;
+ return monty_execute(*m_monty, m_e);
}
-/*
-* Montgomery_Exponentiator Constructor
-*/
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_p(mod),
+ m_mod_p(mod),
m_hints(hints)
{
- // Montgomery reduction only works for positive odd moduli
- if(!m_modulus.is_positive() || m_modulus.is_even())
- throw Invalid_Argument("Montgomery_Exponentiator: invalid modulus");
-
- 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 = 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-25 03:01:23 +0000