/src/botan/src/lib/math/numbertheory/reducer.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | #include <botan/internal/mp_core.h> |
11 | | #include <botan/internal/divide.h> |
12 | | |
13 | | namespace Botan { |
14 | | |
15 | | /* |
16 | | * Modular_Reducer Constructor |
17 | | */ |
18 | | Modular_Reducer::Modular_Reducer(const BigInt& mod) |
19 | 38.4k | { |
20 | 38.4k | if(mod < 0) |
21 | 78 | throw Invalid_Argument("Modular_Reducer: modulus must be positive"); |
22 | | |
23 | | // Left uninitialized if mod == 0 |
24 | 38.3k | m_mod_words = 0; |
25 | | |
26 | 38.3k | if(mod > 0) |
27 | 38.1k | { |
28 | 38.1k | m_modulus = mod; |
29 | 38.1k | m_mod_words = m_modulus.sig_words(); |
30 | | |
31 | | // Compute mu = floor(2^{2k} / m) |
32 | 38.1k | m_mu.set_bit(2 * BOTAN_MP_WORD_BITS * m_mod_words); |
33 | 38.1k | m_mu = ct_divide(m_mu, m_modulus); |
34 | 38.1k | } |
35 | 38.3k | } |
36 | | |
37 | | BigInt Modular_Reducer::reduce(const BigInt& x) const |
38 | 7.96M | { |
39 | 7.96M | BigInt r; |
40 | 7.96M | secure_vector<word> ws; |
41 | 7.96M | reduce(r, x, ws); |
42 | 7.96M | return r; |
43 | 7.96M | } |
44 | | |
45 | | namespace { |
46 | | |
47 | | /* |
48 | | * Like if(cnd) x.rev_sub(...) but in const time |
49 | | */ |
50 | | void cnd_rev_sub(bool cnd, BigInt& x, const word y[], size_t y_sw, secure_vector<word>& ws) |
51 | 7.96M | { |
52 | 7.96M | if(x.sign() != BigInt::Positive) |
53 | 0 | throw Invalid_State("BigInt::sub_rev requires this is positive"); |
54 | | |
55 | 7.96M | const size_t x_sw = x.sig_words(); |
56 | | |
57 | 7.96M | const size_t max_words = std::max(x_sw, y_sw); |
58 | 7.96M | ws.resize(std::max(x_sw, y_sw)); |
59 | 7.96M | clear_mem(ws.data(), ws.size()); |
60 | 7.96M | x.grow_to(max_words); |
61 | | |
62 | 7.96M | const int32_t relative_size = bigint_sub_abs(ws.data(), x.data(), x_sw, y, y_sw); |
63 | | |
64 | 7.96M | x.cond_flip_sign((relative_size > 0) && cnd); |
65 | 7.96M | bigint_cnd_swap(cnd, x.mutable_data(), ws.data(), max_words); |
66 | 7.96M | } |
67 | | |
68 | | } |
69 | | |
70 | | void Modular_Reducer::reduce(BigInt& t1, const BigInt& x, secure_vector<word>& ws) const |
71 | 7.96M | { |
72 | 7.96M | if(&t1 == &x) |
73 | 0 | throw Invalid_State("Modular_Reducer arguments cannot alias"); |
74 | 7.96M | if(m_mod_words == 0) |
75 | 9 | throw Invalid_State("Modular_Reducer: Never initalized"); |
76 | | |
77 | 7.96M | const size_t x_sw = x.sig_words(); |
78 | | |
79 | 7.96M | if(x_sw > 2*m_mod_words) |
80 | 399 | { |
81 | | // too big, fall back to slow boat division |
82 | 399 | t1 = ct_modulo(x, m_modulus); |
83 | 399 | return; |
84 | 399 | } |
85 | | |
86 | 7.96M | t1 = x; |
87 | 7.96M | t1.set_sign(BigInt::Positive); |
88 | 7.96M | t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words - 1)); |
89 | | |
90 | 7.96M | t1.mul(m_mu, ws); |
91 | 7.96M | t1 >>= (BOTAN_MP_WORD_BITS * (m_mod_words + 1)); |
92 | | |
93 | | // TODO add masked mul to avoid computing high bits |
94 | 7.96M | t1.mul(m_modulus, ws); |
95 | 7.96M | t1.mask_bits(BOTAN_MP_WORD_BITS * (m_mod_words + 1)); |
96 | | |
97 | 7.96M | t1.rev_sub(x.data(), std::min(x_sw, m_mod_words + 1), ws); |
98 | | |
99 | | /* |
100 | | * If t1 < 0 then we must add b^(k+1) where b = 2^w. To avoid a |
101 | | * side channel perform the addition unconditionally, with ws set |
102 | | * to either b^(k+1) or else 0. |
103 | | */ |
104 | 7.96M | const word t1_neg = t1.is_negative(); |
105 | | |
106 | 7.96M | if(ws.size() < m_mod_words + 2) |
107 | 177k | ws.resize(m_mod_words + 2); |
108 | 7.96M | clear_mem(ws.data(), ws.size()); |
109 | 7.96M | ws[m_mod_words + 1] = t1_neg; |
110 | | |
111 | 7.96M | t1.add(ws.data(), m_mod_words + 2, BigInt::Positive); |
112 | | |
113 | | // Per HAC this step requires at most 2 subtractions |
114 | 7.96M | t1.ct_reduce_below(m_modulus, ws, 2); |
115 | | |
116 | 7.96M | cnd_rev_sub(t1.is_nonzero() && x.is_negative(), t1, m_modulus.data(), m_modulus.size(), ws); |
117 | 7.96M | } |
118 | | |
119 | | } |