Coverage Report

Created: 2020-02-14 15:38

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