Botan::Montgomery_Exponentiator Class Reference

#include <def_powm.h>

Inheritance diagram for Botan::Montgomery_Exponentiator:

Public Member Functions
Modular_Exponentiator *	copy () const
BigInt	execute () const
	Montgomery_Exponentiator (const BigInt &, Power_Mod::Usage_Hints)
void	set_base (const BigInt &)
void	set_exponent (const BigInt &)

Detailed Description

Montgomery Exponentiator

Definition at line 42 of file def_powm.h.

Constructor & Destructor Documentation

Montgomery_Exponentiator()

Botan::Montgomery_Exponentiator::Montgomery_Exponentiator	(	const BigInt &	mod,
		Power_Mod::Usage_Hints	hints )

Definition at line 130 of file powm_mnt.cpp.

   {
   // Montgomery reduction only works for positive odd moduli
   if(!mod.is_positive() || mod.is_even())
      throw Invalid_Argument("Montgomery_Exponentiator: invalid modulus");
 
   window_bits = 0;
   this->hints = hints;
   modulus = mod;
   exp_bits = 0;
 
   mod_words = modulus.sig_words();
 
   BigInt r(BigInt::Power2, mod_words * BOTAN_MP_WORD_BITS);
   mod_prime = (((r * inverse_mod(r, mod)) - 1) / mod).word_at(0);
 
   R_mod = r % modulus;
 
   R2 = (R_mod * R_mod) % modulus;
   }

References Botan::inverse_mod(), Botan::BigInt::is_even(), Botan::BigInt::is_positive(), Botan::BigInt::Power2, and Botan::BigInt::sig_words().

Referenced by copy(), and Botan::Core_Engine::mod_exp().

Member Function Documentation

copy()

Modular_Exponentiator * Botan::Montgomery_Exponentiator::copy ( ) const

inlinevirtual

Implements Botan::Modular_Exponentiator.

Definition at line 49 of file def_powm.h.

         { return new Montgomery_Exponentiator(*this); }

References Montgomery_Exponentiator().

execute()

BigInt Botan::Montgomery_Exponentiator::execute ( ) const

virtual

Implements Botan::Modular_Exponentiator.

Definition at line 78 of file powm_mnt.cpp.

   {
   const size_t exp_nibbles = (exp_bits + window_bits - 1) / window_bits;
 
   BigInt x = R_mod;
   SecureVector<word> z(2 * (mod_words + 1));
   SecureVector<word> workspace(2 * (mod_words + 1));
   SecureVector<word> e(mod_words);
 
   for(size_t i = exp_nibbles; i > 0; --i)
      {
      for(size_t k = 0; k != window_bits; ++k)
         {
         zeroise(z);
 
         bigint_monty_sqr(&z[0], z.size(),
                          x.data(), x.size(), x.sig_words(),
                          modulus.data(), mod_words, mod_prime,
                          &workspace[0]);
 
         x.assign(&z[0], mod_words + 1);
         }
 
      const u32bit nibble = exp.get_substring(window_bits*(i-1), window_bits);
 
      zeroise(z);
 
      BigInt::const_time_lookup(e, g, nibble);
 
      bigint_monty_mul(&z[0], z.size(),
                       x.data(), x.size(), x.sig_words(),
                       e.data(), e.size(), e.size(),
                       modulus.data(), mod_words, mod_prime,
                       &workspace[0]);
 
      x.assign(&z[0], mod_words + 1);
      }
 
   x.get_reg().resize(2*mod_words+1);
 
   bigint_monty_redc(&x[0], x.size(),
                     modulus.data(), mod_words, mod_prime,
                     &workspace[0]);
 
   x.get_reg().resize(mod_words+1);
 
   return x;
   }

References Botan::BigInt::assign(), Botan::bigint_monty_mul(), Botan::bigint_monty_redc(), Botan::bigint_monty_sqr(), Botan::BigInt::const_time_lookup(), Botan::BigInt::data(), Botan::MemoryRegion< T >::data(), Botan::BigInt::get_reg(), Botan::MemoryRegion< T >::resize(), Botan::BigInt::sig_words(), Botan::BigInt::size(), Botan::MemoryRegion< T >::size(), and Botan::zeroise().

set_base()

void Botan::Montgomery_Exponentiator::set_base ( const BigInt & base )

virtual

Implements Botan::Modular_Exponentiator.

Definition at line 26 of file powm_mnt.cpp.

   {
   window_bits = Power_Mod::window_bits(exp.bits(), base.bits(), hints);
 
   g.resize((1 << window_bits));
 
   SecureVector<word> z(2 * (mod_words + 1));
   SecureVector<word> workspace(z.size());
 
   g[0] = 1;
 
   bigint_monty_mul(&z[0], z.size(),
                    g[0].data(), g[0].size(), g[0].sig_words(),
                    R2.data(), R2.size(), R2.sig_words(),
                    modulus.data(), mod_words, mod_prime,
                    &workspace[0]);
 
   g[0].assign(&z[0], mod_words + 1);
 
   g[1] = (base >= modulus) ? (base % modulus) : base;
 
   bigint_monty_mul(&z[0], z.size(),
                    g[1].data(), g[1].size(), g[1].sig_words(),
                    R2.data(), R2.size(), R2.sig_words(),
                    modulus.data(), mod_words, mod_prime,
                    &workspace[0]);
 
   g[1].assign(&z[0], mod_words + 1);
 
   const BigInt& x = g[1];
   const size_t x_sig = x.sig_words();
 
   for(size_t i = 1; i != g.size(); ++i)
      {
      const BigInt& y = g[i-1];
      const size_t y_sig = y.sig_words();
 
      zeroise(z);
      bigint_monty_mul(&z[0], z.size(),
                       x.data(), x.size(), x_sig,
                       y.data(), y.size(), y_sig,
                       modulus.data(), mod_words, mod_prime,
                       &workspace[0]);
 
      g[i].assign(&z[0], mod_words + 1);
      g[i].grow_to(mod_words);
      }
   }

References Botan::bigint_monty_mul(), Botan::BigInt::bits(), Botan::BigInt::data(), Botan::BigInt::sig_words(), Botan::BigInt::size(), Botan::MemoryRegion< T >::size(), Botan::Power_Mod::window_bits(), and Botan::zeroise().

set_exponent()

void Botan::Montgomery_Exponentiator::set_exponent ( const BigInt & exp )

virtual

Implements Botan::Modular_Exponentiator.

Definition at line 17 of file powm_mnt.cpp.

   {
   this->exp = exp;
   exp_bits = exp.bits();
   }

References Botan::BigInt::bits().

---

The documentation for this class was generated from the following files:

• src/math/numbertheory/def_powm.h
• src/math/numbertheory/powm_mnt.cpp