9#include <botan/pow_mod.h>
10#include <botan/numthry.h>
11#include <botan/reducer.h>
12#include <botan/monty.h>
13#include <botan/internal/monty_exp.h>
14#include <botan/internal/rounding.h>
19class Modular_Exponentiator
22 virtual void set_base(
const BigInt&) = 0;
23 virtual void set_exponent(
const BigInt&) = 0;
24 virtual BigInt execute()
const = 0;
25 virtual Modular_Exponentiator* copy()
const = 0;
27 Modular_Exponentiator() =
default;
28 Modular_Exponentiator(
const Modular_Exponentiator&) =
default;
29 Modular_Exponentiator & operator=(
const Modular_Exponentiator&) =
default;
30 virtual ~Modular_Exponentiator() =
default;
38class Fixed_Window_Exponentiator
final :
public Modular_Exponentiator
41 void set_exponent(
const BigInt& e)
override { m_exp = e; }
42 void set_base(
const BigInt&)
override;
43 BigInt execute()
const override;
45 Modular_Exponentiator* copy()
const override
46 {
return new Fixed_Window_Exponentiator(*
this); }
50 Modular_Reducer m_reducer;
53 std::vector<BigInt> m_g;
57void Fixed_Window_Exponentiator::set_base(
const BigInt& base)
61 m_g.resize(
static_cast<size_t>(1) << m_window_bits);
63 m_g[1] = m_reducer.
reduce(base);
65 for(
size_t i = 2; i != m_g.size(); ++i)
66 m_g[i] = m_reducer.
multiply(m_g[i-1], m_g[1]);
69BigInt Fixed_Window_Exponentiator::execute()
const
71 const size_t exp_nibbles = (m_exp.
bits() + m_window_bits - 1) / m_window_bits;
75 for(
size_t i = exp_nibbles; i > 0; --i)
77 for(
size_t j = 0; j != m_window_bits; ++j)
80 const uint32_t nibble = m_exp.
get_substring(m_window_bits*(i-1), m_window_bits);
83 x = m_reducer.
multiply(x, m_g[nibble]);
91Fixed_Window_Exponentiator::Fixed_Window_Exponentiator(
const BigInt& n,
93 : m_reducer{Modular_Reducer(n)}, m_exp{}, m_window_bits{}, m_g{}, m_hints{hints}
96class Montgomery_Exponentiator
final :
public Modular_Exponentiator
99 void set_exponent(
const BigInt& e)
override { m_e = e; }
100 void set_base(
const BigInt&)
override;
101 BigInt execute()
const override;
103 Modular_Exponentiator* copy()
const override
104 {
return new Montgomery_Exponentiator(*
this); }
106 Montgomery_Exponentiator(
const BigInt&, Power_Mod::Usage_Hints);
109 Modular_Reducer m_mod_p;
110 std::shared_ptr<const Montgomery_Params> m_monty_params;
111 std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
114 Power_Mod::Usage_Hints m_hints;
117void Montgomery_Exponentiator::set_base(
const BigInt& base)
119 size_t window_bits = Power_Mod::window_bits(m_e.bits(), base.bits(), m_hints);
120 m_monty =
monty_precompute(m_monty_params, m_mod_p.reduce(base), window_bits);
123BigInt Montgomery_Exponentiator::execute()
const
132Montgomery_Exponentiator::Montgomery_Exponentiator(
const BigInt& mod,
133 Power_Mod::Usage_Hints hints) :
136 m_monty_params(
std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
148 set_modulus(n, hints, disable_monty);
151Power_Mod::~Power_Mod() { }
158 if(other.m_core.get())
159 m_core.reset(other.m_core->copy());
170 m_core.reset(other.m_core->copy());
188 if(n.
is_odd() && disable_monty ==
false)
189 m_core.reset(
new Montgomery_Exponentiator(n, hints));
191 m_core.reset(
new Fixed_Window_Exponentiator(n, hints));
198void Power_Mod::set_base(
const BigInt& b)
const
211void Power_Mod::set_exponent(
const BigInt& e)
const
218 m_core->set_exponent(e);
228 return m_core->execute();
234size_t Power_Mod::window_bits(
size_t exp_bits,
size_t,
237 static const size_t wsize[][2] = {
246 size_t window_bits = 1;
250 for(
size_t j = 0; wsize[j][0]; ++j)
252 if(exp_bits >= wsize[j][0])
254 window_bits += wsize[j][1];
260 if(hints & Power_Mod::BASE_IS_FIXED)
262 if(hints & Power_Mod::EXP_IS_LARGE)
277 Power_Mod::BASE_IS_SMALL);
279 const size_t b_bits = b.
bits();
280 const size_t n_bits = n.
bits();
282 if(b_bits < n_bits / 32)
283 return Power_Mod::BASE_IS_SMALL;
284 if(b_bits > n_bits / 4)
285 return Power_Mod::BASE_IS_LARGE;
287 return Power_Mod::NO_HINTS;
293Power_Mod::Usage_Hints choose_exp_hints(
const BigInt& e,
const BigInt& n)
295 const size_t e_bits = e.bits();
296 const size_t n_bits = n.bits();
298 if(e_bits < n_bits / 32)
299 return Power_Mod::BASE_IS_SMALL;
300 if(e_bits > n_bits / 4)
301 return Power_Mod::BASE_IS_LARGE;
302 return Power_Mod::NO_HINTS;
310Fixed_Exponent_Power_Mod::Fixed_Exponent_Power_Mod(
const BigInt& e,
uint32_t get_substring(size_t offset, size_t length) const
Fixed_Base_Power_Mod()=default
BigInt square(const BigInt &x) const
BigInt multiply(const BigInt &x, const BigInt &y) const
BigInt reduce(const BigInt &x) const
void set_base(const BigInt &base) const
void set_exponent(const BigInt &exponent) const
static size_t window_bits(size_t exp_bits, size_t base_bits, Power_Mod::Usage_Hints hints)
int(* final)(unsigned char *, CTX *)
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(std::shared_ptr< const Montgomery_Params > params, const BigInt &g, size_t window_bits, bool const_time)
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
size_t round_up(size_t n, size_t align_to)