Botan  1.10.9
pow_mod.cpp
Go to the documentation of this file.
1 /*
2 * Modular Exponentiation Proxy
3 * (C) 1999-2007 Jack Lloyd
4 *
5 * Distributed under the terms of the Botan license
6 */
7 
8 #include <botan/pow_mod.h>
9 #include <botan/libstate.h>
10 #include <botan/engine.h>
11 
12 namespace Botan {
13 
14 /*
15 * Power_Mod Constructor
16 */
18  {
19  core = 0;
20  set_modulus(n, hints);
21  hints = NO_HINTS;
22  }
23 
24 /*
25 * Power_Mod Copy Constructor
26 */
28  {
29  core = 0;
30  hints = other.hints;
31  if(other.core)
32  core = other.core->copy();
33  }
34 
35 /*
36 * Power_Mod Assignment Operator
37 */
39  {
40  delete core;
41  core = 0;
42  if(other.core)
43  core = other.core->copy();
44  return (*this);
45  }
46 
47 /*
48 * Power_Mod Destructor
49 */
51  {
52  delete core;
53  }
54 
55 /*
56 * Set the modulus
57 */
58 void Power_Mod::set_modulus(const BigInt& n, Usage_Hints hints) const
59  {
60  delete core;
61  core = 0;
62 
63  if(n != 0)
64  {
65  Algorithm_Factory::Engine_Iterator i(global_state().algorithm_factory());
66 
67  while(const Engine* engine = i.next())
68  {
69  core = engine->mod_exp(n, hints);
70 
71  if(core)
72  break;
73  }
74 
75  if(!core)
76  throw Lookup_Error("Power_Mod: Unable to find a working engine");
77  }
78  }
79 
80 /*
81 * Set the base
82 */
83 void Power_Mod::set_base(const BigInt& b) const
84  {
85  if(b.is_zero() || b.is_negative())
86  throw Invalid_Argument("Power_Mod::set_base: arg must be > 0");
87 
88  if(!core)
89  throw Internal_Error("Power_Mod::set_base: core was NULL");
90  core->set_base(b);
91  }
92 
93 /*
94 * Set the exponent
95 */
96 void Power_Mod::set_exponent(const BigInt& e) const
97  {
98  if(e.is_negative())
99  throw Invalid_Argument("Power_Mod::set_exponent: arg must be > 0");
100 
101  if(!core)
102  throw Internal_Error("Power_Mod::set_exponent: core was NULL");
103  core->set_exponent(e);
104  }
105 
106 /*
107 * Compute the result
108 */
110  {
111  if(!core)
112  throw Internal_Error("Power_Mod::execute: core was NULL");
113  return core->execute();
114  }
115 
116 /*
117 * Try to choose a good window size
118 */
119 size_t Power_Mod::window_bits(size_t exp_bits, size_t,
121  {
122  static const size_t wsize[][2] = {
123  { 1434, 7 },
124  { 539, 6 },
125  { 197, 4 },
126  { 70, 3 },
127  { 25, 2 },
128  { 0, 0 }
129  };
130 
131  size_t window_bits = 1;
132 
133  if(exp_bits)
134  {
135  for(size_t j = 0; wsize[j][0]; ++j)
136  {
137  if(exp_bits >= wsize[j][0])
138  {
139  window_bits += wsize[j][1];
140  break;
141  }
142  }
143  }
144 
145  if(hints & Power_Mod::BASE_IS_FIXED)
146  window_bits += 2;
147  if(hints & Power_Mod::EXP_IS_LARGE)
148  ++window_bits;
149 
150  return window_bits;
151  }
152 
153 namespace {
154 
155 /*
156 * Choose potentially useful hints
157 */
158 Power_Mod::Usage_Hints choose_base_hints(const BigInt& b, const BigInt& n)
159  {
160  if(b == 2)
163 
164  const size_t b_bits = b.bits();
165  const size_t n_bits = n.bits();
166 
167  if(b_bits < n_bits / 32)
169  if(b_bits > n_bits / 4)
171 
172  return Power_Mod::NO_HINTS;
173  }
174 
175 /*
176 * Choose potentially useful hints
177 */
178 Power_Mod::Usage_Hints choose_exp_hints(const BigInt& e, const BigInt& n)
179  {
180  const size_t e_bits = e.bits();
181  const size_t n_bits = n.bits();
182 
183  if(e_bits < n_bits / 32)
185  if(e_bits > n_bits / 4)
187  return Power_Mod::NO_HINTS;
188  }
189 
190 }
191 
192 /*
193 * Fixed_Exponent_Power_Mod Constructor
194 */
196  const BigInt& n,
197  Usage_Hints hints) :
198  Power_Mod(n, Usage_Hints(hints | EXP_IS_FIXED | choose_exp_hints(e, n)))
199  {
200  set_exponent(e);
201  }
202 
203 /*
204 * Fixed_Base_Power_Mod Constructor
205 */
207  Usage_Hints hints) :
208  Power_Mod(n, Usage_Hints(hints | BASE_IS_FIXED | choose_base_hints(b, n)))
209  {
210  set_base(b);
211  }
212 
213 }
virtual void set_exponent(const BigInt &)=0
BigInt n
Definition: numthry.cpp:26
virtual void set_base(const BigInt &)=0
bool is_negative() const
Definition: bigint.h:245
std::invalid_argument Invalid_Argument
Definition: exceptn.h:20
virtual BigInt execute() const =0
virtual Modular_Exponentiator * copy() const =0
size_t bits() const
Definition: bigint.cpp:253
Power_Mod & operator=(const Power_Mod &)
Definition: pow_mod.cpp:38
Library_State & global_state()
virtual ~Power_Mod()
Definition: pow_mod.cpp:50
void set_base(const BigInt &) const
Definition: pow_mod.cpp:83
static size_t window_bits(size_t exp_bits, size_t base_bits, Power_Mod::Usage_Hints hints)
Definition: pow_mod.cpp:119
bool is_zero() const
Definition: bigint.h:176
Power_Mod(const BigInt &=0, Usage_Hints=NO_HINTS)
Definition: pow_mod.cpp:17
BigInt execute() const
Definition: pow_mod.cpp:109
void set_exponent(const BigInt &) const
Definition: pow_mod.cpp:96
void set_modulus(const BigInt &, Usage_Hints=NO_HINTS) const
Definition: pow_mod.cpp:58