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