<commit_before>/*
* Montgomery Exponentiation
* (C) 1999-2010,2012,2018 <NAME>
*     2016 <NAME>
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/internal/monty_exp.h>
#include <botan/internal/ct_utils.h>
#include <botan/internal/rounding.h>
#include <botan/numthry.h>
#include <botan/reducer.h>
#include <botan/monty.h>

namespace Botan {

class Montgomery_Exponentation_State
   {
   public:
      Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params,
                                     const BigInt& g,
                                     size_t window_bits,
                                     bool const_time);

      BigInt exponentiation(const BigInt& k, size_t max_k_bits) const;

      BigInt exponentiation_vartime(const BigInt& k) const;
   private:
      std::shared_ptr<const Montgomery_Params> m_params;
      std::vector<Montgomery_Int> m_g;
      size_t m_window_bits;
      bool m_const_time;
   };

Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params,
                                                               const BigInt& g,
                                                               size_t window_bits,
                                                               bool const_time) :
   m_params(params),
   m_window_bits(window_bits == 0 ? 4 : window_bits),
   m_const_time(const_time)
   {
   BOTAN_ARG_CHECK(g < m_params->p(), "Montgomery base too big");

   if(m_window_bits < 1 || m_window_bits > 12) // really even 8 is too large ...
      throw Invalid_Argument("Invalid window bits for Montgomery exponentiation");

   const size_t window_size = (static_cast<size_t>(1) << m_window_bits);

   m_g.reserve(window_size);

   m_g.push_back(Montgomery_Int(m_params, m_params->R1(), false));

   m_g.push_back(Montgomery_Int(m_params, g));

   const Montgomery_Int& monty_g = m_g[1];

   for(size_t i = 2; i != window_size; ++i)
      {
      m_g.push_back(monty_g * m_g[i - 1]);
      }

   // Resize each element to exactly p words
   for(size_t i = 0; i != window_size; ++i)
      {
      m_g[i].fix_size();
      if(const_time)
         m_g[i].const_time_poison();
      }
   }

namespace {

void const_time_lookup(secure_vector<word>& output,
                       const std::vector<Montgomery_Int>& g,
                       size_t nibble)
   {
   const size_t words = output.size();

   clear_mem(output.data(), output.size());

   for(size_t i = 0; i != g.size(); ++i)
      {
      const secure_vector<word>& vec = g[i].repr().get_word_vector();

      BOTAN_ASSERT(vec.size() >= words,
                   "Word size as expected in const_time_lookup");

      const auto mask = CT::Mask<word>::is_equal(i, nibble);

      for(size_t w = 0; w != words; ++w)
         {
         output[w] |= mask.if_set_return(vec[w]);
         }
      }
   }

}

BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar, size_t max_k_bits) const
   {
   BOTAN_DEBUG_ASSERT(scalar.bits() <= max_k_bits);<commit_msg>Unroll const_time_lookup by 2<commit_after>/*
* Montgomery Exponentiation
* (C) 1999-2010,2012,2018 <NAME>
*     2016 <NAME>
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/internal/monty_exp.h>
#include <botan/internal/ct_utils.h>
#include <botan/internal/rounding.h>
#include <botan/numthry.h>
#include <botan/reducer.h>
#include <botan/monty.h>

namespace Botan {

class Montgomery_Exponentation_State
   {
   public:
      Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params,
                                     const BigInt& g,
                                     size_t window_bits,
                                     bool const_time);

      BigInt exponentiation(const BigInt& k, size_t max_k_bits) const;

      BigInt exponentiation_vartime(const BigInt& k) const;
   private:
      std::shared_ptr<const Montgomery_Params> m_params;
      std::vector<Montgomery_Int> m_g;
      size_t m_window_bits;
      bool m_const_time;
   };

Montgomery_Exponentation_State::Montgomery_Exponentation_State(std::shared_ptr<const Montgomery_Params> params,
                                                               const BigInt& g,
                                                               size_t window_bits,
                                                               bool const_time) :
   m_params(params),
   m_window_bits(window_bits == 0 ? 4 : window_bits),
   m_const_time(const_time)
   {
   BOTAN_ARG_CHECK(g < m_params->p(), "Montgomery base too big");

   if(m_window_bits < 1 || m_window_bits > 12) // really even 8 is too large ...
      throw Invalid_Argument("Invalid window bits for Montgomery exponentiation");

   const size_t window_size = (static_cast<size_t>(1) << m_window_bits);

   m_g.reserve(window_size);

   m_g.push_back(Montgomery_Int(m_params, m_params->R1(), false));

   m_g.push_back(Montgomery_Int(m_params, g));

   const Montgomery_Int& monty_g = m_g[1];

   for(size_t i = 2; i != window_size; ++i)
      {
      m_g.push_back(monty_g * m_g[i - 1]);
      }

   // Resize each element to exactly p words
   for(size_t i = 0; i != window_size; ++i)
      {
      m_g[i].fix_size();
      if(const_time)
         m_g[i].const_time_poison();
      }
   }

namespace {

void const_time_lookup(secure_vector<word>& output,
                       const std::vector<Montgomery_Int>& g,
                       size_t nibble)
   {
   BOTAN_ASSERT_NOMSG(g.size() % 2 == 0); // actually a power of 2

   const size_t words = output.size();

   clear_mem(output.data(), output.size());

   for(size_t i = 0; i != g.size(); i += 2)
      {
      const secure_vector<word>& vec_0 = g[i  ].repr().get_word_vector();
      const secure_vector<word>& vec_1 = g[i+1].repr().get_word_vector();

      BOTAN_ASSERT_NOMSG(vec_0.size() >= words && vec_1.size() >= words);

      const auto mask_0 = CT::Mask<word>::is_equal(nibble, i);
      const auto mask_1 = CT::Mask<word>::is_equal(nibble, i+1);

      for(size_t w = 0; w != words; ++w)
         {
         output[w] |= mask_0.if_set_return(vec_0[w]);
         output[w] |= mask_1.if_set_return(vec_1[w]);
         }
      }
   }

}

BigInt Montgomery_Exponentation_State::exponentiation(const BigInt& scalar, size_t max_k_bits) const
   {
   BOTAN_DEBUG_ASSERT(scalar.bits() <= max_k_bits);
{'fraction_non_alphanumeric': 0.11626823967711891, 'fraction_numerical': 0.013194660043464762, 'mean_word_length': 2.3839285714285716, 'pattern_counts': {'":': 0, '<': 49, '<?xml version=': 0, '>': 48, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5775097', 'n_tokens_mistral': 2229, 'n_tokens_neox': 2110, 'n_words': 421}