/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 | 19.0M | { |
17 | 19.0M | const size_t x_sw = sig_words(); |
18 | | |
19 | 19.0M | grow_to(std::max(x_sw, y_words) + 1); |
20 | | |
21 | 19.0M | if(sign() == y_sign) |
22 | 13.5M | { |
23 | 13.5M | bigint_add2(mutable_data(), size() - 1, y, y_words); |
24 | 13.5M | } |
25 | 5.47M | else |
26 | 5.47M | { |
27 | 5.47M | const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words); |
28 | | |
29 | 5.47M | if(relative_size >= 0) |
30 | 4.53M | { |
31 | | // *this >= y |
32 | 4.53M | bigint_sub2(mutable_data(), x_sw, y, y_words); |
33 | 4.53M | } |
34 | 940k | else |
35 | 940k | { |
36 | | // *this < y |
37 | 940k | bigint_sub2_rev(mutable_data(), y, y_words); |
38 | 940k | } |
39 | | |
40 | | //this->sign_fixup(relative_size, y_sign); |
41 | 5.47M | if(relative_size < 0) |
42 | 940k | set_sign(y_sign); |
43 | 4.53M | else if(relative_size == 0) |
44 | 8.10k | set_sign(Positive); |
45 | 5.47M | } |
46 | | |
47 | 19.0M | return (*this); |
48 | 19.0M | } |
49 | | |
50 | | BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) |
51 | 18.9M | { |
52 | 18.9M | 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 | 18.9M | BOTAN_DEBUG_ASSERT(*this < mod); |
56 | 18.9M | 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 | 18.9M | const size_t mod_sw = mod.sig_words(); |
69 | 18.9M | BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive"); |
70 | | |
71 | 18.9M | this->grow_to(mod_sw); |
72 | 18.9M | s.grow_to(mod_sw); |
73 | | |
74 | | // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace |
75 | 18.9M | if(ws.size() < 3*mod_sw) |
76 | 9.23M | ws.resize(3*mod_sw); |
77 | | |
78 | 18.9M | word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw); |
79 | 18.9M | BOTAN_DEBUG_ASSERT(borrow == 0); |
80 | | |
81 | | // Compute t - ws |
82 | 18.9M | borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw); |
83 | | |
84 | | // Compute t + s |
85 | 18.9M | bigint_add3_nc(&ws[mod_sw*2], this->data(), mod_sw, s.data(), mod_sw); |
86 | | |
87 | 18.9M | CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw*2], &ws[mod_sw], mod_sw); |
88 | 18.9M | set_words(&ws[0], mod_sw); |
89 | | |
90 | 18.9M | return (*this); |
91 | 18.9M | } |
92 | | |
93 | | BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) |
94 | 177M | { |
95 | 177M | 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 | 177M | BOTAN_DEBUG_ASSERT(*this < mod); |
100 | 177M | BOTAN_DEBUG_ASSERT(s < mod); |
101 | | |
102 | 177M | const size_t mod_sw = mod.sig_words(); |
103 | | |
104 | 177M | this->grow_to(mod_sw); |
105 | 177M | s.grow_to(mod_sw); |
106 | | |
107 | 177M | if(ws.size() < mod_sw) |
108 | 0 | ws.resize(mod_sw); |
109 | | |
110 | 177M | if(mod_sw == 4) |
111 | 48.0M | bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data()); |
112 | 129M | else if(mod_sw == 6) |
113 | 48.1M | bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data()); |
114 | 81.4M | else |
115 | 81.4M | bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data()); |
116 | | |
117 | 177M | return (*this); |
118 | 177M | } |
119 | | |
120 | | BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) |
121 | 76.5M | { |
122 | 76.5M | BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive"); |
123 | 76.5M | BOTAN_ARG_CHECK(y < 16, "y too large"); |
124 | | |
125 | 76.5M | BOTAN_DEBUG_ASSERT(*this < mod); |
126 | | |
127 | 76.5M | *this *= static_cast<word>(y); |
128 | 76.5M | this->reduce_below(mod, ws); |
129 | 76.5M | return (*this); |
130 | 76.5M | } |
131 | | |
132 | | BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) |
133 | 8.54M | { |
134 | 8.54M | if(this->sign() != BigInt::Positive) |
135 | 0 | throw Invalid_State("BigInt::sub_rev requires this is positive"); |
136 | | |
137 | 8.54M | const size_t x_sw = this->sig_words(); |
138 | | |
139 | 8.54M | ws.resize(std::max(x_sw, y_sw)); |
140 | 8.54M | clear_mem(ws.data(), ws.size()); |
141 | | |
142 | 8.54M | const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw); |
143 | | |
144 | 8.54M | this->cond_flip_sign(relative_size > 0); |
145 | 8.54M | this->swap_reg(ws); |
146 | | |
147 | 8.54M | return (*this); |
148 | 8.54M | } |
149 | | |
150 | | /* |
151 | | * Multiplication Operator |
152 | | */ |
153 | | BigInt& BigInt::operator*=(const BigInt& y) |
154 | 1.18k | { |
155 | 1.18k | secure_vector<word> ws; |
156 | 1.18k | return this->mul(y, ws); |
157 | 1.18k | } |
158 | | |
159 | | BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) |
160 | 17.0M | { |
161 | 17.0M | const size_t x_sw = sig_words(); |
162 | 17.0M | const size_t y_sw = y.sig_words(); |
163 | 17.0M | set_sign((sign() == y.sign()) ? Positive : Negative); |
164 | | |
165 | 17.0M | if(x_sw == 0 || y_sw == 0) |
166 | 1.68M | { |
167 | 1.68M | clear(); |
168 | 1.68M | set_sign(Positive); |
169 | 1.68M | } |
170 | 15.3M | else if(x_sw == 1 && y_sw) |
171 | 2.92M | { |
172 | 2.92M | grow_to(y_sw + 1); |
173 | 2.92M | bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0)); |
174 | 2.92M | } |
175 | 12.4M | else if(y_sw == 1 && x_sw) |
176 | 506 | { |
177 | 506 | word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0)); |
178 | 506 | set_word_at(x_sw, carry); |
179 | 506 | } |
180 | 12.4M | else |
181 | 12.4M | { |
182 | 12.4M | const size_t new_size = x_sw + y_sw + 1; |
183 | 12.4M | ws.resize(new_size); |
184 | 12.4M | secure_vector<word> z_reg(new_size); |
185 | | |
186 | 12.4M | bigint_mul(z_reg.data(), z_reg.size(), |
187 | 12.4M | data(), size(), x_sw, |
188 | 12.4M | y.data(), y.size(), y_sw, |
189 | 12.4M | ws.data(), ws.size()); |
190 | | |
191 | 12.4M | this->swap_reg(z_reg); |
192 | 12.4M | } |
193 | | |
194 | 17.0M | return (*this); |
195 | 17.0M | } |
196 | | |
197 | | BigInt& BigInt::square(secure_vector<word>& ws) |
198 | 5.38M | { |
199 | 5.38M | const size_t sw = sig_words(); |
200 | | |
201 | 5.38M | secure_vector<word> z(2*sw); |
202 | 5.38M | ws.resize(z.size()); |
203 | | |
204 | 5.38M | bigint_sqr(z.data(), z.size(), |
205 | 5.38M | data(), size(), sw, |
206 | 5.38M | ws.data(), ws.size()); |
207 | | |
208 | 5.38M | swap_reg(z); |
209 | 5.38M | set_sign(BigInt::Positive); |
210 | | |
211 | 5.38M | return (*this); |
212 | 5.38M | } |
213 | | |
214 | | BigInt& BigInt::operator*=(word y) |
215 | 132M | { |
216 | 132M | if(y == 0) |
217 | 0 | { |
218 | 0 | clear(); |
219 | 0 | set_sign(Positive); |
220 | 0 | } |
221 | | |
222 | 132M | const word carry = bigint_linmul2(mutable_data(), size(), y); |
223 | 132M | set_word_at(size(), carry); |
224 | | |
225 | 132M | return (*this); |
226 | 132M | } |
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 | 3.78M | { |
245 | 3.78M | return (*this = (*this) % mod); |
246 | 3.78M | } |
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 | 6.30M | { |
283 | 6.30M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
284 | 6.30M | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
285 | 6.30M | const size_t size = sig_words(); |
286 | | |
287 | 6.30M | const size_t bits_free = top_bits_free(); |
288 | | |
289 | 6.30M | const size_t new_size = size + shift_words + (bits_free < shift_bits); |
290 | | |
291 | 6.30M | m_data.grow_to(new_size); |
292 | | |
293 | 6.30M | bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits); |
294 | | |
295 | 6.30M | return (*this); |
296 | 6.30M | } |
297 | | |
298 | | /* |
299 | | * Right Shift Operator |
300 | | */ |
301 | | BigInt& BigInt::operator>>=(size_t shift) |
302 | 35.2M | { |
303 | 35.2M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
304 | 35.2M | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
305 | | |
306 | 35.2M | bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits); |
307 | | |
308 | 35.2M | if(is_negative() && is_zero()) |
309 | 0 | set_sign(Positive); |
310 | | |
311 | 35.2M | return (*this); |
312 | 35.2M | } |
313 | | |
314 | | } |