Botan
1.11.15
|
00001 /* 00002 * Montgomery Exponentiation 00003 * (C) 1999-2010,2012 Jack Lloyd 00004 * 00005 * Botan is released under the Simplified BSD License (see license.txt) 00006 */ 00007 00008 #include <botan/internal/def_powm.h> 00009 #include <botan/numthry.h> 00010 #include <botan/internal/mp_core.h> 00011 00012 namespace Botan { 00013 00014 /* 00015 * Set the exponent 00016 */ 00017 void Montgomery_Exponentiator::set_exponent(const BigInt& exp) 00018 { 00019 m_exp = exp; 00020 m_exp_bits = exp.bits(); 00021 } 00022 00023 /* 00024 * Set the base 00025 */ 00026 void Montgomery_Exponentiator::set_base(const BigInt& base) 00027 { 00028 m_window_bits = Power_Mod::window_bits(m_exp.bits(), base.bits(), m_hints); 00029 00030 m_g.resize((1 << m_window_bits)); 00031 00032 BigInt z(BigInt::Positive, 2 * (m_mod_words + 1)); 00033 secure_vector<word> workspace(z.size()); 00034 00035 m_g[0] = 1; 00036 00037 bigint_monty_mul(z.mutable_data(), z.size(), 00038 m_g[0].data(), m_g[0].size(), m_g[0].sig_words(), 00039 m_R2_mod.data(), m_R2_mod.size(), m_R2_mod.sig_words(), 00040 m_modulus.data(), m_mod_words, m_mod_prime, 00041 &workspace[0]); 00042 00043 m_g[0] = z; 00044 00045 m_g[1] = (base >= m_modulus) ? (base % m_modulus) : base; 00046 00047 bigint_monty_mul(z.mutable_data(), z.size(), 00048 m_g[1].data(), m_g[1].size(), m_g[1].sig_words(), 00049 m_R2_mod.data(), m_R2_mod.size(), m_R2_mod.sig_words(), 00050 m_modulus.data(), m_mod_words, m_mod_prime, 00051 &workspace[0]); 00052 00053 m_g[1] = z; 00054 00055 const BigInt& x = m_g[1]; 00056 const size_t x_sig = x.sig_words(); 00057 00058 for(size_t i = 2; i != m_g.size(); ++i) 00059 { 00060 const BigInt& y = m_g[i-1]; 00061 const size_t y_sig = y.sig_words(); 00062 00063 bigint_monty_mul(z.mutable_data(), z.size(), 00064 x.data(), x.size(), x_sig, 00065 y.data(), y.size(), y_sig, 00066 m_modulus.data(), m_mod_words, m_mod_prime, 00067 &workspace[0]); 00068 00069 m_g[i] = z; 00070 } 00071 } 00072 00073 /* 00074 * Compute the result 00075 */ 00076 BigInt Montgomery_Exponentiator::execute() const 00077 { 00078 const size_t exp_nibbles = (m_exp_bits + m_window_bits - 1) / m_window_bits; 00079 00080 BigInt x = m_R_mod; 00081 00082 const size_t z_size = 2*(m_mod_words + 1); 00083 00084 BigInt z(BigInt::Positive, z_size); 00085 secure_vector<word> workspace(z_size); 00086 00087 for(size_t i = exp_nibbles; i > 0; --i) 00088 { 00089 for(size_t k = 0; k != m_window_bits; ++k) 00090 { 00091 bigint_monty_sqr(z.mutable_data(), z_size, 00092 x.data(), x.size(), x.sig_words(), 00093 m_modulus.data(), m_mod_words, m_mod_prime, 00094 &workspace[0]); 00095 00096 x = z; 00097 } 00098 00099 const u32bit nibble = m_exp.get_substring(m_window_bits*(i-1), m_window_bits); 00100 00101 const BigInt& y = m_g[nibble]; 00102 00103 bigint_monty_mul(z.mutable_data(), z_size, 00104 x.data(), x.size(), x.sig_words(), 00105 y.data(), y.size(), y.sig_words(), 00106 m_modulus.data(), m_mod_words, m_mod_prime, 00107 &workspace[0]); 00108 00109 x = z; 00110 } 00111 00112 x.grow_to(2*m_mod_words + 1); 00113 00114 bigint_monty_redc(x.mutable_data(), 00115 m_modulus.data(), m_mod_words, m_mod_prime, 00116 &workspace[0]); 00117 00118 return x; 00119 } 00120 00121 /* 00122 * Montgomery_Exponentiator Constructor 00123 */ 00124 Montgomery_Exponentiator::Montgomery_Exponentiator(const BigInt& mod, 00125 Power_Mod::Usage_Hints hints) : 00126 m_modulus(mod), 00127 m_mod_words(m_modulus.sig_words()), 00128 m_window_bits(1), 00129 m_hints(hints) 00130 { 00131 // Montgomery reduction only works for positive odd moduli 00132 if(!m_modulus.is_positive() || m_modulus.is_even()) 00133 throw Invalid_Argument("Montgomery_Exponentiator: invalid modulus"); 00134 00135 m_mod_prime = monty_inverse(mod.word_at(0)); 00136 00137 const BigInt r = BigInt::power_of_2(m_mod_words * BOTAN_MP_WORD_BITS); 00138 m_R_mod = r % m_modulus; 00139 m_R2_mod = (m_R_mod * m_R_mod) % m_modulus; 00140 } 00141 00142 }