/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 | 13.2M | { |
17 | 13.2M | const size_t x_sw = sig_words(); |
18 | 13.2M | |
19 | 13.2M | grow_to(std::max(x_sw, y_words) + 1); |
20 | 13.2M | |
21 | 13.2M | if(sign() == y_sign) |
22 | 9.36M | { |
23 | 9.36M | bigint_add2(mutable_data(), size() - 1, y, y_words); |
24 | 9.36M | } |
25 | 3.89M | else |
26 | 3.89M | { |
27 | 3.89M | const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words); |
28 | 3.89M | |
29 | 3.89M | if(relative_size >= 0) |
30 | 3.29M | { |
31 | 3.29M | // *this >= y |
32 | 3.29M | bigint_sub2(mutable_data(), x_sw, y, y_words); |
33 | 3.29M | } |
34 | 603k | else |
35 | 603k | { |
36 | 603k | // *this < y |
37 | 603k | bigint_sub2_rev(mutable_data(), y, y_words); |
38 | 603k | } |
39 | 3.89M | |
40 | 3.89M | //this->sign_fixup(relative_size, y_sign); |
41 | 3.89M | if(relative_size < 0) |
42 | 603k | set_sign(y_sign); |
43 | 3.29M | else if(relative_size == 0) |
44 | 4.09k | set_sign(Positive); |
45 | 3.89M | } |
46 | 13.2M | |
47 | 13.2M | return (*this); |
48 | 13.2M | } |
49 | | |
50 | | BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) |
51 | 11.8M | { |
52 | 11.8M | if(this->is_negative() || s.is_negative() || mod.is_negative()) |
53 | 0 | throw Invalid_Argument("BigInt::mod_add expects all arguments are positive"); |
54 | 11.8M | |
55 | 11.8M | BOTAN_DEBUG_ASSERT(*this < mod); |
56 | 11.8M | BOTAN_DEBUG_ASSERT(s < mod); |
57 | 11.8M | |
58 | 11.8M | /* |
59 | 11.8M | t + s or t + s - p == t - (p - s) |
60 | 11.8M | |
61 | 11.8M | So first compute ws = p - s |
62 | 11.8M | |
63 | 11.8M | Then compute t + s and t - ws |
64 | 11.8M | |
65 | 11.8M | If t - ws does not borrow, then that is the correct valued |
66 | 11.8M | */ |
67 | 11.8M | |
68 | 11.8M | const size_t mod_sw = mod.sig_words(); |
69 | 11.8M | BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive"); |
70 | 11.8M | |
71 | 11.8M | this->grow_to(mod_sw); |
72 | 11.8M | s.grow_to(mod_sw); |
73 | 11.8M | |
74 | 11.8M | // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace |
75 | 11.8M | if(ws.size() < 3*mod_sw) |
76 | 6.34M | ws.resize(3*mod_sw); |
77 | 11.8M | |
78 | 11.8M | word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw); |
79 | 11.8M | BOTAN_DEBUG_ASSERT(borrow == 0); |
80 | 11.8M | |
81 | 11.8M | // Compute t - ws |
82 | 11.8M | borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw); |
83 | 11.8M | |
84 | 11.8M | // Compute t + s |
85 | 11.8M | bigint_add3_nc(&ws[mod_sw*2], this->data(), mod_sw, s.data(), mod_sw); |
86 | 11.8M | |
87 | 11.8M | CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw*2], &ws[mod_sw], mod_sw); |
88 | 11.8M | set_words(&ws[0], mod_sw); |
89 | 11.8M | |
90 | 11.8M | return (*this); |
91 | 11.8M | } |
92 | | |
93 | | BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) |
94 | 115M | { |
95 | 115M | if(this->is_negative() || s.is_negative() || mod.is_negative()) |
96 | 0 | throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive"); |
97 | 115M | |
98 | 115M | // We are assuming in this function that *this and s are no more than mod_sw words long |
99 | 115M | BOTAN_DEBUG_ASSERT(*this < mod); |
100 | 115M | BOTAN_DEBUG_ASSERT(s < mod); |
101 | 115M | |
102 | 115M | const size_t mod_sw = mod.sig_words(); |
103 | 115M | |
104 | 115M | this->grow_to(mod_sw); |
105 | 115M | s.grow_to(mod_sw); |
106 | 115M | |
107 | 115M | if(ws.size() < mod_sw) |
108 | 0 | ws.resize(mod_sw); |
109 | 115M | |
110 | 115M | if(mod_sw == 4) |
111 | 25.7M | bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data()); |
112 | 89.3M | else if(mod_sw == 6) |
113 | 24.3M | bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data()); |
114 | 65.0M | else |
115 | 65.0M | bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data()); |
116 | 115M | |
117 | 115M | return (*this); |
118 | 115M | } |
119 | | |
120 | | BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) |
121 | 47.7M | { |
122 | 47.7M | BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive"); |
123 | 47.7M | BOTAN_ARG_CHECK(y < 16, "y too large"); |
124 | 47.7M | |
125 | 47.7M | BOTAN_DEBUG_ASSERT(*this < mod); |
126 | 47.7M | |
127 | 47.7M | *this *= static_cast<word>(y); |
128 | 47.7M | this->reduce_below(mod, ws); |
129 | 47.7M | return (*this); |
130 | 47.7M | } |
131 | | |
132 | | BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) |
133 | 5.81M | { |
134 | 5.81M | if(this->sign() != BigInt::Positive) |
135 | 0 | throw Invalid_State("BigInt::sub_rev requires this is positive"); |
136 | 5.81M | |
137 | 5.81M | const size_t x_sw = this->sig_words(); |
138 | 5.81M | |
139 | 5.81M | ws.resize(std::max(x_sw, y_sw)); |
140 | 5.81M | clear_mem(ws.data(), ws.size()); |
141 | 5.81M | |
142 | 5.81M | const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw); |
143 | 5.81M | |
144 | 5.81M | this->cond_flip_sign(relative_size > 0); |
145 | 5.81M | this->swap_reg(ws); |
146 | 5.81M | |
147 | 5.81M | return (*this); |
148 | 5.81M | } |
149 | | |
150 | | /* |
151 | | * Multiplication Operator |
152 | | */ |
153 | | BigInt& BigInt::operator*=(const BigInt& y) |
154 | 476 | { |
155 | 476 | secure_vector<word> ws; |
156 | 476 | return this->mul(y, ws); |
157 | 476 | } |
158 | | |
159 | | BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) |
160 | 11.6M | { |
161 | 11.6M | const size_t x_sw = sig_words(); |
162 | 11.6M | const size_t y_sw = y.sig_words(); |
163 | 11.6M | set_sign((sign() == y.sign()) ? Positive : Negative); |
164 | 11.6M | |
165 | 11.6M | if(x_sw == 0 || y_sw == 0) |
166 | 1.11M | { |
167 | 1.11M | clear(); |
168 | 1.11M | set_sign(Positive); |
169 | 1.11M | } |
170 | 10.5M | else if(x_sw == 1 && y_sw) |
171 | 2.01M | { |
172 | 2.01M | grow_to(y_sw + 1); |
173 | 2.01M | bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0)); |
174 | 2.01M | } |
175 | 8.50M | else if(y_sw == 1 && x_sw) |
176 | 172 | { |
177 | 172 | word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0)); |
178 | 172 | set_word_at(x_sw, carry); |
179 | 172 | } |
180 | 8.50M | else |
181 | 8.50M | { |
182 | 8.50M | const size_t new_size = x_sw + y_sw + 1; |
183 | 8.50M | ws.resize(new_size); |
184 | 8.50M | secure_vector<word> z_reg(new_size); |
185 | 8.50M | |
186 | 8.50M | bigint_mul(z_reg.data(), z_reg.size(), |
187 | 8.50M | data(), size(), x_sw, |
188 | 8.50M | y.data(), y.size(), y_sw, |
189 | 8.50M | ws.data(), ws.size()); |
190 | 8.50M | |
191 | 8.50M | this->swap_reg(z_reg); |
192 | 8.50M | } |
193 | 11.6M | |
194 | 11.6M | return (*this); |
195 | 11.6M | } |
196 | | |
197 | | BigInt& BigInt::square(secure_vector<word>& ws) |
198 | 3.66M | { |
199 | 3.66M | const size_t sw = sig_words(); |
200 | 3.66M | |
201 | 3.66M | secure_vector<word> z(2*sw); |
202 | 3.66M | ws.resize(z.size()); |
203 | 3.66M | |
204 | 3.66M | bigint_sqr(z.data(), z.size(), |
205 | 3.66M | data(), size(), sw, |
206 | 3.66M | ws.data(), ws.size()); |
207 | 3.66M | |
208 | 3.66M | swap_reg(z); |
209 | 3.66M | set_sign(BigInt::Positive); |
210 | 3.66M | |
211 | 3.66M | return (*this); |
212 | 3.66M | } |
213 | | |
214 | | BigInt& BigInt::operator*=(word y) |
215 | 191M | { |
216 | 191M | if(y == 0) |
217 | 0 | { |
218 | 0 | clear(); |
219 | 0 | set_sign(Positive); |
220 | 0 | } |
221 | 191M | |
222 | 191M | const word carry = bigint_linmul2(mutable_data(), size(), y); |
223 | 191M | set_word_at(size(), carry); |
224 | 191M | |
225 | 191M | return (*this); |
226 | 191M | } |
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.28M | { |
245 | 2.28M | return (*this = (*this) % mod); |
246 | 2.28M | } |
247 | | |
248 | | /* |
249 | | * Modulo Operator |
250 | | */ |
251 | | word BigInt::operator%=(word mod) |
252 | 0 | { |
253 | 0 | if(mod == 0) |
254 | 0 | throw BigInt::DivideByZero(); |
255 | 0 | |
256 | 0 | word remainder = 0; |
257 | 0 |
|
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 | 0 |
|
269 | 0 | if(remainder && sign() == BigInt::Negative) |
270 | 0 | remainder = mod - remainder; |
271 | 0 |
|
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.55M | { |
283 | 4.55M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
284 | 4.55M | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
285 | 4.55M | const size_t size = sig_words(); |
286 | 4.55M | |
287 | 4.55M | const size_t bits_free = top_bits_free(); |
288 | 4.55M | |
289 | 4.55M | const size_t new_size = size + shift_words + (bits_free < shift_bits); |
290 | 4.55M | |
291 | 4.55M | m_data.grow_to(new_size); |
292 | 4.55M | |
293 | 4.55M | bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits); |
294 | 4.55M | |
295 | 4.55M | return (*this); |
296 | 4.55M | } |
297 | | |
298 | | /* |
299 | | * Right Shift Operator |
300 | | */ |
301 | | BigInt& BigInt::operator>>=(size_t shift) |
302 | 23.4M | { |
303 | 23.4M | const size_t shift_words = shift / BOTAN_MP_WORD_BITS; |
304 | 23.4M | const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; |
305 | 23.4M | |
306 | 23.4M | bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits); |
307 | 23.4M | |
308 | 23.4M | if(is_negative() && is_zero()) |
309 | 0 | set_sign(Positive); |
310 | 23.4M | |
311 | 23.4M | return (*this); |
312 | 23.4M | } |
313 | | |
314 | | } |