Botan 2.19.2
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 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#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>
15
16namespace Botan {
17
18class Montgomery_Exponentation_State
19 {
20 public:
21 Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params,
22 const BigInt& g,
23 size_t window_bits,
24 bool const_time);
25
26 BigInt exponentiation(const BigInt& k, size_t max_k_bits) const;
27
28 BigInt exponentiation_vartime(const BigInt& k) const;
29 private:
30 std::shared_ptr<const Montgomery_Params> m_params;
31 std::vector<Montgomery_Int> m_g;
32 size_t m_window_bits;
33 bool m_const_time;
34 };
35
36Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params,
37 const BigInt& g,
38 size_t window_bits,
39 bool const_time) :
40 m_params(params),
41 m_window_bits(window_bits == 0 ? 4 : window_bits),
42 m_const_time(const_time)
43 {
44 BOTAN_ARG_CHECK(g < m_params->p(), "Montgomery base too big");
45
46 if(m_window_bits < 1 || m_window_bits > 12) // really even 8 is too large ...
47 throw Invalid_Argument("Invalid window bits for Montgomery exponentiation");
48
49 const size_t window_size = (static_cast<size_t>(1) << m_window_bits);
50
51 m_g.reserve(window_size);
52
53 m_g.push_back(Montgomery_Int(m_params, m_params->R1(), false));
54
55 m_g.push_back(Montgomery_Int(m_params, g));
56
57 for(size_t i = 2; i != window_size; ++i)
58 {
59 m_g.push_back(m_g[1] * m_g[i - 1]);
60 }
61
62 // Resize each element to exactly p words
63 for(size_t i = 0; i != window_size; ++i)
64 {
65 m_g[i].fix_size();
66 if(const_time)
67 m_g[i].const_time_poison();
68 }
69 }
70
71namespace {
72
73void const_time_lookup(secure_vector<word>& output,
74 const std::vector<Montgomery_Int>& g,
75 size_t nibble)
76 {
77 BOTAN_ASSERT_NOMSG(g.size() % 2 == 0); // actually a power of 2
78
79 const size_t words = output.size();
80
81 clear_mem(output.data(), output.size());
82
83 for(size_t i = 0; i != g.size(); i += 2)
84 {
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();
87
88 BOTAN_ASSERT_NOMSG(vec_0.size() >= words && vec_1.size() >= words);
89
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);
92
93 for(size_t w = 0; w != words; ++w)
94 {
95 output[w] |= mask_0.if_set_return(vec_0[w]);
96 output[w] |= mask_1.if_set_return(vec_1[w]);
97 }
98 }
99 }
100
101}
102
103BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar, size_t max_k_bits) const
104 {
105 BOTAN_DEBUG_ASSERT(scalar.bits() <= max_k_bits);
106 // TODO add a const-time implementation of above assert and use it in release builds
107
108 const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits;
109
110 if(exp_nibbles == 0)
111 return 1;
112
113 secure_vector<word> e_bits(m_params->p_words());
114 secure_vector<word> ws;
115
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);
118
119 for(size_t i = exp_nibbles - 1; i > 0; --i)
120 {
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);
124 }
125
126 x.const_time_unpoison();
127 return x.value();
128 }
129
130BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scalar) const
131 {
132 BOTAN_ASSERT_NOMSG(m_const_time == false);
133
134 const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
135
136 secure_vector<word> ws;
137
138 if(exp_nibbles == 0)
139 return 1;
140
141 Montgomery_Int x = m_g[scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits)];
142
143 for(size_t i = exp_nibbles - 1; i > 0; --i)
144 {
145 x.square_this_n_times(ws, m_window_bits);
146
147 const uint32_t nibble = scalar.get_substring(m_window_bits*(i-1), m_window_bits);
148 if(nibble > 0)
149 x.mul_by(m_g[nibble], ws);
150 }
151
152 x.const_time_unpoison();
153 return x.value();
154 }
155
156std::shared_ptr<const Montgomery_Exponentation_State>
157monty_precompute(std::shared_ptr<const Montgomery_Params> params,
158 const BigInt& g,
159 size_t window_bits,
160 bool const_time)
161 {
162 return std::make_shared<const Montgomery_Exponentation_State>(params, g, window_bits, const_time);
163 }
164
165BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
166 const BigInt& k, size_t max_k_bits)
167 {
168 return precomputed_state.exponentiation(k, max_k_bits);
169 }
170
171BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state,
172 const BigInt& k)
173 {
174 return precomputed_state.exponentiation_vartime(k);
175 }
176
177BigInt monty_multi_exp(std::shared_ptr<const Montgomery_Params> params_p,
178 const BigInt& x_bn,
179 const BigInt& z1,
180 const BigInt& y_bn,
181 const BigInt& z2)
182 {
183 if(z1.is_negative() || z2.is_negative())
184 throw Invalid_Argument("multi_exponentiate exponents must be positive");
185
186 const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);
187
189
190 const Montgomery_Int one(params_p, params_p->R1(), false);
191 //const Montgomery_Int one(params_p, 1);
192
193 const Montgomery_Int x1(params_p, x_bn);
194 const Montgomery_Int x2 = x1.square(ws);
195 const Montgomery_Int x3 = x2.mul(x1, ws);
196
197 const Montgomery_Int y1(params_p, y_bn);
198 const Montgomery_Int y2 = y1.square(ws);
199 const Montgomery_Int y3 = y2.mul(y1, ws);
200
201 const Montgomery_Int y1x1 = y1.mul(x1, ws);
202 const Montgomery_Int y1x2 = y1.mul(x2, ws);
203 const Montgomery_Int y1x3 = y1.mul(x3, ws);
204
205 const Montgomery_Int y2x1 = y2.mul(x1, ws);
206 const Montgomery_Int y2x2 = y2.mul(x2, ws);
207 const Montgomery_Int y2x3 = y2.mul(x3, ws);
208
209 const Montgomery_Int y3x1 = y3.mul(x1, ws);
210 const Montgomery_Int y3x2 = y3.mul(x2, ws);
211 const Montgomery_Int y3x3 = y3.mul(x3, ws);
212
213 const Montgomery_Int* M[16] = {
214 &one,
215 &x1, // 0001
216 &x2, // 0010
217 &x3, // 0011
218 &y1, // 0100
219 &y1x1,
220 &y1x2,
221 &y1x3,
222 &y2, // 1000
223 &y2x1,
224 &y2x2,
225 &y2x3,
226 &y3, // 1100
227 &y3x1,
228 &y3x2,
229 &y3x3
230 };
231
232 Montgomery_Int H = one;
233
234 for(size_t i = 0; i != z_bits; i += 2)
235 {
236 if(i > 0)
237 {
238 H.square_this(ws);
239 H.square_this(ws);
240 }
241
242 const uint32_t z1_b = z1.get_substring(z_bits - i - 2, 2);
243 const uint32_t z2_b = z2.get_substring(z_bits - i - 2, 2);
244
245 const uint32_t z12 = (4*z2_b) + z1_b;
246
247 H.mul_by(*M[z12], ws);
248 }
249
250 return H.value();
251 }
252
253}
254
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
#define BOTAN_ARG_CHECK(expr, msg)
Definition: assert.h:37
size_t bits() const
Definition: bigint.cpp:296
bool is_negative() const
Definition: bigint.h:527
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:213
Montgomery_Int square(secure_vector< word > &ws) const
Definition: monty.cpp:403
BigInt value() const
Definition: monty.cpp:306
Montgomery_Int & square_this(secure_vector< word > &ws)
Definition: monty.cpp:397
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Definition: monty.cpp:358
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:364
Definition: alg_id.cpp:13
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)
Definition: monty_exp.cpp:177
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)
Definition: monty_exp.cpp:157
BigInt monty_execute_vartime(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k)
Definition: monty_exp.cpp:171
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
Definition: monty_exp.cpp:165
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21