diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/lib/math/ec_gfp/curve_gfp.cpp | 172 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/curve_gfp.h | 14 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/curve_nistp.cpp | 137 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/curve_nistp.h | 152 | ||||
| -rw-r--r-- | src/lib/math/ec_gfp/info.txt | 9 | ||||
| -rw-r--r-- | src/lib/math/numbertheory/info.txt | 14 | ||||
| -rw-r--r-- | src/tests/test_bigint.cpp | 154 |
7 files changed, 367 insertions, 285 deletions
diff --git a/src/lib/math/ec_gfp/curve_gfp.cpp b/src/lib/math/ec_gfp/curve_gfp.cpp index 64d45572d..96fe873af 100644 --- a/src/lib/math/ec_gfp/curve_gfp.cpp +++ b/src/lib/math/ec_gfp/curve_gfp.cpp @@ -1,12 +1,12 @@ /* * Elliptic curves over GF(p) Montgomery Representation -* (C) 2014 Jack Lloyd +* (C) 2014,2015 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ #include <botan/curve_gfp.h> -#include <botan/internal/curve_nistp.h> +#include <botan/curve_nistp.h> #include <botan/internal/mp_core.h> #include <botan/internal/mp_asmi.h> @@ -115,54 +115,170 @@ void CurveGFp_Montgomery::curve_sqr(BigInt& z, const BigInt& x, ws.data()); } -} +class CurveGFp_NIST : public CurveGFp_Repr + { + public: + CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) : + m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS) + { + } + + const BigInt& get_a() const override { return m_a; } + + const BigInt& get_b() const override { return m_b; } + + size_t get_p_words() const override { return m_p_words; } + + const BigInt& get_a_rep() const override { return m_a; } + + const BigInt& get_b_rep() const override { return m_b; } + + void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override + { redc(x, ws); } + + void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override + { redc(x, ws); } + + void curve_mul(BigInt& z, const BigInt& x, const BigInt& y, + secure_vector<word>& ws) const override; + + void curve_sqr(BigInt& z, const BigInt& x, + secure_vector<word>& ws) const override; + private: + virtual void redc(BigInt& x, secure_vector<word>& ws) const = 0; + + // Curve parameters + BigInt m_a, m_b; + size_t m_p_words; // cache of m_p.sig_words() + }; -// Default implementation -void CurveGFp_Repr::normalize(BigInt& x, secure_vector<word>& ws, size_t bound) const +void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y, + secure_vector<word>& ws) const { - const BigInt& p = get_p(); - const word* prime = p.data(); + if(x.is_zero() || y.is_zero()) + { + z = 0; + return; + } + const size_t p_words = get_p_words(); + const size_t output_size = 2*p_words + 1; + ws.resize(2*(p_words+2)); - while(x.is_negative()) - x += p; + z.grow_to(output_size); + z.clear(); - x.grow_to(p_words + 1); + bigint_mul(z.mutable_data(), output_size, ws.data(), + x.data(), x.size(), x.sig_words(), + y.data(), y.size(), y.sig_words()); - if(ws.size() < p_words + 1) - ws.resize(p_words + 1); + this->redc(z, ws); + } - for(size_t i = 0; bound == 0 || i < bound; ++i) +void CurveGFp_NIST::curve_sqr(BigInt& z, const BigInt& x, + secure_vector<word>& ws) const + { + if(x.is_zero()) { - const word* xd = x.data(); - word borrow = 0; + z = 0; + return; + } + + const size_t p_words = get_p_words(); + const size_t output_size = 2*p_words + 1; - for(size_t i = 0; i != p_words; ++i) - ws[i] = word_sub(xd[i], prime[i], &borrow); - ws[p_words] = word_sub(xd[p_words], 0, &borrow); + ws.resize(2*(p_words+2)); - if(borrow) - break; + z.grow_to(output_size); + z.clear(); - x.swap_reg(ws); - } + bigint_sqr(z.mutable_data(), output_size, ws.data(), + x.data(), x.size(), x.sig_words()); + + this->redc(z, ws); } +#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32) + +/** +* The NIST P-192 curve +*/ +class CurveGFp_P192 : public CurveGFp_NIST + { + public: + CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {} + const BigInt& get_p() const override { return prime_p192(); } + private: + void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p192(x, ws); } + }; + +/** +* The NIST P-224 curve +*/ +class CurveGFp_P224 : public CurveGFp_NIST + { + public: + CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {} + const BigInt& get_p() const override { return prime_p224(); } + private: + void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p224(x, ws); } + }; + +/** +* The NIST P-256 curve +*/ +class CurveGFp_P256 : public CurveGFp_NIST + { + public: + CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {} + const BigInt& get_p() const override { return prime_p256(); } + private: + void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p256(x, ws); } + }; + +/** +* The NIST P-384 curve +*/ +class CurveGFp_P384 : public CurveGFp_NIST + { + public: + CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {} + const BigInt& get_p() const override { return prime_p384(); } + private: + void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p384(x, ws); } + }; + +#endif + +/** +* The NIST P-521 curve +*/ +class CurveGFp_P521 : public CurveGFp_NIST + { + public: + CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {} + const BigInt& get_p() const override { return prime_p521(); } + private: + void redc(BigInt& x, secure_vector<word>& ws) const override { redc_p521(x, ws); } + }; + +} + std::shared_ptr<CurveGFp_Repr> CurveGFp::choose_repr(const BigInt& p, const BigInt& a, const BigInt& b) { -#if defined(BOTAN_HAS_CURVEGFP_NISTP_M32) - if(p == CurveGFp_P192::prime()) +#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32) + if(p == prime_p192()) return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P192(a, b)); - if(p == CurveGFp_P224::prime()) + if(p == prime_p224()) return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P224(a, b)); - if(p == CurveGFp_P256::prime()) + if(p == prime_p256()) return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P256(a, b)); - if(p == CurveGFp_P384::prime()) + if(p == prime_p384()) return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P384(a, b)); #endif - if(p == CurveGFp_P521::prime()) + if(p == prime_p521()) return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_P521(a, b)); return std::shared_ptr<CurveGFp_Repr>(new CurveGFp_Montgomery(p, a, b)); diff --git a/src/lib/math/ec_gfp/curve_gfp.h b/src/lib/math/ec_gfp/curve_gfp.h index 68fe93274..dde9f633e 100644 --- a/src/lib/math/ec_gfp/curve_gfp.h +++ b/src/lib/math/ec_gfp/curve_gfp.h @@ -45,10 +45,6 @@ class CurveGFp_Repr virtual void curve_sqr(BigInt& z, const BigInt& x, secure_vector<word>& ws) const = 0; - - virtual void normalize(BigInt& x, - secure_vector<word>& ws, - size_t bound) const; }; /** @@ -141,16 +137,6 @@ class BOTAN_DLL CurveGFp return z; } - /** - * Adjust x to be in [0,p) - * @param bound if greater than zero, assume that no more than bound - * additions or subtractions are required to move x into range. - */ - void normalize(BigInt& x, secure_vector<word>& ws, size_t bound = 0) const - { - m_repr->normalize(x, ws, bound); - } - void swap(CurveGFp& other) { std::swap(m_repr, other.m_repr); diff --git a/src/lib/math/ec_gfp/curve_nistp.cpp b/src/lib/math/ec_gfp/curve_nistp.cpp index 002cf2d47..bbc11ff21 100644 --- a/src/lib/math/ec_gfp/curve_nistp.cpp +++ b/src/lib/math/ec_gfp/curve_nistp.cpp @@ -1,63 +1,51 @@ /* -* NIST curve reduction +* NIST prime reductions * (C) 2014,2015 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ -#include <botan/internal/curve_nistp.h> +#include <botan/curve_nistp.h> #include <botan/internal/mp_core.h> +#include <botan/internal/mp_asmi.h> namespace Botan { -void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y, - secure_vector<word>& ws) const - { - if(x.is_zero() || y.is_zero()) - { - z = 0; - return; - } +namespace { - const size_t p_words = get_p_words(); - const size_t output_size = 2*p_words + 1; - ws.resize(2*(p_words+2)); +void normalize(const BigInt& p, BigInt& x, secure_vector<word>& ws, size_t bound) + { + const word* prime = p.data(); + const size_t p_words = p.sig_words(); - z.grow_to(output_size); - z.clear(); + while(x.is_negative()) + x += p; - bigint_mul(z.mutable_data(), output_size, ws.data(), - x.data(), x.size(), x.sig_words(), - y.data(), y.size(), y.sig_words()); + // TODO: provide a high level function for this compare-and-sub operation + x.grow_to(p_words + 1); - this->redc(z, ws); - } + if(ws.size() < p_words + 1) + ws.resize(p_words + 1); -void CurveGFp_NIST::curve_sqr(BigInt& z, const BigInt& x, - secure_vector<word>& ws) const - { - if(x.is_zero()) + for(size_t i = 0; bound == 0 || i < bound; ++i) { - z = 0; - return; - } - - const size_t p_words = get_p_words(); - const size_t output_size = 2*p_words + 1; - - ws.resize(2*(p_words+2)); + const word* xd = x.data(); + word borrow = 0; - z.grow_to(output_size); - z.clear(); + for(size_t i = 0; i != p_words; ++i) + ws[i] = word_sub(xd[i], prime[i], &borrow); + ws[p_words] = word_sub(xd[p_words], 0, &borrow); - bigint_sqr(z.mutable_data(), output_size, ws.data(), - x.data(), x.size(), x.sig_words()); + if(borrow) + break; - this->redc(z, ws); + x.swap_reg(ws); + } } -//static -const BigInt& CurveGFp_P521::prime() +} + +const BigInt& prime_p521() { static const BigInt p521("0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"); @@ -65,12 +53,11 @@ const BigInt& CurveGFp_P521::prime() return p521; } -void CurveGFp_P521::redc(BigInt& x, secure_vector<word>& ws) const +void redc_p521(BigInt& x, secure_vector<word>& ws) { - const size_t p_words = get_p_words(); - - const size_t shift_words = 521 / MP_WORD_BITS, - shift_bits = 521 % MP_WORD_BITS; + const size_t p_full_words = 521 / MP_WORD_BITS; + const size_t p_top_bits = 521 % MP_WORD_BITS; + const size_t p_words = p_full_words + 1; const size_t x_sw = x.sig_words(); @@ -81,16 +68,16 @@ void CurveGFp_P521::redc(BigInt& x, secure_vector<word>& ws) const ws.resize(p_words + 1); clear_mem(ws.data(), ws.size()); - bigint_shr2(ws.data(), x.data(), x_sw, shift_words, shift_bits); + bigint_shr2(ws.data(), x.data(), x_sw, p_full_words, p_top_bits); x.mask_bits(521); bigint_add3(x.mutable_data(), x.data(), p_words, ws.data(), p_words); - normalize(x, ws, max_redc_subtractions()); + normalize(prime_p521(), x, ws, 1); } -#if defined(BOTAN_HAS_CURVEGFP_NISTP_M32) +#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32) namespace { @@ -130,14 +117,13 @@ inline void set_u32bit(BigInt& x, size_t i, T v_in) } -//static -const BigInt& CurveGFp_P192::prime() +const BigInt& prime_p192() { static const BigInt p192("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF"); return p192; } -void CurveGFp_P192::redc(BigInt& x, secure_vector<word>& ws) const +void redc_p192(BigInt& x, secure_vector<word>& ws) { const u32bit X6 = get_u32bit(x, 6); const u32bit X7 = get_u32bit(x, 7); @@ -192,17 +178,16 @@ void CurveGFp_P192::redc(BigInt& x, secure_vector<word>& ws) const // No underflow possible - normalize(x, ws, max_redc_subtractions()); + normalize(prime_p192(), x, ws, 3); } -//static -const BigInt& CurveGFp_P224::prime() +const BigInt& prime_p224() { static const BigInt p224("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001"); return p224; } -void CurveGFp_P224::redc(BigInt& x, secure_vector<word>& ws) const +void redc_p224(BigInt& x, secure_vector<word>& ws) { const u32bit X7 = get_u32bit(x, 7); const u32bit X8 = get_u32bit(x, 8); @@ -271,17 +256,16 @@ void CurveGFp_P224::redc(BigInt& x, secure_vector<word>& ws) const BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); - normalize(x, ws, max_redc_subtractions()); + normalize(prime_p224(), x, ws, 3); } -//static -const BigInt& CurveGFp_P256::prime() +const BigInt& prime_p256() { static const BigInt p256("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF"); return p256; } -void CurveGFp_P256::redc(BigInt& x, secure_vector<word>& ws) const +void redc_p256(BigInt& x, secure_vector<word>& ws) { const u32bit X8 = get_u32bit(x, 8); const u32bit X9 = get_u32bit(x, 9); @@ -396,34 +380,35 @@ void CurveGFp_P256::redc(BigInt& x, secure_vector<word>& ws) const BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); + #if 0 if(S >= 2) { BOTAN_ASSERT(S <= 10, "Expected overflow"); static const BigInt P256_mults[9] = { - 2*get_p(), - 3*get_p(), - 4*get_p(), - 5*get_p(), - 6*get_p(), - 7*get_p(), - 8*get_p(), - 9*get_p(), - 10*get_p() + 2*CurveGFp_P256::prime(), + 3*CurveGFp_P256::prime(), + 4*CurveGFp_P256::prime(), + 5*CurveGFp_P256::prime(), + 6*CurveGFp_P256::prime(), + 7*CurveGFp_P256::prime(), + 8*CurveGFp_P256::prime(), + 9*CurveGFp_P256::prime(), + 10*CurveGFp_P256::prime() }; x -= P256_mults[S - 2]; } + #endif - normalize(x, ws, max_redc_subtractions()); + normalize(prime_p256(), x, ws, 10); } -//static -const BigInt& CurveGFp_P384::prime() +const BigInt& prime_p384() { static const BigInt p384("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF"); return p384; } -void CurveGFp_P384::redc(BigInt& x, secure_vector<word>& ws) const +void redc_p384(BigInt& x, secure_vector<word>& ws) { const u32bit X12 = get_u32bit(x, 12); const u32bit X13 = get_u32bit(x, 13); @@ -569,20 +554,22 @@ void CurveGFp_P384::redc(BigInt& x, secure_vector<word>& ws) const BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow"); set_u32bit(x, 12, S); + #if 0 if(S >= 2) { BOTAN_ASSERT(S <= 4, "Expected overflow"); static const BigInt P384_mults[3] = { - 2*get_p(), - 3*get_p(), - 4*get_p() + 2*CurveGFp_P384::prime(), + 3*CurveGFp_P384::prime(), + 4*CurveGFp_P384::prime() }; x -= P384_mults[S - 2]; } + #endif - normalize(x, ws, max_redc_subtractions()); + normalize(prime_p384(), x, ws, 4); } #endif diff --git a/src/lib/math/ec_gfp/curve_nistp.h b/src/lib/math/ec_gfp/curve_nistp.h index 0bf707f58..e7af69964 100644 --- a/src/lib/math/ec_gfp/curve_nistp.h +++ b/src/lib/math/ec_gfp/curve_nistp.h @@ -1,152 +1,46 @@ /* -* NIST elliptic curves over GF(p) -* (C) 2014 Jack Lloyd +* Arithmetic operations specialized for NIST ECC primes +* (C) 2014,2015 Jack Lloyd * * Botan is released under the Simplified BSD License (see license.txt) */ -#ifndef BOTAN_GFP_CURVE_NIST_H__ -#define BOTAN_GFP_CURVE_NIST_H__ +#ifndef BOTAN_NIST_PRIMES_H__ +#define BOTAN_NIST_PRIMES_H__ -#include <botan/curve_gfp.h> -#include <memory> +#include <botan/bigint.h> namespace Botan { -class CurveGFp_NIST : public CurveGFp_Repr - { - public: - CurveGFp_NIST(size_t p_bits, const BigInt& a, const BigInt& b) : - m_a(a), m_b(b), m_p_words((p_bits + BOTAN_MP_WORD_BITS - 1) / BOTAN_MP_WORD_BITS) - { - } - - size_t get_p_words() const override { return m_p_words; } - - const BigInt& get_a() const override { return m_a; } - - const BigInt& get_b() const override { return m_b; } - - const BigInt& get_a_rep() const override { return m_a; } - - const BigInt& get_b_rep() const override { return m_b; } - - void to_curve_rep(BigInt& x, secure_vector<word>& ws) const override - { redc(x, ws); } - - void from_curve_rep(BigInt& x, secure_vector<word>& ws) const override - { redc(x, ws); } - - void curve_mul(BigInt& z, const BigInt& x, const BigInt& y, - secure_vector<word>& ws) const override; - - void curve_sqr(BigInt& z, const BigInt& x, - secure_vector<word>& ws) const override; - private: - virtual void redc(BigInt& x, secure_vector<word>& ws) const = 0; - - virtual size_t max_redc_subtractions() const = 0; - - // Curve parameters - BigInt m_a, m_b; - size_t m_p_words; // cache of m_p.sig_words() - }; - -#if (BOTAN_MP_WORD_BITS == 32) || (BOTAN_MP_WORD_BITS == 64) - -#define BOTAN_HAS_CURVEGFP_NISTP_M32 - -/** -* The NIST P-192 curve -*/ -class CurveGFp_P192 : public CurveGFp_NIST - { - public: - CurveGFp_P192(const BigInt& a, const BigInt& b) : CurveGFp_NIST(192, a, b) {} - - static const BigInt& prime(); - - const BigInt& get_p() const override { return CurveGFp_P192::prime(); } - - private: - void redc(BigInt& x, secure_vector<word>& ws) const override; - - size_t max_redc_subtractions() const override { return 3; } - }; - /** -* The NIST P-224 curve -*/ -class CurveGFp_P224 : public CurveGFp_NIST - { - public: - CurveGFp_P224(const BigInt& a, const BigInt& b) : CurveGFp_NIST(224, a, b) {} - - static const BigInt& prime(); - - const BigInt& get_p() const override { return CurveGFp_P224::prime(); } - private: - void redc(BigInt& x, secure_vector<word>& ws) const override; - - size_t max_redc_subtractions() const override { return 3; } - }; - -/** -* The NIST P-256 curve +* NIST Prime reduction functions. +* +* Reduces the value in place +* +* ws is a workspace function which is used as a temporary, +* and will be resized as needed. */ -class CurveGFp_P256 : public CurveGFp_NIST - { - public: - CurveGFp_P256(const BigInt& a, const BigInt& b) : CurveGFp_NIST(256, a, b) {} - - static const BigInt& prime(); - - const BigInt& get_p() const override { return CurveGFp_P256::prime(); } - - private: - void redc(BigInt& x, secure_vector<word>& ws) const override; +BOTAN_DLL const BigInt& prime_p521(); +BOTAN_DLL void redc_p521(BigInt& x, secure_vector<word>& ws); - size_t max_redc_subtractions() const override { return 10; } - }; +#if (BOTAN_MP_WORD_BITS == 32) || (BOTAN_MP_WORD_BITS == 64) -/** -* The NIST P-384 curve -*/ -class CurveGFp_P384 : public CurveGFp_NIST - { - public: - CurveGFp_P384(const BigInt& a, const BigInt& b) : CurveGFp_NIST(384, a, b) {} +#define BOTAN_HAS_NIST_PRIME_REDUCERS_W32 - static const BigInt& prime(); +BOTAN_DLL const BigInt& prime_p384(); +BOTAN_DLL void redc_p384(BigInt& x, secure_vector<word>& ws); - const BigInt& get_p() const override { return CurveGFp_P384::prime(); } +BOTAN_DLL const BigInt& prime_p256(); +BOTAN_DLL void redc_p256(BigInt& x, secure_vector<word>& ws); - private: - void redc(BigInt& x, secure_vector<word>& ws) const override; +BOTAN_DLL const BigInt& prime_p224(); +BOTAN_DLL void redc_p224(BigInt& x, secure_vector<word>& ws); - size_t max_redc_subtractions() const override { return 4; } - }; +BOTAN_DLL const BigInt& prime_p192(); +BOTAN_DLL void redc_p192(BigInt& x, secure_vector<word>& ws); #endif -/** -* The NIST P-521 curve -*/ -class CurveGFp_P521 : public CurveGFp_NIST - { - public: - CurveGFp_P521(const BigInt& a, const BigInt& b) : CurveGFp_NIST(521, a, b) {} - - static const BigInt& prime(); - - const BigInt& get_p() const override { return CurveGFp_P521::prime(); } - - private: - void redc(BigInt& x, secure_vector<word>& ws) const override; - - size_t max_redc_subtractions() const override { return 1; } - }; - } #endif diff --git a/src/lib/math/ec_gfp/info.txt b/src/lib/math/ec_gfp/info.txt index 9af40c752..060551562 100644 --- a/src/lib/math/ec_gfp/info.txt +++ b/src/lib/math/ec_gfp/info.txt @@ -2,15 +2,6 @@ define EC_CURVE_GFP 20131128 load_on auto -<header:public> -curve_gfp.h -point_gfp.h -</header:public> - -<header:internal> -curve_nistp.h -</header:internal> - <requires> numbertheory </requires> diff --git a/src/lib/math/numbertheory/info.txt b/src/lib/math/numbertheory/info.txt index e39a236cb..49f7ab2fb 100644 --- a/src/lib/math/numbertheory/info.txt +++ b/src/lib/math/numbertheory/info.txt @@ -12,20 +12,6 @@ reducer.h def_powm.h </header:internal> -<source> -dsa_gen.cpp -jacobi.cpp -make_prm.cpp -mp_numth.cpp -numthry.cpp -pow_mod.cpp -powm_fw.cpp -powm_mnt.cpp -primes.cpp -reducer.cpp -ressol.cpp -</source> - <requires> bigint hash diff --git a/src/tests/test_bigint.cpp b/src/tests/test_bigint.cpp index 748f26ce9..dabe5746e 100644 --- a/src/tests/test_bigint.cpp +++ b/src/tests/test_bigint.cpp @@ -21,27 +21,43 @@ #include <botan/bigint.h> #include <botan/exceptn.h> #include <botan/numthry.h> +#include <botan/reducer.h> + +#if defined(BOTAN_HAS_EC_CURVE_GFP) +#include <botan/curve_nistp.h> +#endif using namespace Botan; namespace { -void test_failure(const char* function, const char* file, int line, - const std::string& what_failed) +class Test_State { - std::cout << "FAIL " << function << " " << file << ":" << line << " " - << what_failed << std::endl; - } + public: + void started(const std::string& /*msg*/) { m_tests_run++; } + + void test_ran(const char* msg); + + void failure(const char* test, const std::string& what_failed) + { + std::cout << "FAIL " << test << " " << what_failed << "\n"; + m_tests_failed++; + } + + size_t ran() const { return m_tests_run; } + size_t failed() const { return m_tests_failed; } + private: + size_t m_tests_run = 0, m_tests_failed = 0; + }; #define BOTAN_CONFIRM_NOTHROW(block) do { \ try { block } \ catch(std::exception& e) { \ - test_failure(BOTAN_CURRENT_FUNCTION, __FILE__, __LINE__, e.what()); \ - ++tests_failed; \ + _test.failure(BOTAN_CURRENT_FUNCTION, e.what()); \ } } while(0) \ #define BOTAN_TEST(lhs, rhs, msg) do { \ - ++tests_run; \ + _test.started(msg); \ BOTAN_CONFIRM_NOTHROW({ \ const auto lhs_val = lhs; \ const auto rhs_val = rhs; \ @@ -52,19 +68,19 @@ void test_failure(const char* function, const char* file, int line, fmt << "expr '" << #lhs << " == " << #rhs << "' false, " \ << "actually " << lhs_val << " " << rhs_val \ << " (" << msg << ")"; \ - test_failure(BOTAN_CURRENT_FUNCTION, __FILE__, __LINE__, fmt.str()); \ - ++tests_failed; \ + _test.failure(BOTAN_CURRENT_FUNCTION, fmt.str()); \ } \ }); \ } while(0) -#define BOTAN_TEST_CASE(name, block) size_t test_ ## name() { \ - size_t tests_run = 0, tests_failed = 0; \ +#define BOTAN_TEST_CASE(name, descr, block) size_t test_ ## name() { \ + Test_State _test; \ BOTAN_CONFIRM_NOTHROW(block); \ - return tests_failed; \ + test_report(descr, _test.ran(), _test.failed()); \ + return _test.failed(); \ } -BOTAN_TEST_CASE(bigint_to_u32bit, { +BOTAN_TEST_CASE(bigint_to_u32bit, "BigInt to_u32bit", { for(size_t i = 0; i != 32; ++i) { const u32bit in = 1 << i; @@ -72,6 +88,100 @@ BOTAN_TEST_CASE(bigint_to_u32bit, { } }); +BigInt test_integer(RandomNumberGenerator& rng, size_t bits) + { + /* + Produces integers with long runs of ones and zeros, for testing for + carry handling problems. + */ + BigInt x = 0; + + auto flip_prob = [](size_t i) { + if(i % 64 == 0) + return .5; + if(i % 32 == 0) + return .4; + if(i % 8 == 0) + return .05; + return .01; + }; + + bool active = rng.next_byte() % 2; + for(size_t i = 0; i != bits; ++i) + { + x <<= 1; + x += static_cast<int>(active); + + const double prob = flip_prob(i); + const double sample = double(rng.next_byte() % 100) / 100.0; // biased + + if(sample < prob) + active = !active; + } + + //std::cout << std::hex << x << "\n"; + return x; + } + +#if defined(BOTAN_HAS_EC_CURVE_GFP) + +void nist_redc_test(Test_State& _test, + const std::string& prime_name, + const BigInt& p, + std::function<void (BigInt&, secure_vector<word>&)> redc_fn) + { + auto& rng = test_rng(); + const size_t trials = 100; + const size_t p_bits = p.bits(); + + Modular_Reducer p_redc(p); + secure_vector<word> ws; + + for(size_t i = 0; i != trials; ++i) + { + const BigInt x = test_integer(rng, 2*p_bits); + + // TODO: time and report all three approaches + const BigInt v1 = x % p; + const BigInt v2 = p_redc.reduce(x); + + BigInt v3 = x; + redc_fn(v3, ws); + + BOTAN_TEST(v1, v2, "reference"); + BOTAN_TEST(v2, v3, "specialized"); + + if(v1 != v2 || v2 != v3) + std::cout << "Prime " << prime_name << " input " << x << "\n"; + } + } + +#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32) + +BOTAN_TEST_CASE(bigint_redc_p192, "P-192 reduction", { + nist_redc_test(_test, "P-192", prime_p192(), redc_p192); + }); + +BOTAN_TEST_CASE(bigint_redc_p224, "P-224 reduction", { + nist_redc_test(_test, "P-224", prime_p224(), redc_p224); + }); + +BOTAN_TEST_CASE(bigint_redc_p256, "P-256 reduction", { + nist_redc_test(_test, "P-256", prime_p256(), redc_p256); + }); + +BOTAN_TEST_CASE(bigint_redc_p384, "P-384 reduction", { + nist_redc_test(_test, "P-384", prime_p384(), redc_p384); + }); + +#endif + +BOTAN_TEST_CASE(bigint_redc_p521, "P-521 reduction", { + nist_redc_test(_test, "P-521", prime_p521(), redc_p521); + }); + +#endif + void strip_comments(std::string& line) { if(line.find('#') != std::string::npos) @@ -349,8 +459,6 @@ size_t test_bigint() bool first = true; size_t counter = 0; - total_errors += test_bigint_to_u32bit(); - auto& rng = test_rng(); while(!test_data.eof()) @@ -429,6 +537,20 @@ size_t test_bigint() << std::dec << alg_count << std::endl; } + total_errors += test_bigint_to_u32bit(); + +#if defined(BOTAN_HAS_EC_CURVE_GFP) + +#if defined(BOTAN_HAS_NIST_PRIME_REDUCERS_W32) + total_errors += test_bigint_redc_p192(); + total_errors += test_bigint_redc_p224(); + total_errors += test_bigint_redc_p256(); + total_errors += test_bigint_redc_p384(); + #endif + + total_errors += test_bigint_redc_p521(); +#endif + return total_errors; } |