9 #include <botan/internal/monty_exp.h>
10 #include <botan/internal/ct_utils.h>
11 #include <botan/internal/rounding.h>
12 #include <botan/numthry.h>
13 #include <botan/reducer.h>
14 #include <botan/monty.h>
18 class Montgomery_Exponentation_State
21 Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params,
26 BigInt exponentiation(
const BigInt& k,
size_t max_k_bits)
const;
28 BigInt exponentiation_vartime(
const BigInt& k)
const;
30 std::shared_ptr<const Montgomery_Params> m_params;
31 std::vector<Montgomery_Int>
m_g;
36 Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params,
42 m_const_time(const_time)
46 if(m_window_bits < 1 || m_window_bits > 12)
47 throw Invalid_Argument(
"Invalid window bits for Montgomery exponentiation");
49 const size_t window_size = (
static_cast<size_t>(1) <<
m_window_bits);
51 m_g.reserve(window_size);
53 m_g.push_back(Montgomery_Int(m_params, m_params->R1(),
false));
55 m_g.push_back(Montgomery_Int(m_params, g));
57 for(
size_t i = 2; i != window_size; ++i)
63 for(
size_t i = 0; i != window_size; ++i)
67 m_g[i].const_time_poison();
73 void const_time_lookup(secure_vector<word>& output,
74 const std::vector<Montgomery_Int>& g,
79 const size_t words = output.size();
83 for(
size_t i = 0; i != g.size(); i += 2)
85 const secure_vector<word>& vec_0 = g[i ].repr().get_word_vector();
86 const secure_vector<word>& vec_1 = g[i+1].repr().get_word_vector();
93 for(
size_t w = 0; w != words; ++w)
95 output[w] |= mask_0.if_set_return(vec_0[w]);
96 output[w] |= mask_1.if_set_return(vec_1[w]);
103 BigInt Montgomery_Exponentation_State::exponentiation(
const BigInt& scalar,
size_t max_k_bits)
const
113 secure_vector<word> e_bits(m_params->p_words());
114 secure_vector<word> ws;
117 Montgomery_Int x(m_params, e_bits.data(), e_bits.size(),
false);
119 for(
size_t i = exp_nibbles - 1; i > 0; --i)
123 x.mul_by(e_bits, ws);
126 x.const_time_unpoison();
130 BigInt Montgomery_Exponentation_State::exponentiation_vartime(
const BigInt& scalar)
const
136 secure_vector<word> ws;
143 for(
size_t i = exp_nibbles - 1; i > 0; --i)
149 x.mul_by(
m_g[nibble], ws);
152 x.const_time_unpoison();
156 std::shared_ptr<const Montgomery_Exponentation_State>
162 return std::make_shared<const Montgomery_Exponentation_State>(params, g, window_bits, const_time);
166 const BigInt& k,
size_t max_k_bits)
168 return precomputed_state.exponentiation(k, max_k_bits);
174 return precomputed_state.exponentiation_vartime(k);
234 for(
size_t i = 0; i != z_bits; i += 2)
245 const uint32_t z12 = (4*z2_b) + z1_b;
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
void clear_mem(T *ptr, size_t n)
std::vector< BigInt > m_g
BigInt monty_multi_exp(std::shared_ptr< const Montgomery_Params > params_p, const BigInt &x_bn, const BigInt &z1, const BigInt &y_bn, const BigInt &z2)
#define BOTAN_ASSERT_NOMSG(expr)
Montgomery_Int square(secure_vector< word > &ws) const
BigInt monty_execute_vartime(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k)
std::vector< T, secure_allocator< T >> secure_vector
#define BOTAN_DEBUG_ASSERT(expr)
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) 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)
#define BOTAN_ARG_CHECK(expr, msg)
uint32_t get_substring(size_t offset, size_t length) const
Montgomery_Int & square_this(secure_vector< word > &ws)
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)
static Mask< T > is_equal(T x, T y)