/src/botan/src/lib/math/bigint/big_ops2.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * (C) 1999-2007,2018 Jack Lloyd |
3 | | * 2016 Matthias Gierlings |
4 | | * |
5 | | * Botan is released under the Simplified BSD License (see license.txt) |
6 | | */ |
7 | | |
8 | | #include <botan/bigint.h> |
9 | | #include <botan/internal/mp_core.h> |
10 | | #include <botan/internal/bit_ops.h> |
11 | | #include <algorithm> |
12 | | |
13 | | namespace Botan { |
14 | | |
15 | | BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign) |
16 | 15.5M | { |
17 | 15.5M | const size_t x_sw = sig_words(); |
18 | | |
19 | 15.5M | grow_to(std::max(x_sw, y_words) + 1); |
20 | | |
21 | 15.5M | if(sign() == y_sign) |
22 | 11.4M | { |
23 | 11.4M | bigint_add2(mutable_data(), size() - 1, y, y_words); |
24 | 11.4M | } |
25 | 4.11M | else |
26 | 4.11M | { |
27 | 4.11M | const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words); |
28 | | |
29 | 4.11M | if(relative_size >= 0) |
30 | 3.40M | { |
31 | | // *this >= y |
32 | 3.40M | bigint_sub2(mutable_data(), x_sw, y, y_words); |
33 | 3.40M | } |
34 | 712k | else |
35 | 712k | { |
36 | | // *this < y |
37 | 712k | bigint_sub2_rev(mutable_data(), y, y_words); |
38 | 712k | } |
39 | | |
40 | | //this->sign_fixup(relative_size, y_sign); |
41 | 4.11M | if(relative_size < 0) |
42 | 712k | set_sign(y_sign); |
43 | 3.40M | else if(relative_size == 0) |
44 | 2.66k | set_sign(Positive); |
45 | 4.11M | } |
46 | | |
47 | 15.5M | return (*this); |
48 | 15.5M | } |
49 | | |
50 | | BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) |
51 | 14.4M | { |
52 | 14.4M | if(this->is_negative() || s.is_negative() || mod.is_negative()) |
53 | 0 | throw Invalid_Argument("BigInt::mod_add expects all arguments are positive"); |
54 | | |
55 | 14.4M | BOTAN_DEBUG_ASSERT(*this < mod); |
56 | 14.4M | BOTAN_DEBUG_ASSERT(s < mod); |
57 | | |
58 | | /* |
59 | | t + s or t + s - p == t - (p - s) |
60 | | |
61 | | So first compute ws = p - s |
62 | | |
63 | | Then compute t + s and t - ws |
64 | | |
65 | | If t - ws does not borrow, then that is the correct valued |
66 | | */ |
67 | | |
68 | 14.4M | const size_t mod_sw = mod.sig_words(); |
69 | 14.4M | BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive"); |
70 | | |
71 | 14.4M | this->grow_to(mod_sw); |
72 | 14.4M | s.grow_to(mod_sw); |
73 | | |
74 | | // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace |
75 | 14.4M | if(ws.size() < 3*mod_sw) |
76 | 7.83M | ws.resize(3*mod_sw); |
77 | | |
78 | 14.4M | word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw); |
79 | 14.4M | BOTAN_DEBUG_ASSERT(borrow == 0); |
80 | | |
81 | | // Compute t - ws |
82 | 14.4M | borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw); |
83 | | |
84 | | // Compute t + s |
85 | 14.4M | bigint_add3_nc(&ws[mod_sw*2], this->data(), mod_sw, s.data(), mod_sw); |
86 | | |
87 | 14.4M | CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw*2], &ws[mod_sw], mod_sw); |
88 | 14.4M | set_words(&ws[0], mod_sw); |
89 | | |
90 | 14.4M | return (*this); |
91 | 14.4M | } |
92 | | |
93 | | BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) |
94 | 139M | { |
95 | 139M | if(this->is_negative() || s.is_negative() || mod.is_negative()) |
96 | 0 | throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive"); |
97 | | |
98 | | // We are assuming in this function that *this and s are no more than mod_sw words long |
99 | 139M | BOTAN_DEBUG_ASSERT(*this < mod); |
100 | 139M | BOTAN_DEBUG_ASSERT(s < mod); |
101 | | |
102 | 139M | const size_t mod_sw = mod.sig_words(); |
103 | | |
104 | 139M | this->grow_to(mod_sw); |
105 | 139M | s.grow_to(mod_sw); |
106 | | |
107 | 139M | if(ws.size() < mod_sw) |
108 | 0 | ws.resize(mod_sw); |
109 | | |
110 | 139M | if(mod_sw == 4) |
111 | 29.3M | bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data()); |
112 | 110M | else if(mod_sw == 6) |
113 | 29.1M | bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data()); |
114 | 81.5M | else |
115 | 81.5M | bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data()); |
116 | | |
117 | 139M | return (*this); |
118 | 139M | } |
119 | | |
120 | | BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) |
121 | 58.2M | { |
122 | 58.2M | BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive"); |
123 | 58.2M | BOTAN_ARG_CHECK(y < 16, "y too large"); |
124 | | |
125 | 58.2M | BOTAN_DEBUG_ASSERT(*this < mod); |
126 | | |
127 | 58.2M | *this *= static_cast<word>(y); |
128 | 58.2M | this->reduce_below(mod, ws); |
129 | 58.2M | return (*this); |
130 | 58.2M | } |
131 | | |
132 | | BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) |
133 | 7.70M | { |
134 | 7.70M | if(this->sign() != BigInt::Positive) |
135 | 0 | throw Invalid_State("BigInt::sub_rev requires this is positive"); |
136 | | |
137 | 7.70M | const size_t x_sw = this->sig_words(); |
138 | | |
139 | 7.70M | ws.resize(std::max(x_sw, y_sw)); |
140 | 7.70M | clear_mem(ws.data(), ws.size()); |
141 | | |
142 | 7.70M | const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw); |
143 | | |
144 | 7.70M | this->cond_flip_sign(relative_size > 0); |
145 | 7.70M | this->swap_reg(ws); |
146 | | |
147 | 7.70M | return (*this); |
148 | 7.70M | } |
149 | | |
150 | | /* |
151 | | * Multiplication Operator |
152 | | */ |
153 | | BigInt& BigInt::operator*=(const BigInt& y) |
154 | 561 | { |
155 | 561 | secure_vector<word> ws; |
156 | 561 | return this->mul(y, ws); |
157 | 561 | } |
158 | | |
159 | | BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) |
160 | 15.4M | { |
161 | 15.4M | const size_t x_sw = sig_words(); |
162 | 15.4M | const size_t y_sw = y.sig_words(); |
163 | 15.4M | set_sign((sign() == y.sign()) ? Positive : Negative); |
164 | | |
165 | 15.4M | if(x_sw == 0 || y_sw == 0) |
166 | 1.30M | { |
167 | 1.30M | clear(); |
168 | 1.30M | set_sign(Positive); |
169 | 1.30M | } |
170 | 14.1M | else if(x_sw == 1 && y_sw) |
171 | 2.55M | { |
172 | 2.55M | grow_to(y_sw + 1); |
173 | 2.55M | bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0)); |
174 | 2.55M | } |
175 | 11.5M | else if(y_sw == 1 && x_sw) |
176 | 237 | { |
177 | 237 | word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0)); |
178 | 237 | set_word_at(x_sw, carry); |
179 | 237 | } |
180 | 11.5M | else |
181 | 11.5M | { |
182 | 11.5M | const size_t new_size = x_sw + y_sw + 1; |
183 | 11.5M | ws.resize(new_size); |
184 | 11.5M | secure_vector<word> z_reg(new_size); |
185 | | |
186 | 11.5M | bigint_mul(z_reg.data(), z_reg.size(), |
187 | 11.5M | data(), size(), x_sw, |
188 | 11.5M | y.data(), y.size(), y_sw, |
189 | 11.5M | ws.data(), ws.size()); |
190 | | |
191 | 11.5M | this->swap_reg(z_reg); |
192 | 11.5M | } |
193 | | |
194 | 15.4M | return (*this); |
195 | 15.4M | } |
196 | | |
197 | | BigInt& BigInt::square(secure_vector<word>& ws) |
198 | 4.96M | { |
199 | 4.96M | const size_t sw = sig_words(); |
200 | | |
201 | 4.96M | secure_vector<word> z(2*sw); |
202 | 4.96M | ws.resize(z.size()); |
203 | | |
204 | 4.96M | bigint_sqr(z.data(), z.size(), |
205 | 4.96M | data(), size(), sw, |
206 | 4.96M | ws.data(), ws.size()); |
207 | | |
208 | 4.96M | swap_reg(z); |
209 | 4.96M | set_sign(BigInt::Positive); |
210 | | |
211 | 4.96M | return (*this); |
212 | 4.96M | } |
213 | | |
214 | | BigInt& BigInt::operator*=(word y) |
215 | 229M | { |
216 | 229M | if(y == 0) |
217 | 0 | { |
218 | 0 | clear(); |
219 | 0 | set_sign(Positive); |
220 | 0 | } |
221 | | |
222 | 229M | const word carry = bigint_linmul2(mutable_data(), size(), y); |
223 | 229M | set_word_at(size(), carry); |
224 | | |
225 | 229M | return (*this); |
226 | 229M | } |
227 | | |
228 | | /* |
229 | | * Division Operator |
230 | | */ |
231 | | BigInt& BigInt::operator/=(const BigInt& y) |
232 | 0 | { |
233 | 0 | if(y.sig_words() == 1 && is_power_of_2(y.word_at(0))) |
234 | 0 | (*this) >>= (y.bits() - 1); |
235 | 0 | else |
236 | 0 | (*this) = (*this) / y; |
237 | 0 | return (*this); |
238 | 0 | } |
239 | | |
240 | | /* |
241 | | * Modulo Operator |
242 | | */ |
243 | | BigInt& BigInt::operator%=(const BigInt& mod) |
244 | 2.80M | { |
245 | 2.80M | return (*this = (*this) % mod); |
246 | 2.80M | } |
247 | | |
248 | | /* |
249 | | * Modulo Operator |
250 | | */ |
251 | | word BigInt::operator%=(word mod) |
252 | 0 | { |
253 | 0 | if(mod == 0) |
254 | 0 | throw Invalid_Argument("BigInt::operator%= divide by zero"); |
255 | | |
256 | 0 | word remainder = 0; |
257 | |
|
258 | 0 | if(is_power_of_2(mod)) |
259 | 0 | { |
260 | 0 | remainder = (word_at(0) & (mod - 1)); |
261 | 0 | } |
262 | 0 | else |
263 | 0 | { |
264 | 0 | const size_t sw = sig_words(); |
265 | 0 | for(size_t i = sw; i > 0; --i) |
266 | 0 | remainder = bigint_modop(remainder, word_at(i-1), mod); |
267 | 0 | } |
268 | |
|
269 | 0 | if(remainder && sign() == BigInt::Negative) |
270 | 0 | remainder = mod - remainder; |
271 | |
|
272 | 0 | m_data.set_to_zero(); |
273 | 0 | m_data.set_word_at(0, remainder); |
274 | 0 | set_sign(BigInt::Positive); |
275 | 0 | return remainder; |
276 | 0 | } |
277 | | |
278 | | /* |
279 | | * Left Shift Operator |
280 | | */ |
281 | | BigInt& BigInt::operator<<=(size_t shift) |
282 | 4.61M | { |
283 | 4.61M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
284 | 4.61M | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
285 | 4.61M | const size_t size = sig_words(); |
286 | | |
287 | 4.61M | const size_t bits_free = top_bits_free(); |
288 | | |
289 | 4.61M | const size_t new_size = size + shift_words + (bits_free < shift_bits); |
290 | | |
291 | 4.61M | m_data.grow_to(new_size); |
292 | | |
293 | 4.61M | bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits); |
294 | | |
295 | 4.61M | return (*this); |
296 | 4.61M | } |
297 | | |
298 | | /* |
299 | | * Right Shift Operator |
300 | | */ |
301 | | BigInt& BigInt::operator>>=(size_t shift) |
302 | 28.5M | { |
303 | 28.5M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
304 | 28.5M | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
305 | | |
306 | 28.5M | bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits); |
307 | | |
308 | 28.5M | if(is_negative() && is_zero()) |
309 | 0 | set_sign(Positive); |
310 | | |
311 | 28.5M | return (*this); |
312 | 28.5M | } |
313 | | |
314 | | } |