Botan  2.12.1
Crypto and TLS for C++11
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 
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  {
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 
71 namespace {
72 
73 void 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 
103 BigInt 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 
130 BigInt 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 
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  {
162  return std::make_shared<const Montgomery_Exponentation_State>(params, g, window_bits, const_time);
163  }
164 
165 BigInt 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 
171 BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state,
172  const BigInt& k)
173  {
174  return precomputed_state.exponentiation_vartime(k);
175  }
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  {
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 
bool is_negative() const
Definition: bigint.h:525
const BigInt & p() const
Definition: monty.h:144
size_t bits() const
Definition: bigint.cpp:288
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:369
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:111
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
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:214
BigInt monty_execute_vartime(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k)
Definition: monty_exp.cpp:171
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
BigInt value() const
Definition: monty.cpp:311
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
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Definition: monty.cpp:363
Definition: alg_id.cpp:13
#define BOTAN_ARG_CHECK(expr, msg)
Definition: assert.h:37
Montgomery_Int & square_this(secure_vector< word > &ws)
Definition: monty.cpp:402
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
Definition: monty_exp.cpp:165
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21
static Mask< T > is_equal(T x, T y)
Definition: ct_utils.h:149
Montgomery_Int square(secure_vector< word > &ws) const
Definition: monty.cpp:408