diff options
author | Simon Warta <[email protected]> | 2015-07-24 00:23:02 +0200 |
---|---|---|
committer | Simon Warta <[email protected]> | 2015-07-24 10:36:57 +0200 |
commit | 81411c5b69a27f308c4921acdb52c25541ef2c73 (patch) | |
tree | 5d9b63d81164536917834b063abb5f7dcc78ec82 /src | |
parent | e5e8635ab5e21991e890b229c9c563ffeec2db31 (diff) |
Fix BigInt random_integer() distribution issue.
Fixes #108
Diffstat (limited to 'src')
-rw-r--r-- | src/lib/math/bigint/big_rand.cpp | 21 | ||||
-rw-r--r-- | src/lib/math/bigint/bigint.cpp | 4 | ||||
-rw-r--r-- | src/lib/math/bigint/bigint.h | 16 | ||||
-rw-r--r-- | src/tests/catchy/test_bigint.cpp | 97 |
4 files changed, 128 insertions, 10 deletions
diff --git a/src/lib/math/bigint/big_rand.cpp b/src/lib/math/bigint/big_rand.cpp index 074c368e0..cfc1facee 100644 --- a/src/lib/math/bigint/big_rand.cpp +++ b/src/lib/math/bigint/big_rand.cpp @@ -15,7 +15,7 @@ namespace Botan { * Randomize this number */ void BigInt::randomize(RandomNumberGenerator& rng, - size_t bitsize) + size_t bitsize, bool set_high_bit) { set_sign(Positive); @@ -27,9 +27,13 @@ void BigInt::randomize(RandomNumberGenerator& rng, { secure_vector<byte> array = rng.random_vec(round_up(bitsize, 8) / 8); + // Always cut unwanted bits if(bitsize % 8) array[0] &= 0xFF >> (8 - (bitsize % 8)); - array[0] |= 0x80 >> ((bitsize % 8) ? (8 - bitsize % 8) : 0); + + // Set the highest bit if wanted + if (set_high_bit) + array[0] |= 0x80 >> ((bitsize % 8) ? (8 - bitsize % 8) : 0); binary_decode(array); } @@ -41,12 +45,19 @@ void BigInt::randomize(RandomNumberGenerator& rng, BigInt BigInt::random_integer(RandomNumberGenerator& rng, const BigInt& min, const BigInt& max) { - BigInt range = max - min; + BigInt delta_upper_bound = max - min - 1; - if(range <= 0) + if(delta_upper_bound < 0) throw Invalid_Argument("random_integer: invalid min/max values"); - return (min + (BigInt(rng, range.bits() + 2) % range)); + // Choose x in [0, delta_upper_bound] + BigInt x; + do { + auto bitsize = delta_upper_bound.bits(); + x.randomize(rng, bitsize, false); + } while(x > delta_upper_bound); + + return min + x; } } diff --git a/src/lib/math/bigint/bigint.cpp b/src/lib/math/bigint/bigint.cpp index 242a7fe0b..0a068c53e 100644 --- a/src/lib/math/bigint/bigint.cpp +++ b/src/lib/math/bigint/bigint.cpp @@ -87,9 +87,9 @@ BigInt::BigInt(const byte input[], size_t length, Base base) /* * Construct a BigInt from an encoded BigInt */ -BigInt::BigInt(RandomNumberGenerator& rng, size_t bits) +BigInt::BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit) { - randomize(rng, bits); + randomize(rng, bits, set_high_bit); } /* diff --git a/src/lib/math/bigint/bigint.h b/src/lib/math/bigint/bigint.h index d866698b3..776884ad9 100644 --- a/src/lib/math/bigint/bigint.h +++ b/src/lib/math/bigint/bigint.h @@ -74,11 +74,15 @@ class BOTAN_DLL BigInt BigInt(const byte buf[], size_t length, Base base = Binary); /** - * Create a random BigInt of the specified size + * \brief Create a random BigInt of the specified size + * * @param rng random number generator * @param bits size in bits + * @param set_high_bit if true, the highest bit is always set + * + * @see randomize */ - BigInt(RandomNumberGenerator& rng, size_t bits); + BigInt(RandomNumberGenerator& rng, size_t bits, bool set_high_bit = true); /** * Create BigInt of specified size, all zeros @@ -431,10 +435,16 @@ class BOTAN_DLL BigInt /** * Fill BigInt with a random number with size of bitsize + * + * If \p set_high_bit is true, the highest bit will be set, which causes + * the entropy to be \a bits-1. Otherwise the highest bit is randomly choosen + * by the rng, causing the entropy to be \a bits. + * * @param rng the random number generator to use * @param bitsize number of bits the created random value should have + * @param set_high_bit if true, the highest bit is always set */ - void randomize(RandomNumberGenerator& rng, size_t bitsize = 0); + void randomize(RandomNumberGenerator& rng, size_t bitsize, bool set_high_bit = true); /** * Store BigInt-value in a given byte array diff --git a/src/tests/catchy/test_bigint.cpp b/src/tests/catchy/test_bigint.cpp index 5f4c960cf..9bd99e919 100644 --- a/src/tests/catchy/test_bigint.cpp +++ b/src/tests/catchy/test_bigint.cpp @@ -71,4 +71,101 @@ TEST_CASE("Bigint basics", "[bigint]") } } +TEST_CASE("Bigint random_integer", "[bigint]") + { + RandomNumberGenerator *rng = RandomNumberGenerator::make_rng(); + + SECTION("min is 0") + { + // 0–9 + const size_t MIN = 0; + const size_t MAX = 10; // excluded + const int ITERATIONS = 10000; + + std::vector<int> counts(MAX, 0); + std::vector<double> ratios(MAX, 1.0); + + for (size_t i = 0; i < ITERATIONS; i++) + { + BigInt b = BigInt::random_integer(*rng, MIN, MAX); + size_t x = b.to_u32bit(); + counts[x]++; + } + + std::stringstream debug; + for (size_t d = MIN; d < MAX; ++d) + { + auto ratio = static_cast<double>(counts[d]) / ITERATIONS; + ratios[d] = ratio; + + if (!debug.str().empty()) + { + debug << ", "; + } + debug << d << ": " << std::setprecision(3) << ratio; + } + + INFO( debug.str() ) + + // Have ~ 10 % on each digit from 0-9 + CHECK(( 0.09 < ratios[0] )); CHECK(( ratios[0] < 0.11 )); + CHECK(( 0.09 < ratios[1] )); CHECK(( ratios[1] < 0.11 )); + CHECK(( 0.09 < ratios[2] )); CHECK(( ratios[2] < 0.11 )); + CHECK(( 0.09 < ratios[3] )); CHECK(( ratios[3] < 0.11 )); + CHECK(( 0.09 < ratios[4] )); CHECK(( ratios[4] < 0.11 )); + CHECK(( 0.09 < ratios[5] )); CHECK(( ratios[5] < 0.11 )); + CHECK(( 0.09 < ratios[6] )); CHECK(( ratios[6] < 0.11 )); + CHECK(( 0.09 < ratios[7] )); CHECK(( ratios[7] < 0.11 )); + CHECK(( 0.09 < ratios[8] )); CHECK(( ratios[8] < 0.11 )); + CHECK(( 0.09 < ratios[9] )); CHECK(( ratios[9] < 0.11 )); + //CHECK( false ); + } + + SECTION("min is 10") + { + // 10–19 + const size_t MIN = 10; + const size_t MAX = 20; // excluded + const size_t ITERATIONS = 10000; + + std::vector<int> counts(MAX, 0); + std::vector<double> ratios(MAX, 1.0); + + for (size_t i = 0; i < ITERATIONS; i++) + { + BigInt b = BigInt::random_integer(*rng, MIN, MAX); + size_t x = b.to_u32bit(); + counts[x]++; + } + + std::stringstream debug; + for (size_t d = MIN; d < MAX; ++d) + { + auto ratio = static_cast<double>(counts[d]) / ITERATIONS; + ratios[d] = ratio; + + if (!debug.str().empty()) + { + debug << ", "; + } + debug << d << ": " << std::setprecision(3) << ratio; + } + + INFO( debug.str() ) + + // Have ~ 10 % on each digit from 10-19 + CHECK(( 0.09 < ratios[10] )); CHECK(( ratios[10] < 0.11 )); + CHECK(( 0.09 < ratios[11] )); CHECK(( ratios[11] < 0.11 )); + CHECK(( 0.09 < ratios[12] )); CHECK(( ratios[12] < 0.11 )); + CHECK(( 0.09 < ratios[13] )); CHECK(( ratios[13] < 0.11 )); + CHECK(( 0.09 < ratios[14] )); CHECK(( ratios[14] < 0.11 )); + CHECK(( 0.09 < ratios[15] )); CHECK(( ratios[15] < 0.11 )); + CHECK(( 0.09 < ratios[16] )); CHECK(( ratios[16] < 0.11 )); + CHECK(( 0.09 < ratios[17] )); CHECK(( ratios[17] < 0.11 )); + CHECK(( 0.09 < ratios[18] )); CHECK(( ratios[18] < 0.11 )); + CHECK(( 0.09 < ratios[19] )); CHECK(( ratios[19] < 0.11 )); + //CHECK( false ); + } + } + #endif |