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>
19 class 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;
38 class 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); }
53 std::vector<BigInt>
m_g;
57 void Fixed_Window_Exponentiator::set_base(
const BigInt& base)
65 for(
size_t i = 2; i !=
m_g.size(); ++i)
69 BigInt Fixed_Window_Exponentiator::execute()
const
75 for(
size_t i = exp_nibbles; i > 0; --i)
91 Fixed_Window_Exponentiator::Fixed_Window_Exponentiator(
const BigInt& n,
96 class 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);
111 std::shared_ptr<const Montgomery_Exponentation_State>
m_monty;
114 Power_Mod::Usage_Hints
m_hints;
117 void Montgomery_Exponentiator::set_base(
const BigInt& base)
119 size_t window_bits = Power_Mod::window_bits(
m_e.bits(), base.bits(),
m_hints);
123 BigInt Montgomery_Exponentiator::execute()
const
132 Montgomery_Exponentiator::Montgomery_Exponentiator(
const BigInt& mod,
133 Power_Mod::Usage_Hints hints) :
148 set_modulus(n, hints, disable_monty);
151 Power_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));
198 void Power_Mod::set_base(
const BigInt& b)
const
211 void Power_Mod::set_exponent(
const BigInt& e)
const
218 m_core->set_exponent(e);
228 return m_core->execute();
234 size_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;
293 Power_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;
310 Fixed_Exponent_Power_Mod::Fixed_Exponent_Power_Mod(
const BigInt& e,
std::vector< BigInt > m_g
int(* final)(unsigned char *, CTX *)
Fixed_Base_Power_Mod()=default
std::shared_ptr< const Montgomery_Params > m_monty_params
BigInt multiply(const BigInt &x, const BigInt &y) const
void set_exponent(const BigInt &exponent) const
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)
std::shared_ptr< const Montgomery_Exponentation_State > m_monty
BigInt reduce(const BigInt &x) const
static size_t window_bits(size_t exp_bits, size_t base_bits, Power_Mod::Usage_Hints hints)
Modular_Reducer m_reducer
uint32_t get_substring(size_t offset, size_t length) const
Power_Mod::Usage_Hints m_hints
void set_base(const BigInt &base) const
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
BigInt square(const BigInt &x) const
size_t round_up(size_t n, size_t align_to)