Botan  2.13.0
Crypto and TLS for C++11
pow_mod.cpp
Go to the documentation of this file.
1 /*
2 * Modular Exponentiation Proxy
3 * (C) 1999-2007,2012,2018,2019 Jack Lloyd
4 * 2016 Matthias Gierlings
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 */
8 
9 #include <botan/pow_mod.h>
10 #include <botan/numthry.h>
11 #include <botan/reducer.h>
12 #include <botan/monty.h>
13 #include <botan/internal/monty_exp.h>
14 #include <botan/internal/rounding.h>
15 #include <vector>
16 
17 namespace Botan {
18 
19 class Modular_Exponentiator
20  {
21  public:
22  virtual void set_base(const BigInt&) = 0;
23  virtual void set_exponent(const BigInt&) = 0;
24  virtual BigInt execute() const = 0;
25  virtual Modular_Exponentiator* copy() const = 0;
26 
27  Modular_Exponentiator() = default;
28  Modular_Exponentiator(const Modular_Exponentiator&) = default;
29  Modular_Exponentiator & operator=(const Modular_Exponentiator&) = default;
30  virtual ~Modular_Exponentiator() = default;
31  };
32 
33 namespace {
34 
35 /**
36 * Fixed Window Exponentiator
37 */
38 class Fixed_Window_Exponentiator final : public Modular_Exponentiator
39  {
40  public:
41  void set_exponent(const BigInt& e) override { m_exp = e; }
42  void set_base(const BigInt&) override;
43  BigInt execute() const override;
44 
45  Modular_Exponentiator* copy() const override
46  { return new Fixed_Window_Exponentiator(*this); }
47 
48  Fixed_Window_Exponentiator(const BigInt&, Power_Mod::Usage_Hints);
49  private:
50  Modular_Reducer m_reducer;
51  BigInt m_exp;
52  size_t m_window_bits;
53  std::vector<BigInt> m_g;
54  Power_Mod::Usage_Hints m_hints;
55  };
56 
57 void Fixed_Window_Exponentiator::set_base(const BigInt& base)
58  {
59  m_window_bits = Power_Mod::window_bits(m_exp.bits(), base.bits(), m_hints);
60 
61  m_g.resize(static_cast<size_t>(1) << m_window_bits);
62  m_g[0] = 1;
63  m_g[1] = m_reducer.reduce(base);
64 
65  for(size_t i = 2; i != m_g.size(); ++i)
66  m_g[i] = m_reducer.multiply(m_g[i-1], m_g[1]);
67  }
68 
69 BigInt Fixed_Window_Exponentiator::execute() const
70  {
71  const size_t exp_nibbles = (m_exp.bits() + m_window_bits - 1) / m_window_bits;
72 
73  BigInt x = 1;
74 
75  for(size_t i = exp_nibbles; i > 0; --i)
76  {
77  for(size_t j = 0; j != m_window_bits; ++j)
78  x = m_reducer.square(x);
79 
80  const uint32_t nibble = m_exp.get_substring(m_window_bits*(i-1), m_window_bits);
81 
82  // not const time:
83  x = m_reducer.multiply(x, m_g[nibble]);
84  }
85  return x;
86  }
87 
88 /*
89 * Fixed_Window_Exponentiator Constructor
90 */
91 Fixed_Window_Exponentiator::Fixed_Window_Exponentiator(const BigInt& n,
93  : m_reducer{Modular_Reducer(n)}, m_exp{}, m_window_bits{}, m_g{}, m_hints{hints}
94  {}
95 
96 class Montgomery_Exponentiator final : public Modular_Exponentiator
97  {
98  public:
99  void set_exponent(const BigInt& e) override { m_e = e; }
100  void set_base(const BigInt&) override;
101  BigInt execute() const override;
102 
103  Modular_Exponentiator* copy() const override
104  { return new Montgomery_Exponentiator(*this); }
105 
106  Montgomery_Exponentiator(const BigInt&, Power_Mod::Usage_Hints);
107  private:
108  BigInt m_p;
109  Modular_Reducer m_mod_p;
110  std::shared_ptr<const Montgomery_Params> m_monty_params;
111  std::shared_ptr<const Montgomery_Exponentation_State> m_monty;
112 
113  BigInt m_e;
114  Power_Mod::Usage_Hints m_hints;
115  };
116 
117 void Montgomery_Exponentiator::set_base(const BigInt& base)
118  {
119  size_t window_bits = Power_Mod::window_bits(m_e.bits(), base.bits(), m_hints);
120  m_monty = monty_precompute(m_monty_params, m_mod_p.reduce(base), window_bits);
121  }
122 
123 BigInt Montgomery_Exponentiator::execute() const
124  {
125  /*
126  This leaks size of e via loop iterations, not possible to fix without
127  breaking this API. Round up to avoid leaking fine details.
128  */
129  return monty_execute(*m_monty, m_e, round_up(m_e.bits(), 8));
130  }
131 
132 Montgomery_Exponentiator::Montgomery_Exponentiator(const BigInt& mod,
133  Power_Mod::Usage_Hints hints) :
134  m_p(mod),
135  m_mod_p(mod),
136  m_monty_params(std::make_shared<Montgomery_Params>(m_p, m_mod_p)),
137  m_hints(hints)
138  {
139  }
140 
141 }
142 
143 /*
144 * Power_Mod Constructor
145 */
146 Power_Mod::Power_Mod(const BigInt& n, Usage_Hints hints, bool disable_monty)
147  {
148  set_modulus(n, hints, disable_monty);
149  }
150 
151 Power_Mod::~Power_Mod() { /* for ~unique_ptr */ }
152 
153 /*
154 * Power_Mod Copy Constructor
155 */
156 Power_Mod::Power_Mod(const Power_Mod& other)
157  {
158  if(other.m_core.get())
159  m_core.reset(other.m_core->copy());
160  }
161 
162 /*
163 * Power_Mod Assignment Operator
164 */
165 Power_Mod& Power_Mod::operator=(const Power_Mod& other)
166  {
167  if(this != &other)
168  {
169  if(other.m_core)
170  m_core.reset(other.m_core->copy());
171  else
172  m_core.reset();
173  }
174  return (*this);
175  }
176 
177 /*
178 * Set the modulus
179 */
180 void Power_Mod::set_modulus(const BigInt& n, Usage_Hints hints, bool disable_monty) const
181  {
182  // Allow set_modulus(0) to mean "drop old state"
183 
184  m_core.reset();
185 
186  if(n != 0)
187  {
188  if(n.is_odd() && disable_monty == false)
189  m_core.reset(new Montgomery_Exponentiator(n, hints));
190  else
191  m_core.reset(new Fixed_Window_Exponentiator(n, hints));
192  }
193  }
194 
195 /*
196 * Set the base
197 */
198 void Power_Mod::set_base(const BigInt& b) const
199  {
200  if(b.is_negative())
201  throw Invalid_Argument("Power_Mod::set_base: arg must be non-negative");
202 
203  if(!m_core)
204  throw Internal_Error("Power_Mod::set_base: m_core was NULL");
205  m_core->set_base(b);
206  }
207 
208 /*
209 * Set the exponent
210 */
211 void Power_Mod::set_exponent(const BigInt& e) const
212  {
213  if(e.is_negative())
214  throw Invalid_Argument("Power_Mod::set_exponent: arg must be > 0");
215 
216  if(!m_core)
217  throw Internal_Error("Power_Mod::set_exponent: m_core was NULL");
218  m_core->set_exponent(e);
219  }
220 
221 /*
222 * Compute the result
223 */
224 BigInt Power_Mod::execute() const
225  {
226  if(!m_core)
227  throw Internal_Error("Power_Mod::execute: m_core was NULL");
228  return m_core->execute();
229  }
230 
231 /*
232 * Try to choose a good window size
233 */
234 size_t Power_Mod::window_bits(size_t exp_bits, size_t,
236  {
237  static const size_t wsize[][2] = {
238  { 1434, 7 },
239  { 539, 6 },
240  { 197, 4 },
241  { 70, 3 },
242  { 17, 2 },
243  { 0, 0 }
244  };
245 
246  size_t window_bits = 1;
247 
248  if(exp_bits)
249  {
250  for(size_t j = 0; wsize[j][0]; ++j)
251  {
252  if(exp_bits >= wsize[j][0])
253  {
254  window_bits += wsize[j][1];
255  break;
256  }
257  }
258  }
259 
260  if(hints & Power_Mod::BASE_IS_FIXED)
261  window_bits += 2;
262  if(hints & Power_Mod::EXP_IS_LARGE)
263  ++window_bits;
264 
265  return window_bits;
266  }
267 
268 namespace {
269 
270 /*
271 * Choose potentially useful hints
272 */
273 Power_Mod::Usage_Hints choose_base_hints(const BigInt& b, const BigInt& n)
274  {
275  if(b == 2)
276  return Power_Mod::Usage_Hints(Power_Mod::BASE_IS_2 |
277  Power_Mod::BASE_IS_SMALL);
278 
279  const size_t b_bits = b.bits();
280  const size_t n_bits = n.bits();
281 
282  if(b_bits < n_bits / 32)
283  return Power_Mod::BASE_IS_SMALL;
284  if(b_bits > n_bits / 4)
285  return Power_Mod::BASE_IS_LARGE;
286 
287  return Power_Mod::NO_HINTS;
288  }
289 
290 /*
291 * Choose potentially useful hints
292 */
293 Power_Mod::Usage_Hints choose_exp_hints(const BigInt& e, const BigInt& n)
294  {
295  const size_t e_bits = e.bits();
296  const size_t n_bits = n.bits();
297 
298  if(e_bits < n_bits / 32)
299  return Power_Mod::BASE_IS_SMALL;
300  if(e_bits > n_bits / 4)
301  return Power_Mod::BASE_IS_LARGE;
302  return Power_Mod::NO_HINTS;
303  }
304 
305 }
306 
307 /*
308 * Fixed_Exponent_Power_Mod Constructor
309 */
310 Fixed_Exponent_Power_Mod::Fixed_Exponent_Power_Mod(const BigInt& e,
311  const BigInt& n,
312  Usage_Hints hints) :
313  Power_Mod(n, Usage_Hints(hints | EXP_IS_FIXED | choose_exp_hints(e, n)))
314  {
315  set_exponent(e);
316  }
317 
318 /*
319 * Fixed_Base_Power_Mod Constructor
320 */
322  Usage_Hints hints) :
323  Power_Mod(n, Usage_Hints(hints | BASE_IS_FIXED | choose_base_hints(b, n)))
324  {
325  set_base(b);
326  }
327 
328 }
bool is_negative() const
Definition: bigint.h:525
size_t bits() const
Definition: bigint.cpp:288
int(* final)(unsigned char *, CTX *)
Definition: bigint.h:1135
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:214
void set_exponent(const BigInt &exponent) const
Definition: pow_mod.cpp:211
bool is_odd() const
Definition: bigint.h:407
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
Definition: alg_id.cpp:13
static size_t window_bits(size_t exp_bits, size_t base_bits, Power_Mod::Usage_Hints hints)
Definition: pow_mod.cpp:234
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
void set_base(const BigInt &base) const
Definition: pow_mod.cpp:198
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
BigInt square(const BigInt &x) const
Definition: reducer.h:39
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31