9#include <botan/internal/monty_exp.h>
11#include <botan/internal/ct_utils.h>
12#include <botan/internal/monty.h>
13#include <botan/internal/rounding.h>
17class Montgomery_Exponentation_State
final {
19 Montgomery_Exponentation_State(
const Montgomery_Int& g,
size_t window_bits,
bool const_time);
21 Montgomery_Int exponentiation(
const BigInt& k,
size_t max_k_bits)
const;
23 Montgomery_Int exponentiation_vartime(
const BigInt& k)
const;
26 std::shared_ptr<const Montgomery_Params> m_params;
27 std::vector<Montgomery_Int> m_g;
31Montgomery_Exponentation_State::Montgomery_Exponentation_State(
const Montgomery_Int& g,
34 m_params(g._params()), m_window_bits(window_bits == 0 ? 4 : window_bits) {
35 if(m_window_bits < 1 || m_window_bits > 12) {
36 throw Invalid_Argument(
"Invalid window bits for Montgomery exponentiation");
39 const size_t window_size = (
static_cast<size_t>(1) << m_window_bits);
41 m_g.reserve(window_size);
43 m_g.push_back(Montgomery_Int::one(m_params));
47 for(
size_t i = 2; i != window_size; ++i) {
48 m_g.push_back(m_g[1] * m_g[i - 1]);
57 CT::poison_range(m_g);
63void const_time_lookup(secure_vector<word>& output,
const std::vector<Montgomery_Int>& g,
size_t nibble) {
66 const size_t words = output.size();
70 for(
size_t i = 0; i != g.size(); i += 2) {
71 const secure_vector<word>& vec_0 = g[i].repr().get_word_vector();
72 const secure_vector<word>& vec_1 = g[i + 1].repr().get_word_vector();
76 const auto mask_0 = CT::Mask<word>::is_equal(nibble, i);
77 const auto mask_1 = CT::Mask<word>::is_equal(nibble, i + 1);
79 for(
size_t w = 0; w != words; ++w) {
80 output[w] |= mask_0.if_set_return(vec_0[w]);
81 output[w] |= mask_1.if_set_return(vec_1[w]);
88Montgomery_Int Montgomery_Exponentation_State::exponentiation(
const BigInt& scalar,
size_t max_k_bits)
const {
92 const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits;
94 if(exp_nibbles == 0) {
95 return Montgomery_Int::one(m_params);
98 secure_vector<word> e_bits(m_params->p_words());
99 secure_vector<word> ws;
101 const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits * (exp_nibbles - 1), m_window_bits));
102 Montgomery_Int x(m_params, e_bits.data(), e_bits.size(),
false);
104 for(
size_t i = exp_nibbles - 1; i > 0; --i) {
105 x.square_this_n_times(ws, m_window_bits);
106 const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits * (i - 1), m_window_bits));
107 x.mul_by(e_bits, ws);
114Montgomery_Int Montgomery_Exponentation_State::exponentiation_vartime(
const BigInt& scalar)
const {
115 const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
117 secure_vector<word> ws;
119 if(exp_nibbles == 0) {
120 return Montgomery_Int::one(m_params);
123 Montgomery_Int x = m_g[scalar.get_substring(m_window_bits * (exp_nibbles - 1), m_window_bits)];
125 for(
size_t i = exp_nibbles - 1; i > 0; --i) {
126 x.square_this_n_times(ws, m_window_bits);
128 const uint32_t nibble = scalar.get_substring(m_window_bits * (i - 1), m_window_bits);
130 x.mul_by(m_g[nibble], ws);
141 return std::make_shared<const Montgomery_Exponentation_State>(g, window_bits, const_time);
145 const std::shared_ptr<const Montgomery_Params>& params,
const BigInt& g,
size_t window_bits,
bool const_time) {
154 return precomputed_state.exponentiation(k, max_k_bits);
158 return precomputed_state.exponentiation_vartime(k);
216 for(
size_t i = 0; i != z_bits; i += 2) {
225 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 *)
Montgomery_Int monty_execute_vartime(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k)
constexpr size_t round_up(size_t n, size_t align_to)
Montgomery_Int monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
std::vector< T, secure_allocator< T > > secure_vector
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(const Montgomery_Int &g, size_t window_bits, bool const_time)
constexpr void clear_mem(T *ptr, size_t n)
Montgomery_Int 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)