Botan  2.7.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 
35 /*
36 * Barrett Reduction
37 */
39  {
40  if(m_mod_words == 0)
41  throw Invalid_State("Modular_Reducer: Never initalized");
42 
43  const size_t x_sw = x.sig_words();
44 
45  if(x_sw >= (2*m_mod_words - 1) && x.cmp(m_modulus_2, false) >= 0)
46  {
47  // too big, fall back to normal division
48  return (x % m_modulus);
49  }
50 
52 
53  BigInt t1 = x;
55  t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words - 1));
56 
57  t1.mul(m_mu, ws);
58  t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words + 1));
59 
60  // TODO add masked mul to avoid computing high bits
61  t1.mul(m_modulus, ws);
62  t1.mask_bits(BOTAN_MP_WORD_BITS * (m_mod_words + 1));
63 
64  t1.rev_sub(x.data(), std::min(x_sw, m_mod_words + 1), ws);
65 
66  /*
67  * If t1 < 0 then we must add b^(k+1) where b = 2^w. To avoid a
68  * side channel perform the addition unconditionally, with ws set
69  * to either b^(k+1) or else 0.
70  */
71  const word t1_neg = t1.is_negative();
72 
73  if(ws.size() < m_mod_words + 2)
74  ws.resize(m_mod_words + 2);
75  clear_mem(ws.data(), ws.size());
76  ws[m_mod_words + 1] = t1_neg;
77 
78  t1.add(ws.data(), m_mod_words + 2, BigInt::Positive);
79 
80  t1.reduce_below(m_modulus, ws);
81 
82  if(x.is_negative() && t1.is_nonzero())
83  {
84  t1.rev_sub(m_modulus.data(), m_modulus.size(), ws);
85  }
86 
87  return t1;
88  }
89 
90 }
bool is_negative() const
Definition: bigint.h:460
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:349
void mask_bits(size_t n)
Definition: bigint.h:381
const word * data() const
Definition: bigint.h:551
BigInt square(const BigInt &x)
Definition: mp_numth.cpp:19
size_t size() const
Definition: bigint.h:513
static BigInt power_of_2(size_t n)
Definition: bigint.h:642
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:519
BigInt reduce(const BigInt &x) const
Definition: reducer.cpp:38
void reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:266
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:496