Botan 3.14.1
Crypto and TLS for C&
monty_exp.cpp
Go to the documentation of this file.
1/*
2* Montgomery Exponentiation
3* (C) 1999-2010,2012,2018,2025 Jack Lloyd
4* 2016 Matthias Gierlings
5*
6* Botan is released under the Simplified BSD License (see license.txt)
7*/
8
9#include <botan/internal/monty_exp.h>
10
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>
16
17#if defined(BOTAN_HAS_MONTY_EXP_AVX512)
18 #include <botan/internal/cpuid.h>
19 #include <botan/internal/monty_exp_avx512.h>
20#endif
21
22namespace Botan {
23
24namespace {
25
26class Montgomery_Exponentiation_Generic final : public Montgomery_Exponentiation_State {
27 public:
28 Montgomery_Exponentiation_Generic(const Montgomery_Int& g, size_t window_bits);
29
30 Montgomery_Int exponentiation(const BigInt& k, size_t max_k_bits) const override;
31
32 Montgomery_Int exponentiation_vartime(const BigInt& k) const override;
33
34 private:
35 Montgomery_Params m_params;
36 std::vector<Montgomery_Int> m_g;
37 size_t m_window_bits;
38};
39
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);
43
44 m_g.reserve(window_size);
45
46 m_g.push_back(Montgomery_Int::one(m_params));
47
48 m_g.push_back(g);
49
50 secure_vector<word> ws(2 * m_params.p_words());
51
52 for(size_t i = 2; i != window_size; ++i) {
53 if(i % 2 == 0) {
54 m_g.push_back(m_g[i / 2].square(ws));
55 } else {
56 m_g.push_back(m_g[1].mul(m_g[i - 1], ws));
57 }
58 }
59}
60
61void const_time_lookup(secure_vector<word>& output, const std::vector<Montgomery_Int>& g, size_t nibble) {
62 BOTAN_ASSERT_NOMSG(g.size() % 2 == 0); // actually a power of 2
63
64 const size_t words = output.size();
65
66 clear_mem(output.data(), output.size());
67
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();
71
72 BOTAN_ASSERT_NOMSG(vec_0.size() >= words && vec_1.size() >= words);
73
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);
76
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]);
80 }
81 }
82}
83
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");
86 BOTAN_DEBUG_ASSERT(scalar.bits() <= max_k_bits);
87 // TODO add a const-time implementation of above assert and use it in release builds
88
89 const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits;
90
91 if(exp_nibbles == 0) {
92 return Montgomery_Int::one(m_params);
93 }
94
95 secure_vector<word> e_bits(m_params.p_words());
96 secure_vector<word> ws(2 * m_params.p_words());
97
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});
100
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);
105 }
106
107 return x;
108}
109
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;
112
113 secure_vector<word> ws(2 * m_params.p_words());
114
115 if(exp_nibbles == 0) {
116 return Montgomery_Int::one(m_params);
117 }
118
119 Montgomery_Int x = m_g[scalar.get_substring(m_window_bits * (exp_nibbles - 1), m_window_bits)];
120
121 for(size_t i = exp_nibbles - 1; i > 0; --i) {
122 x.square_this_n_times(ws, m_window_bits);
123
124 const uint32_t nibble = scalar.get_substring(m_window_bits * (i - 1), m_window_bits);
125 if(nibble > 0) {
126 x.mul_by(m_g[nibble], ws);
127 }
128 }
129
130 return x;
131}
132
133} // namespace
134
135std::shared_ptr<const Montgomery_Exponentiation_State> monty_precompute(const Montgomery_Int& g, size_t window_bits) {
136 if(window_bits == 0) {
137 window_bits = 4;
138 }
139
140 if(window_bits < 1 || window_bits > 12) { // really even 8 is too large ...
141 throw Invalid_Argument("Invalid window bits for Montgomery exponentiation");
142 }
143
144#if defined(BOTAN_HAS_MONTY_EXP_AVX512)
146 if(auto state = make_monty_exp_avx512(g, window_bits)) {
147 return state;
148 }
149 }
150#endif
151
152 return std::make_shared<const Montgomery_Exponentiation_Generic>(g, window_bits);
153}
154
155std::shared_ptr<const Montgomery_Exponentiation_State> monty_precompute(const Montgomery_Params& params,
156 const BigInt& g,
157 size_t window_bits) {
158 BOTAN_ARG_CHECK(g.signum() >= 0 && g < params.p(), "Montgomery exponentiation base integer out of range");
159 const Montgomery_Int monty_g(params, g);
160 return monty_precompute(monty_g, window_bits);
161}
162
164 const BigInt& k,
165 size_t max_k_bits) {
166 return precomputed_state.exponentiation(k, max_k_bits);
167}
168
170 return precomputed_state.exponentiation_vartime(k);
171}
172
174 const Montgomery_Params& params_p, const BigInt& x_bn, const BigInt& z1, const BigInt& y_bn, const BigInt& z2) {
175 if(z1.signum() < 0 || z2.signum() < 0) {
176 throw Invalid_Argument("multi_exponentiate exponents must be positive");
177 }
178
179 // The exponents are consumed two bits at a time
180 const size_t max_z1z2 = std::max(z1.bits(), z2.bits());
181 const size_t z_bits = 2 * ceil_division<size_t>(max_z1z2, 2);
182
183 secure_vector<word> ws(2 * params_p.p_words());
184
185 const Montgomery_Int one = Montgomery_Int::one(params_p);
186
187 const Montgomery_Int x1(params_p, x_bn);
188 const Montgomery_Int x2 = x1.square(ws);
189 const Montgomery_Int x3 = x2.mul(x1, ws);
190
191 const Montgomery_Int y1(params_p, y_bn);
192 const Montgomery_Int y2 = y1.square(ws);
193 const Montgomery_Int y3 = y2.mul(y1, ws);
194
195 const Montgomery_Int y1x1 = y1.mul(x1, ws);
196 const Montgomery_Int y1x2 = y1.mul(x2, ws);
197 const Montgomery_Int y1x3 = y1.mul(x3, ws);
198
199 const Montgomery_Int y2x1 = y2.mul(x1, ws);
200 const Montgomery_Int y2x2 = y2.mul(x2, ws);
201 const Montgomery_Int y2x3 = y2.mul(x3, ws);
202
203 const Montgomery_Int y3x1 = y3.mul(x1, ws);
204 const Montgomery_Int y3x2 = y3.mul(x2, ws);
205 const Montgomery_Int y3x3 = y3.mul(x3, ws);
206
207 // NOLINTNEXTLINE(*-const-correctness) bug in clang-tidy
208 const Montgomery_Int* M[16] = {&one,
209 &x1, // 0001
210 &x2, // 0010
211 &x3, // 0011
212 &y1, // 0100
213 &y1x1,
214 &y1x2,
215 &y1x3,
216 &y2, // 1000
217 &y2x1,
218 &y2x2,
219 &y2x3,
220 &y3, // 1100
221 &y3x1,
222 &y3x2,
223 &y3x3};
224
225 Montgomery_Int H = one;
226
227 for(size_t i = 0; i != z_bits; i += 2) {
228 if(i > 0) {
229 H.square_this_n_times(ws, 2);
230 }
231
232 const uint32_t z1_b = z1.get_substring(z_bits - i - 2, 2);
233 const uint32_t z2_b = z2.get_substring(z_bits - i - 2, 2);
234
235 const uint32_t z12 = (4 * z2_b) + z1_b;
236
237 if(z12 > 0) {
238 H.mul_by(*M[z12], ws);
239 }
240 }
241
242 return H;
243}
244
245} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_DEBUG_ASSERT(expr)
Definition assert.h:136
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
int signum() const
Definition bigint.h:493
size_t bits() const
Definition bigint.cpp:308
uint32_t get_substring(size_t offset, size_t length) const
Definition bigint.cpp:240
static bool has(CPUID::Feature feat)
Definition cpuid.h:93
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
Definition monty.cpp:505
static Montgomery_Int one(const Montgomery_Params &params)
Definition monty.cpp:237
Montgomery_Int & square_this_n_times(secure_vector< word > &ws, size_t n)
Definition monty.cpp:363
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Definition monty.cpp:326
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition monty.cpp:344
size_t p_words() const
Definition monty.h:58
const BigInt & p() const
Definition monty.h:41
BOTAN_FORCE_INLINE constexpr T ceil_division(T a, T b)
Definition bit_ops.h:167
BigInt square(const BigInt &x)
Definition numthry.cpp:184
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 &params_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
Definition secmem.h:128
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:118
Montgomery_Int monty_execute(const Montgomery_Exponentiation_State &precomputed_state, const BigInt &k, size_t max_k_bits)