/src/botan/src/lib/math/bigint/divide.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Division Algorithms |
3 | | * (C) 1999-2007,2012,2018,2021 Jack Lloyd |
4 | | * |
5 | | * Botan is released under the Simplified BSD License (see license.txt) |
6 | | */ |
7 | | |
8 | | #include <botan/internal/divide.h> |
9 | | |
10 | | #include <botan/internal/bit_ops.h> |
11 | | #include <botan/internal/ct_utils.h> |
12 | | #include <botan/internal/mp_core.h> |
13 | | |
14 | | namespace Botan { |
15 | | |
16 | | namespace { |
17 | | |
18 | | /* |
19 | | * Handle signed operands, if necessary |
20 | | */ |
21 | 128k | void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r) { |
22 | 128k | q.cond_flip_sign(x.sign() != y.sign()); |
23 | | |
24 | 128k | if(x.is_negative() && r.is_nonzero()) { |
25 | 0 | q -= 1; |
26 | 0 | r = y.abs() - r; |
27 | 0 | } |
28 | 128k | } |
29 | | |
30 | 256k | inline bool division_check(word q, word y2, word y1, word x3, word x2, word x1) { |
31 | | /* |
32 | | Compute (y3,y2,y1) = (y2,y1) * q |
33 | | and return true if (y3,y2,y1) > (x3,x2,x1) |
34 | | */ |
35 | | |
36 | 256k | word y3 = 0; |
37 | 256k | y1 = word_madd2(q, y1, &y3); |
38 | 256k | y2 = word_madd2(q, y2, &y3); |
39 | | |
40 | 256k | const word x[3] = {x1, x2, x3}; |
41 | 256k | const word y[3] = {y1, y2, y3}; |
42 | | |
43 | 256k | return bigint_ct_is_lt(x, 3, y, 3).is_set(); |
44 | 256k | } |
45 | | |
46 | | } // namespace |
47 | | |
48 | 854 | void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) { |
49 | 854 | if(y.is_zero()) { |
50 | 0 | throw Invalid_Argument("ct_divide: cannot divide by zero"); |
51 | 0 | } |
52 | | |
53 | 854 | const size_t x_words = x.sig_words(); |
54 | 854 | const size_t y_words = y.sig_words(); |
55 | | |
56 | 854 | const size_t x_bits = x.bits(); |
57 | | |
58 | 854 | BigInt q = BigInt::with_capacity(x_words); |
59 | 854 | BigInt r = BigInt::with_capacity(y_words); |
60 | 854 | BigInt t = BigInt::with_capacity(y_words); // a temporary |
61 | | |
62 | 657k | for(size_t i = 0; i != x_bits; ++i) { |
63 | 656k | const size_t b = x_bits - 1 - i; |
64 | 656k | const bool x_b = x.get_bit(b); |
65 | | |
66 | 656k | r *= 2; |
67 | 656k | r.conditionally_set_bit(0, x_b); |
68 | | |
69 | 656k | const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0; |
70 | | |
71 | 656k | q.conditionally_set_bit(b, r_gte_y); |
72 | 656k | r.ct_cond_swap(r_gte_y, t); |
73 | 656k | } |
74 | | |
75 | 854 | sign_fixup(x, y, q, r); |
76 | 854 | r_out = r; |
77 | 854 | q_out = q; |
78 | 854 | } |
79 | | |
80 | 152k | void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) { |
81 | 152k | if(y == 0) { |
82 | 0 | throw Invalid_Argument("ct_divide_word: cannot divide by zero"); |
83 | 0 | } |
84 | | |
85 | 152k | const size_t x_words = x.sig_words(); |
86 | 152k | const size_t x_bits = x.bits(); |
87 | | |
88 | 152k | BigInt q = BigInt::with_capacity(x_words); |
89 | 152k | word r = 0; |
90 | | |
91 | 29.5M | for(size_t i = 0; i != x_bits; ++i) { |
92 | 29.3M | const size_t b = x_bits - 1 - i; |
93 | 29.3M | const bool x_b = x.get_bit(b); |
94 | | |
95 | 29.3M | const auto r_carry = CT::Mask<word>::expand(r >> (BOTAN_MP_WORD_BITS - 1)); |
96 | | |
97 | 29.3M | r *= 2; |
98 | 29.3M | r += x_b; |
99 | | |
100 | 29.3M | const auto r_gte_y = CT::Mask<word>::is_gte(r, y) | r_carry; |
101 | 29.3M | q.conditionally_set_bit(b, r_gte_y.is_set()); |
102 | 29.3M | r = r_gte_y.select(r - y, r); |
103 | 29.3M | } |
104 | | |
105 | 152k | if(x.is_negative()) { |
106 | 0 | q.flip_sign(); |
107 | 0 | if(r != 0) { |
108 | 0 | --q; |
109 | 0 | r = y - r; |
110 | 0 | } |
111 | 0 | } |
112 | | |
113 | 152k | r_out = r; |
114 | 152k | q_out = q; |
115 | 152k | } |
116 | | |
117 | 0 | BigInt ct_modulo(const BigInt& x, const BigInt& y) { |
118 | 0 | if(y.is_negative() || y.is_zero()) { |
119 | 0 | throw Invalid_Argument("ct_modulo requires y > 0"); |
120 | 0 | } |
121 | | |
122 | 0 | const size_t y_words = y.sig_words(); |
123 | |
|
124 | 0 | const size_t x_bits = x.bits(); |
125 | |
|
126 | 0 | BigInt r = BigInt::with_capacity(y_words); |
127 | 0 | BigInt t = BigInt::with_capacity(y_words); |
128 | |
|
129 | 0 | for(size_t i = 0; i != x_bits; ++i) { |
130 | 0 | const size_t b = x_bits - 1 - i; |
131 | 0 | const bool x_b = x.get_bit(b); |
132 | |
|
133 | 0 | r *= 2; |
134 | 0 | r.conditionally_set_bit(0, x_b); |
135 | |
|
136 | 0 | const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0; |
137 | |
|
138 | 0 | r.ct_cond_swap(r_gte_y, t); |
139 | 0 | } |
140 | |
|
141 | 0 | if(x.is_negative()) { |
142 | 0 | if(r.is_nonzero()) { |
143 | 0 | r = y - r; |
144 | 0 | } |
145 | 0 | } |
146 | |
|
147 | 0 | return r; |
148 | 0 | } |
149 | | |
150 | | /* |
151 | | * Solve x = q * y + r |
152 | | * |
153 | | * See Handbook of Applied Cryptography section 14.2.5 |
154 | | */ |
155 | 127k | void vartime_divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) { |
156 | 127k | if(y_arg.is_zero()) { |
157 | 0 | throw Invalid_Argument("vartime_divide: cannot divide by zero"); |
158 | 0 | } |
159 | | |
160 | 127k | const size_t y_words = y_arg.sig_words(); |
161 | | |
162 | 127k | BOTAN_ASSERT_NOMSG(y_words > 0); |
163 | | |
164 | 127k | BigInt y = y_arg; |
165 | | |
166 | 127k | BigInt r = x; |
167 | 127k | BigInt q = BigInt::zero(); |
168 | 127k | secure_vector<word> ws; |
169 | | |
170 | 127k | r.set_sign(BigInt::Positive); |
171 | 127k | y.set_sign(BigInt::Positive); |
172 | | |
173 | | // Calculate shifts needed to normalize y with high bit set |
174 | 127k | const size_t shifts = y.top_bits_free(); |
175 | | |
176 | 127k | y <<= shifts; |
177 | 127k | r <<= shifts; |
178 | | |
179 | | // we know y has not changed size, since we only shifted up to set high bit |
180 | 127k | const size_t t = y_words - 1; |
181 | 127k | const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however |
182 | | |
183 | 127k | BOTAN_ASSERT_NOMSG(n >= t); |
184 | | |
185 | 127k | q.grow_to(n - t + 1); |
186 | | |
187 | 127k | word* q_words = q.mutable_data(); |
188 | | |
189 | 127k | BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n - t)); |
190 | | |
191 | | // Set q_{n-t} to number of times r > shifted_y |
192 | 127k | q_words[n - t] = r.reduce_below(shifted_y, ws); |
193 | | |
194 | 127k | const word y_t0 = y.word_at(t); |
195 | 127k | const word y_t1 = y.word_at(t - 1); |
196 | 127k | BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS - 1)) == 1); |
197 | | |
198 | 255k | for(size_t j = n; j != t; --j) { |
199 | 128k | const word x_j0 = r.word_at(j); |
200 | 128k | const word x_j1 = r.word_at(j - 1); |
201 | 128k | const word x_j2 = r.word_at(j - 2); |
202 | | |
203 | 128k | word qjt = bigint_divop(x_j0, x_j1, y_t0); |
204 | | |
205 | 128k | qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(MP_WORD_MAX, qjt); |
206 | | |
207 | | // Per HAC 14.23, this operation is required at most twice |
208 | 128k | qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2); |
209 | 128k | qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2); |
210 | 128k | BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false); |
211 | | |
212 | 128k | shifted_y >>= BOTAN_MP_WORD_BITS; |
213 | | // Now shifted_y == y << (BOTAN_MP_WORD_BITS * (j-t-1)) |
214 | | |
215 | | // TODO this sequence could be better |
216 | 128k | r -= qjt * shifted_y; |
217 | 128k | qjt -= r.is_negative(); |
218 | 128k | r += static_cast<word>(r.is_negative()) * shifted_y; |
219 | | |
220 | 128k | q_words[j - t - 1] = qjt; |
221 | 128k | } |
222 | | |
223 | 127k | r >>= shifts; |
224 | | |
225 | 127k | sign_fixup(x, y_arg, q, r); |
226 | | |
227 | 127k | r_out = r; |
228 | 127k | q_out = q; |
229 | 127k | } |
230 | | |
231 | | } // namespace Botan |