Botan  2.11.0
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  const Montgomery_Int& monty_g = m_g[1];
58 
59  for(size_t i = 2; i != window_size; ++i)
60  {
61  m_g.push_back(monty_g * m_g[i - 1]);
62  }
63 
64  // Resize each element to exactly p words
65  for(size_t i = 0; i != window_size; ++i)
66  {
67  m_g[i].fix_size();
68  if(const_time)
69  m_g[i].const_time_poison();
70  }
71  }
72 
73 namespace {
74 
75 void const_time_lookup(secure_vector<word>& output,
76  const std::vector<Montgomery_Int>& g,
77  size_t nibble)
78  {
79  BOTAN_ASSERT_NOMSG(g.size() % 2 == 0); // actually a power of 2
80 
81  const size_t words = output.size();
82 
83  clear_mem(output.data(), output.size());
84 
85  for(size_t i = 0; i != g.size(); i += 2)
86  {
87  const secure_vector<word>& vec_0 = g[i ].repr().get_word_vector();
88  const secure_vector<word>& vec_1 = g[i+1].repr().get_word_vector();
89 
90  BOTAN_ASSERT_NOMSG(vec_0.size() >= words && vec_1.size() >= words);
91 
92  const auto mask_0 = CT::Mask<word>::is_equal(nibble, i);
93  const auto mask_1 = CT::Mask<word>::is_equal(nibble, i+1);
94 
95  for(size_t w = 0; w != words; ++w)
96  {
97  output[w] |= mask_0.if_set_return(vec_0[w]);
98  output[w] |= mask_1.if_set_return(vec_1[w]);
99  }
100  }
101  }
102 
103 }
104 
105 BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar, size_t max_k_bits) const
106  {
107  BOTAN_DEBUG_ASSERT(scalar.bits() <= max_k_bits);
108  // TODO add a const-time implementation of above assert and use it in release builds
109 
110  const size_t exp_nibbles = (max_k_bits + m_window_bits - 1) / m_window_bits;
111 
112  if(exp_nibbles == 0)
113  return 1;
114 
115  secure_vector<word> e_bits(m_params->p_words());
116  secure_vector<word> ws;
117 
118  const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits));
119  Montgomery_Int x(m_params, e_bits.data(), e_bits.size(), false);
120 
121  for(size_t i = exp_nibbles - 1; i > 0; --i)
122  {
123  x.square_this_n_times(ws, m_window_bits);
124  const_time_lookup(e_bits, m_g, scalar.get_substring(m_window_bits*(i-1), m_window_bits));
125  x.mul_by(e_bits, ws);
126  }
127 
128  x.const_time_unpoison();
129  return x.value();
130  }
131 
132 BigInt Montgomery_Exponentation_State::exponentiation_vartime(const BigInt& scalar) const
133  {
134  BOTAN_ASSERT_NOMSG(m_const_time == false);
135 
136  const size_t exp_nibbles = (scalar.bits() + m_window_bits - 1) / m_window_bits;
137 
138  secure_vector<word> ws;
139 
140  if(exp_nibbles == 0)
141  return 1;
142 
143  Montgomery_Int x = m_g[scalar.get_substring(m_window_bits*(exp_nibbles-1), m_window_bits)];
144 
145  for(size_t i = exp_nibbles - 1; i > 0; --i)
146  {
147  x.square_this_n_times(ws, m_window_bits);
148 
149  const uint32_t nibble = scalar.get_substring(m_window_bits*(i-1), m_window_bits);
150  if(nibble > 0)
151  x.mul_by(m_g[nibble], ws);
152  }
153 
154  x.const_time_unpoison();
155  return x.value();
156  }
157 
158 std::shared_ptr<const Montgomery_Exponentation_State>
159 monty_precompute(std::shared_ptr<const Montgomery_Params> params,
160  const BigInt& g,
161  size_t window_bits,
162  bool const_time)
163  {
164  return std::make_shared<const Montgomery_Exponentation_State>(params, g, window_bits, const_time);
165  }
166 
167 BigInt monty_execute(const Montgomery_Exponentation_State& precomputed_state,
168  const BigInt& k, size_t max_k_bits)
169  {
170  return precomputed_state.exponentiation(k, max_k_bits);
171  }
172 
173 BigInt monty_execute_vartime(const Montgomery_Exponentation_State& precomputed_state,
174  const BigInt& k)
175  {
176  return precomputed_state.exponentiation_vartime(k);
177  }
178 
179 BigInt monty_multi_exp(std::shared_ptr<const Montgomery_Params> params_p,
180  const BigInt& x_bn,
181  const BigInt& z1,
182  const BigInt& y_bn,
183  const BigInt& z2)
184  {
185  if(z1.is_negative() || z2.is_negative())
186  throw Invalid_Argument("multi_exponentiate exponents must be positive");
187 
188  const size_t z_bits = round_up(std::max(z1.bits(), z2.bits()), 2);
189 
191 
192  const Montgomery_Int one(params_p, params_p->R1(), false);
193  //const Montgomery_Int one(params_p, 1);
194 
195  const Montgomery_Int x1(params_p, x_bn);
196  const Montgomery_Int x2 = x1.square(ws);
197  const Montgomery_Int x3 = x2.mul(x1, ws);
198 
199  const Montgomery_Int y1(params_p, y_bn);
200  const Montgomery_Int y2 = y1.square(ws);
201  const Montgomery_Int y3 = y2.mul(y1, ws);
202 
203  const Montgomery_Int y1x1 = y1.mul(x1, ws);
204  const Montgomery_Int y1x2 = y1.mul(x2, ws);
205  const Montgomery_Int y1x3 = y1.mul(x3, ws);
206 
207  const Montgomery_Int y2x1 = y2.mul(x1, ws);
208  const Montgomery_Int y2x2 = y2.mul(x2, ws);
209  const Montgomery_Int y2x3 = y2.mul(x3, ws);
210 
211  const Montgomery_Int y3x1 = y3.mul(x1, ws);
212  const Montgomery_Int y3x2 = y3.mul(x2, ws);
213  const Montgomery_Int y3x3 = y3.mul(x3, ws);
214 
215  const Montgomery_Int* M[16] = {
216  &one,
217  &x1, // 0001
218  &x2, // 0010
219  &x3, // 0011
220  &y1, // 0100
221  &y1x1,
222  &y1x2,
223  &y1x3,
224  &y2, // 1000
225  &y2x1,
226  &y2x2,
227  &y2x3,
228  &y3, // 1100
229  &y3x1,
230  &y3x2,
231  &y3x3
232  };
233 
234  Montgomery_Int H = one;
235 
236  for(size_t i = 0; i != z_bits; i += 2)
237  {
238  if(i > 0)
239  {
240  H.square_this(ws);
241  H.square_this(ws);
242  }
243 
244  const uint32_t z1_b = z1.get_substring(z_bits - i - 2, 2);
245  const uint32_t z2_b = z2.get_substring(z_bits - i - 2, 2);
246 
247  const uint32_t z12 = (4*z2_b) + z1_b;
248 
249  H.mul_by(*M[z12], ws);
250  }
251 
252  return H.value();
253  }
254 
255 }
256 
BigInt const BigInt & x
Definition: numthry.h:139
class BOTAN_PUBLIC_API(2, 11) Argon2 final class BOTAN_PUBLIC_API(2, 11) Argon2_Family final void size_t const char size_t const uint8_t size_t const uint8_t size_t const uint8_t size_t uint8_t size_t size_t M
Definition: argon2.h:87
const BigInt const PointGFp const BigInt & z2
Definition: point_gfp.h:350
const BigInt & p() const
Definition: monty.h:144
Montgomery_Int & mul_by(const Montgomery_Int &other, secure_vector< word > &ws)
Definition: monty.cpp:368
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:111
secure_vector< word > & ws
Definition: curve_nistp.h:24
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:179
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
BigInt monty_execute_vartime(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k)
Definition: monty_exp.cpp:173
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
BigInt value() const
Definition: monty.cpp:310
const botan_mp_t scalar
Definition: ffi.h:1325
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:159
Montgomery_Int mul(const Montgomery_Int &other, secure_vector< word > &ws) const
Definition: monty.cpp:362
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:401
void BlockCipher const uint8_t size_t uint8_t output[]
Definition: package.h:29
const BigInt & z1
Definition: point_gfp.h:350
std::pair< BigInt, SymmetricKey > BOTAN_PUBLIC_API(2, 0) srp6_client_agree(const std std::pair< BigInt, SymmetricKey > BOTAN_PUBLIC_API(2, 11) srp6_client_agree(const std BigInt BOTAN_PUBLIC_API(2, 0) generate_srp6_verifier(const std BigInt BOTAN_PUBLIC_API(2, 11) generate_srp6_verifier(const std std::string const BigInt & g
Definition: srp6.h:102
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:167
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:407
secure_vector< uint8_t > const std::string const std::vector< uint8_t > & params
Definition: pbes2.h:80