Botan  2.7.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 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/pow_mod.h>
9 #include <botan/internal/def_powm.h>
10 
11 namespace Botan {
12 
13 /*
14 * Power_Mod Constructor
15 */
16 Power_Mod::Power_Mod(const BigInt& n, Usage_Hints hints, bool disable_monty)
17  {
18  set_modulus(n, hints, disable_monty);
19  }
20 
21 /*
22 * Power_Mod Copy Constructor
23 */
25  {
26  if(other.m_core.get())
27  m_core.reset(other.m_core->copy());
28  }
29 
30 /*
31 * Power_Mod Assignment Operator
32 */
34  {
35  if(this != &other)
36  {
37  if(other.m_core)
38  m_core.reset(other.m_core->copy());
39  else
40  m_core.reset();
41  }
42  return (*this);
43  }
44 
45 /*
46 * Set the modulus
47 */
48 void Power_Mod::set_modulus(const BigInt& n, Usage_Hints hints, bool disable_monty) const
49  {
50  // Allow set_modulus(0) to mean "drop old state"
51 
52  m_core.reset();
53 
54  if(n != 0)
55  {
56  if(n.is_odd() && disable_monty == false)
57  m_core.reset(new Montgomery_Exponentiator(n, hints));
58  else
59  m_core.reset(new Fixed_Window_Exponentiator(n, hints));
60  }
61  }
62 
63 /*
64 * Set the base
65 */
66 void Power_Mod::set_base(const BigInt& b) const
67  {
68  if(b.is_zero() || b.is_negative())
69  throw Invalid_Argument("Power_Mod::set_base: arg must be > 0");
70 
71  if(!m_core)
72  throw Internal_Error("Power_Mod::set_base: m_core was NULL");
73  m_core->set_base(b);
74  }
75 
76 /*
77 * Set the exponent
78 */
79 void Power_Mod::set_exponent(const BigInt& e) const
80  {
81  if(e.is_negative())
82  throw Invalid_Argument("Power_Mod::set_exponent: arg must be > 0");
83 
84  if(!m_core)
85  throw Internal_Error("Power_Mod::set_exponent: m_core was NULL");
86  m_core->set_exponent(e);
87  }
88 
89 /*
90 * Compute the result
91 */
93  {
94  if(!m_core)
95  throw Internal_Error("Power_Mod::execute: m_core was NULL");
96  return m_core->execute();
97  }
98 
99 /*
100 * Try to choose a good window size
101 */
102 size_t Power_Mod::window_bits(size_t exp_bits, size_t,
104  {
105  static const size_t wsize[][2] = {
106  { 1434, 7 },
107  { 539, 6 },
108  { 197, 4 },
109  { 70, 3 },
110  { 17, 2 },
111  { 0, 0 }
112  };
113 
114  size_t window_bits = 1;
115 
116  if(exp_bits)
117  {
118  for(size_t j = 0; wsize[j][0]; ++j)
119  {
120  if(exp_bits >= wsize[j][0])
121  {
122  window_bits += wsize[j][1];
123  break;
124  }
125  }
126  }
127 
128  if(hints & Power_Mod::BASE_IS_FIXED)
129  window_bits += 2;
130  if(hints & Power_Mod::EXP_IS_LARGE)
131  ++window_bits;
132 
133  return window_bits;
134  }
135 
136 namespace {
137 
138 /*
139 * Choose potentially useful hints
140 */
141 Power_Mod::Usage_Hints choose_base_hints(const BigInt& b, const BigInt& n)
142  {
143  if(b == 2)
146 
147  const size_t b_bits = b.bits();
148  const size_t n_bits = n.bits();
149 
150  if(b_bits < n_bits / 32)
152  if(b_bits > n_bits / 4)
154 
155  return Power_Mod::NO_HINTS;
156  }
157 
158 /*
159 * Choose potentially useful hints
160 */
161 Power_Mod::Usage_Hints choose_exp_hints(const BigInt& e, const BigInt& n)
162  {
163  const size_t e_bits = e.bits();
164  const size_t n_bits = n.bits();
165 
166  if(e_bits < n_bits / 32)
168  if(e_bits > n_bits / 4)
170  return Power_Mod::NO_HINTS;
171  }
172 
173 }
174 
175 /*
176 * Fixed_Exponent_Power_Mod Constructor
177 */
179  const BigInt& n,
180  Usage_Hints hints) :
181  Power_Mod(n, Usage_Hints(hints | EXP_IS_FIXED | choose_exp_hints(e, n)))
182  {
183  set_exponent(e);
184  }
185 
186 /*
187 * Fixed_Base_Power_Mod Constructor
188 */
190  Usage_Hints hints) :
191  Power_Mod(n, Usage_Hints(hints | BASE_IS_FIXED | choose_base_hints(b, n)))
192  {
193  set_base(b);
194  }
195 
196 }
bool is_negative() const
Definition: bigint.h:460
size_t bits() const
Definition: bigint.cpp:228
bool is_zero() const
Definition: bigint.h:355
Power_Mod(const BigInt &modulus=0, Usage_Hints hints=NO_HINTS, bool disable_montgomery_arith=false)
Definition: pow_mod.cpp:16
void set_exponent(const BigInt &exponent) const
Definition: pow_mod.cpp:79
Power_Mod & operator=(const Power_Mod &)
Definition: pow_mod.cpp:33
bool is_odd() const
Definition: bigint.h:343
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:102
void set_modulus(const BigInt &modulus, Usage_Hints hints=NO_HINTS, bool disable_montgomery_arith=false) const
Definition: pow_mod.cpp:48
BigInt execute() const
Definition: pow_mod.cpp:92
void set_base(const BigInt &base) const
Definition: pow_mod.cpp:66