Botan 2.19.5 Crypto and TLS for C&

big_ops2.cpp
Go to the documentation of this file.
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 {
17 const size_t x_sw = sig_words();
18
19 grow_to(std::max(x_sw, y_words) + 1);
20
21 if(sign() == y_sign)
22 {
23 bigint_add2(mutable_data(), size() - 1, y, y_words);
24 }
25 else
26 {
27 const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words);
28
29 if(relative_size >= 0)
30 {
31 // *this >= y
32 bigint_sub2(mutable_data(), x_sw, y, y_words);
33 }
34 else
35 {
36 // *this < y
37 bigint_sub2_rev(mutable_data(), y, y_words);
38 }
39
40 //this->sign_fixup(relative_size, y_sign);
41 if(relative_size < 0)
42 set_sign(y_sign);
43 else if(relative_size == 0)
44 set_sign(Positive);
45 }
46
47 return (*this);
48 }
49
50 BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws)
51 {
52 if(this->is_negative() || s.is_negative() || mod.is_negative())
53 throw Invalid_Argument("BigInt::mod_add expects all arguments are positive");
54
55 BOTAN_DEBUG_ASSERT(*this < mod);
56 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 const size_t mod_sw = mod.sig_words();
69 BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive");
70
71 this->grow_to(mod_sw);
72 s.grow_to(mod_sw);
73
74 // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace
75 if(ws.size() < 3*mod_sw)
76 ws.resize(3*mod_sw);
77
78 word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw);
79 BOTAN_DEBUG_ASSERT(borrow == 0);
80
81 // Compute t - ws
82 borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw);
83
84 // Compute t + s
85 bigint_add3_nc(&ws[mod_sw*2], this->data(), mod_sw, s.data(), mod_sw);
86
87 CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw*2], &ws[mod_sw], mod_sw);
88 set_words(&ws[0], mod_sw);
89
90 return (*this);
91 }
92
93 BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws)
94 {
95 if(this->is_negative() || s.is_negative() || mod.is_negative())
96 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 BOTAN_DEBUG_ASSERT(*this < mod);
100 BOTAN_DEBUG_ASSERT(s < mod);
101
102 const size_t mod_sw = mod.sig_words();
103
104 this->grow_to(mod_sw);
105 s.grow_to(mod_sw);
106
107 if(ws.size() < mod_sw)
108 ws.resize(mod_sw);
109
110 if(mod_sw == 4)
111 bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data());
112 else if(mod_sw == 6)
113 bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data());
114 else
115 bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data());
116
117 return (*this);
118 }
119
120 BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws)
121 {
122 BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive");
123 BOTAN_ARG_CHECK(y < 16, "y too large");
124
125 BOTAN_DEBUG_ASSERT(*this < mod);
126
127 *this *= static_cast<word>(y);
128 this->reduce_below(mod, ws);
129 return (*this);
130 }
131
132 BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws)
133 {
134 if(this->sign() != BigInt::Positive)
135 throw Invalid_State("BigInt::sub_rev requires this is positive");
136
137 const size_t x_sw = this->sig_words();
138
139 ws.resize(std::max(x_sw, y_sw));
140 clear_mem(ws.data(), ws.size());
141
142 const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw);
143
144 this->cond_flip_sign(relative_size > 0);
145 this->swap_reg(ws);
146
147 return (*this);
148 }
149
150/*
151* Multiplication Operator
152*/
153 BigInt& BigInt::operator*=(const BigInt& y)
154 {
155 secure_vector<word> ws;
156 return this->mul(y, ws);
157 }
158
159 BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws)
160 {
161 const size_t x_sw = sig_words();
162 const size_t y_sw = y.sig_words();
163 set_sign((sign() == y.sign()) ? Positive : Negative);
164
165 if(x_sw == 0 || y_sw == 0)
166 {
167 clear();
168 set_sign(Positive);
169 }
170 else if(x_sw == 1 && y_sw)
171 {
172 grow_to(y_sw + 1);
173 bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
174 }
175 else if(y_sw == 1 && x_sw)
176 {
177 word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
178 set_word_at(x_sw, carry);
179 }
180 else
181 {
182 const size_t new_size = x_sw + y_sw + 1;
183 ws.resize(new_size);
184 secure_vector<word> z_reg(new_size);
185
186 bigint_mul(z_reg.data(), z_reg.size(),
187 data(), size(), x_sw,
188 y.data(), y.size(), y_sw,
189 ws.data(), ws.size());
190
191 this->swap_reg(z_reg);
192 }
193
194 return (*this);
195 }
196
197 BigInt& BigInt::square(secure_vector<word>& ws)
198 {
199 const size_t sw = sig_words();
200
201 secure_vector<word> z(2*sw);
202 ws.resize(z.size());
203
204 bigint_sqr(z.data(), z.size(),
205 data(), size(), sw,
206 ws.data(), ws.size());
207
208 swap_reg(z);
209 set_sign(BigInt::Positive);
210
211 return (*this);
212 }
213
214 BigInt& BigInt::operator*=(word y)
215 {
216 if(y == 0)
217 {
218 clear();
219 set_sign(Positive);
220 }
221
222 const word carry = bigint_linmul2(mutable_data(), size(), y);
223 set_word_at(size(), carry);
224
225 return (*this);
226 }
227
228/*
229* Division Operator
230*/
231 BigInt& BigInt::operator/=(const BigInt& y)
232 {
233 if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
234 (*this) >>= (y.bits() - 1);
235 else
236 (*this) = (*this) / y;
237 return (*this);
238 }
239
240/*
241* Modulo Operator
242*/
243 BigInt& BigInt::operator%=(const BigInt& mod)
244 {
245 return (*this = (*this) % mod);
246 }
247
248/*
249* Modulo Operator
250*/
251word BigInt::operator%=(word mod)
252 {
253 if(mod == 0)
254 throw BigInt::DivideByZero();
255
256 word remainder = 0;
257
258 if(is_power_of_2(mod))
259 {
260 remainder = (word_at(0) & (mod - 1));
261 }
262 else
263 {
264 const size_t sw = sig_words();
265 for(size_t i = sw; i > 0; --i)
266 remainder = bigint_modop(remainder, word_at(i-1), mod);
267 }
268
269 if(remainder && sign() == BigInt::Negative)
270 remainder = mod - remainder;
271
272 m_data.set_to_zero();
273 m_data.set_word_at(0, remainder);
274 set_sign(BigInt::Positive);
275 return remainder;
276 }
277
278/*
279* Left Shift Operator
280*/
281 BigInt& BigInt::operator<<=(size_t shift)
282 {
283 const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
284 const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
285 const size_t size = sig_words();
286
287 const size_t bits_free = top_bits_free();
288
289 const size_t new_size = size + shift_words + (bits_free < shift_bits);
290
291 m_data.grow_to(new_size);
292
293 bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits);
294
295 return (*this);
296 }
297
298/*
299* Right Shift Operator
300*/
301 BigInt& BigInt::operator>>=(size_t shift)
302 {
303 const size_t shift_words = shift / BOTAN_MP_WORD_BITS;
304 const size_t shift_bits = shift % BOTAN_MP_WORD_BITS;
305
306 bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);
307
308 if(is_negative() && is_zero())
309 set_sign(Positive);
310
311 return (*this);
312 }
313
314}
BOTAN_DEBUG_ASSERT
#define BOTAN_DEBUG_ASSERT(expr)
Definition: assert.h:123
BOTAN_ARG_CHECK
#define BOTAN_ARG_CHECK(expr, msg)
Definition: assert.h:37
Botan::BigInt::DivideByZero
Definition: bigint.h:44
Botan::BigInt
Definition: bigint.h:25
Botan::BigInt::operator>>=
BigInt & operator>>=(size_t shift)
Definition: big_ops2.cpp:301
Botan::BigInt::mod_mul
BigInt & mod_mul(uint8_t y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:120
Botan::BigInt::sig_words
size_t sig_words() const
Definition: bigint.h:592
Botan::BigInt::operator/=
BigInt & operator/=(const BigInt &y)
Definition: big_ops2.cpp:231
Botan::BigInt::set_word_at
void set_word_at(size_t i, word w)
Definition: bigint.h:519
Botan::BigInt::mutable_data
word * mutable_data()
Definition: bigint.h:620
Botan::BigInt::size
size_t size() const
Definition: bigint.h:586
Botan::BigInt::rev_sub
BigInt & rev_sub(const word y[], size_t y_words, secure_vector< word > &ws)
Definition: big_ops2.cpp:132
Botan::BigInt::grow_to
void grow_to(size_t n) const
Definition: bigint.h:642
Botan::BigInt::set_words
void set_words(const word w[], size_t len)
Definition: bigint.h:524
Botan::BigInt::operator*=
BigInt & operator*=(const BigInt &y)
Definition: big_ops2.cpp:153
Botan::BigInt::top_bits_free
size_t top_bits_free() const
Definition: bigint.cpp:294
Botan::BigInt::mod_add
BigInt & mod_add(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:50
Botan::BigInt::data
const word * data() const
Definition: bigint.h:626
Botan::BigInt::word_at
word word_at(size_t n) const
Definition: bigint.h:514
Botan::BigInt::mul
BigInt & mul(const BigInt &y, secure_vector< word > &ws)
Definition: big_ops2.cpp:159
Botan::BigInt::cond_flip_sign
void cond_flip_sign(bool predicate)
Definition: bigint.cpp:517
Botan::BigInt::mod_sub
BigInt & mod_sub(const BigInt &y, const BigInt &mod, secure_vector< word > &ws)
Definition: big_ops2.cpp:93
Botan::BigInt::bits
size_t bits() const
Definition: bigint.cpp:304
Botan::BigInt::operator%=
BigInt & operator%=(const BigInt &y)
Definition: big_ops2.cpp:243
Botan::BigInt::clear
void clear()
Definition: bigint.h:372
Botan::BigInt::sign
Sign sign() const
Definition: bigint.h:545
Botan::BigInt::operator<<=
BigInt & operator<<=(size_t shift)
Definition: big_ops2.cpp:281
Botan::BigInt::add
BigInt & add(const word y[], size_t y_words, Sign sign)
Definition: big_ops2.cpp:15
Botan::BigInt::Sign
Sign
Definition: bigint.h:35
Botan::BigInt::Positive
@ Positive
Definition: bigint.h:35
Botan::BigInt::Negative
@ Negative
Definition: bigint.h:35
Botan::BigInt::is_zero
bool is_zero() const
Definition: bigint.h:427
Botan::BigInt::reduce_below
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
Definition: bigint.cpp:344
Botan::BigInt::square
BigInt & square(secure_vector< word > &ws)
Definition: big_ops2.cpp:197
Botan::BigInt::is_negative
bool is_negative() const
Definition: bigint.h:533
Botan::BigInt::swap_reg
void swap_reg(secure_vector< word > &reg)
Definition: bigint.h:173
Botan::BigInt::set_sign
void set_sign(Sign sign)
Definition: bigint.h:569
Botan::Invalid_Argument
Definition: exceptn.h:137
Botan::Invalid_State
Definition: exceptn.h:216
Botan::CT::conditional_copy_mem
Mask< T > conditional_copy_mem(T cnd, T *to, const T *from0, const T *from1, size_t elems)
Definition: ct_utils.h:363
Botan
Definition: alg_id.cpp:13
Botan::bigint_sub2_rev
void bigint_sub2_rev(word x[], const word y[], size_t y_size)
Definition: mp_core.h:324
Botan::bigint_shr1
void bigint_shr1(word x[], size_t x_size, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:427
Botan::bigint_linmul3
void bigint_linmul3(word z[], const word x[], size_t x_size, word y)
Definition: mp_core.h:504
Botan::bigint_linmul2
word BOTAN_WARN_UNUSED_RESULT bigint_linmul2(word x[], size_t x_size, word y)
Definition: mp_core.h:489
Botan::bigint_sub2
word bigint_sub2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:300
Botan::bigint_shl1
void bigint_shl1(word x[], size_t x_size, size_t x_words, size_t word_shift, size_t bit_shift)
Definition: mp_core.h:409
Botan::bigint_sqr
void bigint_sqr(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:357
Botan::bigint_sub_abs
CT::Mask< word > bigint_sub_abs(word z[], const word x[], const word y[], size_t N, word ws[])
Definition: mp_core.h:377
Botan::bigint_mul
void bigint_mul(word z[], size_t z_size, const word x[], size_t x_size, size_t x_sw, const word y[], size_t y_size, size_t y_sw, word workspace[], size_t ws_size)
Definition: mp_karat.cpp:298
Botan::carry
void carry(int64_t &h0, int64_t &h1)
Definition: ed25519_internal.h:32
Botan::bigint_add2
void bigint_add2(word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:280
Botan::bigint_add3_nc
word bigint_add3_nc(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:250
Botan::bigint_modop
word bigint_modop(word n1, word n0, word d)
Definition: mp_core.h:755
Botan::bigint_cmp
int32_t bigint_cmp(const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:525
Botan::secure_vector
std::vector< T, secure_allocator< T > > secure_vector
Definition: secmem.h:65
Botan::is_power_of_2
constexpr bool is_power_of_2(T arg)
Definition: bit_ops.h:43
Botan::clear_mem
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
Botan::bigint_sub3
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)
Definition: mp_core.h:342
Botan::bigint_mod_sub
void bigint_mod_sub(word t[], const word s[], const word mod[], size_t mod_sw, word ws[])
Definition: mp_core.h:687