diff options
-rw-r--r-- | src/lib/cert/x509/x509_ca.cpp | 1 | ||||
-rw-r--r-- | src/lib/cert/x509/x509_ca.h | 1 | ||||
-rw-r--r-- | src/lib/cert/x509/x509self.cpp | 1 | ||||
-rw-r--r-- | src/lib/math/bigint/big_ops2.cpp | 6 | ||||
-rw-r--r-- | src/lib/math/bigint/big_ops3.cpp | 5 | ||||
-rw-r--r-- | src/lib/math/ec_gfp/curve_gfp.cpp | 19 | ||||
-rw-r--r-- | src/lib/math/mp/mp_core.h | 13 | ||||
-rw-r--r-- | src/lib/math/mp/mp_karat.cpp | 58 | ||||
-rw-r--r-- | src/lib/math/mp/mp_monty.cpp | 25 | ||||
-rw-r--r-- | src/lib/math/numbertheory/mp_numth.cpp | 16 | ||||
-rw-r--r-- | src/lib/math/numbertheory/powm_mnt.cpp | 28 | ||||
-rw-r--r-- | src/lib/pubkey/curve25519/donna.cpp | 76 |
12 files changed, 114 insertions, 135 deletions
diff --git a/src/lib/cert/x509/x509_ca.cpp b/src/lib/cert/x509/x509_ca.cpp index 3f7af77f5..02f77c8f6 100644 --- a/src/lib/cert/x509/x509_ca.cpp +++ b/src/lib/cert/x509/x509_ca.cpp @@ -1,6 +1,7 @@ /* * X.509 Certificate Authority * (C) 1999-2010 Jack Lloyd +* 2016 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) */ diff --git a/src/lib/cert/x509/x509_ca.h b/src/lib/cert/x509/x509_ca.h index 8cedb9db9..17e534cfd 100644 --- a/src/lib/cert/x509/x509_ca.h +++ b/src/lib/cert/x509/x509_ca.h @@ -1,6 +1,7 @@ /* * X.509 Certificate Authority * (C) 1999-2008 Jack Lloyd +* 2016 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) */ diff --git a/src/lib/cert/x509/x509self.cpp b/src/lib/cert/x509/x509self.cpp index 62f9fc370..636b9fbb6 100644 --- a/src/lib/cert/x509/x509self.cpp +++ b/src/lib/cert/x509/x509self.cpp @@ -1,6 +1,7 @@ /* * PKCS #10/Self Signed Cert Creation * (C) 1999-2008 Jack Lloyd +* 2016 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) */ diff --git a/src/lib/math/bigint/big_ops2.cpp b/src/lib/math/bigint/big_ops2.cpp index 9a3408247..6e234f036 100644 --- a/src/lib/math/bigint/big_ops2.cpp +++ b/src/lib/math/bigint/big_ops2.cpp @@ -1,6 +1,7 @@ /* * BigInt Assignment Operators * (C) 1999-2007 Jack Lloyd +* 2016 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -118,10 +119,7 @@ BigInt& BigInt::operator*=(const BigInt& y) secure_vector<word> z(data(), data() + x_sw); secure_vector<word> workspace(size()); - - bigint_mul(mutable_data(), size(), workspace.data(), - z.data(), z.size(), x_sw, - y.data(), y.size(), y_sw); + bigint_mul(*this, BigInt(*this), y, workspace.data()); } return (*this); diff --git a/src/lib/math/bigint/big_ops3.cpp b/src/lib/math/bigint/big_ops3.cpp index 6cf837020..24927b4fc 100644 --- a/src/lib/math/bigint/big_ops3.cpp +++ b/src/lib/math/bigint/big_ops3.cpp @@ -1,6 +1,7 @@ /* * BigInt Binary Operators * (C) 1999-2007 Jack Lloyd +* 2016 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -93,9 +94,7 @@ BigInt operator*(const BigInt& x, const BigInt& y) else if(x_sw && y_sw) { secure_vector<word> workspace(z.size()); - bigint_mul(z.mutable_data(), z.size(), workspace.data(), - x.data(), x.size(), x_sw, - y.data(), y.size(), y_sw); + bigint_mul(z, x, y, workspace.data()); } if(x_sw && y_sw && x.sign() != y.sign()) diff --git a/src/lib/math/ec_gfp/curve_gfp.cpp b/src/lib/math/ec_gfp/curve_gfp.cpp index 9bf2191c6..96593e601 100644 --- a/src/lib/math/ec_gfp/curve_gfp.cpp +++ b/src/lib/math/ec_gfp/curve_gfp.cpp @@ -1,6 +1,7 @@ /* * Elliptic curves over GF(p) Montgomery Representation * (C) 2014,2015 Jack Lloyd +* 2016 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -80,20 +81,14 @@ void CurveGFp_Montgomery::curve_mul(BigInt& z, const BigInt& x, const BigInt& y, return; } - const size_t x_sw = x.sig_words(); - const size_t y_sw = y.sig_words(); - const size_t output_size = 2*m_p_words + 1; ws.resize(2*(m_p_words+2)); z.grow_to(output_size); z.clear(); - bigint_monty_mul(z.mutable_data(), output_size, - x.data(), x.size(), x_sw, - y.data(), y.size(), y_sw, - m_p.data(), m_p_words, m_p_dash, - ws.data()); + bigint_monty_mul(z, x, y, m_p.data(), m_p_words, m_p_dash, ws.data()); + } void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x, @@ -115,9 +110,7 @@ void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x, z.grow_to(output_size); z.clear(); - bigint_monty_sqr(z.mutable_data(), output_size, - x.data(), x.size(), x_sw, - m_p.data(), m_p_words, m_p_dash, + bigint_monty_sqr(z, x, m_p.data(), m_p_words, m_p_dash, ws.data()); } @@ -174,9 +167,7 @@ void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y, z.grow_to(output_size); z.clear(); - bigint_mul(z.mutable_data(), output_size, ws.data(), - x.data(), x.size(), x.sig_words(), - y.data(), y.size(), y.sig_words()); + bigint_mul(z, x, y, ws.data()); this->redc(z, ws); } diff --git a/src/lib/math/mp/mp_core.h b/src/lib/math/mp/mp_core.h index 73f13742c..c4ce005ba 100644 --- a/src/lib/math/mp/mp_core.h +++ b/src/lib/math/mp/mp_core.h @@ -2,6 +2,7 @@ * MPI Algorithms * (C) 1999-2010 Jack Lloyd * 2006 Luca Piccarreta +* 2016 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -9,6 +10,7 @@ #ifndef BOTAN_MP_CORE_OPS_H__ #define BOTAN_MP_CORE_OPS_H__ +#include <botan/bigint.h> #include <botan/mp_types.h> namespace Botan { @@ -134,17 +136,14 @@ void bigint_monty_redc(word z[], /* * Montgomery Multiplication */ -void bigint_monty_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, +void bigint_monty_mul(BigInt& z, const BigInt& x, const BigInt& y, const word p[], size_t p_size, word p_dash, word workspace[]); /* * Montgomery Squaring */ -void bigint_monty_sqr(word z[], size_t z_size, - const word x[], size_t x_size, size_t x_sw, +void bigint_monty_sqr(BigInt& z, const BigInt& x, const word p[], size_t p_size, word p_dash, word workspace[]); @@ -182,9 +181,7 @@ void bigint_comba_sqr16(word out[32], const word in[16]); /* * High Level Multiplication/Squaring Interfaces */ -void bigint_mul(word z[], size_t z_size, word workspace[], - const word x[], size_t x_size, size_t x_sw, - const word y[], size_t y_size, size_t y_sw); +void bigint_mul(BigInt& z, const BigInt& x, const BigInt& y, word workspace[]); void bigint_sqr(word z[], size_t z_size, word workspace[], const word x[], size_t x_size, size_t x_sw); diff --git a/src/lib/math/mp/mp_karat.cpp b/src/lib/math/mp/mp_karat.cpp index 9135fdd6a..7a763e2a9 100644 --- a/src/lib/math/mp/mp_karat.cpp +++ b/src/lib/math/mp/mp_karat.cpp @@ -1,6 +1,7 @@ /* * Multiplication and Squaring * (C) 1999-2010 Jack Lloyd +* 2016 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -252,60 +253,55 @@ size_t karatsuba_size(size_t z_size, size_t x_size, size_t x_sw) /* * Multiplication Algorithm Dispatcher */ -void bigint_mul(word z[], size_t z_size, word workspace[], - const word x[], size_t x_size, size_t x_sw, - const word y[], size_t y_size, size_t y_sw) +void bigint_mul(BigInt& z, const BigInt& x, const BigInt& y, word workspace[]) { - // checking that z_size >= x_sw + y_sw without overflow - BOTAN_ASSERT(z_size > x_sw && z_size > y_sw && z_size-x_sw >= y_sw, "Output size is sufficient"); - - if(x_sw == 1) + if(x.sig_words() == 1) { - bigint_linmul3(z, y, y_sw, x[0]); + bigint_linmul3(z.mutable_data(), y.data(), y.sig_words(), x.data()[0]); } - else if(y_sw == 1) + else if(y.sig_words() == 1) { - bigint_linmul3(z, x, x_sw, y[0]); + bigint_linmul3(z.mutable_data(), x.data(), x.sig_words(), y.data()[0]); } - else if(x_sw <= 4 && x_size >= 4 && - y_sw <= 4 && y_size >= 4 && z_size >= 8) + else if(x.sig_words() <= 4 && x.size() >= 4 && + y.sig_words() <= 4 && y.size() >= 4 && z.size() >= 8) { - bigint_comba_mul4(z, x, y); + bigint_comba_mul4(z.mutable_data(), x.data(), y.data()); } - else if(x_sw <= 6 && x_size >= 6 && - y_sw <= 6 && y_size >= 6 && z_size >= 12) + else if(x.sig_words() <= 6 && x.size() >= 6 && + y.sig_words() <= 6 && y.size() >= 6 && z.size() >= 12) { - bigint_comba_mul6(z, x, y); + bigint_comba_mul6(z.mutable_data(), x.data(), y.data()); } - else if(x_sw <= 8 && x_size >= 8 && - y_sw <= 8 && y_size >= 8 && z_size >= 16) + else if(x.sig_words() <= 8 && x.size() >= 8 && + y.sig_words() <= 8 && y.size() >= 8 && z.size() >= 16) { - bigint_comba_mul8(z, x, y); + bigint_comba_mul8(z.mutable_data(), x.data(), y.data()); } - else if(x_sw <= 9 && x_size >= 9 && - y_sw <= 9 && y_size >= 9 && z_size >= 18) + else if(x.sig_words() <= 9 && x.size() >= 9 && + y.sig_words() <= 9 && y.size() >= 9 && z.size() >= 18) { - bigint_comba_mul9(z, x, y); + bigint_comba_mul9(z.mutable_data(), x.data(), y.data()); } - else if(x_sw <= 16 && x_size >= 16 && - y_sw <= 16 && y_size >= 16 && z_size >= 32) + else if(x.sig_words() <= 16 && x.size() >= 16 && + y.sig_words() <= 16 && y.size() >= 16 && z.size() >= 32) { - bigint_comba_mul16(z, x, y); + bigint_comba_mul16(z.mutable_data(), x.data(), y.data()); } - else if(x_sw < KARATSUBA_MULTIPLY_THRESHOLD || - y_sw < KARATSUBA_MULTIPLY_THRESHOLD || + else if(x.sig_words() < KARATSUBA_MULTIPLY_THRESHOLD || + y.sig_words() < KARATSUBA_MULTIPLY_THRESHOLD || !workspace) { - basecase_mul(z, x, x_sw, y, y_sw); + basecase_mul(z.mutable_data(), x.data(), x.sig_words(), y.data(), y.sig_words()); } else { - const size_t N = karatsuba_size(z_size, x_size, x_sw, y_size, y_sw); + const size_t N = karatsuba_size(z.size(), x.size(), x.sig_words(), y.size(), y.sig_words()); if(N) - karatsuba_mul(z, x, y, N, workspace); + karatsuba_mul(z.mutable_data(), x.data(), y.data(), N, workspace); else - basecase_mul(z, x, x_sw, y, y_sw); + basecase_mul(z.mutable_data(), x.data(), x.sig_words(), y.data(), y.sig_words()); } } diff --git a/src/lib/math/mp/mp_monty.cpp b/src/lib/math/mp/mp_monty.cpp index 7e427b540..88b5de715 100644 --- a/src/lib/math/mp/mp_monty.cpp +++ b/src/lib/math/mp/mp_monty.cpp @@ -2,10 +2,12 @@ * Montgomery Reduction * (C) 1999-2011 Jack Lloyd * 2006 Luca Piccarreta +* 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/mp_madd.h> #include <botan/internal/mp_asmi.h> @@ -92,30 +94,25 @@ void bigint_monty_redc(word z[], BOTAN_ASSERT(borrow == 0 || borrow == 1, "Expected borrow"); } -void bigint_monty_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, +void bigint_monty_mul(BigInt& z, const BigInt& x, const BigInt& y, const word p[], size_t p_size, word p_dash, word ws[]) { - bigint_mul(&z[0], z_size, &ws[0], - &x[0], x_size, x_sw, - &y[0], y_size, y_sw); + bigint_mul(z, x, y, &ws[0]); - bigint_monty_redc(&z[0], + bigint_monty_redc(z.mutable_data(), &p[0], p_size, p_dash, &ws[0]); + } -void bigint_monty_sqr(word z[], size_t z_size, - const word x[], size_t x_size, size_t x_sw, - const word p[], size_t p_size, word p_dash, - word ws[]) +void bigint_monty_sqr(BigInt& z, const BigInt& x, const word p[], + size_t p_size, word p_dash, word ws[]) { - bigint_sqr(&z[0], z_size, &ws[0], - &x[0], x_size, x_sw); + bigint_sqr(z.mutable_data(), z.size(), &ws[0], + x.data(), x.size(), x.sig_words()); - bigint_monty_redc(&z[0], + bigint_monty_redc(z.mutable_data(), &p[0], p_size, p_dash, &ws[0]); } diff --git a/src/lib/math/numbertheory/mp_numth.cpp b/src/lib/math/numbertheory/mp_numth.cpp index 3373b9ee7..d78d21128 100644 --- a/src/lib/math/numbertheory/mp_numth.cpp +++ b/src/lib/math/numbertheory/mp_numth.cpp @@ -1,6 +1,7 @@ /* * Fused and Important MP Algorithms * (C) 1999-2007 Jack Lloyd +* 2016 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -40,20 +41,13 @@ BigInt mul_add(const BigInt& a, const BigInt& b, const BigInt& c) if(a.sign() != b.sign()) sign = BigInt::Negative; - const size_t a_sw = a.sig_words(); - const size_t b_sw = b.sig_words(); - const size_t c_sw = c.sig_words(); - - BigInt r(sign, std::max(a.size() + b.size(), c_sw) + 1); + BigInt r(sign, std::max(a.size() + b.size(), c.sig_words()) + 1); secure_vector<word> workspace(r.size()); - bigint_mul(r.mutable_data(), r.size(), - workspace.data(), - a.data(), a.size(), a_sw, - b.data(), b.size(), b_sw); + bigint_mul(r, a, b, workspace.data()); - const size_t r_size = std::max(r.sig_words(), c_sw); - bigint_add2(r.mutable_data(), r_size, c.data(), c_sw); + const size_t r_size = std::max(r.sig_words(), c.sig_words()); + bigint_add2(r.mutable_data(), r_size, c.data(), c.sig_words()); return r; } diff --git a/src/lib/math/numbertheory/powm_mnt.cpp b/src/lib/math/numbertheory/powm_mnt.cpp index 5c441db3a..572f0de98 100644 --- a/src/lib/math/numbertheory/powm_mnt.cpp +++ b/src/lib/math/numbertheory/powm_mnt.cpp @@ -1,6 +1,7 @@ /* * Montgomery Exponentiation * (C) 1999-2010,2012 Jack Lloyd +* 2016 Matthias Gierlings * * Botan is released under the Simplified BSD License (see license.txt) */ @@ -8,6 +9,7 @@ #include <botan/internal/def_powm.h> #include <botan/numthry.h> #include <botan/internal/mp_core.h> +#include <iostream> namespace Botan { @@ -34,36 +36,26 @@ void Montgomery_Exponentiator::set_base(const BigInt& base) m_g[0] = 1; - bigint_monty_mul(z.mutable_data(), z.size(), - m_g[0].data(), m_g[0].size(), m_g[0].sig_words(), - m_R2_mod.data(), m_R2_mod.size(), m_R2_mod.sig_words(), + bigint_monty_mul(z, m_g[0], m_R2_mod, m_modulus.data(), m_mod_words, m_mod_prime, workspace.data()); - m_g[0] = z; m_g[1] = (base >= m_modulus) ? (base % m_modulus) : base; - bigint_monty_mul(z.mutable_data(), z.size(), - m_g[1].data(), m_g[1].size(), m_g[1].sig_words(), - m_R2_mod.data(), m_R2_mod.size(), m_R2_mod.sig_words(), + bigint_monty_mul(z, m_g[1], m_R2_mod, m_modulus.data(), m_mod_words, m_mod_prime, workspace.data()); m_g[1] = z; const BigInt& x = m_g[1]; - const size_t x_sig = x.sig_words(); for(size_t i = 2; i != m_g.size(); ++i) { const BigInt& y = m_g[i-1]; - const size_t y_sig = y.sig_words(); - bigint_monty_mul(z.mutable_data(), z.size(), - x.data(), x.size(), x_sig, - y.data(), y.size(), y_sig, - m_modulus.data(), m_mod_words, m_mod_prime, + bigint_monty_mul(z, x, y, m_modulus.data(), m_mod_words, m_mod_prime, workspace.data()); m_g[i] = z; @@ -82,15 +74,13 @@ BigInt Montgomery_Exponentiator::execute() const const size_t z_size = 2*(m_mod_words + 1); BigInt z(BigInt::Positive, z_size); - secure_vector<word> workspace(z_size); + secure_vector<word> workspace(z.size()); for(size_t i = exp_nibbles; i > 0; --i) { for(size_t k = 0; k != m_window_bits; ++k) { - bigint_monty_sqr(z.mutable_data(), z_size, - x.data(), x.size(), x.sig_words(), - m_modulus.data(), m_mod_words, m_mod_prime, + bigint_monty_sqr(z, x, m_modulus.data(), m_mod_words, m_mod_prime, workspace.data()); x = z; @@ -100,9 +90,7 @@ BigInt Montgomery_Exponentiator::execute() const const BigInt& y = m_g[nibble]; - bigint_monty_mul(z.mutable_data(), z_size, - x.data(), x.size(), x.sig_words(), - y.data(), y.size(), y.sig_words(), + bigint_monty_mul(z, x, y, m_modulus.data(), m_mod_words, m_mod_prime, workspace.data()); diff --git a/src/lib/pubkey/curve25519/donna.cpp b/src/lib/pubkey/curve25519/donna.cpp index 9b28e412c..a0e4d249f 100644 --- a/src/lib/pubkey/curve25519/donna.cpp +++ b/src/lib/pubkey/curve25519/donna.cpp @@ -39,6 +39,26 @@ typedef byte u8; typedef u64bit limb; typedef limb felem[5]; +typedef struct + { + limb* x; + limb* z; + } fmonty_pair_t; + +typedef struct + { + fmonty_pair_t q; + fmonty_pair_t q_dash; + const limb* q_minus_q_dash; + } fmonty_in_t; + +typedef struct + { + fmonty_pair_t two_q; + fmonty_pair_t q_plus_q_dash; + } fmonty_out_t; + + #if !defined(BOTAN_TARGET_HAS_NATIVE_UINT128) typedef donna128 uint128_t; #endif @@ -273,44 +293,41 @@ fcontract(u8 *output, const felem input) { /* Input: Q, Q', Q-Q' * Output: 2Q, Q+Q' * - * x2 z3: long form - * x3 z3: long form - * x z: short form, destroyed - * xprime zprime: short form, destroyed - * qmqp: short form, preserved + * result.two_q (2*Q): long form + * result.q_plus_q_dash (Q + Q): long form + * in.q: short form, destroyed + * in.q_dash: short form, destroyed + * in.q_minus_q_dash: short form, preserved */ static void -fmonty(limb *x2, limb *z2, /* output 2Q */ - limb *x3, limb *z3, /* output Q + Q' */ - limb *x, limb *z, /* input Q */ - limb *xprime, limb *zprime, /* input Q' */ - const limb *qmqp /* input Q - Q' */) { +fmonty(fmonty_out_t& result, fmonty_in_t& in) +{ limb origx[5], origxprime[5], zzz[5], xx[5], zz[5], xxprime[5], - zzprime[5], zzzprime[5]; + zzprime[5], zzzprime[5]; - copy_mem(origx, x, 5); - fsum(x, z); - fdifference_backwards(z, origx); // does x - z + copy_mem(origx, in.q.x, 5); + fsum(in.q.x, in.q.z); + fdifference_backwards(in.q.z, origx); // does x - z - copy_mem(origxprime, xprime, 5); - fsum(xprime, zprime); - fdifference_backwards(zprime, origxprime); - fmul(xxprime, xprime, z); - fmul(zzprime, x, zprime); + copy_mem(origxprime, in.q_dash.x, 5); + fsum(in.q_dash.x, in.q_dash.z); + fdifference_backwards(in.q_dash.z, origxprime); + fmul(xxprime, in.q_dash.x, in.q.z); + fmul(zzprime, in.q.x, in.q_dash.z); copy_mem(origxprime, xxprime, 5); fsum(xxprime, zzprime); fdifference_backwards(zzprime, origxprime); - fsquare_times(x3, xxprime, 1); + fsquare_times(result.q_plus_q_dash.x, xxprime, 1); fsquare_times(zzzprime, zzprime, 1); - fmul(z3, zzzprime, qmqp); + fmul(result.q_plus_q_dash.z, zzzprime, in.q_minus_q_dash); - fsquare_times(xx, x, 1); - fsquare_times(zz, z, 1); - fmul(x2, xx, zz); + fsquare_times(xx, in.q.x, 1); + fsquare_times(zz, in.q.z, 1); + fmul(result.two_q.x, xx, zz); fdifference_backwards(zz, xx); // does zz = xx - zz fscalar_product(zzz, zz, 121665); fsum(zzz, xx); - fmul(z2, zz, zzz); + fmul(result.two_q.z, zz, zzz); } // ----------------------------------------------------------------------------- @@ -356,11 +373,10 @@ cmult(limb *resultx, limb *resultz, const u8 *n, const limb *q) { swap_conditional(nqx, nqpqx, bit); swap_conditional(nqz, nqpqz, bit); - fmonty(nqx2, nqz2, - nqpqx2, nqpqz2, - nqx, nqz, - nqpqx, nqpqz, - q); + + fmonty_out_t result { nqx2, nqz2, nqpqx2, nqpqz2 }; + fmonty_in_t in { nqx, nqz, nqpqx, nqpqz, q }; + fmonty(result, in); swap_conditional(nqx2, nqpqx2, bit); swap_conditional(nqz2, nqpqz2, bit); |