From ac03a40cbac4545909b6529d358c253f8a6d3b45 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Sat, 15 Mar 2014 09:25:46 +0100 Subject: ash,hush: fix a thinko about 2^64-1 factorization function old new delta next_random 113 119 +6 Signed-off-by: Denys Vlasenko --- shell/random.c | 16 +++++++++++----- 1 file changed, 11 insertions(+), 5 deletions(-) (limited to 'shell/random.c') diff --git a/shell/random.c b/shell/random.c index fc2dfc26d..5d3620516 100644 --- a/shell/random.c +++ b/shell/random.c @@ -80,7 +80,6 @@ next_random(random_t *rnd) rnd->galois_LFSR = t; /* http://en.wikipedia.org/wiki/Xorshift - * Period 2^64-1 = 3 * 715827883 * 2147483647 * Moderately good statistical properties: * fails the following "dieharder -g 200 -a" tests: * diehard_operm5| 0 @@ -102,11 +101,19 @@ next_random(random_t *rnd) * dab_filltree| 32 * dab_monobit2| 12 */ + again: t = rnd->xs64_x ^ (rnd->xs64_x << a); rnd->xs64_x = rnd->xs64_y; rnd->xs64_y = rnd->xs64_y ^ (rnd->xs64_y >> c) ^ t ^ (t >> b); + /* + * Period 2^64-1 = 2^32+1 * 2^32-1 has a common divisor with Galois LFSR. + * By skipping two possible states (0x1 and 0x2) we reduce period to + * 2^64-3 = 13 * 3889 * 364870227143809 which has no common divisors: + */ + if (rnd->xs64_y == 0 && rnd->xs64_x <= 2) + goto again; - /* Combined LCG + Galois LFSR have 2^32 * 2^32-1 period. + /* Combined LCG + Galois LFSR rng has 2^32 * 2^32-1 period. * Strength: * individually, both are extremely weak cryptographycally; * when combined, they fail the following "dieharder -g 200 -a" tests: @@ -118,9 +125,8 @@ next_random(random_t *rnd) * dab_monobit2| 12 * * Combining them with xorshift-64 increases period to - * 2^32 * 2^32-1 * 2^64-1 / 3 - * (2^32-1 and 2^64-1 have one common divisor 3, hence "/ 3" part), - * which is about 2^128 / 3, or in base 10 ~1.13*10^38. + * 2^32 * 2^32-1 * 2^64-3 + * which is about 2^128, or in base 10 ~3.40*10^38. * Strength of the combination: * passes all "dieharder -g 200 -a" tests. * -- cgit v1.2.3