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>
18class 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;
36Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params,
41 m_window_bits(window_bits == 0 ? 4 : window_bits),
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)
59 m_g.push_back(m_g[1] * m_g[i - 1]);
63 for(
size_t i = 0; i != window_size; ++i)
67 m_g[i].const_time_poison();
73void 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();
90 const auto mask_0 = CT::Mask<word>::is_equal(nibble, i);
91 const auto mask_1 = CT::Mask<word>::is_equal(nibble, i+1);
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]);
103BigInt Montgomery_Exponentation_State::exponentiation(
const BigInt& scalar,
size_t max_k_bits)
const
108 const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits;
113 secure_vector<word> e_bits(m_params->p_words());
114 secure_vector<word> ws;
116 const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits));
117 Montgomery_Int x(m_params, e_bits.data(), e_bits.size(),
false);
119 for(
size_t i = exp_nibbles - 1; i > 0; --i)
121 x.square_this_n_times(ws, m_window_bits);
122 const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(i-1), m_window_bits));
123 x.mul_by(e_bits, ws);
126 x.const_time_unpoison();
130BigInt Montgomery_Exponentation_State::exponentiation_vartime(
const BigInt& scalar)
const
134 const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
136 secure_vector<word> ws;
141 Montgomery_Int x = m_g[scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits)];
143 for(
size_t i = exp_nibbles - 1; i > 0; --i)
145 x.square_this_n_times(ws, m_window_bits);
147 const uint32_t nibble = scalar.get_substring(m_window_bits*(i-1), m_window_bits);
149 x.mul_by(m_g[nibble], ws);
152 x.const_time_unpoison();
156std::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;
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ARG_CHECK(expr, msg)
uint32_t get_substring(size_t offset, size_t length) const
Montgomery_Int square(secure_vector< word > &ws) const
Montgomery_Int & square_this(secure_vector< word > &ws)
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
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)
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_vartime(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k)
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
std::vector< T, secure_allocator< T > > secure_vector
void clear_mem(T *ptr, size_t n)
size_t round_up(size_t n, size_t align_to)