summaryrefslogtreecommitdiff
path: root/shell
diff options
context:
space:
mode:
authorDenys Vlasenko2014-03-15 09:25:46 +0100
committerDenys Vlasenko2014-03-15 09:25:46 +0100
commitac03a40cbac4545909b6529d358c253f8a6d3b45 (patch)
tree9b4bc1c4bff113fcdaf9a3dc794e9bd9498ba6cd /shell
parent2bba591991f5ac9b97582e37375dd49492c63df0 (diff)
downloadbusybox-ac03a40cbac4545909b6529d358c253f8a6d3b45.zip
busybox-ac03a40cbac4545909b6529d358c253f8a6d3b45.tar.gz
ash,hush: fix a thinko about 2^64-1 factorization
function old new delta next_random 113 119 +6 Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
Diffstat (limited to 'shell')
-rw-r--r--shell/random.c16
1 files changed, 11 insertions, 5 deletions
diff --git a/shell/random.c b/shell/random.c
index fc2dfc2..5d36205 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.
*