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/internal/monty.h>
18class Montgomery_Exponentation_State
final
21 Montgomery_Exponentation_State(
const 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;
35Montgomery_Exponentation_State::Montgomery_Exponentation_State(
36 const std::shared_ptr<const Montgomery_Params>& params,
41 m_window_bits(window_bits == 0 ? 4 : window_bits)
45 if(m_window_bits < 1 || m_window_bits > 12)
46 throw Invalid_Argument(
"Invalid window bits for Montgomery exponentiation");
48 const size_t window_size = (
static_cast<size_t>(1) << m_window_bits);
50 m_g.reserve(window_size);
52 m_g.push_back(Montgomery_Int(m_params, m_params->R1(),
false));
54 m_g.push_back(Montgomery_Int(m_params, g));
56 for(
size_t i = 2; i != window_size; ++i)
58 m_g.push_back(m_g[1] * m_g[i - 1]);
62 for(
size_t i = 0; i != window_size; ++i)
66 m_g[i].const_time_poison();
72void const_time_lookup(secure_vector<word>& output,
73 const std::vector<Montgomery_Int>& g,
78 const size_t words = output.size();
82 for(
size_t i = 0; i != g.size(); i += 2)
84 const secure_vector<word>& vec_0 = g[i ].repr().get_word_vector();
85 const secure_vector<word>& vec_1 = g[i+1].repr().get_word_vector();
89 const auto mask_0 = CT::Mask<word>::is_equal(nibble, i);
90 const auto mask_1 = CT::Mask<word>::is_equal(nibble, i+1);
92 for(
size_t w = 0; w != words; ++w)
94 output[w] |= mask_0.if_set_return(vec_0[w]);
95 output[w] |= mask_1.if_set_return(vec_1[w]);
102BigInt Montgomery_Exponentation_State::exponentiation(
const BigInt& scalar,
size_t max_k_bits)
const
107 const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits;
110 return BigInt::one();
112 secure_vector<word> e_bits(m_params->p_words());
113 secure_vector<word> ws;
115 const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits));
116 Montgomery_Int x(m_params, e_bits.data(), e_bits.size(),
false);
118 for(
size_t i = exp_nibbles - 1; i > 0; --i)
120 x.square_this_n_times(ws, m_window_bits);
121 const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(i-1), m_window_bits));
122 x.mul_by(e_bits, ws);
125 x.const_time_unpoison();
129BigInt Montgomery_Exponentation_State::exponentiation_vartime(
const BigInt& scalar)
const
131 const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
133 secure_vector<word> ws;
136 return BigInt::one();
138 Montgomery_Int x = m_g[scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits)];
140 for(
size_t i = exp_nibbles - 1; i > 0; --i)
142 x.square_this_n_times(ws, m_window_bits);
144 const uint32_t nibble = scalar.get_substring(m_window_bits*(i-1), m_window_bits);
146 x.mul_by(m_g[nibble], ws);
149 x.const_time_unpoison();
153std::shared_ptr<const Montgomery_Exponentation_State>
159 return std::make_shared<const Montgomery_Exponentation_State>(params, g, window_bits, const_time);
163 const BigInt& k,
size_t max_k_bits)
165 return precomputed_state.exponentiation(k, max_k_bits);
171 return precomputed_state.exponentiation_vartime(k);
231 for(
size_t i = 0; i != z_bits; i += 2)
242 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)
int(* final)(unsigned char *, CTX *)
BigInt monty_multi_exp(const std::shared_ptr< const Montgomery_Params > ¶ms_p, const BigInt &x_bn, const BigInt &z1, const BigInt &y_bn, const BigInt &z2)
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
constexpr void clear_mem(T *ptr, size_t n)
size_t round_up(size_t n, size_t align_to)
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(const std::shared_ptr< const Montgomery_Params > ¶ms, const BigInt &g, size_t window_bits, bool const_time)