Botan 2.19.2
Crypto and TLS for C&
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
17namespace Botan {
18
19class 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
33namespace {
34
35/**
36* Fixed Window Exponentiator
37*/
38class 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;
55 };
56
57void 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
69BigInt 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*/
91Fixed_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
96class 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
117void 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
123BigInt 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
132Montgomery_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*/
146Power_Mod::Power_Mod(const BigInt& n, Usage_Hints hints, bool disable_monty)
147 {
148 set_modulus(n, hints, disable_monty);
149 }
150
151Power_Mod::~Power_Mod() { /* for ~unique_ptr */ }
152
153/*
154* Power_Mod Copy Constructor
155*/
156Power_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*/
165Power_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*/
180void 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*/
198void 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*/
211void 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*/
224BigInt 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*/
234size_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
268namespace {
269
270/*
271* Choose potentially useful hints
272*/
273Power_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*/
293Power_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*/
310Fixed_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_odd() const
Definition: bigint.h:409
size_t bits() const
Definition: bigint.cpp:296
bool is_negative() const
Definition: bigint.h:527
uint32_t get_substring(size_t offset, size_t length) const
Definition: bigint.cpp:213
BigInt square(const BigInt &x) const
Definition: reducer.h:39
BigInt multiply(const BigInt &x, const BigInt &y) const
Definition: reducer.h:31
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:37
void set_base(const BigInt &base) const
Definition: pow_mod.cpp:198
void set_exponent(const BigInt &exponent) const
Definition: pow_mod.cpp:211
static size_t window_bits(size_t exp_bits, size_t base_bits, Power_Mod::Usage_Hints hints)
Definition: pow_mod.cpp:234
int(* final)(unsigned char *, CTX *)
Definition: alg_id.cpp:13
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
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
Definition: bigint.h:1143