Botan
1.11.15
|
00001 /* 00002 * Modular Exponentiation Proxy 00003 * (C) 1999-2007 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/pow_mod.h> 00009 #include <botan/internal/def_powm.h> 00010 00011 namespace Botan { 00012 00013 /* 00014 * Power_Mod Constructor 00015 */ 00016 Power_Mod::Power_Mod(const BigInt& n, Usage_Hints hints) 00017 { 00018 core = nullptr; 00019 set_modulus(n, hints); 00020 } 00021 00022 /* 00023 * Power_Mod Copy Constructor 00024 */ 00025 Power_Mod::Power_Mod(const Power_Mod& other) 00026 { 00027 core = nullptr; 00028 if(other.core) 00029 core = other.core->copy(); 00030 } 00031 00032 /* 00033 * Power_Mod Assignment Operator 00034 */ 00035 Power_Mod& Power_Mod::operator=(const Power_Mod& other) 00036 { 00037 delete core; 00038 core = nullptr; 00039 if(other.core) 00040 core = other.core->copy(); 00041 return (*this); 00042 } 00043 00044 /* 00045 * Power_Mod Destructor 00046 */ 00047 Power_Mod::~Power_Mod() 00048 { 00049 delete core; 00050 core = nullptr; 00051 } 00052 00053 /* 00054 * Set the modulus 00055 */ 00056 void Power_Mod::set_modulus(const BigInt& n, Usage_Hints hints) const 00057 { 00058 delete core; 00059 00060 if(n.is_odd()) 00061 core = new Montgomery_Exponentiator(n, hints); 00062 else if(n != 0) 00063 core = new Fixed_Window_Exponentiator(n, hints); 00064 } 00065 00066 /* 00067 * Set the base 00068 */ 00069 void Power_Mod::set_base(const BigInt& b) const 00070 { 00071 if(b.is_zero() || b.is_negative()) 00072 throw Invalid_Argument("Power_Mod::set_base: arg must be > 0"); 00073 00074 if(!core) 00075 throw Internal_Error("Power_Mod::set_base: core was NULL"); 00076 core->set_base(b); 00077 } 00078 00079 /* 00080 * Set the exponent 00081 */ 00082 void Power_Mod::set_exponent(const BigInt& e) const 00083 { 00084 if(e.is_negative()) 00085 throw Invalid_Argument("Power_Mod::set_exponent: arg must be > 0"); 00086 00087 if(!core) 00088 throw Internal_Error("Power_Mod::set_exponent: core was NULL"); 00089 core->set_exponent(e); 00090 } 00091 00092 /* 00093 * Compute the result 00094 */ 00095 BigInt Power_Mod::execute() const 00096 { 00097 if(!core) 00098 throw Internal_Error("Power_Mod::execute: core was NULL"); 00099 return core->execute(); 00100 } 00101 00102 /* 00103 * Try to choose a good window size 00104 */ 00105 size_t Power_Mod::window_bits(size_t exp_bits, size_t, 00106 Power_Mod::Usage_Hints hints) 00107 { 00108 static const size_t wsize[][2] = { 00109 { 1434, 7 }, 00110 { 539, 6 }, 00111 { 197, 4 }, 00112 { 70, 3 }, 00113 { 25, 2 }, 00114 { 0, 0 } 00115 }; 00116 00117 size_t window_bits = 1; 00118 00119 if(exp_bits) 00120 { 00121 for(size_t j = 0; wsize[j][0]; ++j) 00122 { 00123 if(exp_bits >= wsize[j][0]) 00124 { 00125 window_bits += wsize[j][1]; 00126 break; 00127 } 00128 } 00129 } 00130 00131 if(hints & Power_Mod::BASE_IS_FIXED) 00132 window_bits += 2; 00133 if(hints & Power_Mod::EXP_IS_LARGE) 00134 ++window_bits; 00135 00136 return window_bits; 00137 } 00138 00139 namespace { 00140 00141 /* 00142 * Choose potentially useful hints 00143 */ 00144 Power_Mod::Usage_Hints choose_base_hints(const BigInt& b, const BigInt& n) 00145 { 00146 if(b == 2) 00147 return Power_Mod::Usage_Hints(Power_Mod::BASE_IS_2 | 00148 Power_Mod::BASE_IS_SMALL); 00149 00150 const size_t b_bits = b.bits(); 00151 const size_t n_bits = n.bits(); 00152 00153 if(b_bits < n_bits / 32) 00154 return Power_Mod::BASE_IS_SMALL; 00155 if(b_bits > n_bits / 4) 00156 return Power_Mod::BASE_IS_LARGE; 00157 00158 return Power_Mod::NO_HINTS; 00159 } 00160 00161 /* 00162 * Choose potentially useful hints 00163 */ 00164 Power_Mod::Usage_Hints choose_exp_hints(const BigInt& e, const BigInt& n) 00165 { 00166 const size_t e_bits = e.bits(); 00167 const size_t n_bits = n.bits(); 00168 00169 if(e_bits < n_bits / 32) 00170 return Power_Mod::BASE_IS_SMALL; 00171 if(e_bits > n_bits / 4) 00172 return Power_Mod::BASE_IS_LARGE; 00173 return Power_Mod::NO_HINTS; 00174 } 00175 00176 } 00177 00178 /* 00179 * Fixed_Exponent_Power_Mod Constructor 00180 */ 00181 Fixed_Exponent_Power_Mod::Fixed_Exponent_Power_Mod(const BigInt& e, 00182 const BigInt& n, 00183 Usage_Hints hints) : 00184 Power_Mod(n, Usage_Hints(hints | EXP_IS_FIXED | choose_exp_hints(e, n))) 00185 { 00186 set_exponent(e); 00187 } 00188 00189 /* 00190 * Fixed_Base_Power_Mod Constructor 00191 */ 00192 Fixed_Base_Power_Mod::Fixed_Base_Power_Mod(const BigInt& b, const BigInt& n, 00193 Usage_Hints hints) : 00194 Power_Mod(n, Usage_Hints(hints | BASE_IS_FIXED | choose_base_hints(b, n))) 00195 { 00196 set_base(b); 00197 } 00198 00199 }