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