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