diff options
Diffstat (limited to 'src')
42 files changed, 938 insertions, 2365 deletions
diff --git a/src/block/aes_intel/aes_intel.h b/src/block/aes_intel/aes_intel.h index 164655072..239516e24 100644 --- a/src/block/aes_intel/aes_intel.h +++ b/src/block/aes_intel/aes_intel.h @@ -18,6 +18,8 @@ namespace Botan { class BOTAN_DLL AES_128_Intel : public BlockCipher { public: + u32bit parallelism() const { return 8; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; @@ -38,6 +40,8 @@ class BOTAN_DLL AES_128_Intel : public BlockCipher class BOTAN_DLL AES_192_Intel : public BlockCipher { public: + u32bit parallelism() const { return 8; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; @@ -58,6 +62,8 @@ class BOTAN_DLL AES_192_Intel : public BlockCipher class BOTAN_DLL AES_256_Intel : public BlockCipher { public: + u32bit parallelism() const { return 8; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; diff --git a/src/block/block_cipher.h b/src/block/block_cipher.h index 06e8c5cea..2d9198c58 100644 --- a/src/block/block_cipher.h +++ b/src/block/block_cipher.h @@ -24,6 +24,11 @@ class BOTAN_DLL BlockCipher : public SymmetricAlgorithm const u32bit BLOCK_SIZE; /** + * @return the preferred parallelism of this cipher + */ + virtual u32bit parallelism() const { return 4; } + + /** * Encrypt a block. * @param in The plaintext block to be encrypted as a byte array. * Must be of length BLOCK_SIZE. diff --git a/src/block/idea_sse2/idea_sse2.h b/src/block/idea_sse2/idea_sse2.h index 167c981f8..657581d74 100644 --- a/src/block/idea_sse2/idea_sse2.h +++ b/src/block/idea_sse2/idea_sse2.h @@ -18,6 +18,8 @@ namespace Botan { class BOTAN_DLL IDEA_SSE2 : public IDEA { public: + u32bit parallelism() const { return 16; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; diff --git a/src/block/noekeon_simd/noekeon_simd.h b/src/block/noekeon_simd/noekeon_simd.h index 466c4b741..55fdfbd22 100644 --- a/src/block/noekeon_simd/noekeon_simd.h +++ b/src/block/noekeon_simd/noekeon_simd.h @@ -18,6 +18,8 @@ namespace Botan { class BOTAN_DLL Noekeon_SIMD : public Noekeon { public: + u32bit parallelism() const { return 8; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; diff --git a/src/block/serpent_simd/serp_simd.h b/src/block/serpent_simd/serp_simd.h index 1ecb70159..dc2b08736 100644 --- a/src/block/serpent_simd/serp_simd.h +++ b/src/block/serpent_simd/serp_simd.h @@ -18,6 +18,8 @@ namespace Botan { class BOTAN_DLL Serpent_SIMD : public Serpent { public: + u32bit parallelism() const { return 8; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; diff --git a/src/block/xtea_simd/xtea_simd.h b/src/block/xtea_simd/xtea_simd.h index e4ce734ed..04a4977ae 100644 --- a/src/block/xtea_simd/xtea_simd.h +++ b/src/block/xtea_simd/xtea_simd.h @@ -18,6 +18,8 @@ namespace Botan { class BOTAN_DLL XTEA_SIMD : public XTEA { public: + u32bit parallelism() const { return 16; } + void encrypt_n(const byte in[], byte out[], u32bit blocks) const; void decrypt_n(const byte in[], byte out[], u32bit blocks) const; BlockCipher* clone() const { return new XTEA_SIMD; } diff --git a/src/build-data/buildh.in b/src/build-data/buildh.in index 231a7aeeb..6412d8a6a 100644 --- a/src/build-data/buildh.in +++ b/src/build-data/buildh.in @@ -22,17 +22,6 @@ #define BOTAN_KARAT_SQR_THRESHOLD 32 #define BOTAN_PRIVATE_KEY_OP_BLINDING_BITS 64 -/* -* Toggles for parallel block cipher mode processing -* -* CBC and CFB can only use parallel processing in decryption mode -*/ -#define BOTAN_PARALLEL_BLOCKS_ECB 16 -#define BOTAN_PARALLEL_BLOCKS_CBC 16 -#define BOTAN_PARALLEL_BLOCKS_CFB 16 -#define BOTAN_PARALLEL_BLOCKS_CTR 16 -#define BOTAN_PARALLEL_BLOCKS_XTS 16 - /* PK key consistency checking toggles */ #define BOTAN_PUBLIC_KEY_STRONG_CHECKS_ON_LOAD 1 #define BOTAN_PRIVATE_KEY_STRONG_CHECKS_ON_LOAD 1 diff --git a/src/filters/buf_filt.h b/src/filters/buf_filt.h index de4102844..582f585b0 100644 --- a/src/filters/buf_filt.h +++ b/src/filters/buf_filt.h @@ -27,6 +27,8 @@ class BOTAN_DLL Buffered_Filter virtual void buffered_block(const byte input[], u32bit length) = 0; virtual void buffered_final(const byte input[], u32bit length) = 0; + u32bit buffered_block_size() const { return main_block_mod; } + u32bit current_position() const { return buffer_pos; } void buffer_reset() { buffer_pos = 0; } private: diff --git a/src/filters/modes/cbc/cbc.cpp b/src/filters/modes/cbc/cbc.cpp index 7722fad2f..4f484da77 100644 --- a/src/filters/modes/cbc/cbc.cpp +++ b/src/filters/modes/cbc/cbc.cpp @@ -114,7 +114,7 @@ std::string CBC_Encryption::name() const */ CBC_Decryption::CBC_Decryption(BlockCipher* ciph, BlockCipherModePaddingMethod* pad) : - Buffered_Filter(BOTAN_PARALLEL_BLOCKS_CBC * ciph->BLOCK_SIZE, + Buffered_Filter(ciph->parallelism() * ciph->BLOCK_SIZE, ciph->BLOCK_SIZE), cipher(ciph), padder(pad) { @@ -122,7 +122,7 @@ CBC_Decryption::CBC_Decryption(BlockCipher* ciph, throw Invalid_Block_Size(name(), padder->name()); state.resize(cipher->BLOCK_SIZE); - temp.resize(BOTAN_PARALLEL_BLOCKS_CBC * cipher->BLOCK_SIZE); + temp.resize(buffered_block_size()); } /* @@ -132,7 +132,7 @@ CBC_Decryption::CBC_Decryption(BlockCipher* ciph, BlockCipherModePaddingMethod* pad, const SymmetricKey& key, const InitializationVector& iv) : - Buffered_Filter(BOTAN_PARALLEL_BLOCKS_CBC * ciph->BLOCK_SIZE, + Buffered_Filter(ciph->parallelism() * ciph->BLOCK_SIZE, ciph->BLOCK_SIZE), cipher(ciph), padder(pad) { @@ -140,7 +140,7 @@ CBC_Decryption::CBC_Decryption(BlockCipher* ciph, throw Invalid_Block_Size(name(), padder->name()); state.resize(cipher->BLOCK_SIZE); - temp.resize(BOTAN_PARALLEL_BLOCKS_CBC * cipher->BLOCK_SIZE); + temp.resize(buffered_block_size()); set_key(key); set_iv(iv); diff --git a/src/filters/modes/ecb/ecb.cpp b/src/filters/modes/ecb/ecb.cpp index 2ce6576e3..948daf6c2 100644 --- a/src/filters/modes/ecb/ecb.cpp +++ b/src/filters/modes/ecb/ecb.cpp @@ -14,12 +14,12 @@ namespace Botan { */ ECB_Encryption::ECB_Encryption(BlockCipher* ciph, BlockCipherModePaddingMethod* pad) : - Buffered_Filter(ciph->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB, 0) + Buffered_Filter(ciph->BLOCK_SIZE * ciph->parallelism(), 0) { cipher = ciph; padder = pad; - temp.resize(cipher->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB); + temp.resize(buffered_block_size()); } /* @@ -28,12 +28,12 @@ ECB_Encryption::ECB_Encryption(BlockCipher* ciph, ECB_Encryption::ECB_Encryption(BlockCipher* ciph, BlockCipherModePaddingMethod* pad, const SymmetricKey& key) : - Buffered_Filter(ciph->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB, 0) + Buffered_Filter(ciph->BLOCK_SIZE * ciph->parallelism(), 0) { cipher = ciph; padder = pad; - temp.resize(cipher->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB); + temp.resize(buffered_block_size()); cipher->set_key(key); } @@ -111,12 +111,12 @@ void ECB_Encryption::buffered_final(const byte input[], u32bit input_length) */ ECB_Decryption::ECB_Decryption(BlockCipher* ciph, BlockCipherModePaddingMethod* pad) : - Buffered_Filter(ciph->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB, 1) + Buffered_Filter(ciph->BLOCK_SIZE * ciph->parallelism(), 1) { cipher = ciph; padder = pad; - temp.resize(cipher->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB); + temp.resize(buffered_block_size()); } /* @@ -125,12 +125,12 @@ ECB_Decryption::ECB_Decryption(BlockCipher* ciph, ECB_Decryption::ECB_Decryption(BlockCipher* ciph, BlockCipherModePaddingMethod* pad, const SymmetricKey& key) : - Buffered_Filter(ciph->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB, 1) + Buffered_Filter(ciph->BLOCK_SIZE * ciph->parallelism(), 1) { cipher = ciph; padder = pad; - temp.resize(cipher->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_ECB); + temp.resize(buffered_block_size()); cipher->set_key(key); } diff --git a/src/filters/modes/xts/xts.cpp b/src/filters/modes/xts/xts.cpp index aeef4e88d..26095e830 100644 --- a/src/filters/modes/xts/xts.cpp +++ b/src/filters/modes/xts/xts.cpp @@ -30,13 +30,21 @@ void poly_double(byte tweak[], u32bit size) tweak[0] ^= polynomial; } +/* XTS needs to process at least 2 blocks in parallel + because block_size+1 bytes are needed at the end +*/ +u32bit xts_parallelism(BlockCipher* cipher) + { + return std::max<u32bit>(cipher->parallelism(), 2); + } + } /* * XTS_Encryption constructor */ XTS_Encryption::XTS_Encryption(BlockCipher* ciph) : - Buffered_Filter(BOTAN_PARALLEL_BLOCKS_XTS * ciph->BLOCK_SIZE, + Buffered_Filter(xts_parallelism(ciph) * ciph->BLOCK_SIZE, ciph->BLOCK_SIZE + 1), cipher(ciph) { @@ -44,7 +52,7 @@ XTS_Encryption::XTS_Encryption(BlockCipher* ciph) : throw std::invalid_argument("Bad cipher for XTS: " + cipher->name()); cipher2 = cipher->clone(); - tweak.resize(BOTAN_PARALLEL_BLOCKS_XTS * cipher->BLOCK_SIZE); + tweak.resize(buffered_block_size()); } /* @@ -53,7 +61,7 @@ XTS_Encryption::XTS_Encryption(BlockCipher* ciph) : XTS_Encryption::XTS_Encryption(BlockCipher* ciph, const SymmetricKey& key, const InitializationVector& iv) : - Buffered_Filter(BOTAN_PARALLEL_BLOCKS_XTS * ciph->BLOCK_SIZE, + Buffered_Filter(xts_parallelism(ciph) * ciph->BLOCK_SIZE, ciph->BLOCK_SIZE + 1), cipher(ciph) { @@ -61,7 +69,7 @@ XTS_Encryption::XTS_Encryption(BlockCipher* ciph, throw std::invalid_argument("Bad cipher for XTS: " + cipher->name()); cipher2 = cipher->clone(); - tweak.resize(BOTAN_PARALLEL_BLOCKS_XTS * cipher->BLOCK_SIZE); + tweak.resize(buffered_block_size()); set_key(key); set_iv(iv); @@ -210,7 +218,7 @@ void XTS_Encryption::buffered_final(const byte input[], u32bit length) * XTS_Decryption constructor */ XTS_Decryption::XTS_Decryption(BlockCipher* ciph) : - Buffered_Filter(BOTAN_PARALLEL_BLOCKS_XTS * ciph->BLOCK_SIZE, + Buffered_Filter(xts_parallelism(ciph) * ciph->BLOCK_SIZE, ciph->BLOCK_SIZE + 1), cipher(ciph) { @@ -218,7 +226,7 @@ XTS_Decryption::XTS_Decryption(BlockCipher* ciph) : throw std::invalid_argument("Bad cipher for XTS: " + cipher->name()); cipher2 = ciph->clone(); - tweak.resize(BOTAN_PARALLEL_BLOCKS_XTS * cipher->BLOCK_SIZE); + tweak.resize(buffered_block_size()); } /* @@ -227,7 +235,7 @@ XTS_Decryption::XTS_Decryption(BlockCipher* ciph) : XTS_Decryption::XTS_Decryption(BlockCipher* ciph, const SymmetricKey& key, const InitializationVector& iv) : - Buffered_Filter(BOTAN_PARALLEL_BLOCKS_XTS * ciph->BLOCK_SIZE, + Buffered_Filter(xts_parallelism(ciph) * ciph->BLOCK_SIZE, ciph->BLOCK_SIZE + 1), cipher(ciph) { @@ -235,7 +243,7 @@ XTS_Decryption::XTS_Decryption(BlockCipher* ciph, throw std::invalid_argument("Bad cipher for XTS: " + cipher->name()); cipher2 = ciph->clone(); - tweak.resize(BOTAN_PARALLEL_BLOCKS_XTS * cipher->BLOCK_SIZE); + tweak.resize(buffered_block_size()); set_key(key); set_iv(iv); diff --git a/src/math/gfpmath/curve_gfp.cpp b/src/math/gfpmath/curve_gfp.cpp deleted file mode 100644 index e6e69ab0f..000000000 --- a/src/math/gfpmath/curve_gfp.cpp +++ /dev/null @@ -1,58 +0,0 @@ -/* -* Elliptic curves over GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008-2010 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#include <botan/curve_gfp.h> -#include <botan/bigint.h> -#include <assert.h> -#include <ostream> - -namespace Botan { - -CurveGFp::CurveGFp(const GFpElement& a, const GFpElement& b, - const BigInt& p) : - modulus(p), mA(a), mB(b), - mres_a(mA), mres_b(mB), mres_one(p, 1) - { - if(p != mA.get_p() || p != mB.get_p()) - throw Invalid_Argument("could not construct curve: moduli of arguments differ"); - - mres_a.turn_on_sp_red_mul(); - mres_a.get_mres(); - - mres_b.turn_on_sp_red_mul(); - mres_b.get_mres(); - - mres_one.turn_on_sp_red_mul(); - mres_one.get_mres(); - } - -// swaps the states of *this and other, does not throw -void CurveGFp::swap(CurveGFp& other) - { - std::swap(mA, other.mA); - std::swap(mB, other.mB); - std::swap(modulus, other.modulus); - std::swap(mres_a, other.mres_a); - std::swap(mres_b, other.mres_b); - std::swap(mres_one, other.mres_one); - } - -bool operator==(const CurveGFp& lhs, const CurveGFp& rhs) - { - return (lhs.get_p() == rhs.get_p() && - lhs.get_a() == rhs.get_a() && - lhs.get_b() == rhs.get_b()); - } - -std::ostream& operator<<(std::ostream& output, const CurveGFp& elem) - { - return output << "y^2 = x^3 + (" << elem.get_a() << ")x + (" << elem.get_b() << ")"; - } - -} diff --git a/src/math/gfpmath/curve_gfp.h b/src/math/gfpmath/curve_gfp.h deleted file mode 100644 index d2ca437fb..000000000 --- a/src/math/gfpmath/curve_gfp.h +++ /dev/null @@ -1,133 +0,0 @@ -/* -* Elliptic curves over GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2010 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_GFP_CURVE_H__ -#define BOTAN_GFP_CURVE_H__ - -#include <botan/bigint.h> -#include <botan/gfp_element.h> -#include <iosfwd> - -namespace Botan { - -/** -* This class represents an elliptic curve over GF(p) -*/ -class BOTAN_DLL CurveGFp - { - public: - - /** - * Construct the elliptic curve E: y^2 = x^3 + ax + b over GF(p) - * @param a first coefficient - * @param b second coefficient - * @param p prime number of the field - */ - CurveGFp(const GFpElement& a, const GFpElement& b, - const BigInt& p); - - // CurveGFp(const CurveGFp& other) = default; - // CurveGFp& operator=(const CurveGFp& other) = default; - - // getters - - /** - * Get coefficient a - * @result coefficient a - */ - const GFpElement& get_a() const { return mA; } - - /** - * Get coefficient b - * @result coefficient b - */ - const GFpElement& get_b() const { return mB; } - - /** - * Get the GFpElement coefficient a transformed - * to its m-residue. This can be used for efficency reasons: the curve - * stores the transformed version after the first invocation of this - * function. - * @result the coefficient a, transformed to its m-residue - */ - const GFpElement& get_mres_a() const { return mres_a; } - - /** - * Get the GFpElement coefficient b transformed - * to its m-residue. This can be used for efficency reasons: the curve - * stores the transformed version after the first invocation of this - * function. - * @result the coefficient b, transformed to its m-residue - */ - const GFpElement& get_mres_b() const { return mres_b; } - - /** - * Get the GFpElement 1 transformed - * to its m-residue. This can be used for efficency reasons: the curve - * stores the transformed version after the first invocation of this - * function. - * @result the GFpElement 1, transformed to its m-residue - */ - const GFpElement& get_mres_one() { return mres_one; } - - /** - * Get prime modulus of the field of the curve - * @result prime modulus of the field of the curve - */ - const BigInt& get_p() const { return modulus.get_p(); } - - /** - * swaps the states of *this and other, does not throw - * @param other The curve to swap values with - */ - void swap(CurveGFp& other); - - private: - GFpModulus modulus; - GFpElement mA; - GFpElement mB; - GFpElement mres_a, mres_b, mres_one; - }; - -// relational operators -bool operator==(const CurveGFp& lhs, const CurveGFp& rhs); - -inline bool operator!=(const CurveGFp& lhs, const CurveGFp& rhs) - { - return !(lhs == rhs); - } - -// io operators -std::ostream& operator<<(std::ostream& output, const CurveGFp& elem); - -// swaps the states of curve1 and curve2, does not throw! -// cf. Meyers, Item 25 -inline -void swap(CurveGFp& curve1, CurveGFp& curve2) - { - curve1.swap(curve2); - } - -} // namespace Botan - - -namespace std { - -// swaps the states of curve1 and curve2, does not throw! -// cf. Meyers, Item 25 -template<> inline -void swap<Botan::CurveGFp>(Botan::CurveGFp& curve1, - Botan::CurveGFp& curve2) - { - curve1.swap(curve2); - } - -} // namespace std - -#endif diff --git a/src/math/gfpmath/gfp_element.cpp b/src/math/gfpmath/gfp_element.cpp deleted file mode 100644 index 3bb4d0002..000000000 --- a/src/math/gfpmath/gfp_element.cpp +++ /dev/null @@ -1,559 +0,0 @@ -/* -* Arithmetic for prime fields GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* -* Distributed under the terms of the Botan license -*/ - -#include <botan/gfp_element.h> -#include <botan/numthry.h> -#include <botan/internal/def_powm.h> -#include <botan/internal/mp_asm.h> -#include <botan/internal/mp_asmi.h> -#include <ostream> -#include <assert.h> - -namespace Botan { - -namespace { - -void inner_montg_mult_sos(word result[], - const word* a_bar, const word* b_bar, - const word* n, const word* n_dash, u32bit s) - { - SecureVector<word> t; - t.grow_to(2*s+1); - - // t = a_bar * b_bar - for (u32bit i=0; i<s; i++) - { - word C = 0; - word S = 0; - for (u32bit j=0; j<s; j++) - { - // we use: - // word word_madd3(word a, word b, word c, word d, word* carry) - // returns a * b + c + d and resets the carry (not using it as input) - - S = word_madd3(a_bar[j], b_bar[i], t[i+j], &C); - t[i+j] = S; - } - t[i+s] = C; - } - - // ??? - for (u32bit i=0; i<s; i++) - { - // word word_madd2(word a, word b, word c, word* carry) - // returns a * b + c, resets the carry - - word C = 0; - word zero = 0; - word m = word_madd2(t[i], n_dash[0], &zero); - - for (u32bit j=0; j<s; j++) - { - word S = word_madd3(m, n[j], t[i+j], &C); - t[i+j] = S; - } - - //// mp_mulop.cpp: - ////word bigint_mul_add_words(word z[], const word x[], u32bit x_size, word y) - u32bit cnt = 0; - while (C > 0) - { - // we need not worry here about C > 1, because the other operand is zero - - word tmp = t[i+s+cnt] + C; - C = (tmp < t[i+s+cnt]); - t[i+s+cnt] = tmp; - cnt++; - } - } - - // u = t - SecureVector<word> u; - u.grow_to(s+1); - for (u32bit j=0; j<s+1; j++) - { - u[j] = t[j+s]; - } - - // t = u - n - word B = 0; - word D = 0; - for (u32bit i=0; i<s; i++) - { - D = word_sub(u[i], n[i], &B); - t[i] = D; - } - D = word_sub(u[s], 0, &B); - t[s] = D; - - // if t >= 0 (B == 0 -> no borrow), return t - if(B == 0) - { - for (u32bit i=0; i<s; i++) - { - result[i] = t[i]; - } - } - else // else return u - { - for (u32bit i=0; i<s; i++) - { - result[i] = u[i]; - } - } - } - -void montg_mult(BigInt& result, BigInt& a_bar, BigInt& b_bar, const BigInt& m, const BigInt& m_dash, const BigInt) - { - if(m.is_zero() || m_dash.is_zero()) - throw Invalid_Argument("montg_mult(): neither modulus nor m_dash may be zero (and one of them was)"); - - if(a_bar.is_zero() || b_bar.is_zero()) - result = 0; - - u32bit s = m.sig_words(); - a_bar.grow_to(s); - b_bar.grow_to(s); - result.grow_to(s); - - inner_montg_mult_sos(result.get_reg(), a_bar.data(), b_bar.data(), - m.data(), m_dash.data(), s); - } - -/** -* Calculates R=b^n (here b=2) with R>m (and R beeing as small as -* possible) for an odd modulus m. No check for parity is performed! -*/ -BigInt montgm_calc_r_oddmod(const BigInt& prime) - { - u32bit n = prime.sig_words(); - BigInt result(1); - result <<= n*BOTAN_MP_WORD_BITS; - return result; - } - -/** -*calculates m' with r*r^-1 - m*m' = 1 -* where r^-1 is the multiplicative inverse of r to the modulus m -*/ -BigInt montgm_calc_m_dash(const BigInt& r, const BigInt& m, const BigInt& r_inv) - { - BigInt result = ((r * r_inv) - BigInt(1))/m; - return result; - } - -BigInt montg_trf_to_mres(const BigInt& ord_res, const BigInt& r, const BigInt& m) - { - BigInt result(ord_res); - result *= r; - result %= m; - return result; - } - -BigInt montg_trf_to_ordres(const BigInt& m_res, const BigInt& m, const BigInt& r_inv) - { - BigInt result(m_res); - result *= r_inv; - result %= m; - return result; - } - -} - -GFpElement::GFpElement(const BigInt& p, const BigInt& value, bool use_montgomery) - : modulus(p), m_value(value %p), m_use_montgm(use_montgomery), m_is_trf(false) - { - if(m_use_montgm) - ensure_montgm_precomp(); - } - -void GFpElement::turn_on_sp_red_mul() - { - ensure_montgm_precomp(); - m_use_montgm = true; - } - -void GFpElement::turn_off_sp_red_mul() - { - if(m_is_trf) - { - trf_to_ordres(); - // will happen soon anyway, so we can do it here already - // (this is not lazy but way more secure concerning our internal logic here) - } - m_use_montgm = false; - } - -void GFpElement::ensure_montgm_precomp() - { - if((!modulus.get_r().is_zero()) && (!modulus.get_r_inv().is_zero()) && (!modulus.get_p_dash().is_zero())) - { - // values are already set, nothing more to do - } - else - { - BigInt tmp_r(montgm_calc_r_oddmod(modulus.get_p())); - - BigInt tmp_r_inv(inverse_mod(tmp_r, modulus.get_p())); - - BigInt tmp_p_dash(montgm_calc_m_dash(tmp_r, modulus.get_p(), tmp_r_inv)); - - modulus.reset_values(tmp_p_dash, tmp_r, tmp_r_inv); - } - - } - -void GFpElement::trf_to_mres() const - { - if(!m_use_montgm) - { - throw Illegal_Transformation("GFpElement is not allowed to be transformed to m-residue"); - } - assert(m_is_trf == false); - assert(!modulus.get_r_inv().is_zero()); - assert(!modulus.get_p_dash().is_zero()); - m_value = montg_trf_to_mres(m_value, modulus.get_r(), modulus.get_p()); - m_is_trf = true; - } - -void GFpElement::trf_to_ordres() const - { - assert(m_is_trf == true); - m_value = montg_trf_to_ordres(m_value, modulus.get_p(), modulus.get_r_inv()); - m_is_trf = false; - } - -bool GFpElement::align_operands_res(const GFpElement& lhs, const GFpElement& rhs) //static - { - assert(lhs.modulus.get_p() == rhs.modulus.get_p()); - if(lhs.m_use_montgm && rhs.m_use_montgm) - { - assert(rhs.modulus.get_p_dash() == lhs.modulus.get_p_dash()); - assert(rhs.modulus.get_r() == lhs.modulus.get_r()); - assert(rhs.modulus.get_r_inv() == lhs.modulus.get_r_inv()); - if(!lhs.m_is_trf && !rhs.m_is_trf) - { - return false; - } - else if(lhs.m_is_trf && rhs.m_is_trf) - { - return true; - } - else // one is transf., the other not - { - if(!lhs.m_is_trf) - { - lhs.trf_to_mres(); - assert(rhs.m_is_trf==true); - return true; - } - assert(rhs.m_is_trf==false); - assert(lhs.m_is_trf==true); - rhs.trf_to_mres(); // the only possibility left... - return true; - } - } - else // at least one of them does not use mm - // (so it is impossible that both use it) - { - if(lhs.m_is_trf) - { - lhs.trf_to_ordres(); - assert(rhs.m_is_trf == false); - return false; - } - if(rhs.m_is_trf) - { - rhs.trf_to_ordres(); - assert(lhs.m_is_trf == false); - return false; - } - return false; - } - assert(false); - } - -bool GFpElement::is_trf_to_mres() const - { - return m_is_trf; - } - -const BigInt& GFpElement::get_p() const - { - return (modulus.get_p()); - } - -const BigInt& GFpElement::get_value() const - { - if(m_is_trf) - { - assert(m_use_montgm); - trf_to_ordres(); - } - return m_value; - } - -const BigInt& GFpElement::get_mres() const - { - if(!m_use_montgm) - { - // does the following exception really make sense? - // wouldn't it be better to simply turn on montg.mult. when - // this explicit request is made? - throw Illegal_Transformation("GFpElement is not allowed to be transformed to m-residue"); - } - if(!m_is_trf) - { - trf_to_mres(); - } - - return m_value; - } - -GFpElement& GFpElement::operator+=(const GFpElement& rhs) - { - GFpElement::align_operands_res(*this, rhs); - - BigInt workspace = m_value; - workspace += rhs.m_value; - if(workspace >= modulus.get_p()) - workspace -= modulus.get_p(); - - m_value = workspace; - assert(m_value < modulus.get_p()); - assert(m_value >= 0); - - return *this; - } - -GFpElement& GFpElement::operator-=(const GFpElement& rhs) - { - GFpElement::align_operands_res(*this, rhs); - - BigInt workspace = m_value; - - workspace -= rhs.m_value; - - if(workspace.is_negative()) - workspace += modulus.get_p(); - - m_value = workspace; - assert(m_value < modulus.get_p()); - assert(m_value >= 0); - return *this; - } - -GFpElement& GFpElement::operator*= (u32bit rhs) - { - BigInt workspace = m_value; - workspace *= rhs; - workspace %= modulus.get_p(); - m_value = workspace; - return *this; - } - -GFpElement& GFpElement::operator*=(const GFpElement& rhs) - { - assert(rhs.modulus.get_p() == modulus.get_p()); - // here, we do not use align_operands_res() for one simple reason: - // we want to enforce the transformation to an m-residue, otherwise it would - // never happen - if(m_use_montgm && rhs.m_use_montgm) - { - assert(rhs.modulus.get_p() == modulus.get_p()); // is montgm. mult is on, then precomps must be there - assert(rhs.modulus.get_p_dash() == modulus.get_p_dash()); - assert(rhs.modulus.get_r() == modulus.get_r()); - if(!m_is_trf) - { - trf_to_mres(); - } - if(!rhs.m_is_trf) - { - rhs.trf_to_mres(); - } - BigInt workspace = m_value; - montg_mult(m_value, workspace, rhs.m_value, modulus.get_p(), modulus.get_p_dash(), modulus.get_r()); - } - else // ordinary multiplication - { - if(m_is_trf) - { - assert(m_use_montgm); - trf_to_ordres(); - } - if(rhs.m_is_trf) - { - assert(rhs.m_use_montgm); - rhs.trf_to_ordres(); - } - - BigInt workspace = m_value; - workspace *= rhs.m_value; - workspace %= modulus.get_p(); - m_value = workspace; - } - return *this; - } - -GFpElement& GFpElement::operator/=(const GFpElement& rhs) - { - bool use_mres = GFpElement::align_operands_res(*this, rhs); - assert((this->m_is_trf && rhs.m_is_trf) || !(this->m_is_trf && rhs.m_is_trf)); - - if(use_mres) - { - assert(m_use_montgm && rhs.m_use_montgm); - GFpElement rhs_ordres(rhs); - rhs_ordres.trf_to_ordres(); - rhs_ordres.inverse_in_place(); - BigInt workspace = m_value; - workspace *= rhs_ordres.get_value(); - workspace %= modulus.get_p(); - m_value = workspace; - } - else - { - GFpElement inv_rhs(rhs); - inv_rhs.inverse_in_place(); - *this *= inv_rhs; - } - return *this; - } - -bool GFpElement::is_zero() - { - return (m_value.is_zero()); - // this is correct because x_bar = x * r = x = 0 for x = 0 - } - -GFpElement& GFpElement::inverse_in_place() - { - m_value = inverse_mod(m_value, modulus.get_p()); - - if(m_is_trf) - { - assert(m_use_montgm); - - m_value *= modulus.get_r(); - m_value *= modulus.get_r(); - m_value %= modulus.get_p(); - } - assert(m_value <= modulus.get_p()); - return *this; - } - -GFpElement& GFpElement::negate() - { - m_value = modulus.get_p() - m_value; - assert(m_value <= modulus.get_p()); - return *this; - } - -void GFpElement::swap(GFpElement& other) - { - std::swap(m_value, other.m_value); - std::swap(modulus, other.modulus); - std::swap<bool>(m_use_montgm,other.m_use_montgm); - std::swap<bool>(m_is_trf,other.m_is_trf); - } - -std::ostream& operator<<(std::ostream& output, const GFpElement& elem) - { - return output << '(' << elem.get_value() << "," << elem.get_p() << ')'; - } - -bool operator==(const GFpElement& lhs, const GFpElement& rhs) - { - if(lhs.get_p() != rhs.get_p()) - return false; - - // so the modulus is equal, now check the values - bool use_mres = GFpElement::align_operands_res(lhs, rhs); - - if(use_mres) - { - return (lhs.get_mres() == rhs.get_mres()); - } - else - { - return(lhs.get_value() == rhs.get_value()); - } - } - -GFpElement operator+(const GFpElement& lhs, const GFpElement& rhs) - { - // consider the case that lhs and rhs both use montgm: - // then += returns an element which uses montgm. - // thus the return value of op+ here will be an element - // using montgm in this case - // NOTE: the rhs might be transformed when using op+, the lhs never - GFpElement result(lhs); - result += rhs; - return result; - } - -GFpElement operator-(const GFpElement& lhs, const GFpElement& rhs) - { - GFpElement result(lhs); - result -= rhs; - return result; - // NOTE: the rhs might be transformed when using op-, the lhs never - } - -GFpElement operator-(const GFpElement& lhs) - { - return(GFpElement(lhs)).negate(); - } - -GFpElement operator*(const GFpElement& lhs, const GFpElement& rhs) - { - // consider the case that lhs and rhs both use montgm: - // then *= returns an element which uses montgm. - // thus the return value of op* here will be an element - // using montgm in this case - GFpElement result(lhs); - result *= rhs; - return result; - } - -GFpElement operator*(const GFpElement& lhs, u32bit rhs) - { - GFpElement result(lhs); - result *= rhs; - return result; - } - -GFpElement operator*(u32bit lhs, const GFpElement& rhs) - { - return rhs*lhs; - } - -GFpElement operator/(const GFpElement& lhs, const GFpElement& rhs) - { - GFpElement result (lhs); - result /= rhs; - return result; - } - -SecureVector<byte> FE2OSP(const GFpElement& elem) - { - return BigInt::encode_1363(elem.get_value(), elem.get_p().bytes()); - } - -GFpElement OS2FEP(MemoryRegion<byte> const& os, BigInt p) - { - return GFpElement(p, BigInt::decode(os.begin(), os.size())); - } - -GFpElement inverse(const GFpElement& elem) - { - return GFpElement(elem).inverse_in_place(); - } - -} - diff --git a/src/math/gfpmath/gfp_element.h b/src/math/gfpmath/gfp_element.h deleted file mode 100644 index 538d41a47..000000000 --- a/src/math/gfpmath/gfp_element.h +++ /dev/null @@ -1,230 +0,0 @@ -/* -* Arithmetic for prime fields GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2009-2010 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_GFP_ELEMENT_H__ -#define BOTAN_GFP_ELEMENT_H__ - -#include <botan/bigint.h> -#include <botan/gfp_modulus.h> -#include <iosfwd> - -namespace Botan { - -struct BOTAN_DLL Illegal_Transformation : public Exception - { - Illegal_Transformation(const std::string& err = - "Requested transformation is not possible") : - Exception(err) {} - }; - -/** - * This class represents one element in GF(p). Enables the convenient, - * transparent use of the montgomery multiplication. - */ -class BOTAN_DLL GFpElement - { - public: - - /** construct an element of GF(p) with the given value. - * use_montg defaults to false and determines wether Montgomery - * multiplications will be use when applying operators *, *= - * @param p the prime number of the field - * @param value the element value - * @param use_montgm whether this object will use Montgomery multiplication - */ - GFpElement(const BigInt& p, const BigInt& value, bool use_montgm = true); - - // GFpElement(const GFpElement& other) = default; - - // const GFpElement& operator=(const GFpElement& other) = default; - - /** - * Switch Montgomery multiplcation optimizations ON - */ - void turn_on_sp_red_mul(); - - /** - * Switch Montgomery multiplcation optimizations OFF - */ - void turn_off_sp_red_mul(); - - /** - * += Operator - * @param rhs the GFpElement to add to the local value - * @result *this - */ - GFpElement& operator+=(const GFpElement& rhs); - - /** - * -= Operator - * @param rhs the GFpElement to subtract from the local value - * @result *this - */ - GFpElement& operator-=(const GFpElement& rhs); - - /** - * *= Operator - * @param rhs the GFpElement to multiply with the local value - * @result *this - */ - GFpElement& operator*=(const GFpElement& rhs); - /** - * /= Operator - * @param rhs the GFpElement to divide the local value by - * @result *this - */ - GFpElement& operator/=(const GFpElement& rhs); - - /** - * *= Operator - * @param rhs the value to multiply with the local value - * @result *this - */ - GFpElement& operator*=(u32bit rhs); - - /** - * Negate internal value(*this *= -1 ) - * @return *this - */ - GFpElement& negate(); - - /** - * Assigns the inverse of *this to *this, i.e. - * *this = (*this)^(-1) - * @result *this - */ - GFpElement& inverse_in_place(); - - /** - * checks whether the value is zero (without provoking - * a backtransformation to the ordinary-residue) - * @result true, if the value is zero, false otherwise. - */ - bool is_zero(); - - /** - * return prime number of GF(p) - * @result a prime number - */ - const BigInt& get_p() const; - - /** - * Return the represented value in GF(p) - * @result The value in GF(p) - */ - const BigInt& get_value() const; - - /** - * Tells whether this GFpElement is currently transformed to an m-residue, - * i.e. in the form x_bar = x * r mod m. - * @result true if it is currently transformed to its m-residue. - */ - bool is_trf_to_mres() const; - - /** - * Transforms this to x_bar = x * r mod m - * @result return the value x_bar. - */ - const BigInt& get_mres() const; - - /** - * Check, if montgomery multiplication is used. - * @result true, if montgomery multiplication is used, false otherwise - */ - bool is_use_montgm() const - { - return m_use_montgm; - } - - /** - * Transforms the arguments in such way that either both - * are in m-residue representation (returns true) or both are - * in ordinary residue representation (returns false). - * m-residue is prefered in case of ambiguity. - * does not toggle m_use_montgm of the arguments. - * Don't be confused about the constness of the arguments: - * the transformation between normal residue and m-residue is - * considered as leaving the object const. - * @param lhs the first operand to be aligned - * @param rhs the second operand to be aligned - * @result true if both are transformed to their m-residue, - * false it both are transformed to their normal residue. - */ - static bool align_operands_res(const GFpElement& lhs, const GFpElement& rhs); - - /** - * swaps the states of *this and other, does not throw! - * @param other The value to swap with - */ - void swap(GFpElement& other); - private: - void ensure_montgm_precomp(); - void trf_to_mres() const; - void trf_to_ordres() const; - - GFpModulus modulus; - mutable BigInt m_value; // ordinary residue or m-residue respectively - - // data members for montgomery multiplication - bool m_use_montgm; - mutable bool m_is_trf; // if m_value is montgomery - }; - -// relational operators -bool BOTAN_DLL operator==(const GFpElement& lhs, const GFpElement& rhs); -inline bool operator!=(const GFpElement& lhs, const GFpElement& rhs ) - { - return !operator==(lhs, rhs); - } - -// arithmetic operators -GFpElement BOTAN_DLL operator+(const GFpElement& lhs, const GFpElement& rhs); -GFpElement BOTAN_DLL operator-(const GFpElement& lhs, const GFpElement& rhs); -GFpElement BOTAN_DLL operator-(const GFpElement& lhs); - -GFpElement BOTAN_DLL operator*(const GFpElement& lhs, const GFpElement& rhs); -GFpElement BOTAN_DLL operator/(const GFpElement& lhs, const GFpElement& rhs); -GFpElement BOTAN_DLL operator*(const GFpElement& lhs, u32bit rhs); -GFpElement BOTAN_DLL operator*(u32bit rhs, const GFpElement& lhs); - - -/** -* write a GFpElement to an output stream. -* @param output the output stream to write to -* @param elem the object to write -* @result the output stream -*/ -BOTAN_DLL std::ostream& operator<<(std::ostream& output, const GFpElement& elem); - -// return (*this)^(-1) -GFpElement BOTAN_DLL inverse(const GFpElement& elem); - -// encoding and decoding -SecureVector<byte> BOTAN_DLL FE2OSP(const GFpElement& elem); -GFpElement BOTAN_DLL OS2FEP(MemoryRegion<byte> const& os, BigInt p); - -inline void swap(GFpElement& x, GFpElement& y) - { - x.swap(y); - } - -} - -namespace std { - -template<> inline -void swap<Botan::GFpElement>(Botan::GFpElement& x, - Botan::GFpElement& y) - { - x.swap(y); - } - -} - -#endif diff --git a/src/math/gfpmath/gfp_modulus.h b/src/math/gfpmath/gfp_modulus.h deleted file mode 100644 index fcdd13ee1..000000000 --- a/src/math/gfpmath/gfp_modulus.h +++ /dev/null @@ -1,131 +0,0 @@ -/* -* Modulus and related data for a specific implementation of GF(p) -* -* (C) 2008 Martin Doering, Christoph Ludwig, Falko Strenzke -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_GFP_MODULUS_H__ -#define BOTAN_GFP_MODULUS_H__ - -#include <botan/bigint.h> - -namespace Botan { - -class GFpElement; - -/** -* This class represents a GFpElement modulus including the modulus -* related values necessary for the montgomery multiplication. -*/ -class BOTAN_DLL GFpModulus - { - public: - - /** - * Construct a GF(P)-Modulus from a BigInt - */ - GFpModulus(const BigInt& p) - : m_p(p), - m_p_dash(), - m_r(), - m_r_inv() - {} - - // GFpModulus(const GFpModulus& other) = default; - // GFpModulus& operator=(const GFpModulus& other) = default; - - /** - * Tells whether the precomputations necessary for the use of the - * montgomery multiplication have yet been established. - * @result true if the precomputated value are already available. - */ - bool has_precomputations() const - { - return(!m_p_dash.is_zero() && !m_r.is_zero() && !m_r_inv.is_zero()); - } - - /** - * Swaps this with another GFpModulus, does not throw. - * @param other the GFpModulus to swap *this with. - */ - void swap(GFpModulus& other) - { - std::swap(m_p, other.m_p); - std::swap(m_p_dash, other.m_p_dash); - std::swap(m_r, other.m_r); - std::swap(m_r_inv, other.m_r_inv); - } - - /** - * Tells whether the modulus of *this is equal to the argument. - * @param mod the modulus to compare this with - * @result true if the modulus of *this and the argument are equal. - */ - bool p_equal_to(const BigInt& mod) const - { - return (m_p == mod); - } - - /** - * Return the modulus of this GFpModulus. - * @result the modulus of *this. - */ - const BigInt& get_p() const - { - return m_p; - } - - /** - * returns the montgomery multiplication related value r. - * Warning: will be zero if precomputations have not yet been - * performed! - * @result r - */ - const BigInt& get_r() const - { - return m_r; - } - - /** - * returns the montgomery multiplication related value r^{-1}. - * Warning: will be zero if precomputations have not yet been - * performed! - * @result r^{-1} - */ - const BigInt& get_r_inv() const - { - return m_r_inv; - } - - /** - * returns the montgomery multiplication related value p'. - * Warning: will be zero if precomputations have not yet been - * performed! - * @result p' - */ - const BigInt& get_p_dash() const - { - return m_p_dash; - } - - void reset_values(const BigInt& new_p_dash, - const BigInt& new_r, - const BigInt& new_r_inv) - { - m_p_dash = new_p_dash; - m_r = new_r; - m_r_inv = new_r_inv; - } - - private: - BigInt m_p; // the modulus itself - BigInt m_p_dash; - BigInt m_r; - BigInt m_r_inv; - }; - -} - -#endif diff --git a/src/math/gfpmath/info.txt b/src/math/gfpmath/info.txt deleted file mode 100644 index b7b430805..000000000 --- a/src/math/gfpmath/info.txt +++ /dev/null @@ -1,19 +0,0 @@ -define BIGINT_GFP - -<header:public> -curve_gfp.h -gfp_element.h -gfp_modulus.h -point_gfp.h -</header:public> - -<source> -curve_gfp.cpp -gfp_element.cpp -point_gfp.cpp -</source> - -<requires> -bigint -numbertheory -</requires> diff --git a/src/math/gfpmath/point_gfp.cpp b/src/math/gfpmath/point_gfp.cpp deleted file mode 100644 index 4b2de7913..000000000 --- a/src/math/gfpmath/point_gfp.cpp +++ /dev/null @@ -1,750 +0,0 @@ -/* -* Arithmetic for point groups of elliptic curves over GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#include <botan/point_gfp.h> -#include <botan/numthry.h> - -namespace Botan { - -// construct the point at infinity or a random point -PointGFp::PointGFp(const CurveGFp& curve) : - mC(curve), - mX(curve.get_p(), 0), - mY(curve.get_p(), 1), - mZ(curve.get_p(), 0) - { - } - -// construct a point given its jacobian projective coordinates -PointGFp::PointGFp(const CurveGFp& curve, const GFpElement& x, - const GFpElement& y, const GFpElement& z) : - mC(curve), - mX(x), - mY(y), - mZ(z) - { - } - -PointGFp::PointGFp(const CurveGFp& curve, - const GFpElement& x, - const GFpElement& y) : - mC(curve), - mX(x), - mY(y), - mZ(curve.get_p(),1) - { - } - -// arithmetic operators -PointGFp& PointGFp::operator+=(const PointGFp& rhs) - { - if(is_zero()) - { - *this = rhs; - return *this; - } - if(rhs.is_zero()) - { - return *this; - } - - GFpElement U1 = mX; - GFpElement S1 = mY; - - if(rhs.mZ != mC.get_mres_one()) - { - GFpElement rhs_z2 = rhs.mZ * rhs.mZ; - - U1 *= rhs_z2; - S1 *= rhs_z2 * rhs.mZ; - } - - GFpElement U2 = rhs.mX; - GFpElement S2 = rhs.mY; - - if(mZ != mC.get_mres_one()) - { - GFpElement lhs_z2 = mZ * mZ; - - U2 *= lhs_z2; - S2 *= lhs_z2 * mZ; - } - - GFpElement H(U2 - U1); - GFpElement r(S2 - S1); - - if(H.is_zero()) - { - if(r.is_zero()) - { - mult2_in_place(); - return *this; - } - - *this = PointGFp(mC); // setting myself to zero - return *this; - } - - U2 = H * H; - - S2 = U2 * H; - - U2 *= U1; - - GFpElement x(r*r - S2 - (U2+U2)); - - GFpElement z(S1 * S2); - - GFpElement y(r * (U2-x) - z); - - if(mZ == mC.get_mres_one()) - { - if(rhs.mZ != mC.get_mres_one()) - z = rhs.mZ * H; - else - z = H; - } - else if(rhs.mZ != mC.get_mres_one()) - { - U1 = mZ * rhs.mZ; - z = U1 * H; - } - else - z = mZ * H; - - mX = x; - mY = y; - mZ = z; - - return *this; - - } -PointGFp& PointGFp::operator-=(const PointGFp& rhs) - { - PointGFp minus_rhs = PointGFp(rhs).negate(); - - if(is_zero()) - { - *this = minus_rhs; - } - else - { - *this += minus_rhs; - } - return *this; - } - -PointGFp& PointGFp::mult_this_secure(const BigInt& scalar, - const BigInt& /*point_order*/, - const BigInt& /*max_secr*/) - { - // NOTE: FS: so far this is code duplication of op*=. - // we have to see how we deal with this. - // fact is that we will probably modify this function - // while evaluating the countermeasures - // whereas we probably will not start modifying the - // function operator*=. - // however, in the end both should be merged. - - // use montgomery mult. in this operation - this->turn_on_sp_red_mul(); - - PointGFp H(mC); - - PointGFp P(*this); - BigInt m(scalar); - - if(m < BigInt(0)) - { - m = -m; - P.negate(); - } - if(P.is_zero() || (m == BigInt(0))) - { - *this = H; - return *this; - } - if(m == BigInt(1)) - return *this; - - int mul_bits = m.bits(); - - for(int i = mul_bits - 1; i >= 0; i--) - { - H.mult2_in_place(); - - if(m.get_bit(i)) - H += P; - } - - if(!H.is_zero()) // cannot convert if H == O - *this = H.get_z_to_one(); - else - *this = H; - - mX.turn_off_sp_red_mul(); - mY.turn_off_sp_red_mul(); - mZ.turn_off_sp_red_mul(); - return *this; - } - -PointGFp& PointGFp::operator*=(const BigInt& scalar) - { - // use montgomery mult. in this operation - - this->turn_on_sp_red_mul(); - - PointGFp H(this->mC); // create as zero - H.turn_on_sp_red_mul(); - PointGFp P(*this); - P.turn_on_sp_red_mul(); - BigInt m(scalar); - - if(m < BigInt(0)) - { - m = -m; - P.negate(); - } - - if(P.is_zero() || (m == BigInt(0))) - { - *this = H; - return *this; - } - - if(m == BigInt(1)) //*this == P already - return *this; - - const int l = m.bits() - 1; - for(int i = l; i >= 0; --i) - { - H.mult2_in_place(); - if(m.get_bit(i)) - H += P; - } - - if(!H.is_zero()) // cannot convert if H == O - *this = H.get_z_to_one(); - else - *this = H; - - return *this; - } - -PointGFp& PointGFp::negate() - { - if(!is_zero()) - mY.negate(); - - return *this; - } - -// *this *= 2 -PointGFp& PointGFp::mult2_in_place() - { - if(is_zero()) - return *this; - else if(mY.is_zero()) - { - *this = PointGFp(mC); // setting myself to zero - return *this; - } - - GFpElement Y_squared = mY*mY; - - GFpElement S = mX * Y_squared; - - GFpElement x = S + S; - - S = x + x; - - GFpElement a_z4 = mC.get_mres_a(); - if(mZ != mC.get_mres_one()) - { - GFpElement z2 = mZ * mZ; - a_z4 *= z2; - a_z4 *= z2; - } - - GFpElement y(mX * mX); - - GFpElement M(y + y + y + a_z4); - - x = M * M - (S+S); - - y = Y_squared * Y_squared; - - GFpElement U(y + y); - - GFpElement z = U + U; - - U = z + z; - - y = M * (S - x) - U; - - if(mZ != mC.get_mres_one()) - z = mY * mZ; - else - z = mY; - - z = z + z; - - mX = x; - mY = y; - mZ = z; - - return *this; - } - -void PointGFp::turn_on_sp_red_mul() const - { - mX.turn_on_sp_red_mul(); - mY.turn_on_sp_red_mul(); - mZ.turn_on_sp_red_mul(); - - // also pretransform, otherwise - // we might have bad results with respect to - // performance because - // additions/subtractions in mult2_in_place() - // and op+= spread untransformed GFpElements - mX.get_mres(); - mY.get_mres(); - mZ.get_mres(); - } - -/** -* returns a point equivalent to *this but were -* Z has value one, i.e. x and y correspond to -* their values in affine coordinates -*/ -PointGFp PointGFp::get_z_to_one() const - { - return PointGFp(*this).set_z_to_one(); - } - -/** -* changes the representation of *this so that -* Z has value one, i.e. x and y correspond to -* their values in affine coordinates. -* returns *this. -*/ -const PointGFp& PointGFp::set_z_to_one() const - { - if(!(mZ.get_value() == BigInt(1)) && !(mZ.get_value() == BigInt(0))) - { - GFpElement z = inverse(mZ); - GFpElement z2 = z * z; - z *= z2; - GFpElement x = mX * z2; - GFpElement y = mY * z; - mZ = GFpElement(mC.get_p(), BigInt(1)); - mX = x; - mY = y; - } - else - { - if(mZ.get_value() == BigInt(0)) - { - throw Illegal_Transformation("cannot convert Z to one"); - } - } - return *this; // mZ = 1 already - } - -GFpElement PointGFp::get_affine_x() const - { - if(is_zero()) - throw Illegal_Transformation("cannot convert to affine"); - - GFpElement z2 = mZ * mZ; - return mX * z2.inverse_in_place(); - } - -GFpElement PointGFp::get_affine_y() const - { - if(is_zero()) - throw Illegal_Transformation("cannot convert to affine"); - - GFpElement z3 = mZ * mZ * mZ; - return mY * z3.inverse_in_place(); - } - -GFpElement PointGFp::get_jac_proj_x() const - { - return GFpElement(mX); - } - -GFpElement PointGFp::get_jac_proj_y() const - { - return GFpElement(mY); - } - -GFpElement PointGFp::get_jac_proj_z() const - { - return GFpElement(mZ); - } - -// Is this the point at infinity? -bool PointGFp::is_zero() const - { - return(mX.is_zero() && mZ.is_zero()); - //NOTE: the calls to GFpElement::is_zero() instead of getting the value and - // and comparing it are import because they do not provoke backtransformations - // to the ordinary residue. - } - -// Is the point still on the curve?? -// (If everything is correct, the point is always on its curve; then the -// function will return silently. If Oskar managed to corrupt this object's state, -// then it will throw an exception.) - -void PointGFp::check_invariants() const - { - if(is_zero()) - { - return; - } - const GFpElement y2 = mY * mY; - const GFpElement x3 = mX * mX * mX; - - if(mZ.get_value() == BigInt(1)) - { - GFpElement ax = mC.get_a() * mX; - if(y2 != (x3 + ax + mC.get_b())) - { - throw Illegal_Point(); - } - - } - - GFpElement Zpow2 = mZ * mZ; - GFpElement Zpow3 = Zpow2 * mZ; - GFpElement AZpow4 = Zpow3 * mZ * mC.get_a(); - const GFpElement aXZ4 = AZpow4 * mX; - const GFpElement bZ6 = mC.get_b() * Zpow3 * Zpow3; - - if(y2 != (x3 + aXZ4 + bZ6)) - throw Illegal_Point(); - } - -// swaps the states of *this and other, does not throw! -void PointGFp::swap(PointGFp& other) - { - mC.swap(other.mC); - mX.swap(other.mX); - mY.swap(other.mY); - mZ.swap(other.mZ); - } - -PointGFp mult2(const PointGFp& point) - { - return (PointGFp(point)).mult2_in_place(); - } - -bool operator==(const PointGFp& lhs, PointGFp const& rhs) - { - if(lhs.is_zero() && rhs.is_zero()) - { - return true; - } - if((lhs.is_zero() && !rhs.is_zero()) || (!lhs.is_zero() && rhs.is_zero())) - { - return false; - } - // neither operand is zero, so we can call get_z_to_one() - //assert(!lhs.is_zero()); - //assert(!rhs.is_zero()); - PointGFp aff_lhs = lhs.get_z_to_one(); - PointGFp aff_rhs = rhs.get_z_to_one(); - return (aff_lhs.get_curve() == aff_rhs.get_curve() && - aff_lhs.get_jac_proj_x() == aff_rhs.get_jac_proj_x() && - aff_lhs.get_jac_proj_y() == aff_rhs.get_jac_proj_y()); - } - -// arithmetic operators -PointGFp operator+(const PointGFp& lhs, PointGFp const& rhs) - { - PointGFp tmp(lhs); - return tmp += rhs; - } - -PointGFp operator-(const PointGFp& lhs, PointGFp const& rhs) - { - PointGFp tmp(lhs); - return tmp -= rhs; - } - -PointGFp operator-(const PointGFp& lhs) - { - return PointGFp(lhs).negate(); - } - -PointGFp operator*(const BigInt& scalar, const PointGFp& point) - { - PointGFp result(point); - return result *= scalar; - } - -PointGFp operator*(const PointGFp& point, const BigInt& scalar) - { - PointGFp result(point); - return result *= scalar; - } - -PointGFp mult_point_secure(const PointGFp& point, const BigInt& scalar, - const BigInt& point_order, const BigInt& max_secret) - { - PointGFp result(point); - result.mult_this_secure(scalar, point_order, max_secret); - return result; - } - -// encoding and decoding -SecureVector<byte> EC2OSP(const PointGFp& point, byte format) - { - SecureVector<byte> result; - if(format == PointGFp::UNCOMPRESSED) - { - result = encode_uncompressed(point); - } - else if(format == PointGFp::COMPRESSED) - { - result = encode_compressed(point); - - } - else if(format == PointGFp::HYBRID) - { - result = encode_hybrid(point); - } - else - { - throw Invalid_Argument("illegal point encoding format specification"); - } - return result; - } -SecureVector<byte> encode_compressed(const PointGFp& point) - { - - - if(point.is_zero()) - { - SecureVector<byte> result (1); - result[0] = 0; - return result; - - } - u32bit l = point.get_curve().get_p().bits(); - int dummy = l & 7; - if(dummy != 0) - { - l += 8 - dummy; - } - l /= 8; - SecureVector<byte> result (l+1); - result[0] = 2; - BigInt x = point.get_affine_x().get_value(); - SecureVector<byte> bX = BigInt::encode_1363(x, l); - result.copy(1, bX.begin(), bX.size()); - BigInt y = point.get_affine_y().get_value(); - if(y.get_bit(0)) - { - result[0] |= 1; - } - return result; - } - - -SecureVector<byte> encode_uncompressed(const PointGFp& point) - { - if(point.is_zero()) - { - SecureVector<byte> result (1); - result[0] = 0; - return result; - } - u32bit l = point.get_curve().get_p().bits(); - int dummy = l & 7; - if(dummy != 0) - { - l += 8 - dummy; - } - l /= 8; - SecureVector<byte> result (2*l+1); - result[0] = 4; - BigInt x = point.get_affine_x().get_value(); - BigInt y = point.get_affine_y().get_value(); - SecureVector<byte> bX = BigInt::encode_1363(x, l); - SecureVector<byte> bY = BigInt::encode_1363(y, l); - result.copy(1, bX.begin(), l); - result.copy(l+1, bY.begin(), l); - return result; - - } - -SecureVector<byte> encode_hybrid(const PointGFp& point) - { - if(point.is_zero()) - { - SecureVector<byte> result (1); - result[0] = 0; - return result; - } - u32bit l = point.get_curve().get_p().bits(); - int dummy = l & 7; - if(dummy != 0) - { - l += 8 - dummy; - } - l /= 8; - SecureVector<byte> result (2*l+1); - result[0] = 6; - BigInt x = point.get_affine_x().get_value(); - BigInt y = point.get_affine_y().get_value(); - SecureVector<byte> bX = BigInt::encode_1363(x, l); - SecureVector<byte> bY = BigInt::encode_1363(y, l); - result.copy(1, bX.begin(), bX.size()); - result.copy(l+1, bY.begin(), bY.size()); - if(y.get_bit(0)) - { - result[0] |= 1; - } - return result; - } - -PointGFp OS2ECP(MemoryRegion<byte> const& os, const CurveGFp& curve) - { - if(os.size() == 1 && os[0] == 0) - { - return PointGFp(curve); // return zero - } - SecureVector<byte> bX; - SecureVector<byte> bY; - - GFpElement x(1,0); - GFpElement y(1,0); - GFpElement z(1,0); - - const byte pc = os[0]; - BigInt bi_dec_x; - BigInt bi_dec_y; - switch (pc) - { - case 2: - case 3: - //compressed form - bX = SecureVector<byte>(os.size() - 1); - bX.copy(os.begin()+1, os.size()-1); - - bi_dec_x = BigInt::decode(bX, bX.size()); - x = GFpElement(curve.get_p(), bi_dec_x); - bool yMod2; - yMod2 = (pc & 1) == 1; - y = PointGFp::decompress(yMod2, x, curve); - break; - case 4: - // uncompressed form - int l; - l = (os.size() -1)/2; - bX = SecureVector<byte>(l); - bY = SecureVector<byte>(l); - bX.copy(os.begin()+1, l); - bY.copy(os.begin()+1+l, l); - bi_dec_x = BigInt::decode(bX.begin(), bX.size()); - - bi_dec_y = BigInt::decode(bY.begin(),bY.size()); - x = GFpElement(curve.get_p(), bi_dec_x); - y = GFpElement(curve.get_p(), bi_dec_y); - break; - - case 6: - case 7: - //hybrid form - l = (os.size() - 1)/2; - bX = SecureVector<byte>(l); - bY = SecureVector<byte>(l); - bX.copy(os.begin() + 1, l); - bY.copy(os.begin()+1+l, l); - yMod2 = (pc & 0x01) == 1; - if(!(PointGFp::decompress(yMod2, x, curve) == y)) - { - throw Illegal_Point("error during decoding hybrid format"); - } - break; - default: - throw Invalid_Argument("encountered illegal format specification while decoding point"); - } - z = GFpElement(curve.get_p(), BigInt(1)); - //assert((x.is_trf_to_mres() && x.is_use_montgm()) || !x.is_trf_to_mres()); - //assert((y.is_trf_to_mres() && y.is_use_montgm()) || !y.is_trf_to_mres()); - //assert((z.is_trf_to_mres() && z.is_use_montgm()) || !z.is_trf_to_mres()); - PointGFp result(curve, x, y, z); - result.check_invariants(); - //assert((result.get_jac_proj_x().is_trf_to_mres() && result.get_jac_proj_x().is_use_montgm()) || !result.get_jac_proj_x().is_trf_to_mres()); - //assert((result.get_jac_proj_y().is_trf_to_mres() && result.get_jac_proj_y().is_use_montgm()) || !result.get_jac_proj_y().is_trf_to_mres()); - //assert((result.get_jac_proj_z().is_trf_to_mres() && result.get_jac_proj_z().is_use_montgm()) || !result.get_jac_proj_z().is_trf_to_mres()); - return result; - } - -GFpElement PointGFp::decompress(bool yMod2, const GFpElement& x, - const CurveGFp& curve) - { - BigInt xVal = x.get_value(); - BigInt xpow3 = xVal * xVal * xVal; - BigInt g = curve.get_a().get_value() * xVal; - g += xpow3; - g += curve.get_b().get_value(); - g = g%curve.get_p(); - BigInt z = ressol(g, curve.get_p()); - - if(z < 0) - throw Illegal_Point("error during decompression"); - - bool zMod2 = z.get_bit(0); - if((zMod2 && ! yMod2) || (!zMod2 && yMod2)) - { - z = curve.get_p() - z; - } - return GFpElement(curve.get_p(),z); - } - -PointGFp create_random_point(RandomNumberGenerator& rng, - const CurveGFp& curve) - { - - // create a random point - GFpElement mX(1,1); - GFpElement mY(1,1); - GFpElement mZ(1,1); - GFpElement minusOne(curve.get_p(), BigInt(BigInt::Negative,1)); - mY = minusOne; - GFpElement y2(1,1); - GFpElement x(1,1); - - while (mY == minusOne) - { - BigInt value(rng, curve.get_p().bits()); - mX = GFpElement(curve.get_p(),value); - y2 = curve.get_a() * mX; - x = mX * mX; - x *= mX; - y2 += (x + curve.get_b()); - - value = ressol(y2.get_value(), curve.get_p()); - - if(value < 0) - mY = minusOne; - else - mY = GFpElement(curve.get_p(), value); - } - mZ = GFpElement(curve.get_p(), BigInt(1)); - - return PointGFp(curve, mX, mY, mZ); - } - -} // namespace Botan diff --git a/src/math/gfpmath/point_gfp.h b/src/math/gfpmath/point_gfp.h deleted file mode 100644 index 276635f56..000000000 --- a/src/math/gfpmath/point_gfp.h +++ /dev/null @@ -1,268 +0,0 @@ -/* -* Arithmetic for point groups of elliptic curves over GF(p) -* -* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke -* 2008-2010 Jack Lloyd -* -* Distributed under the terms of the Botan license -*/ - -#ifndef BOTAN_POINT_GFP_H__ -#define BOTAN_POINT_GFP_H__ - -#include <botan/curve_gfp.h> -#include <vector> - -namespace Botan { - -struct BOTAN_DLL Illegal_Point : public Exception - { - Illegal_Point(const std::string& err = "") : Exception(err) {} - }; - -/** -* This class represents one point on a curve of GF(p) -*/ -class BOTAN_DLL PointGFp - { - public: - /** - * uncompressed encoding byte value - */ - static const int UNCOMPRESSED = 0; - - /** - * compressed encoding byte value - */ - static const int COMPRESSED = 1; - - /** - * hybrid encoding byte value - */ - static const int HYBRID = 2; - - /** - * Construct the point O - * @param curve The base curve - */ - PointGFp(const CurveGFp& curve); - - /** - * Construct a point given its affine coordinates - * @param curve the base curve - * @param x affine x coordinate - * @param y affine y coordinate - */ - PointGFp(const CurveGFp& curve, - const GFpElement& x, - const GFpElement& y); - - /** - * Construct a point given its jacobian projective coordinates - * @param curve the base curve - * @param x jacobian projective x coordinate - * @param y jacobian projective y coordinate - * @param z jacobian projective y coordinate - */ - PointGFp(const CurveGFp& curve, - const GFpElement& x, - const GFpElement& y, - const GFpElement& z); - - //PointGFp(const PointGFp& other) = default; - //PointGFp& operator=(const PointGFp& other) = default; - - /** - * += Operator - * @param rhs the PointGFp to add to the local value - * @result resulting PointGFp - */ - PointGFp& operator+=(const PointGFp& rhs); - - /** - * -= Operator - * @param rhs the PointGFp to subtract from the local value - * @result resulting PointGFp - */ - PointGFp& operator-=(const PointGFp& rhs); - - /** - * *= Operator - * This function turns on the the special reduction multiplication - * itself for fast computation, turns it off again when finished. - * @param scalar the PointGFp to multiply with *this - * @result resulting PointGFp - */ - PointGFp& operator*=(const BigInt& scalar); - - /** - * the equivalent to operator*= with countermeasures against - * sidechannel attacks, using the randomized exponent - * and add-and-double-always - * countermeasures (suitable for ECDSA and ECKAEG) - * @param scalar the scalar to multiply the point with - * @param point_order a multiple of the order of the point - *(= n * k in the general case; k is the cofactor) - * @param max_secr the maximal size of the scalar - * (will usually be n-1 ) - * @result resulting PointGFp - */ - PointGFp& mult_this_secure(const BigInt& scalar, - const BigInt& point_order, - const BigInt& max_secr); - - /** - * Negate internal value(*this *= -1 ) - * @return *this - */ - PointGFp& negate(); - - /** - * Multiply the point by two(*this *= 2 ) - * @return *this - */ - PointGFp& mult2_in_place(); - - /** - * Set z coordinate to one. - * @return *this - */ - const PointGFp& set_z_to_one() const; - - /** - * Turn on the special reduction multiplication (i.e. the - * Montgomery multiplication in the current implementation) for - * the coordinates. This enables fast execution of mult2_in_place() - * and operator+=(). - */ - void turn_on_sp_red_mul() const; - - /** - * Return a point - * where the coordinates are transformed - * so that z equals one, - * thus x and y have just the affine values. - * @result *this - */ - PointGFp get_z_to_one() const; - - /** - * Return base curve of this point - * @result the curve over GF(p) of this point - */ - const CurveGFp& get_curve() const { return mC; } - - /** - * get affine x coordinate - * @result affine x coordinate - */ - GFpElement get_affine_x() const; - - /** - * get affine y coordinate - * @result affine y coordinate - */ - GFpElement get_affine_y() const; - - /** - * get the jacobian projective x coordinate - * @result jacobian projective x coordinate - */ - GFpElement get_jac_proj_x() const; - - /** - * get the jacobian projective y coordinate - * @result jacobian projective y coordinate - */ - GFpElement get_jac_proj_y() const; - - /** - * get the jacobian projective z coordinate - * @result jacobian projective z coordinate - */ - GFpElement get_jac_proj_z() const; - - /** - * Is this the point at infinity? - * @result true, if this point is at infinity, false otherwise. - */ - bool is_zero() const; - - /** - * Checks whether the point is to be found on the underlying curve. - * Throws an Invalid_Point exception in case of detecting that the point - * does not satisfy the curve equation. - * To be used to ensure against fault attacks. - */ - void check_invariants() const; - - /** - * swaps the states of *this and other, does not throw! - * @param other the object to swap values with - */ - void swap(PointGFp& other); - - static GFpElement decompress(bool yMod2, GFpElement const& x, const CurveGFp& curve); - - private: - CurveGFp mC; - mutable GFpElement mX; // NOTE: these values must be mutable (affine<->proj) - mutable GFpElement mY; - mutable GFpElement mZ; - }; - -// relational operators -bool BOTAN_DLL operator==(const PointGFp& lhs, const PointGFp& rhs); -inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs ) - { - return !operator==(lhs, rhs); - } - -// arithmetic operators -PointGFp BOTAN_DLL operator+(const PointGFp& lhs, const PointGFp& rhs); -PointGFp BOTAN_DLL operator-(const PointGFp& lhs, const PointGFp& rhs); -PointGFp BOTAN_DLL operator-(const PointGFp& lhs); - -PointGFp BOTAN_DLL operator*(const BigInt& scalar, const PointGFp& point); -PointGFp BOTAN_DLL operator*(const PointGFp& point, const BigInt& scalar); -PointGFp BOTAN_DLL mult_point_secure(const PointGFp& point, - const BigInt& scalar, - const BigInt& point_order, - const BigInt& max_secret); - -PointGFp BOTAN_DLL mult2(const PointGFp& point); - -PointGFp BOTAN_DLL create_random_point(RandomNumberGenerator& rng, - const CurveGFp& curve); - -// encoding and decoding -SecureVector<byte> BOTAN_DLL EC2OSP(const PointGFp& point, byte format); -PointGFp BOTAN_DLL OS2ECP(MemoryRegion<byte> const& os, const CurveGFp& curve); - -/* Should these be private? */ -SecureVector<byte> -BOTAN_DLL encode_uncompressed(const PointGFp& point); - -SecureVector<byte> BOTAN_DLL encode_hybrid(const PointGFp& point); -SecureVector<byte> BOTAN_DLL encode_compressed(const PointGFp& point); - -// swaps the states of point1 and point2, does not throw! -// cf. Meyers, Item 25 -inline -void swap(PointGFp& point1, PointGFp& point2 ) - { - point1.swap(point2); - } - -} // namespace Botan - -namespace std { - -// swaps the states of point1 and point2, does not throw! -// cf. Meyers, Item 25 -template<> inline void -swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y) { x.swap(y); } - -} // namespace std - -#endif diff --git a/src/math/numbertheory/curve_gfp.h b/src/math/numbertheory/curve_gfp.h new file mode 100644 index 000000000..697065dfe --- /dev/null +++ b/src/math/numbertheory/curve_gfp.h @@ -0,0 +1,96 @@ +/* +* Elliptic curves over GF(p) +* +* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2010 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_GFP_CURVE_H__ +#define BOTAN_GFP_CURVE_H__ + +#include <botan/numthry.h> +#include <botan/reducer.h> + +namespace Botan { + +/** +* This class represents an elliptic curve over GF(p) +*/ +class BOTAN_DLL CurveGFp + { + public: + + /** + * Construct the elliptic curve E: y^2 = x^3 + ax + b over GF(p) + * @param p prime number of the field + * @param a first coefficient + * @param b second coefficient + */ + CurveGFp(const BigInt& p, const BigInt& a, const BigInt& b) : + p(p), a(a), b(b), reducer_p(p) {} + + // CurveGFp(const CurveGFp& other) = default; + // CurveGFp& operator=(const CurveGFp& other) = default; + + /** + * Get coefficient a + * @result coefficient a + */ + const BigInt& get_a() const { return a; } + + /** + * Get coefficient b + * @result coefficient b + */ + const BigInt& get_b() const { return b; } + + /** + * Get prime modulus of the field of the curve + * @result prime modulus of the field of the curve + */ + const BigInt& get_p() const { return p; } + + const Modular_Reducer& mod_p() const { return reducer_p; } + + /** + * swaps the states of *this and other, does not throw + * @param other The curve to swap values with + */ + void swap(CurveGFp& other) + { + std::swap(a, other.a); + std::swap(b, other.b); + std::swap(p, other.p); + } + + bool operator==(const CurveGFp& other) const + { + return (p == other.p && a == other.a && b == other.b); + } + + private: + BigInt p, a, b; + Modular_Reducer reducer_p; + }; + +inline bool operator!=(const CurveGFp& lhs, const CurveGFp& rhs) + { + return !(lhs == rhs); + } + +} + +namespace std { + +template<> inline +void swap<Botan::CurveGFp>(Botan::CurveGFp& curve1, + Botan::CurveGFp& curve2) + { + curve1.swap(curve2); + } + +} // namespace std + +#endif diff --git a/src/math/numbertheory/info.txt b/src/math/numbertheory/info.txt index 19abfaaa0..58851e055 100644 --- a/src/math/numbertheory/info.txt +++ b/src/math/numbertheory/info.txt @@ -4,7 +4,9 @@ define BIGINT_MATH <header:public> blinding.h +curve_gfp.h numthry.h +point_gfp.h pow_mod.h reducer.h </header:public> @@ -20,6 +22,7 @@ jacobi.cpp make_prm.cpp mp_numth.cpp numthry.cpp +point_gfp.cpp pow_mod.cpp powm_fw.cpp powm_mnt.cpp diff --git a/src/math/numbertheory/numthry.cpp b/src/math/numbertheory/numthry.cpp index 760250712..f79fdec2b 100644 --- a/src/math/numbertheory/numthry.cpp +++ b/src/math/numbertheory/numthry.cpp @@ -1,11 +1,12 @@ /* * Number Theory Functions -* (C) 1999-2009 Jack Lloyd +* (C) 1999-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ #include <botan/numthry.h> +#include <botan/reducer.h> #include <botan/internal/bit_ops.h> #include <algorithm> @@ -14,6 +15,62 @@ namespace Botan { namespace { /* +* Miller-Rabin Primality Tester +*/ +class MillerRabin_Test + { + public: + bool passes_test(const BigInt& nonce); + MillerRabin_Test(const BigInt& num); + private: + BigInt n, r, n_minus_1; + u32bit s; + Fixed_Exponent_Power_Mod pow_mod; + Modular_Reducer reducer; + }; + +/* +* Miller-Rabin Test +*/ +bool MillerRabin_Test::passes_test(const BigInt& a) + { + if(a < 2 || a >= n_minus_1) + throw Invalid_Argument("Bad size for nonce in Miller-Rabin test"); + + BigInt y = pow_mod(a); + if(y == 1 || y == n_minus_1) + return true; + + for(u32bit i = 1; i != s; ++i) + { + y = reducer.square(y); + + if(y == 1) + return false; + if(y == n_minus_1) + return true; + } + return false; + } + +/* +* Miller-Rabin Constructor +*/ +MillerRabin_Test::MillerRabin_Test(const BigInt& num) + { + if(num.is_even() || num < 3) + throw Invalid_Argument("MillerRabin_Test: Invalid number for testing"); + + n = num; + n_minus_1 = n - 1; + s = low_zero_bits(n_minus_1); + r = n_minus_1 >> s; + + pow_mod = Fixed_Exponent_Power_Mod(r, n); + reducer = Modular_Reducer(n); + } + +/* * Miller-Rabin Iterations */ u32bit miller_rabin_test_iterations(u32bit bits, bool verify) @@ -300,45 +357,4 @@ bool passes_mr_tests(RandomNumberGenerator& rng, return true; } -/* -* Miller-Rabin Test -*/ -bool MillerRabin_Test::passes_test(const BigInt& a) - { - if(a < 2 || a >= n_minus_1) - throw Invalid_Argument("Bad size for nonce in Miller-Rabin test"); - - BigInt y = pow_mod(a); - if(y == 1 || y == n_minus_1) - return true; - - for(u32bit i = 1; i != s; ++i) - { - y = reducer.square(y); - - if(y == 1) - return false; - if(y == n_minus_1) - return true; - } - return false; - } - -/* -* Miller-Rabin Constructor -*/ -MillerRabin_Test::MillerRabin_Test(const BigInt& num) - { - if(num.is_even() || num < 3) - throw Invalid_Argument("MillerRabin_Test: Invalid number for testing"); - - n = num; - n_minus_1 = n - 1; - s = low_zero_bits(n_minus_1); - r = n_minus_1 >> s; - - pow_mod = Fixed_Exponent_Power_Mod(r, n); - reducer = Modular_Reducer(n); - } - } diff --git a/src/math/numbertheory/numthry.h b/src/math/numbertheory/numthry.h index ae2c219fc..080f184a4 100644 --- a/src/math/numbertheory/numthry.h +++ b/src/math/numbertheory/numthry.h @@ -9,7 +9,6 @@ #define BOTAN_NUMBER_THEORY_H__ #include <botan/bigint.h> -#include <botan/reducer.h> #include <botan/pow_mod.h> #include <botan/rng.h> @@ -100,21 +99,6 @@ const u32bit PRIME_PRODUCTS_TABLE_SIZE = 256; extern const u16bit BOTAN_DLL PRIMES[]; extern const u64bit PRIME_PRODUCTS[]; -/* -* Miller-Rabin Primality Tester -*/ -class BOTAN_DLL MillerRabin_Test - { - public: - bool passes_test(const BigInt&); - MillerRabin_Test(const BigInt&); - private: - BigInt n, r, n_minus_1; - u32bit s; - Fixed_Exponent_Power_Mod pow_mod; - Modular_Reducer reducer; - }; - } #endif diff --git a/src/math/numbertheory/point_gfp.cpp b/src/math/numbertheory/point_gfp.cpp new file mode 100644 index 000000000..06c42d18c --- /dev/null +++ b/src/math/numbertheory/point_gfp.cpp @@ -0,0 +1,423 @@ +/* +* Arithmetic for point groups of elliptic curves over GF(p) +* +* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2008-2010 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#include <botan/point_gfp.h> +#include <botan/numthry.h> + +namespace Botan { + +namespace { + +BigInt decompress_point(bool yMod2, + const BigInt& x, + const CurveGFp& curve) + { + BigInt xpow3 = x * x * x; + + BigInt g = curve.get_a() * x; + g += xpow3; + g += curve.get_b(); + g = g % curve.get_p(); + + BigInt z = ressol(g, curve.get_p()); + + if(z < 0) + throw Illegal_Point("error during decompression"); + + if(z.get_bit(0) != yMod2) + z = curve.get_p() - z; + + return z; + } + +} + +// arithmetic operators +PointGFp& PointGFp::operator+=(const PointGFp& rhs) + { + if(rhs.is_zero()) + return *this; + + if(is_zero()) + { + *this = rhs; + return *this; + } + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt rhs_z2 = mod_p.square(rhs.coord_z); + BigInt U1 = mod_p.multiply(coord_x, rhs_z2); + BigInt S1 = mod_p.multiply(coord_y, mod_p.multiply(rhs.coord_z, rhs_z2)); + + BigInt lhs_z2 = mod_p.square(coord_z); + BigInt U2 = mod_p.multiply(rhs.coord_x, lhs_z2); + BigInt S2 = mod_p.multiply(rhs.coord_y, mod_p.multiply(coord_z, lhs_z2)); + + BigInt H = mod_p.reduce(U2 - U1); + BigInt r = mod_p.reduce(S2 - S1); + + if(H.is_zero()) + { + if(r.is_zero()) + { + mult2_in_place(); + return *this; + } + + *this = PointGFp(curve); // setting myself to zero + return *this; + } + + U2 = mod_p.square(H); + + S2 = mod_p.multiply(U2, H); + + U2 = mod_p.multiply(U1, U2); + + BigInt x = mod_p.reduce(mod_p.square(r) - S2 - mod_p.multiply(2, U2)); + BigInt y = mod_p.reduce(mod_p.multiply(r, (U2-x)) - mod_p.multiply(S1, S2)); + BigInt z = mod_p.multiply(mod_p.multiply(coord_z, rhs.coord_z), H); + + coord_x = x; + coord_y = y; + coord_z = z; + + return *this; + } + +PointGFp& PointGFp::operator-=(const PointGFp& rhs) + { + PointGFp minus_rhs = PointGFp(rhs).negate(); + + if(is_zero()) + *this = minus_rhs; + else + *this += minus_rhs; + + return *this; + } + +PointGFp& PointGFp::operator*=(const BigInt& scalar) + { + if(scalar.abs() <= 2) // special cases for small values + { + u32bit value = scalar.abs().to_u32bit(); + + if(value == 0) + *this = PointGFp(curve); // set to zero point + else if(value == 1) + { + if(scalar.is_negative()) + this->negate(); + } + else if(value == 2) + { + this->mult2_in_place(); + if(scalar.is_negative()) + this->negate(); + } + + return *this; + } + + PointGFp H(this->curve); // create as zero + PointGFp P(*this); + + if(scalar.is_negative()) + P.negate(); + + for(int i = scalar.bits() - 1; i >= 0; --i) + { + H.mult2_in_place(); + if(scalar.get_bit(i)) + H += P; + } + + if(!H.is_zero()) // cannot convert if H == O + { + /** + * Convert H to an equivalent point with z == 1, thus x and y + * correspond to their affine coordinates + */ + if(H.coord_z != 1) + { + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt z_inv = inverse_mod(H.coord_z, curve.get_p()); + + BigInt z_inv_2 = mod_p.square(z_inv); + + H.coord_x = mod_p.multiply(H.coord_x, z_inv_2); + H.coord_y = mod_p.multiply(H.coord_y, mod_p.multiply(z_inv, z_inv_2)); + H.coord_z = 1; + } + } + + *this = H; + return *this; + } + +PointGFp& PointGFp::negate() + { + if(!is_zero()) + coord_y = curve.get_p() - coord_y; + + return *this; + } + +// *this *= 2 +void PointGFp::mult2_in_place() + { + if(is_zero()) + return; + else if(coord_y.is_zero()) + { + *this = PointGFp(curve); // setting myself to zero + return; + } + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt y_2 = mod_p.square(coord_y); + + BigInt S = mod_p.multiply(4, mod_p.multiply(coord_x, y_2)); + + BigInt a_z4 = mod_p.multiply(curve.get_a(), + mod_p.square(mod_p.square(coord_z))); + + BigInt M = mod_p.reduce(a_z4 + 3 * mod_p.square(coord_x)); + + BigInt x = mod_p.reduce(mod_p.square(M) - mod_p.multiply(2, S)); + + BigInt y = mod_p.square(y_2); + + BigInt z = mod_p.multiply(2, mod_p.reduce(y + y)); + + BigInt U = mod_p.reduce(z + z); + + y = mod_p.reduce(mod_p.multiply(M, S - x) - U); + + z = mod_p.multiply(2, mod_p.multiply(coord_y, coord_z)); + + coord_x = x; + coord_y = y; + coord_z = z; + } + +BigInt PointGFp::get_affine_x() const + { + if(is_zero()) + throw Illegal_Transformation("cannot convert to affine"); + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt z2 = mod_p.square(coord_z); + return mod_p.multiply(coord_x, inverse_mod(z2, curve.get_p())); + } + +BigInt PointGFp::get_affine_y() const + { + if(is_zero()) + throw Illegal_Transformation("cannot convert to affine"); + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt z3 = mod_p.cube(coord_z); + return mod_p.multiply(coord_y, inverse_mod(z3, curve.get_p())); + } + +// Is this the point at infinity? +bool PointGFp::is_zero() const + { + return(coord_x.is_zero() && coord_z.is_zero()); + } + +void PointGFp::check_invariants() const + { + /* + Is the point still on the curve?? (If everything is correct, the + point is always on its curve; then the function will return + silently. If Oskar managed to corrupt this object's state, then it + will throw an exception.) + */ + + if(is_zero()) + return; + + const Modular_Reducer& mod_p = curve.mod_p(); + + BigInt y2 = mod_p.square(coord_y); + BigInt x3 = mod_p.cube(coord_x); + + BigInt ax = mod_p.multiply(coord_x, curve.get_a()); + + if(coord_z == 1) + { + if(mod_p.reduce(x3 + ax + curve.get_b()) != y2) + throw Illegal_Point("Invalid ECP point: y^2 != x^3 + a*x + b"); + } + + BigInt z2 = mod_p.square(coord_z); + BigInt z3 = mod_p.multiply(coord_z, z2); + + BigInt ax_z4 = mod_p.multiply(mod_p.multiply(z3, coord_z), ax); + + BigInt b_z6 = mod_p.multiply(curve.get_b(), mod_p.square(z3)); + + if(y2 != mod_p.reduce(x3 + ax_z4 + b_z6)) + throw Illegal_Point("Invalid ECP point: y^2 != x^3 + a*x*z^4 + b*z^6"); + } + +// swaps the states of *this and other, does not throw! +void PointGFp::swap(PointGFp& other) + { + curve.swap(other.curve); + coord_x.swap(other.coord_x); + coord_y.swap(other.coord_y); + coord_z.swap(other.coord_z); + } + +bool PointGFp::operator==(const PointGFp& other) const + { + return (coord_x == other.coord_x && + coord_y == other.coord_y && + coord_z == other.coord_z && + get_curve() == other.get_curve()); + } + +// arithmetic operators +PointGFp operator+(const PointGFp& lhs, PointGFp const& rhs) + { + PointGFp tmp(lhs); + return tmp += rhs; + } + +PointGFp operator-(const PointGFp& lhs, PointGFp const& rhs) + { + PointGFp tmp(lhs); + return tmp -= rhs; + } + +PointGFp operator-(const PointGFp& lhs) + { + return PointGFp(lhs).negate(); + } + +PointGFp operator*(const BigInt& scalar, const PointGFp& point) + { + PointGFp result(point); + return result *= scalar; + } + +PointGFp operator*(const PointGFp& point, const BigInt& scalar) + { + PointGFp result(point); + return result *= scalar; + } + +// encoding and decoding +SecureVector<byte> EC2OSP(const PointGFp& point, byte format) + { + if(point.is_zero()) + return SecureVector<byte>(1); // single 0 byte + + const u32bit p_bytes = point.get_curve().get_p().bytes(); + + BigInt x = point.get_affine_x(); + BigInt y = point.get_affine_y(); + + SecureVector<byte> bX = BigInt::encode_1363(x, p_bytes); + SecureVector<byte> bY = BigInt::encode_1363(y, p_bytes); + + if(format == PointGFp::UNCOMPRESSED) + { + SecureVector<byte> result(2*p_bytes+1); + result[0] = 4; + + result.copy(1, bX.begin(), p_bytes); + result.copy(p_bytes+1, bY.begin(), p_bytes); + return result; + } + else if(format == PointGFp::COMPRESSED) + { + SecureVector<byte> result(p_bytes+1); + result[0] = 2; + + result.copy(1, bX.begin(), bX.size()); + + if(y.get_bit(0)) + result[0] |= 1; + + return result; + } + else if(format == PointGFp::HYBRID) + { + SecureVector<byte> result(2*p_bytes+1); + result[0] = 6; + + result.copy(1, bX.begin(), bX.size()); + result.copy(p_bytes+1, bY.begin(), bY.size()); + + if(y.get_bit(0)) + result[0] |= 1; + + return result; + } + else + throw Invalid_Argument("illegal point encoding format specification"); + } + +PointGFp OS2ECP(const MemoryRegion<byte>& os, const CurveGFp& curve) + { + if(os.size() == 1 && os[0] == 0) + return PointGFp(curve); // return zero + + const byte pc = os[0]; + + BigInt x, y; + + if(pc == 2 || pc == 3) + { + //compressed form + x = BigInt::decode(&os[1], os.size() - 1); + + bool yMod2 = ((pc & 0x01) == 1); + y = decompress_point(yMod2, x, curve); + } + else if(pc == 4) + { + // uncompressed form + u32bit l = (os.size() - 1) / 2; + + x = BigInt::decode(&os[1], l); + y = BigInt::decode(&os[l+1], l); + } + else if(pc == 6 || pc == 7) + { + // hybrid form + u32bit l = (os.size() - 1) / 2; + + x = BigInt::decode(&os[1], l); + y = BigInt::decode(&os[l+1], l); + + bool yMod2 = ((pc & 0x01) == 1); + + if(decompress_point(yMod2, x, curve) != y) + throw Illegal_Point("OS2ECP: Decoding error in hybrid format"); + } + else + throw Invalid_Argument("OS2ECP: Unknown format type"); + + PointGFp result(curve, x, y); + result.check_invariants(); + return result; + } + +} diff --git a/src/math/numbertheory/point_gfp.h b/src/math/numbertheory/point_gfp.h new file mode 100644 index 000000000..0741b5e56 --- /dev/null +++ b/src/math/numbertheory/point_gfp.h @@ -0,0 +1,201 @@ +/* +* Arithmetic for point groups of elliptic curves over GF(p) +* +* (C) 2007 Martin Doering, Christoph Ludwig, Falko Strenzke +* 2008-2010 Jack Lloyd +* +* Distributed under the terms of the Botan license +*/ + +#ifndef BOTAN_POINT_GFP_H__ +#define BOTAN_POINT_GFP_H__ + +#include <botan/curve_gfp.h> +#include <vector> + +namespace Botan { + +struct BOTAN_DLL Illegal_Transformation : public Exception + { + Illegal_Transformation(const std::string& err = + "Requested transformation is not possible") : + Exception(err) {} + }; + +struct BOTAN_DLL Illegal_Point : public Exception + { + Illegal_Point(const std::string& err = "Malformed ECP point detected") : + Exception(err) {} + }; + +/** +* This class represents one point on a curve of GF(p) +*/ +class BOTAN_DLL PointGFp + { + public: + enum Compression_Type { + UNCOMPRESSED = 0, + COMPRESSED = 1, + HYBRID = 2 + }; + + /** + * Construct the point O + * @param curve The base curve + */ + PointGFp(const CurveGFp& curve) : + curve(curve), coord_x(0), coord_y(1), coord_z(0) {} + + /** + * Construct a point given its affine coordinates + * @param curve the base curve + * @param x affine x coordinate + * @param y affine y coordinate + */ + PointGFp(const CurveGFp& curve, + const BigInt& x, const BigInt& y) : + curve(curve), coord_x(x), coord_y(y), coord_z(1) {} + + /** + * Construct a point given its jacobian projective coordinates + * @param curve the base curve + * @param x jacobian projective x coordinate + * @param y jacobian projective y coordinate + * @param z jacobian projective z coordinate + */ + PointGFp(const CurveGFp& curve, + const BigInt& x, const BigInt& y, const BigInt& z) : + curve(curve), coord_x(x), coord_y(y), coord_z(z) {} + + //PointGFp(const PointGFp& other) = default; + //PointGFp& operator=(const PointGFp& other) = default; + + /** + * += Operator + * @param rhs the PointGFp to add to the local value + * @result resulting PointGFp + */ + PointGFp& operator+=(const PointGFp& rhs); + + /** + * -= Operator + * @param rhs the PointGFp to subtract from the local value + * @result resulting PointGFp + */ + PointGFp& operator-=(const PointGFp& rhs); + + /** + * *= Operator + * This function turns on the the special reduction multiplication + * itself for fast computation, turns it off again when finished. + * @param scalar the PointGFp to multiply with *this + * @result resulting PointGFp + */ + PointGFp& operator*=(const BigInt& scalar); + + /** + * Negate this point + * @return *this + */ + PointGFp& negate(); + + /** + * Return base curve of this point + * @result the curve over GF(p) of this point + */ + const CurveGFp& get_curve() const { return curve; } + + /** + * get affine x coordinate + * @result affine x coordinate + */ + BigInt get_affine_x() const; + + /** + * get affine y coordinate + * @result affine y coordinate + */ + BigInt get_affine_y() const; + + /** + * get the jacobian projective x coordinate + * @result jacobian projective x coordinate + */ + const BigInt& get_jac_proj_x() const { return coord_x; } + + /** + * get the jacobian projective y coordinate + * @result jacobian projective y coordinate + */ + const BigInt& get_jac_proj_y() const { return coord_y; } + + /** + * get the jacobian projective z coordinate + * @result jacobian projective z coordinate + */ + const BigInt& get_jac_proj_z() const { return coord_z; } + + /** + * Is this the point at infinity? + * @result true, if this point is at infinity, false otherwise. + */ + bool is_zero() const; + + /** + * Checks whether the point is to be found on the underlying curve. + * Throws an Invalid_Point exception in case of detecting that the point + * does not satisfy the curve equation. + * To be used to ensure against fault attacks. + */ + void check_invariants() const; + + /** + * swaps the states of *this and other, does not throw! + * @param other the object to swap values with + */ + void swap(PointGFp& other); + + /** + * Equality operator + */ + bool operator==(const PointGFp& other) const; + private: + /** + * Multiply the point by two + */ + void mult2_in_place(); + + CurveGFp curve; + BigInt coord_x, coord_y, coord_z; + }; + +// relational operators +inline bool operator!=(const PointGFp& lhs, const PointGFp& rhs) + { + return !(rhs == lhs); + } + +// arithmetic operators +PointGFp BOTAN_DLL operator+(const PointGFp& lhs, const PointGFp& rhs); +PointGFp BOTAN_DLL operator-(const PointGFp& lhs, const PointGFp& rhs); +PointGFp BOTAN_DLL operator-(const PointGFp& lhs); + +PointGFp BOTAN_DLL operator*(const BigInt& scalar, const PointGFp& point); +PointGFp BOTAN_DLL operator*(const PointGFp& point, const BigInt& scalar); + +// encoding and decoding +SecureVector<byte> BOTAN_DLL EC2OSP(const PointGFp& point, byte format); +PointGFp BOTAN_DLL OS2ECP(const MemoryRegion<byte>& os, const CurveGFp& curve); + +} + +namespace std { + +template<> +inline void swap<Botan::PointGFp>(Botan::PointGFp& x, Botan::PointGFp& y) + { x.swap(y); } + +} + +#endif diff --git a/src/math/numbertheory/reducer.cpp b/src/math/numbertheory/reducer.cpp index aa53f1a0e..257ece56e 100644 --- a/src/math/numbertheory/reducer.cpp +++ b/src/math/numbertheory/reducer.cpp @@ -1,12 +1,11 @@ /* * Modular Reducer -* (C) 1999-2007 Jack Lloyd +* (C) 1999-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ #include <botan/reducer.h> -#include <botan/numthry.h> #include <botan/internal/mp_core.h> namespace Botan { @@ -78,20 +77,4 @@ BigInt Modular_Reducer::reduce(const BigInt& x) const return t1; } -/* -* Multiply, followed by a reduction -*/ -BigInt Modular_Reducer::multiply(const BigInt& x, const BigInt& y) const - { - return reduce(x * y); - } - -/* -* Square, followed by a reduction -*/ -BigInt Modular_Reducer::square(const BigInt& x) const - { - return reduce(Botan::square(x)); - } - } diff --git a/src/math/numbertheory/reducer.h b/src/math/numbertheory/reducer.h index d234e0735..80c0f27e1 100644 --- a/src/math/numbertheory/reducer.h +++ b/src/math/numbertheory/reducer.h @@ -1,14 +1,14 @@ /* * Modular Reducer -* (C) 1999-2007 Jack Lloyd +* (C) 1999-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ -#ifndef BOTAN_MODARITH_H__ -#define BOTAN_MODARITH_H__ +#ifndef BOTAN_MODULAR_REDUCER_H__ +#define BOTAN_MODULAR_REDUCER_H__ -#include <botan/bigint.h> +#include <botan/numthry.h> namespace Botan { @@ -18,14 +18,30 @@ namespace Botan { class BOTAN_DLL Modular_Reducer { public: - BigInt multiply(const BigInt&, const BigInt&) const; - BigInt square(const BigInt&) const; - BigInt reduce(const BigInt&) const; + BigInt reduce(const BigInt& x) const; + + /** + * Multiply mod p + */ + BigInt multiply(const BigInt& x, const BigInt& y) const + { return reduce(x * y); } + + /** + * Square mod p + */ + BigInt square(const BigInt& x) const + { return reduce(Botan::square(x)); } + + /** + * Cube mod p + */ + BigInt cube(const BigInt& x) const + { return multiply(x, this->square(x)); } bool initialized() const { return (mod_words != 0); } Modular_Reducer() { mod_words = 0; } - Modular_Reducer(const BigInt&); + Modular_Reducer(const BigInt& mod); private: BigInt modulus, modulus_2, mu; u32bit mod_words, mod2_words, mu_words; diff --git a/src/pubkey/ec_dompar/ec_dompar.cpp b/src/pubkey/ec_dompar/ec_dompar.cpp index 3719153f0..30a121875 100644 --- a/src/pubkey/ec_dompar/ec_dompar.cpp +++ b/src/pubkey/ec_dompar/ec_dompar.cpp @@ -429,18 +429,19 @@ EC_Domain_Params get_ec_dompar(const std::string& oid) std::vector<std::string> dom_par = get_standard_domain_parameter(oid); BigInt p(dom_par[0]); // give as 0x... - GFpElement a(p, BigInt(dom_par[1])); - GFpElement b(p, BigInt(dom_par[2])); + BigInt a(dom_par[1]); + BigInt b(dom_par[2]); + BigInt order(dom_par[4]); + BigInt cofactor(dom_par[5]); Pipe pipe(new Hex_Decoder); pipe.process_msg(dom_par[3]); SecureVector<byte> sv_g = pipe.read_all(); - CurveGFp curve(a, b, p); - PointGFp G = OS2ECP ( sv_g, curve ); + CurveGFp curve(p, a, b); + + PointGFp G = OS2ECP(sv_g, curve); G.check_invariants(); - BigInt order(dom_par[4]); - BigInt cofactor(dom_par[5]); EC_Domain_Params result(curve, G, order, cofactor); return result; } @@ -465,32 +466,32 @@ EC_Domain_Params::EC_Domain_Params(const CurveGFp& curve, const PointGFp& base_p namespace { -SecureVector<byte> encode_der_ec_dompar_explicit(EC_Domain_Params const& dom_pars) +SecureVector<byte> encode_der_ec_dompar_explicit(const EC_Domain_Params& dom_pars) { u32bit ecpVers1 = 1; OID curve_type_oid("1.2.840.10045.1.1"); - DER_Encoder der; + const u32bit p_bytes = dom_pars.get_curve().get_p().bytes(); - der.start_cons(SEQUENCE) + return DER_Encoder() + .start_cons(SEQUENCE) .encode(ecpVers1) .start_cons(SEQUENCE) .encode(curve_type_oid) .encode(dom_pars.get_curve().get_p()) .end_cons() .start_cons(SEQUENCE) - .encode(FE2OSP ( dom_pars.get_curve().get_a() ), OCTET_STRING) - .encode(FE2OSP ( dom_pars.get_curve().get_b() ), OCTET_STRING) + .encode(BigInt::encode_1363(dom_pars.get_curve().get_a(), p_bytes), OCTET_STRING) + .encode(BigInt::encode_1363(dom_pars.get_curve().get_b(), p_bytes), OCTET_STRING) .end_cons() .encode(EC2OSP ( dom_pars.get_base_point(), PointGFp::UNCOMPRESSED), OCTET_STRING) .encode(dom_pars.get_order()) .encode(dom_pars.get_cofactor()) - .end_cons(); - - return der.get_contents(); + .end_cons() + .get_contents(); } -EC_Domain_Params decode_ber_ec_dompar_explicit(SecureVector<byte> const& encoded) +EC_Domain_Params decode_ber_ec_dompar_explicit(const SecureVector<byte>& encoded) { BigInt ecpVers1(1); OID curve_type_oid; @@ -500,35 +501,37 @@ EC_Domain_Params decode_ber_ec_dompar_explicit(SecureVector<byte> const& encoded SecureVector<byte> sv_base_point; BigInt order; BigInt cofactor; - BER_Decoder dec(encoded); - dec - .start_cons(SEQUENCE) - .decode(ecpVers1) - .start_cons(SEQUENCE) - .decode(curve_type_oid) - .decode(p) - .end_cons() + + BER_Decoder(encoded) .start_cons(SEQUENCE) - .decode(sv_a, OCTET_STRING) - .decode(sv_b, OCTET_STRING) + .decode(ecpVers1) + .start_cons(SEQUENCE) + .decode(curve_type_oid) + .decode(p) + .end_cons() + .start_cons(SEQUENCE) + .decode(sv_a, OCTET_STRING) + .decode(sv_b, OCTET_STRING) + .end_cons() + .decode(sv_base_point, OCTET_STRING) + .decode(order) + .decode(cofactor) .end_cons() - .decode(sv_base_point, OCTET_STRING) - .decode(order) - .decode(cofactor) - .verify_end() - .end_cons(); + .verify_end(); + if(ecpVers1 != 1) - { throw Decoding_Error("wrong ecpVers"); - } + // Set the domain parameters if(curve_type_oid.as_string() != "1.2.840.10045.1.1") // NOTE: hardcoded: prime field type { throw Decoding_Error("wrong curve type oid where prime field was expected"); } - GFpElement a(p,BigInt::decode(sv_a, sv_a.size())); - GFpElement b(p,BigInt::decode(sv_b, sv_b.size())); - CurveGFp curve(a,b,p); + + CurveGFp curve(p, + BigInt::decode(sv_a, sv_a.size()), + BigInt::decode(sv_b, sv_b.size())); + PointGFp G = OS2ECP ( sv_base_point, curve ); G.check_invariants(); return EC_Domain_Params(curve, G, order, cofactor); @@ -536,7 +539,7 @@ EC_Domain_Params decode_ber_ec_dompar_explicit(SecureVector<byte> const& encoded } // end anonymous namespace -SecureVector<byte> encode_der_ec_dompar(EC_Domain_Params const& dom_pars, EC_dompar_enc enc_type) +SecureVector<byte> encode_der_ec_dompar(const EC_Domain_Params& dom_pars, EC_dompar_enc enc_type) { SecureVector<byte> result; @@ -560,7 +563,7 @@ SecureVector<byte> encode_der_ec_dompar(EC_Domain_Params const& dom_pars, EC_dom return result; } -EC_Domain_Params decode_ber_ec_dompar(SecureVector<byte> const& encoded) +EC_Domain_Params decode_ber_ec_dompar(const SecureVector<byte>& encoded) { BER_Decoder dec(encoded); BER_Object obj = dec.get_next_object(); @@ -579,7 +582,7 @@ EC_Domain_Params decode_ber_ec_dompar(SecureVector<byte> const& encoded) throw Decoding_Error("encountered unexpected when trying to decode domain parameters"); } -bool operator==(EC_Domain_Params const& lhs, EC_Domain_Params const& rhs) +bool operator==(const EC_Domain_Params& lhs, const EC_Domain_Params& rhs) { return ((lhs.get_curve() == rhs.get_curve()) && (lhs.get_base_point() == rhs.get_base_point()) && diff --git a/src/pubkey/ec_dompar/ec_dompar.h b/src/pubkey/ec_dompar/ec_dompar.h index 5f03f1c5f..f5f573ba9 100644 --- a/src/pubkey/ec_dompar/ec_dompar.h +++ b/src/pubkey/ec_dompar/ec_dompar.h @@ -11,9 +11,7 @@ #define BOTAN_ECC_DOMAIN_PARAMETERS_H__ #include <botan/point_gfp.h> -#include <botan/gfp_element.h> #include <botan/curve_gfp.h> -#include <botan/bigint.h> #include <botan/der_enc.h> #include <botan/ber_dec.h> #include <botan/alg_id.h> diff --git a/src/pubkey/ec_dompar/info.txt b/src/pubkey/ec_dompar/info.txt index b05903b69..fd40b887d 100644 --- a/src/pubkey/ec_dompar/info.txt +++ b/src/pubkey/ec_dompar/info.txt @@ -2,8 +2,7 @@ define ECC_DOMAIN_PARAMATERS <requires> asn1 -bigint filters -gfpmath +numbertheory hex </requires> diff --git a/src/pubkey/ecc_key/ecc_key.cpp b/src/pubkey/ecc_key/ecc_key.cpp index 7d3c79868..e6d4aeae6 100644 --- a/src/pubkey/ecc_key/ecc_key.cpp +++ b/src/pubkey/ecc_key/ecc_key.cpp @@ -163,15 +163,11 @@ void EC_PrivateKey::generate_private_key(RandomNumberGenerator& rng) throw Invalid_State("cannot generate private key when domain parameters are not set"); } - BigInt tmp_private_value(0); - tmp_private_value = BigInt::random_integer(rng, 1, mp_dom_pars->get_order()); + m_private_value = BigInt::random_integer(rng, 1, mp_dom_pars->get_order()); + mp_public_point = std::unique_ptr<PointGFp>( new PointGFp (mp_dom_pars->get_base_point())); - mp_public_point->mult_this_secure(tmp_private_value, - mp_dom_pars->get_order(), - mp_dom_pars->get_order()-1); - //assert(mp_public_point.get() != 0); - tmp_private_value.swap(m_private_value); + *mp_public_point *= m_private_value; } /** diff --git a/src/pubkey/ecc_key/ecc_key.h b/src/pubkey/ecc_key/ecc_key.h index ea0f3f4ad..f8a419ffe 100644 --- a/src/pubkey/ecc_key/ecc_key.h +++ b/src/pubkey/ecc_key/ecc_key.h @@ -10,10 +10,8 @@ #ifndef BOTAN_ECC_PUBLIC_KEY_BASE_H__ #define BOTAN_ECC_PUBLIC_KEY_BASE_H__ -#include <botan/bigint.h> -#include <botan/curve_gfp.h> -#include <botan/pk_keys.h> #include <botan/ec_dompar.h> +#include <botan/pk_keys.h> #include <botan/x509_key.h> #include <botan/pkcs8.h> #include <memory> diff --git a/src/pubkey/ecc_key/info.txt b/src/pubkey/ecc_key/info.txt index 92455189a..4650fb612 100644 --- a/src/pubkey/ecc_key/info.txt +++ b/src/pubkey/ecc_key/info.txt @@ -5,7 +5,6 @@ alloc asn1 bigint ec_dompar -gfpmath numbertheory pk_codecs </requires> diff --git a/src/pubkey/ecdsa/ecdsa.cpp b/src/pubkey/ecdsa/ecdsa.cpp index dffd37e6f..93c65c3a8 100644 --- a/src/pubkey/ecdsa/ecdsa.cpp +++ b/src/pubkey/ecdsa/ecdsa.cpp @@ -40,10 +40,10 @@ ECDSA_PrivateKey::ECDSA_PrivateKey(const EC_Domain_Params& domain, mp_dom_pars = std::unique_ptr<EC_Domain_Params>(new EC_Domain_Params(domain)); m_private_value = x; + mp_public_point = std::unique_ptr<PointGFp>(new PointGFp (mp_dom_pars->get_base_point())); - mp_public_point->mult_this_secure(m_private_value, - mp_dom_pars->get_order(), - mp_dom_pars->get_order()-1); + + *mp_public_point *= m_private_value; try { diff --git a/src/pubkey/ecdsa/ecdsa_op.cpp b/src/pubkey/ecdsa/ecdsa_op.cpp index 7bbeded73..dd92ac5c0 100644 --- a/src/pubkey/ecdsa/ecdsa_op.cpp +++ b/src/pubkey/ecdsa/ecdsa_op.cpp @@ -1,7 +1,7 @@ /* * ECDSA Operation * (C) 2007 FlexSecure GmbH -* 2008-2009 Jack Lloyd +* 2008-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -14,7 +14,8 @@ namespace Botan { Default_ECDSA_Op::Default_ECDSA_Op(const EC_Domain_Params& domain, const BigInt& priv, const PointGFp& pub) : - dom_pars(domain), pub_key(pub), priv_key(priv) + dom_pars(domain), mod_n(dom_pars.get_order()), + pub_key(pub), priv_key(priv) { } @@ -26,10 +27,6 @@ bool Default_ECDSA_Op::verify(const byte msg[], u32bit msg_len, if(sig_len != n.bytes()*2) return false; - // NOTE: it is not checked whether the public point is set - if(dom_pars.get_curve().get_p() == 0) - throw Internal_Error("domain parameters not set"); - BigInt e(msg, msg_len); BigInt r(sig, sig_len / 2); @@ -44,9 +41,7 @@ bool Default_ECDSA_Op::verify(const byte msg[], u32bit msg_len, if(R.is_zero()) return false; - BigInt x = R.get_affine_x().get_value(); - - return (x % n == r); + return (mod_n.reduce(R.get_affine_x()) == r); } SecureVector<byte> Default_ECDSA_Op::sign(const byte msg[], u32bit msg_len, @@ -57,26 +52,18 @@ SecureVector<byte> Default_ECDSA_Op::sign(const byte msg[], u32bit msg_len, const BigInt& n = dom_pars.get_order(); - if(n == 0) - throw Internal_Error("Default_ECDSA_Op::sign(): domain parameters not set"); - BigInt e(msg, msg_len); - PointGFp k_times_P(dom_pars.get_base_point()); - k_times_P.mult_this_secure(k, n, n-1); - k_times_P.check_invariants(); - BigInt r = k_times_P.get_affine_x().get_value() % n; + PointGFp k_times_P = dom_pars.get_base_point() * k; + BigInt r = mod_n.reduce(k_times_P.get_affine_x()); if(r == 0) throw Internal_Error("Default_ECDSA_Op::sign: r was zero"); BigInt k_inv = inverse_mod(k, n); - BigInt s(r); - s *= priv_key; - s += e; - s *= k_inv; - s %= n; + BigInt s = mod_n.reduce(mod_n.multiply(r, priv_key) + e); + s = mod_n.multiply(s, k_inv); SecureVector<byte> output(2*n.bytes()); r.binary_encode(output + (output.size() / 2 - r.bytes())); diff --git a/src/pubkey/ecdsa/ecdsa_op.h b/src/pubkey/ecdsa/ecdsa_op.h index c203905f9..3a492ccf4 100644 --- a/src/pubkey/ecdsa/ecdsa_op.h +++ b/src/pubkey/ecdsa/ecdsa_op.h @@ -10,6 +10,7 @@ #define BOTAN_ECDSA_OPERATIONS_H__ #include <botan/ec_dompar.h> +#include <botan/reducer.h> namespace Botan { @@ -52,6 +53,8 @@ class BOTAN_DLL Default_ECDSA_Op : public ECDSA_Operation const PointGFp& pub_key); private: EC_Domain_Params dom_pars; + Modular_Reducer mod_n; + PointGFp pub_key; BigInt priv_key; }; diff --git a/src/pubkey/ecdsa/info.txt b/src/pubkey/ecdsa/info.txt index be5ac037a..799fff32f 100644 --- a/src/pubkey/ecdsa/info.txt +++ b/src/pubkey/ecdsa/info.txt @@ -5,7 +5,6 @@ alloc asn1 ec_dompar ecc_key -gfpmath libstate numbertheory rng diff --git a/src/pubkey/eckaeg/eckaeg_op.cpp b/src/pubkey/eckaeg/eckaeg_op.cpp index 0cb5c3d55..4fb0a23eb 100644 --- a/src/pubkey/eckaeg/eckaeg_op.cpp +++ b/src/pubkey/eckaeg/eckaeg_op.cpp @@ -1,7 +1,7 @@ /* * ECKAEG Operation * (C) 2007 FlexSecure GmbH -* 2008 Jack Lloyd +* 2008-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -22,15 +22,18 @@ Default_ECKAEG_Op::Default_ECKAEG_Op(const EC_Domain_Params& dom_pars, SecureVector<byte> Default_ECKAEG_Op::agree(const PointGFp& i) const { - BigInt cofactor(m_dom_pars.get_cofactor()); + BigInt cofactor = m_dom_pars.get_cofactor(); BigInt n = m_dom_pars.get_order(); - BigInt l(inverse_mod(cofactor,n)); // l=h^-1 mod n - PointGFp Q(cofactor*i); // q = h*Pb - PointGFp S(Q); - BigInt group_order = m_dom_pars.get_cofactor() * n; - S.mult_this_secure((m_priv_key*l)%n, group_order, n-1); + + BigInt l = inverse_mod(cofactor, n); + + PointGFp S = cofactor * i; + S *= (m_priv_key * l) % n; + S.check_invariants(); - return FE2OSP(S.get_affine_x()); // fe2os(xs) + + return BigInt::encode_1363(S.get_affine_x(), + S.get_curve().get_p().bytes()); } } diff --git a/src/pubkey/eckaeg/info.txt b/src/pubkey/eckaeg/info.txt index 53a744daa..cac352a2a 100644 --- a/src/pubkey/eckaeg/info.txt +++ b/src/pubkey/eckaeg/info.txt @@ -5,7 +5,6 @@ alloc asn1 ec_dompar ecc_key -gfpmath libstate numbertheory </requires> diff --git a/src/pubkey/gost_3410/gost_3410.cpp b/src/pubkey/gost_3410/gost_3410.cpp index 21e2653c9..d3e98665d 100644 --- a/src/pubkey/gost_3410/gost_3410.cpp +++ b/src/pubkey/gost_3410/gost_3410.cpp @@ -2,7 +2,7 @@ * GOST 34.10-2001 implemenation * (C) 2007 Falko Strenzke, FlexSecure GmbH * Manuel Hartl, FlexSecure GmbH -* (C) 2008-2009 Jack Lloyd +* (C) 2008-2010 Jack Lloyd * * Distributed under the terms of the Botan license */ @@ -39,9 +39,8 @@ GOST_3410_PrivateKey::GOST_3410_PrivateKey(const EC_Domain_Params& domain, m_private_value = x; mp_public_point = std::unique_ptr<PointGFp>(new PointGFp (mp_dom_pars->get_base_point())); - mp_public_point->mult_this_secure(m_private_value, - mp_dom_pars->get_order(), - mp_dom_pars->get_order()-1); + + *mp_public_point *= m_private_value; try { @@ -73,8 +72,8 @@ X509_Encoder* GOST_3410_PublicKey::x509_encoder() const key->affirm_init(); // Trust CryptoPro to come up with something obnoxious - const BigInt x = key->mp_public_point->get_affine_x().get_value(); - const BigInt y = key->mp_public_point->get_affine_y().get_value(); + const BigInt x = key->mp_public_point->get_affine_x(); + const BigInt y = key->mp_public_point->get_affine_y(); SecureVector<byte> bits(2*std::max(x.bytes(), y.bytes())); @@ -126,8 +125,7 @@ X509_Decoder* GOST_3410_PublicKey::x509_decoder() key->mp_public_point.reset( new PointGFp(key->domain_parameters().get_curve(), - GFpElement(x, p), - GFpElement(y, p))); + x, y)); key->X509_load_hook(); } @@ -235,7 +233,7 @@ bool GOST_3410_PublicKey::verify(const byte msg[], u32bit msg_len, PointGFp R = (z1 * mp_dom_pars->get_base_point() + z2 * *mp_public_point); - return (R.get_affine_x().get_value() == r); + return (R.get_affine_x() == r); } GOST_3410_PublicKey::GOST_3410_PublicKey(const EC_Domain_Params& dom_par, @@ -331,10 +329,10 @@ GOST_3410_PrivateKey::sign(const byte msg[], if(e == 0) e = 1; - PointGFp k_times_P(mp_dom_pars->get_base_point()); - k_times_P.mult_this_secure(k, n, n-1); + PointGFp k_times_P = mp_dom_pars->get_base_point() * k; k_times_P.check_invariants(); - BigInt r = k_times_P.get_affine_x().get_value() % n; + + BigInt r = k_times_P.get_affine_x() % n; if(r == 0) throw Internal_Error("GOST_3410::sign: r was zero"); diff --git a/src/pubkey/gost_3410/info.txt b/src/pubkey/gost_3410/info.txt index 1d6c1ed17..05df445ec 100644 --- a/src/pubkey/gost_3410/info.txt +++ b/src/pubkey/gost_3410/info.txt @@ -7,7 +7,6 @@ alloc asn1 ec_dompar ecc_key -gfpmath libstate numbertheory rng diff --git a/src/stream/ctr/ctr.cpp b/src/stream/ctr/ctr.cpp index 0b0f72da2..421c9f0c0 100644 --- a/src/stream/ctr/ctr.cpp +++ b/src/stream/ctr/ctr.cpp @@ -22,8 +22,8 @@ CTR_BE::CTR_BE(BlockCipher* ciph) : { position = 0; - counter.resize(permutation->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_CTR); - buffer.resize(permutation->BLOCK_SIZE * BOTAN_PARALLEL_BLOCKS_CTR); + counter.resize(permutation->BLOCK_SIZE * permutation->parallelism()); + buffer.resize(counter.size()); } /* |