Knuth suggests the Bays-Durham shuffle (Algorithm 3.2.2 B in TAoCP) as
a way to increase the apparent randomness of a sequence by reordering
it.
From the cryptographic point of view the algorithm as given leaks
information about its internal state. The output value is copied to
the auxiliary variable (Y in Knuth's notation), hence any attacker
will know the value of Y after seeing a single output. This
information leak could be prevented by a small change to the
algorithm: rather than setting Y to the output of the previous
iteration, set Y to the input of the current iteration. This
separates the value of Y from the output value and so reduces the
attacker's knowledge of the internal state of the system.
Using Knuth's notation, this changes the algorithm to:
B1 [Extract j.] Set Y to the next member of the sequence <X_n>.
Set j <- floor(k * Y / m).
B2 [Exchange.] Output V[j].
Set V[j] <- Y.
Here k, m, V[j] and <X_n> are as defined in Knuth. There is no need
to set Y on initialisation as it will now be set in step B1.
As a minor benefit this change also reduces the storage requirement
slightly as there is no need to retain the value of Y in the state.
rossum
