Botan  2.1.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  m_core = nullptr;
19  set_modulus(n, hints, disable_monty);
20  }
21 
22 /*
23 * Power_Mod Copy Constructor
24 */
26  {
27  m_core = nullptr;
28  if(other.m_core)
29  m_core = other.m_core->copy();
30  }
31 
32 /*
33 * Power_Mod Assignment Operator
34 */
36  {
37  if(this != &other)
38  {
39  delete m_core;
40  m_core = nullptr;
41  if(other.m_core)
42  {
43  m_core = other.m_core->copy();
44  }
45  }
46  return (*this);
47  }
48 
49 /*
50 * Power_Mod Destructor
51 */
53  {
54  delete m_core;
55  m_core = nullptr;
56  }
57 
58 /*
59 * Set the modulus
60 */
61 void Power_Mod::set_modulus(const BigInt& n, Usage_Hints hints, bool disable_monty) const
62  {
63  // Allow set_modulus(0) to mean "drop old state"
64 
65  delete m_core;
66  m_core = nullptr;
67 
68  if(n != 0)
69  {
70  if(n.is_odd() && disable_monty == false)
71  m_core = new Montgomery_Exponentiator(n, hints);
72 
73  if(!m_core)
74  m_core = new Fixed_Window_Exponentiator(n, hints);
75  }
76  }
77 
78 /*
79 * Set the base
80 */
81 void Power_Mod::set_base(const BigInt& b) const
82  {
83  if(b.is_zero() || b.is_negative())
84  throw Invalid_Argument("Power_Mod::set_base: arg must be > 0");
85 
86  if(!m_core)
87  throw Internal_Error("Power_Mod::set_base: m_core was NULL");
88  m_core->set_base(b);
89  }
90 
91 /*
92 * Set the exponent
93 */
94 void Power_Mod::set_exponent(const BigInt& e) const
95  {
96  if(e.is_negative())
97  throw Invalid_Argument("Power_Mod::set_exponent: arg must be > 0");
98 
99  if(!m_core)
100  throw Internal_Error("Power_Mod::set_exponent: m_core was NULL");
101  m_core->set_exponent(e);
102  }
103 
104 /*
105 * Compute the result
106 */
108  {
109  if(!m_core)
110  throw Internal_Error("Power_Mod::execute: m_core was NULL");
111  return m_core->execute();
112  }
113 
114 /*
115 * Try to choose a good window size
116 */
117 size_t Power_Mod::window_bits(size_t exp_bits, size_t,
119  {
120  static const size_t wsize[][2] = {
121  { 1434, 7 },
122  { 539, 6 },
123  { 197, 4 },
124  { 70, 3 },
125  { 25, 2 },
126  { 0, 0 }
127  };
128 
129  size_t window_bits = 1;
130 
131  if(exp_bits)
132  {
133  for(size_t j = 0; wsize[j][0]; ++j)
134  {
135  if(exp_bits >= wsize[j][0])
136  {
137  window_bits += wsize[j][1];
138  break;
139  }
140  }
141  }
142 
143  if(hints & Power_Mod::BASE_IS_FIXED)
144  window_bits += 2;
145  if(hints & Power_Mod::EXP_IS_LARGE)
146  ++window_bits;
147 
148  return window_bits;
149  }
150 
151 namespace {
152 
153 /*
154 * Choose potentially useful hints
155 */
156 Power_Mod::Usage_Hints choose_base_hints(const BigInt& b, const BigInt& n)
157  {
158  if(b == 2)
161 
162  const size_t b_bits = b.bits();
163  const size_t n_bits = n.bits();
164 
165  if(b_bits < n_bits / 32)
167  if(b_bits > n_bits / 4)
169 
170  return Power_Mod::NO_HINTS;
171  }
172 
173 /*
174 * Choose potentially useful hints
175 */
176 Power_Mod::Usage_Hints choose_exp_hints(const BigInt& e, const BigInt& n)
177  {
178  const size_t e_bits = e.bits();
179  const size_t n_bits = n.bits();
180 
181  if(e_bits < n_bits / 32)
183  if(e_bits > n_bits / 4)
185  return Power_Mod::NO_HINTS;
186  }
187 
188 }
189 
190 /*
191 * Fixed_Exponent_Power_Mod Constructor
192 */
194  const BigInt& n,
195  Usage_Hints hints) :
196  Power_Mod(n, Usage_Hints(hints | EXP_IS_FIXED | choose_exp_hints(e, n)))
197  {
198  set_exponent(e);
199  }
200 
201 /*
202 * Fixed_Base_Power_Mod Constructor
203 */
205  Usage_Hints hints) :
206  Power_Mod(n, Usage_Hints(hints | BASE_IS_FIXED | choose_base_hints(b, n)))
207  {
208  set_base(b);
209  }
210 
211 }
virtual void set_exponent(const BigInt &)=0
bool is_odd() const
Definition: bigint.h:238
void set_modulus(const BigInt &modulus, Usage_Hints=NO_HINTS, bool disable_montgomery_arith=false) const
Definition: pow_mod.cpp:61
virtual void set_base(const BigInt &)=0
bool is_negative() const
Definition: bigint.h:348
virtual BigInt execute() const =0
Power_Mod(const BigInt &modulus=0, Usage_Hints hints=NO_HINTS, bool disable_montgomery_arith=false)
Definition: pow_mod.cpp:16
virtual Modular_Exponentiator * copy() const =0
size_t bits() const
Definition: bigint.cpp:184
Power_Mod & operator=(const Power_Mod &)
Definition: pow_mod.cpp:35
void set_exponent(const BigInt &exponent) const
Definition: pow_mod.cpp:94
virtual ~Power_Mod()
Definition: pow_mod.cpp:52
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:117
void set_base(const BigInt &base) const
Definition: pow_mod.cpp:81
bool is_zero() const
Definition: bigint.h:250
BigInt execute() const
Definition: pow_mod.cpp:107