/src/botan/src/lib/math/numbertheory/monty_exp.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | |
16 | | namespace Botan { |
17 | | |
18 | | class 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 | | |
36 | | Montgomery_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 | 81.5k | { |
44 | 81.5k | BOTAN_ARG_CHECK(g < m_params->p(), "Montgomery base too big"); |
45 | 81.5k | |
46 | 81.5k | if(m_window_bits < 1 || m_window_bits > 12) // really even 8 is too large ... |
47 | 0 | throw Invalid_Argument("Invalid window bits for Montgomery exponentiation"); |
48 | 81.5k | |
49 | 81.5k | const size_t window_size = (static_cast<size_t>(1) << m_window_bits); |
50 | 81.5k | |
51 | 81.5k | m_g.reserve(window_size); |
52 | 81.5k | |
53 | 81.5k | m_g.push_back(Montgomery_Int(m_params, m_params->R1(), false)); |
54 | 81.5k | |
55 | 81.5k | m_g.push_back(Montgomery_Int(m_params, g)); |
56 | 81.5k | |
57 | 1.14M | for(size_t i = 2; i != window_size; ++i) |
58 | 1.06M | { |
59 | 1.06M | m_g.push_back(m_g[1] * m_g[i - 1]); |
60 | 1.06M | } |
61 | 81.5k | |
62 | 81.5k | // Resize each element to exactly p words |
63 | 1.30M | for(size_t i = 0; i != window_size; ++i) |
64 | 1.22M | { |
65 | 1.22M | m_g[i].fix_size(); |
66 | 1.22M | if(const_time) |
67 | 1.21M | m_g[i].const_time_poison(); |
68 | 1.22M | } |
69 | 81.5k | } |
70 | | |
71 | | namespace { |
72 | | |
73 | | void const_time_lookup(secure_vector<word>& output, |
74 | | const std::vector<Montgomery_Int>& g, |
75 | | size_t nibble) |
76 | 2.60M | { |
77 | 2.60M | BOTAN_ASSERT_NOMSG(g.size() % 2 == 0); // actually a power of 2 |
78 | 2.60M | |
79 | 2.60M | const size_t words = output.size(); |
80 | 2.60M | |
81 | 2.60M | clear_mem(output.data(), output.size()); |
82 | 2.60M | |
83 | 23.4M | for(size_t i = 0; i != g.size(); i += 2) |
84 | 20.8M | { |
85 | 20.8M | const secure_vector<word>& vec_0 = g[i ].repr().get_word_vector(); |
86 | 20.8M | const secure_vector<word>& vec_1 = g[i+1].repr().get_word_vector(); |
87 | 20.8M | |
88 | 20.8M | BOTAN_ASSERT_NOMSG(vec_0.size() >= words && vec_1.size() >= words); |
89 | 20.8M | |
90 | 20.8M | const auto mask_0 = CT::Mask<word>::is_equal(nibble, i); |
91 | 20.8M | const auto mask_1 = CT::Mask<word>::is_equal(nibble, i+1); |
92 | 20.8M | |
93 | 394M | for(size_t w = 0; w != words; ++w) |
94 | 373M | { |
95 | 373M | output[w] |= mask_0.if_set_return(vec_0[w]); |
96 | 373M | output[w] |= mask_1.if_set_return(vec_1[w]); |
97 | 373M | } |
98 | 20.8M | } |
99 | 2.60M | } |
100 | | |
101 | | } |
102 | | |
103 | | BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar, size_t max_k_bits) const |
104 | 75.5k | { |
105 | 75.5k | BOTAN_DEBUG_ASSERT(scalar.bits() <= max_k_bits); |
106 | 75.5k | // TODO add a const-time implementation of above assert and use it in release builds |
107 | 75.5k | |
108 | 75.5k | const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits; |
109 | 75.5k | |
110 | 75.5k | if(exp_nibbles == 0) |
111 | 8 | return 1; |
112 | 75.5k | |
113 | 75.5k | secure_vector<word> e_bits(m_params->p_words()); |
114 | 75.5k | secure_vector<word> ws; |
115 | 75.5k | |
116 | 75.5k | const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits)); |
117 | 75.5k | Montgomery_Int x(m_params, e_bits.data(), e_bits.size(), false); |
118 | 75.5k | |
119 | 2.60M | for(size_t i = exp_nibbles - 1; i > 0; --i) |
120 | 2.53M | { |
121 | 2.53M | x.square_this_n_times(ws, m_window_bits); |
122 | 2.53M | const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(i-1), m_window_bits)); |
123 | 2.53M | x.mul_by(e_bits, ws); |
124 | 2.53M | } |
125 | 75.5k | |
126 | 75.5k | x.const_time_unpoison(); |
127 | 75.5k | return x.value(); |
128 | 75.5k | } |
129 | | |
130 | | BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scalar) const |
131 | 5.69k | { |
132 | 5.69k | BOTAN_ASSERT_NOMSG(m_const_time == false); |
133 | 5.69k | |
134 | 5.69k | const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits; |
135 | 5.69k | |
136 | 5.69k | secure_vector<word> ws; |
137 | 5.69k | |
138 | 5.69k | if(exp_nibbles == 0) |
139 | 0 | return 1; |
140 | 5.69k | |
141 | 5.69k | Montgomery_Int x = m_g[scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits)]; |
142 | 5.69k | |
143 | 309k | for(size_t i = exp_nibbles - 1; i > 0; --i) |
144 | 304k | { |
145 | 304k | x.square_this_n_times(ws, m_window_bits); |
146 | 304k | |
147 | 304k | const uint32_t nibble = scalar.get_substring(m_window_bits*(i-1), m_window_bits); |
148 | 304k | if(nibble > 0) |
149 | 65.8k | x.mul_by(m_g[nibble], ws); |
150 | 304k | } |
151 | 5.69k | |
152 | 5.69k | x.const_time_unpoison(); |
153 | 5.69k | return x.value(); |
154 | 5.69k | } |
155 | | |
156 | | std::shared_ptr<const Montgomery_Exponentation_State> |
157 | | monty_precompute(std::shared_ptr<const Montgomery_Params> params, |
158 | | const BigInt& g, |
159 | | size_t window_bits, |
160 | | bool const_time) |
161 | 81.5k | { |
162 | 81.5k | return std::make_shared<const Montgomery_Exponentation_State>(params, g, window_bits, const_time); |
163 | 81.5k | } |
164 | | |
165 | | BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state, |
166 | | const BigInt& k, size_t max_k_bits) |
167 | 75.5k | { |
168 | 75.5k | return precomputed_state.exponentiation(k, max_k_bits); |
169 | 75.5k | } |
170 | | |
171 | | BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state, |
172 | | const BigInt& k) |
173 | 5.69k | { |
174 | 5.69k | return precomputed_state.exponentiation_vartime(k); |
175 | 5.69k | } |
176 | | |
177 | | BigInt 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 | 75 | { |
183 | 75 | if(z1.is_negative() || z2.is_negative()) |
184 | 0 | throw Invalid_Argument("multi_exponentiate exponents must be positive"); |
185 | 75 | |
186 | 75 | const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2); |
187 | 75 | |
188 | 75 | secure_vector<word> ws; |
189 | 75 | |
190 | 75 | const Montgomery_Int one(params_p, params_p->R1(), false); |
191 | 75 | //const Montgomery_Int one(params_p, 1); |
192 | 75 | |
193 | 75 | const Montgomery_Int x1(params_p, x_bn); |
194 | 75 | const Montgomery_Int x2 = x1.square(ws); |
195 | 75 | const Montgomery_Int x3 = x2.mul(x1, ws); |
196 | 75 | |
197 | 75 | const Montgomery_Int y1(params_p, y_bn); |
198 | 75 | const Montgomery_Int y2 = y1.square(ws); |
199 | 75 | const Montgomery_Int y3 = y2.mul(y1, ws); |
200 | 75 | |
201 | 75 | const Montgomery_Int y1x1 = y1.mul(x1, ws); |
202 | 75 | const Montgomery_Int y1x2 = y1.mul(x2, ws); |
203 | 75 | const Montgomery_Int y1x3 = y1.mul(x3, ws); |
204 | 75 | |
205 | 75 | const Montgomery_Int y2x1 = y2.mul(x1, ws); |
206 | 75 | const Montgomery_Int y2x2 = y2.mul(x2, ws); |
207 | 75 | const Montgomery_Int y2x3 = y2.mul(x3, ws); |
208 | 75 | |
209 | 75 | const Montgomery_Int y3x1 = y3.mul(x1, ws); |
210 | 75 | const Montgomery_Int y3x2 = y3.mul(x2, ws); |
211 | 75 | const Montgomery_Int y3x3 = y3.mul(x3, ws); |
212 | 75 | |
213 | 75 | const Montgomery_Int* M[16] = { |
214 | 75 | &one, |
215 | 75 | &x1, // 0001 |
216 | 75 | &x2, // 0010 |
217 | 75 | &x3, // 0011 |
218 | 75 | &y1, // 0100 |
219 | 75 | &y1x1, |
220 | 75 | &y1x2, |
221 | 75 | &y1x3, |
222 | 75 | &y2, // 1000 |
223 | 75 | &y2x1, |
224 | 75 | &y2x2, |
225 | 75 | &y2x3, |
226 | 75 | &y3, // 1100 |
227 | 75 | &y3x1, |
228 | 75 | &y3x2, |
229 | 75 | &y3x3 |
230 | 75 | }; |
231 | 75 | |
232 | 75 | Montgomery_Int H = one; |
233 | 75 | |
234 | 25.7k | for(size_t i = 0; i != z_bits; i += 2) |
235 | 25.6k | { |
236 | 25.6k | if(i > 0) |
237 | 25.5k | { |
238 | 25.5k | H.square_this(ws); |
239 | 25.5k | H.square_this(ws); |
240 | 25.5k | } |
241 | 25.6k | |
242 | 25.6k | const uint32_t z1_b = z1.get_substring(z_bits - i - 2, 2); |
243 | 25.6k | const uint32_t z2_b = z2.get_substring(z_bits - i - 2, 2); |
244 | 25.6k | |
245 | 25.6k | const uint32_t z12 = (4*z2_b) + z1_b; |
246 | 25.6k | |
247 | 25.6k | H.mul_by(*M[z12], ws); |
248 | 25.6k | } |
249 | 75 | |
250 | 75 | return H.value(); |
251 | 75 | } |
252 | | |
253 | | } |
254 | | |