Botan 2.13.0 Crypto and TLS for C++11

- Main Page
- Namespaces
- Classes
- Files

- File List
- File Members

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,
92 Power_Mod::Usage_Hints hints)
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,
235 Power_Mod::Usage_Hints hints)
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 */
321 Fixed_Base_Power_Mod::Fixed_Base_Power_Mod(const BigInt& b, const BigInt& n,
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 }
Botan::Invalid_Argument
Definition: exceptn.h:136
Botan::BigInt::is_odd
bool is_odd() const
Definition: bigint.h:407
Botan::BigInt
Definition: bigint.h:24
m_g
std::vector< BigInt > m_g
Definition: pow_mod.cpp:53
final
int(* final)(unsigned char *, CTX *)
Definition: commoncrypto_hash.cpp:28
std
Definition: bigint.h:1135
Botan::Internal_Error
Definition: exceptn.h:341
Botan::BigInt::is_negative
bool is_negative() const
Definition: bigint.h:525
m_exp
BigInt m_exp
Definition: pow_mod.cpp:51
m_mod_p
Modular_Reducer m_mod_p
Definition: pow_mod.cpp:109
Botan::Fixed_Base_Power_Mod::Fixed_Base_Power_Mod
Fixed_Base_Power_Mod()=default
Botan::BigInt::bits
size_t bits() const
Definition: bigint.cpp:288
m_window_bits
size_t m_window_bits
Definition: pow_mod.cpp:52
Botan::Power_Mod
Definition: pow_mod.h:22
m_monty_params
std::shared_ptr< const Montgomery_Params > m_monty_params
Definition: pow_mod.cpp:110
Botan::Modular_Reducer::multiply
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31
Botan::Power_Mod::set_exponent
void set_exponent(const BigInt &exponent) const
Definition: pow_mod.cpp:211
m_e
BigInt m_e
Definition: pow_mod.cpp:113
Botan::monty_precompute
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
m_monty
std::shared_ptr< const Montgomery_Exponentation_State > m_monty
Definition: pow_mod.cpp:111
Botan
Definition: alg_id.cpp:13
Botan::Modular_Reducer::reduce
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
Botan::Power_Mod::window_bits
static size_t window_bits(size_t exp_bits, size_t base_bits, Power_Mod::Usage_Hints hints)
Definition: pow_mod.cpp:234
m_reducer
Modular_Reducer m_reducer
Definition: pow_mod.cpp:50
Botan::BigInt::get_substring
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:214
Botan::Power_Mod::Usage_Hints
Usage_Hints
Definition: pow_mod.h:26
m_hints
Power_Mod::Usage_Hints m_hints
Definition: pow_mod.cpp:54
m_p
BigInt m_p
Definition: pow_mod.cpp:108
Botan::Power_Mod::set_base
void set_base(const BigInt &base) const
Definition: pow_mod.cpp:198
Botan::monty_execute
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
Definition: monty_exp.cpp:165
Botan::Modular_Reducer::square
BigInt square(const BigInt &x) const
Definition: reducer.h:39
Botan::round_up
size_t round_up(size_t n, size_t align_to)
Definition: rounding.h:21