Botan  2.8.0
Crypto and TLS for C++11
reducer.cpp
Go to the documentation of this file.
1 /*
2 * Modular Reducer
3 * (C) 1999-2011,2018 Jack Lloyd
4 *
5 * Botan is released under the Simplified BSD License (see license.txt)
6 */
7 
8 #include <botan/reducer.h>
9 #include <botan/internal/ct_utils.h>
10 
11 namespace Botan {
12 
13 /*
14 * Modular_Reducer Constructor
15 */
17  {
18  if(mod < 0)
19  throw Invalid_Argument("Modular_Reducer: modulus must be positive");
20 
21  // Left uninitialized if mod == 0
22  m_mod_words = 0;
23 
24  if(mod > 0)
25  {
26  m_modulus = mod;
27  m_mod_words = m_modulus.sig_words();
28 
29  m_modulus_2 = Botan::square(m_modulus);
30 
31  m_mu = BigInt::power_of_2(2 * BOTAN_MP_WORD_BITS * m_mod_words) / m_modulus;
32  }
33  }
34 
36  {
37  BigInt r;
39  reduce(r, x, ws);
40  return r;
41  }
42 
44  {
45  if(&t1 == &x)
46  throw Invalid_State("Modular_Reducer arguments cannot alias");
47  if(m_mod_words == 0)
48  throw Invalid_State("Modular_Reducer: Never initalized");
49 
50  const size_t x_sw = x.sig_words();
51 
52  if(x_sw >= (2*m_mod_words - 1) && x.cmp(m_modulus_2, false) >= 0)
53  {
54  // too big, fall back to normal division
55  t1 = x % m_modulus;
56  return;
57  }
58 
59  t1 = x;
61  t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words - 1));
62 
63  t1.mul(m_mu, ws);
64  t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words + 1));
65 
66  // TODO add masked mul to avoid computing high bits
67  t1.mul(m_modulus, ws);
68  t1.mask_bits(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
69 
70  t1.rev_sub(x.data(), std::min(x_sw, m_mod_words + 1), ws);
71 
72  /*
73  * If t1 < 0 then we must add b^(k+1) where b = 2^w. To avoid a
74  * side channel perform the addition unconditionally, with ws set
75  * to either b^(k+1) or else 0.
76  */
77  const word t1_neg = t1.is_negative();
78 
79  if(ws.size() < m_mod_words + 2)
80  ws.resize(m_mod_words + 2);
81  clear_mem(ws.data(), ws.size());
82  ws[m_mod_words + 1] = t1_neg;
83 
84  t1.add(ws.data(), m_mod_words + 2, BigInt::Positive);
85 
86  t1.reduce_below(m_modulus, ws);
87 
88  if(x.is_negative() && t1.is_nonzero())
89  {
90  t1.rev_sub(m_modulus.data(), m_modulus.size(), ws);
91  }
92  }
93 
94 }
bool is_negative() const
Definition: bigint.h:478
int32_t cmp(const BigInt &n, bool check_signs=true) const
Definition: bigint.cpp:131
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:97
bool is_nonzero() const
Definition: bigint.h:356
void mask_bits(size_t n)
Definition: bigint.h:388
const word * data() const
Definition: bigint.h:569
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
size_t size() const
Definition: bigint.h:531
static BigInt power_of_2(size_t n)
Definition: bigint.h:666
BigInt & add(const word y[], size_t y_words, Sign sign)
Definition: big_ops2.cpp:15
Definition: alg_id.cpp:13
size_t sig_words() const
Definition: bigint.h:537
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:35
void reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:267
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:88
BigInt & mul(const BigInt &y, secure_vector< word > &ws)
Definition: big_ops2.cpp:210
BigInt & rev_sub(const word y[], size_t y_size, secure_vector< word > &ws)
Definition: big_ops2.cpp:166
void set_sign(Sign sign)
Definition: bigint.h:514