9#include <botan/internal/monty_exp.h>
11#include <botan/exceptn.h>
12#include <botan/mem_ops.h>
13#include <botan/internal/bit_ops.h>
14#include <botan/internal/ct_utils.h>
15#include <botan/internal/monty.h>
17#if defined(BOTAN_HAS_MONTY_EXP_AVX512)
18 #include <botan/internal/cpuid.h>
19 #include <botan/internal/monty_exp_avx512.h>
28 Montgomery_Exponentiation_Generic(
const Montgomery_Int& g,
size_t window_bits);
30 Montgomery_Int exponentiation(
const BigInt& k,
size_t max_k_bits)
const override;
32 Montgomery_Int exponentiation_vartime(
const BigInt& k)
const override;
35 Montgomery_Params m_params;
36 std::vector<Montgomery_Int> m_g;
40Montgomery_Exponentiation_Generic::Montgomery_Exponentiation_Generic(
const Montgomery_Int& g,
size_t window_bits) :
41 m_params(g._params()), m_window_bits(window_bits) {
42 const size_t window_size = (
static_cast<size_t>(1) << m_window_bits);
44 m_g.reserve(window_size);
46 m_g.push_back(Montgomery_Int::one(m_params));
50 secure_vector<word> ws(2 * m_params.p_words());
52 for(
size_t i = 2; i != window_size; ++i) {
54 m_g.push_back(m_g[i / 2].
square(ws));
56 m_g.push_back(m_g[1].mul(m_g[i - 1], ws));
61void const_time_lookup(secure_vector<word>& output,
const std::vector<Montgomery_Int>& g,
size_t nibble) {
64 const size_t words = output.size();
68 for(
size_t i = 0; i != g.size(); i += 2) {
69 const secure_vector<word>& vec_0 = g[i].repr();
70 const secure_vector<word>& vec_1 = g[i + 1].repr();
74 const auto mask_0 = CT::Mask<word>::is_equal(nibble, i);
75 const auto mask_1 = CT::Mask<word>::is_equal(nibble, i + 1);
77 for(
size_t w = 0; w != words; ++w) {
78 output[w] |= mask_0.if_set_return(vec_0[w]);
79 output[w] |= mask_1.if_set_return(vec_1[w]);
84Montgomery_Int Montgomery_Exponentiation_Generic::exponentiation(
const BigInt& scalar,
size_t max_k_bits)
const {
85 BOTAN_ARG_CHECK(scalar.signum() >= 0,
"Invalid scalar for Montgomery exponentiation");
89 const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits;
91 if(exp_nibbles == 0) {
92 return Montgomery_Int::one(m_params);
95 secure_vector<word> e_bits(m_params.p_words());
96 secure_vector<word> ws(2 * m_params.p_words());
98 const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits * (exp_nibbles - 1), m_window_bits));
99 Montgomery_Int x(m_params, std::span{e_bits});
101 for(
size_t i = exp_nibbles - 1; i > 0; --i) {
102 x.square_this_n_times(ws, m_window_bits);
103 const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits * (i - 1), m_window_bits));
104 x.mul_by(e_bits, ws);
110Montgomery_Int Montgomery_Exponentiation_Generic::exponentiation_vartime(
const BigInt& scalar)
const {
111 const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
113 secure_vector<word> ws(2 * m_params.p_words());
115 if(exp_nibbles == 0) {
116 return Montgomery_Int::one(m_params);
119 Montgomery_Int x = m_g[scalar.get_substring(m_window_bits * (exp_nibbles - 1), m_window_bits)];
121 for(
size_t i = exp_nibbles - 1; i > 0; --i) {
122 x.square_this_n_times(ws, m_window_bits);
124 const uint32_t nibble = scalar.get_substring(m_window_bits * (i - 1), m_window_bits);
126 x.mul_by(m_g[nibble], ws);
136 if(window_bits == 0) {
140 if(window_bits < 1 || window_bits > 12) {
141 throw Invalid_Argument(
"Invalid window bits for Montgomery exponentiation");
144#if defined(BOTAN_HAS_MONTY_EXP_AVX512)
152 return std::make_shared<const Montgomery_Exponentiation_Generic>(g, window_bits);
157 size_t window_bits) {
158 BOTAN_ARG_CHECK(g.
signum() >= 0 && g < params.
p(),
"Montgomery exponentiation base integer out of range");
180 const size_t max_z1z2 = std::max(z1.
bits(), z2.
bits());
227 for(
size_t i = 0; i != z_bits; i += 2) {
235 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
static bool has(CPUID::Feature feat)
virtual Montgomery_Int exponentiation(const BigInt &k, size_t max_k_bits) const =0
virtual Montgomery_Int exponentiation_vartime(const BigInt &k) const =0
Montgomery_Int square(secure_vector< word > &ws) const
static Montgomery_Int one(const Montgomery_Params ¶ms)
Montgomery_Int & square_this_n_times(secure_vector< word > &ws, size_t n)
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
BOTAN_FORCE_INLINE constexpr T ceil_division(T a, T b)
BigInt square(const BigInt &x)
std::unique_ptr< Montgomery_Exponentiation_State > make_monty_exp_avx512(const Montgomery_Int &g, size_t window_bits)
std::shared_ptr< const Montgomery_Exponentiation_State > monty_precompute(const Montgomery_Int &g, size_t window_bits)
Montgomery_Int monty_multi_exp(const Montgomery_Params ¶ms_p, const BigInt &x_bn, const BigInt &z1, const BigInt &y_bn, const BigInt &z2)
Montgomery_Int monty_execute_vartime(const Montgomery_Exponentiation_State &precomputed_state, const BigInt &k)
std::vector< T, secure_allocator< T > > secure_vector
constexpr void clear_mem(T *ptr, size_t n)
Montgomery_Int monty_execute(const Montgomery_Exponentiation_State &precomputed_state, const BigInt &k, size_t max_k_bits)