CODEWITHSUNDEEP
javarandomshuffleseeding
Lydon Ch
Lydon Ch

Reputation: 8815

Java SecureRandom internal state

I'm trying to shuffle an array of integer as per below,

and from http://en.wikipedia.org/wiki/Fisher-Yates_shuffle,

"An additional problem occurs when the Fisher–Yates shuffle is used with a pseudorandom number generator or PRNG: as the sequence of numbers output by such a generator is entirely determined by its internal state at the start of a sequence, a shuffle driven by such a generator cannot possibly produce more distinct permutations than the generator has distinct possible states. ... "

  1. Is it enough if I seed my SecureRandom generator with a lot of bytes ?

  2. What's the easiest way to fill the seed byte array ? i.e.

    byte[] seed = new byte[2048]; // fill the seed byte with random stuff, what's the easiest way ? SecureRandom secureRandom = new SecureRandom(seed);

Code:

/**
 * http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
 * 
 * To shuffle an array a of n elements (indices 0..n-1):
 *      for i from n − 1 downto 1 do
 *          j ← random integer with 0 ≤ j ≤ i
 *          exchange a[j] and a[i]
 */
public int[] shuffle (int[] inSet ) {

    int [] returnSet = Arrays.copyOf(inSet, inSet.length);

    for( int i = inSet.length-1; i > 0; i-- ) {

        // j ← random integer with 0 ≤ j ≤ i
        int j = secureRandom.nextInt(i+1); 

        // swap returnSet[i] and returnSet[j]
        int temp = returnSet[i];
        returnSet[i] = returnSet[j];
        returnSet[j] = temp; 
    }
    return returnSet;
}

Upvotes: 1

Views: 733

Answers (2)

Enno Shioji
Enno Shioji

Reputation: 26882

Here is a good article: "A Java Programmer’s Guide to Random Numbers"

Basically, a) You don't want to use java.util.Random as it is exhibits periodic behavior (bad randomness), b) SecureRandom is a big improvement over java.util.Random, but depending on the number of elements you want to shuffle, the degrees of freedom it provides might be too small (see this section for details). Also another problem is that SecureRandom is quite slow. If you have performance problems, you can follow the link above for alternative PRNGs that are faster than SecureRandom.

Upvotes: 3

disorder
disorder

Reputation: 291

I think that the size of the array is not so important as its content. One common practise is to create the seed on current time. You can also ask the user (if possible) to apply some random keyboard or mouse input. I've noticed this technique in password managers.

Everything depends on your needs. I bet that quite sensible way would be to take System.currentTimeMillis() (optionally you can play with it by joining it multiple times or hash it).

Upvotes: 0

Related Questions