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 */
Power_Mod(const BigInt & n,Usage_Hints hints)17 Power_Mod::Power_Mod(const BigInt& n, Usage_Hints hints)
18 {
19 core = 0;
20 set_modulus(n, hints);
21 hints = NO_HINTS;
22 }
23
24 /*
25 * Power_Mod Copy Constructor
26 */
Power_Mod(const Power_Mod & other)27 Power_Mod::Power_Mod(const Power_Mod& other)
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 */
operator =(const Power_Mod & other)38 Power_Mod& Power_Mod::operator=(const Power_Mod& other)
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 */
~Power_Mod()50 Power_Mod::~Power_Mod()
51 {
52 delete core;
53 }
54
55 /*
56 * Set the modulus
57 */
set_modulus(const BigInt & n,Usage_Hints hints) const58 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 */
set_base(const BigInt & b) const83 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 */
set_exponent(const BigInt & e) const96 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 */
execute() const109 BigInt Power_Mod::execute() const
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 */
window_bits(size_t exp_bits,size_t,Power_Mod::Usage_Hints hints)119 size_t Power_Mod::window_bits(size_t exp_bits, size_t,
120 Power_Mod::Usage_Hints hints)
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 */
choose_base_hints(const BigInt & b,const BigInt & n)158 Power_Mod::Usage_Hints choose_base_hints(const BigInt& b, const BigInt& n)
159 {
160 if(b == 2)
161 return Power_Mod::Usage_Hints(Power_Mod::BASE_IS_2 |
162 Power_Mod::BASE_IS_SMALL);
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)
168 return Power_Mod::BASE_IS_SMALL;
169 if(b_bits > n_bits / 4)
170 return Power_Mod::BASE_IS_LARGE;
171
172 return Power_Mod::NO_HINTS;
173 }
174
175 /*
176 * Choose potentially useful hints
177 */
choose_exp_hints(const BigInt & e,const BigInt & n)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)
184 return Power_Mod::BASE_IS_SMALL;
185 if(e_bits > n_bits / 4)
186 return Power_Mod::BASE_IS_LARGE;
187 return Power_Mod::NO_HINTS;
188 }
189
190 }
191
192 /*
193 * Fixed_Exponent_Power_Mod Constructor
194 */
Fixed_Exponent_Power_Mod(const BigInt & e,const BigInt & n,Usage_Hints hints)195 Fixed_Exponent_Power_Mod::Fixed_Exponent_Power_Mod(const BigInt& e,
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 */
Fixed_Base_Power_Mod(const BigInt & b,const BigInt & n,Usage_Hints hints)206 Fixed_Base_Power_Mod::Fixed_Base_Power_Mod(const BigInt& b, const BigInt& n,
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 }
214