/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 | 21.3M | { |
17 | 21.3M | const size_t x_sw = sig_words(); |
18 | | |
19 | 21.3M | grow_to(std::max(x_sw, y_words) + 1); |
20 | | |
21 | 21.3M | if(sign() == y_sign) |
22 | 16.2M | { |
23 | 16.2M | bigint_add2(mutable_data(), size() - 1, y, y_words); |
24 | 16.2M | } |
25 | 5.13M | else |
26 | 5.13M | { |
27 | 5.13M | const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words); |
28 | | |
29 | 5.13M | if(relative_size >= 0) |
30 | 4.25M | { |
31 | | // *this >= y |
32 | 4.25M | bigint_sub2(mutable_data(), x_sw, y, y_words); |
33 | 4.25M | } |
34 | 881k | else |
35 | 881k | { |
36 | | // *this < y |
37 | 881k | bigint_sub2_rev(mutable_data(), y, y_words); |
38 | 881k | } |
39 | | |
40 | | //this->sign_fixup(relative_size, y_sign); |
41 | 5.13M | if(relative_size < 0) |
42 | 881k | set_sign(y_sign); |
43 | 4.25M | else if(relative_size == 0) |
44 | 7.45k | set_sign(Positive); |
45 | 5.13M | } |
46 | | |
47 | 21.3M | return (*this); |
48 | 21.3M | } |
49 | | |
50 | | BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) |
51 | 17.7M | { |
52 | 17.7M | 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 | 17.7M | BOTAN_DEBUG_ASSERT(*this < mod); |
56 | 17.7M | 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 | 17.7M | const size_t mod_sw = mod.sig_words(); |
69 | 17.7M | BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive"); |
70 | | |
71 | 17.7M | this->grow_to(mod_sw); |
72 | 17.7M | s.grow_to(mod_sw); |
73 | | |
74 | | // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace |
75 | 17.7M | if(ws.size() < 3*mod_sw) |
76 | 10.3M | ws.resize(3*mod_sw); |
77 | | |
78 | 17.7M | word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw); |
79 | 17.7M | BOTAN_DEBUG_ASSERT(borrow == 0); |
80 | 17.7M | BOTAN_UNUSED(borrow); |
81 | | |
82 | | // Compute t - ws |
83 | 17.7M | borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw); |
84 | | |
85 | | // Compute t + s |
86 | 17.7M | bigint_add3_nc(&ws[mod_sw*2], this->data(), mod_sw, s.data(), mod_sw); |
87 | | |
88 | 17.7M | CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw*2], &ws[mod_sw], mod_sw); |
89 | 17.7M | set_words(&ws[0], mod_sw); |
90 | | |
91 | 17.7M | return (*this); |
92 | 17.7M | } |
93 | | |
94 | | BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) |
95 | 174M | { |
96 | 174M | if(this->is_negative() || s.is_negative() || mod.is_negative()) |
97 | 0 | throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive"); |
98 | | |
99 | | // We are assuming in this function that *this and s are no more than mod_sw words long |
100 | 174M | BOTAN_DEBUG_ASSERT(*this < mod); |
101 | 174M | BOTAN_DEBUG_ASSERT(s < mod); |
102 | | |
103 | 174M | const size_t mod_sw = mod.sig_words(); |
104 | | |
105 | 174M | this->grow_to(mod_sw); |
106 | 174M | s.grow_to(mod_sw); |
107 | | |
108 | 174M | if(ws.size() < mod_sw) |
109 | 0 | ws.resize(mod_sw); |
110 | | |
111 | 174M | if(mod_sw == 4) |
112 | 48.3M | bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data()); |
113 | 126M | else if(mod_sw == 6) |
114 | 44.0M | bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data()); |
115 | 82.4M | else |
116 | 82.4M | bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data()); |
117 | | |
118 | 174M | return (*this); |
119 | 174M | } |
120 | | |
121 | | BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) |
122 | 72.6M | { |
123 | 72.6M | BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive"); |
124 | 72.6M | BOTAN_ARG_CHECK(y < 16, "y too large"); |
125 | | |
126 | 72.6M | BOTAN_DEBUG_ASSERT(*this < mod); |
127 | | |
128 | 72.6M | *this *= static_cast<word>(y); |
129 | 72.6M | this->reduce_below(mod, ws); |
130 | 72.6M | return (*this); |
131 | 72.6M | } |
132 | | |
133 | | BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) |
134 | 11.4M | { |
135 | 11.4M | if(this->sign() != BigInt::Positive) |
136 | 0 | throw Invalid_State("BigInt::sub_rev requires this is positive"); |
137 | | |
138 | 11.4M | const size_t x_sw = this->sig_words(); |
139 | | |
140 | 11.4M | ws.resize(std::max(x_sw, y_sw)); |
141 | 11.4M | clear_mem(ws.data(), ws.size()); |
142 | | |
143 | 11.4M | const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw); |
144 | | |
145 | 11.4M | this->cond_flip_sign(relative_size > 0); |
146 | 11.4M | this->swap_reg(ws); |
147 | | |
148 | 11.4M | return (*this); |
149 | 11.4M | } |
150 | | |
151 | | /* |
152 | | * Multiplication Operator |
153 | | */ |
154 | | BigInt& BigInt::operator*=(const BigInt& y) |
155 | 1.06k | { |
156 | 1.06k | secure_vector<word> ws; |
157 | 1.06k | return this->mul(y, ws); |
158 | 1.06k | } |
159 | | |
160 | | BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) |
161 | 22.9M | { |
162 | 22.9M | const size_t x_sw = sig_words(); |
163 | 22.9M | const size_t y_sw = y.sig_words(); |
164 | 22.9M | set_sign((sign() == y.sign()) ? Positive : Negative); |
165 | | |
166 | 22.9M | if(x_sw == 0 || y_sw == 0) |
167 | 2.54M | { |
168 | 2.54M | clear(); |
169 | 2.54M | set_sign(Positive); |
170 | 2.54M | } |
171 | 20.4M | else if(x_sw == 1 && y_sw) |
172 | 5.44M | { |
173 | 5.44M | grow_to(y_sw + 1); |
174 | 5.44M | bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0)); |
175 | 5.44M | } |
176 | 14.9M | else if(y_sw == 1 && x_sw) |
177 | 500 | { |
178 | 500 | word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0)); |
179 | 500 | set_word_at(x_sw, carry); |
180 | 500 | } |
181 | 14.9M | else |
182 | 14.9M | { |
183 | 14.9M | const size_t new_size = x_sw + y_sw + 1; |
184 | 14.9M | ws.resize(new_size); |
185 | 14.9M | secure_vector<word> z_reg(new_size); |
186 | | |
187 | 14.9M | bigint_mul(z_reg.data(), z_reg.size(), |
188 | 14.9M | data(), size(), x_sw, |
189 | 14.9M | y.data(), y.size(), y_sw, |
190 | 14.9M | ws.data(), ws.size()); |
191 | | |
192 | 14.9M | this->swap_reg(z_reg); |
193 | 14.9M | } |
194 | | |
195 | 22.9M | return (*this); |
196 | 22.9M | } |
197 | | |
198 | | BigInt& BigInt::square(secure_vector<word>& ws) |
199 | 6.31M | { |
200 | 6.31M | const size_t sw = sig_words(); |
201 | | |
202 | 6.31M | secure_vector<word> z(2*sw); |
203 | 6.31M | ws.resize(z.size()); |
204 | | |
205 | 6.31M | bigint_sqr(z.data(), z.size(), |
206 | 6.31M | data(), size(), sw, |
207 | 6.31M | ws.data(), ws.size()); |
208 | | |
209 | 6.31M | swap_reg(z); |
210 | 6.31M | set_sign(BigInt::Positive); |
211 | | |
212 | 6.31M | return (*this); |
213 | 6.31M | } |
214 | | |
215 | | BigInt& BigInt::operator*=(word y) |
216 | 135M | { |
217 | 135M | if(y == 0) |
218 | 0 | { |
219 | 0 | clear(); |
220 | 0 | set_sign(Positive); |
221 | 0 | } |
222 | | |
223 | 135M | const word carry = bigint_linmul2(mutable_data(), size(), y); |
224 | 135M | set_word_at(size(), carry); |
225 | | |
226 | 135M | return (*this); |
227 | 135M | } |
228 | | |
229 | | /* |
230 | | * Division Operator |
231 | | */ |
232 | | BigInt& BigInt::operator/=(const BigInt& y) |
233 | 0 | { |
234 | 0 | if(y.sig_words() == 1 && is_power_of_2(y.word_at(0))) |
235 | 0 | (*this) >>= (y.bits() - 1); |
236 | 0 | else |
237 | 0 | (*this) = (*this) / y; |
238 | 0 | return (*this); |
239 | 0 | } |
240 | | |
241 | | /* |
242 | | * Modulo Operator |
243 | | */ |
244 | | BigInt& BigInt::operator%=(const BigInt& mod) |
245 | 3.57M | { |
246 | 3.57M | return (*this = (*this) % mod); |
247 | 3.57M | } |
248 | | |
249 | | /* |
250 | | * Modulo Operator |
251 | | */ |
252 | | word BigInt::operator%=(word mod) |
253 | 0 | { |
254 | 0 | if(mod == 0) |
255 | 0 | throw Invalid_Argument("BigInt::operator%= divide by zero"); |
256 | | |
257 | 0 | word remainder = 0; |
258 | |
|
259 | 0 | if(is_power_of_2(mod)) |
260 | 0 | { |
261 | 0 | remainder = (word_at(0) & (mod - 1)); |
262 | 0 | } |
263 | 0 | else |
264 | 0 | { |
265 | 0 | const size_t sw = sig_words(); |
266 | 0 | for(size_t i = sw; i > 0; --i) |
267 | 0 | remainder = bigint_modop(remainder, word_at(i-1), mod); |
268 | 0 | } |
269 | |
|
270 | 0 | if(remainder && sign() == BigInt::Negative) |
271 | 0 | remainder = mod - remainder; |
272 | |
|
273 | 0 | m_data.set_to_zero(); |
274 | 0 | m_data.set_word_at(0, remainder); |
275 | 0 | set_sign(BigInt::Positive); |
276 | 0 | return remainder; |
277 | 0 | } |
278 | | |
279 | | /* |
280 | | * Left Shift Operator |
281 | | */ |
282 | | BigInt& BigInt::operator<<=(size_t shift) |
283 | 5.91M | { |
284 | 5.91M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
285 | 5.91M | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
286 | 5.91M | const size_t size = sig_words(); |
287 | | |
288 | 5.91M | const size_t bits_free = top_bits_free(); |
289 | | |
290 | 5.91M | const size_t new_size = size + shift_words + (bits_free < shift_bits); |
291 | | |
292 | 5.91M | m_data.grow_to(new_size); |
293 | | |
294 | 5.91M | bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits); |
295 | | |
296 | 5.91M | return (*this); |
297 | 5.91M | } |
298 | | |
299 | | /* |
300 | | * Right Shift Operator |
301 | | */ |
302 | | BigInt& BigInt::operator>>=(size_t shift) |
303 | 41.2M | { |
304 | 41.2M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
305 | 41.2M | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
306 | | |
307 | 41.2M | bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits); |
308 | | |
309 | 41.2M | if(is_negative() && is_zero()) |
310 | 0 | set_sign(Positive); |
311 | | |
312 | 41.2M | return (*this); |
313 | 41.2M | } |
314 | | |
315 | | } |