Change random methods without losing too much performance

I have a class in C# that uses a Random object to get a list of numbers randomized from an array of 1-25. Now what I need is improve this method to use RNGCryptoServiceProvider because it is not random enough for the application.

I know that RNGCryptoServiceProvider is slower than Random, but I need to change it and I don't know anything about this class. How big should the Buffer storage be so as to not slow down the client PC too much?

What I'm passing to the method is this array:

string[] num25 = { "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25" };

This is the actual code:

public static class RandomStringArrayTool
{
    /// 
    /// Stores the current random number
    /// 
    static Random _random = new Random();

    /// 
    /// Return randomized version of the string array
    /// 
    public static string[] RandomizeStrings(string[] arr)
    {
        List> list = new List>();
        // Add all strings from array
        // Add new random int each time
        foreach (string s in arr)
        {
            list.Add(new KeyValuePair(_random.Next(), s));
        }
        // Sort the list by the random number
        var sorted = from item in list
                     orderby item.Key
                     select item;
        // Allocate new string array
        string[] result = new string[arr.Length];
        // Copy values to array
        int index = 0;
        foreach (KeyValuePair pair in sorted)
        {
            result[index] = pair.Value;
            index++;
        }
        // Return copied array
        return result;
    }
}

First of all, you should shuffle the array instead of sorting it on a random number. There can be duplicates in the random numbers, which means that lower numbers would end up earlier in the array slightly more often. This is naturally a small difference as the random numbers are large, but as you want to avoid any predictable pattern, it is still important.

Look at the Fisher-Yates algorithm for shuffling the values in an array.

To use the crypto random generator, you need a way to transform the bytes that it returns into a number in a specific range. You can use a method like the following to get a number in a range with the same probability for all numbers in the range (limited only by the randomness of the generator). It calculates the largest range of numbers that can be used to create a number in the desired range, then loops until it has picked a number in that range.

public static int GetInt(RNGCryptoServiceProvider rnd, int max) {
  byte[] r = new byte[4];
  int value;
  do {
    rnd.GetBytes(r);
    value = BitConverter.ToInt32(r, 0) & Int32.MaxValue;
  } while (value >= max * (Int32.MaxValue / max));
  return value % max;
}

This is based on the example on documentation page for the GetBytes method, but adapted for larger numbers.

On my computer the function will generate a million random numbers in 450 ms. The Random class does it in 20 ms, so it's slower, but not very slow. Shuffling on the other hand is faster than sorting, so you will get some performance back there.

StackExchange Code Review Q#60500, answer score: 6