diff options
Diffstat (limited to 'comm/third_party/botan/src/lib/math/bigint/big_ops2.cpp')
| -rw-r--r-- | comm/third_party/botan/src/lib/math/bigint/big_ops2.cpp | 314 |
1 files changed, 314 insertions, 0 deletions
diff --git a/comm/third_party/botan/src/lib/math/bigint/big_ops2.cpp b/comm/third_party/botan/src/lib/math/bigint/big_ops2.cpp new file mode 100644 index 0000000000..cc85f5e96d --- /dev/null +++ b/comm/third_party/botan/src/lib/math/bigint/big_ops2.cpp @@ -0,0 +1,314 @@ +/* +* (C) 1999-2007,2018 Jack Lloyd +* 2016 Matthias Gierlings +* +* Botan is released under the Simplified BSD License (see license.txt) +*/ + +#include <botan/bigint.h> +#include <botan/internal/mp_core.h> +#include <botan/internal/bit_ops.h> +#include <algorithm> + +namespace Botan { + +BigInt& BigInt::add(const word y[], size_t y_words, Sign y_sign) + { + const size_t x_sw = sig_words(); + + grow_to(std::max(x_sw, y_words) + 1); + + if(sign() == y_sign) + { + bigint_add2(mutable_data(), size() - 1, y, y_words); + } + else + { + const int32_t relative_size = bigint_cmp(data(), x_sw, y, y_words); + + if(relative_size >= 0) + { + // *this >= y + bigint_sub2(mutable_data(), x_sw, y, y_words); + } + else + { + // *this < y + bigint_sub2_rev(mutable_data(), y, y_words); + } + + //this->sign_fixup(relative_size, y_sign); + if(relative_size < 0) + set_sign(y_sign); + else if(relative_size == 0) + set_sign(Positive); + } + + return (*this); + } + +BigInt& BigInt::mod_add(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) + { + if(this->is_negative() || s.is_negative() || mod.is_negative()) + throw Invalid_Argument("BigInt::mod_add expects all arguments are positive"); + + BOTAN_DEBUG_ASSERT(*this < mod); + BOTAN_DEBUG_ASSERT(s < mod); + + /* + t + s or t + s - p == t - (p - s) + + So first compute ws = p - s + + Then compute t + s and t - ws + + If t - ws does not borrow, then that is the correct valued + */ + + const size_t mod_sw = mod.sig_words(); + BOTAN_ARG_CHECK(mod_sw > 0, "BigInt::mod_add modulus must be positive"); + + this->grow_to(mod_sw); + s.grow_to(mod_sw); + + // First mod_sw for p - s, 2*mod_sw for bigint_addsub workspace + if(ws.size() < 3*mod_sw) + ws.resize(3*mod_sw); + + word borrow = bigint_sub3(&ws[0], mod.data(), mod_sw, s.data(), mod_sw); + BOTAN_DEBUG_ASSERT(borrow == 0); + + // Compute t - ws + borrow = bigint_sub3(&ws[mod_sw], this->data(), mod_sw, &ws[0], mod_sw); + + // Compute t + s + bigint_add3_nc(&ws[mod_sw*2], this->data(), mod_sw, s.data(), mod_sw); + + CT::conditional_copy_mem(borrow, &ws[0], &ws[mod_sw*2], &ws[mod_sw], mod_sw); + set_words(&ws[0], mod_sw); + + return (*this); + } + +BigInt& BigInt::mod_sub(const BigInt& s, const BigInt& mod, secure_vector<word>& ws) + { + if(this->is_negative() || s.is_negative() || mod.is_negative()) + throw Invalid_Argument("BigInt::mod_sub expects all arguments are positive"); + + // We are assuming in this function that *this and s are no more than mod_sw words long + BOTAN_DEBUG_ASSERT(*this < mod); + BOTAN_DEBUG_ASSERT(s < mod); + + const size_t mod_sw = mod.sig_words(); + + this->grow_to(mod_sw); + s.grow_to(mod_sw); + + if(ws.size() < mod_sw) + ws.resize(mod_sw); + + if(mod_sw == 4) + bigint_mod_sub_n<4>(mutable_data(), s.data(), mod.data(), ws.data()); + else if(mod_sw == 6) + bigint_mod_sub_n<6>(mutable_data(), s.data(), mod.data(), ws.data()); + else + bigint_mod_sub(mutable_data(), s.data(), mod.data(), mod_sw, ws.data()); + + return (*this); + } + +BigInt& BigInt::mod_mul(uint8_t y, const BigInt& mod, secure_vector<word>& ws) + { + BOTAN_ARG_CHECK(this->is_negative() == false, "*this must be positive"); + BOTAN_ARG_CHECK(y < 16, "y too large"); + + BOTAN_DEBUG_ASSERT(*this < mod); + + *this *= static_cast<word>(y); + this->reduce_below(mod, ws); + return (*this); + } + +BigInt& BigInt::rev_sub(const word y[], size_t y_sw, secure_vector<word>& ws) + { + if(this->sign() != BigInt::Positive) + throw Invalid_State("BigInt::sub_rev requires this is positive"); + + const size_t x_sw = this->sig_words(); + + ws.resize(std::max(x_sw, y_sw)); + clear_mem(ws.data(), ws.size()); + + const int32_t relative_size = bigint_sub_abs(ws.data(), data(), x_sw, y, y_sw); + + this->cond_flip_sign(relative_size > 0); + this->swap_reg(ws); + + return (*this); + } + +/* +* Multiplication Operator +*/ +BigInt& BigInt::operator*=(const BigInt& y) + { + secure_vector<word> ws; + return this->mul(y, ws); + } + +BigInt& BigInt::mul(const BigInt& y, secure_vector<word>& ws) + { + const size_t x_sw = sig_words(); + const size_t y_sw = y.sig_words(); + set_sign((sign() == y.sign()) ? Positive : Negative); + + if(x_sw == 0 || y_sw == 0) + { + clear(); + set_sign(Positive); + } + else if(x_sw == 1 && y_sw) + { + grow_to(y_sw + 1); + bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0)); + } + else if(y_sw == 1 && x_sw) + { + word carry = bigint_linmul2(mutable_data(), x_sw, y.word_at(0)); + set_word_at(x_sw, carry); + } + else + { + const size_t new_size = x_sw + y_sw + 1; + ws.resize(new_size); + secure_vector<word> z_reg(new_size); + + bigint_mul(z_reg.data(), z_reg.size(), + data(), size(), x_sw, + y.data(), y.size(), y_sw, + ws.data(), ws.size()); + + this->swap_reg(z_reg); + } + + return (*this); + } + +BigInt& BigInt::square(secure_vector<word>& ws) + { + const size_t sw = sig_words(); + + secure_vector<word> z(2*sw); + ws.resize(z.size()); + + bigint_sqr(z.data(), z.size(), + data(), size(), sw, + ws.data(), ws.size()); + + swap_reg(z); + set_sign(BigInt::Positive); + + return (*this); + } + +BigInt& BigInt::operator*=(word y) + { + if(y == 0) + { + clear(); + set_sign(Positive); + } + + const word carry = bigint_linmul2(mutable_data(), size(), y); + set_word_at(size(), carry); + + return (*this); + } + +/* +* Division Operator +*/ +BigInt& BigInt::operator/=(const BigInt& y) + { + if(y.sig_words() == 1 && is_power_of_2(y.word_at(0))) + (*this) >>= (y.bits() - 1); + else + (*this) = (*this) / y; + return (*this); + } + +/* +* Modulo Operator +*/ +BigInt& BigInt::operator%=(const BigInt& mod) + { + return (*this = (*this) % mod); + } + +/* +* Modulo Operator +*/ +word BigInt::operator%=(word mod) + { + if(mod == 0) + throw BigInt::DivideByZero(); + + word remainder = 0; + + if(is_power_of_2(mod)) + { + remainder = (word_at(0) & (mod - 1)); + } + else + { + const size_t sw = sig_words(); + for(size_t i = sw; i > 0; --i) + remainder = bigint_modop(remainder, word_at(i-1), mod); + } + + if(remainder && sign() == BigInt::Negative) + remainder = mod - remainder; + + m_data.set_to_zero(); + m_data.set_word_at(0, remainder); + set_sign(BigInt::Positive); + return remainder; + } + +/* +* Left Shift Operator +*/ +BigInt& BigInt::operator<<=(size_t shift) + { + const size_t shift_words = shift / BOTAN_MP_WORD_BITS; + const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; + const size_t size = sig_words(); + + const size_t bits_free = top_bits_free(); + + const size_t new_size = size + shift_words + (bits_free < shift_bits); + + m_data.grow_to(new_size); + + bigint_shl1(m_data.mutable_data(), new_size, size, shift_words, shift_bits); + + return (*this); + } + +/* +* Right Shift Operator +*/ +BigInt& BigInt::operator>>=(size_t shift) + { + const size_t shift_words = shift / BOTAN_MP_WORD_BITS; + const size_t shift_bits = shift % BOTAN_MP_WORD_BITS; + + bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits); + + if(is_negative() && is_zero()) + set_sign(Positive); + + return (*this); + } + +} |