Botan  1.11.15
src/lib/math/numbertheory/powm_mnt.cpp
Go to the documentation of this file.
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 }