I'm trying to convert from random bytes to integers within a range. Basically converting as such:
byte[] GetRandomBytes(int count) -> int NextInteger(int min, int max)
Another way to think about it would be: I have a RNGCryptoServiceProvider
but would rather have the interface to Random
.
My current algorithm works out how many bits it needs based on min
and max
, gets a random int (after masking off any bits it doesn't need), then loops until it gets a number less than max - min
.
Question 1: Is my algorithm sound?
Question 1a: Is the below implementation sound (c#) (specifically: RandomSourceBase.Next(int, int)
)?
using System;
using System.Collections.Generic;
using System.Security.Cryptography;
namespace ConsoleApplication1
{
public abstract class RandomSourceBase
{
public abstract byte[] GetRandomBytes(int numberOfBytes);
public int Next()
{
return Next(0, Int32.MaxValue);
}
public int Next(int maxValue)
{
return Next(0, maxValue);
}
public int Next(int minValue, int maxValue)
{
if (minValue < 0)
throw new ArgumentOutOfRangeException("minValue", minValue, "MinValue must be greater than or equal to zero.");
if (maxValue <= minValue)
throw new ArgumentOutOfRangeException("maxValue", maxValue, "MaxValue must be greater than minValue.");
int range = maxValue - minValue;
if (range == 1) // Trivial case.
return minValue;
// Determine how many bits are required for the range requested.
int bitsRequired = (int)Math.Ceiling(Math.Log(range, 2) + 1);
int bitmask = (1 << bitsRequired) - 1;
// Loop until we get a number within the range.
int result = -1;
while (result < 0 || result > range - 1)
{
var bytes = this.GetRandomBytes(4);
result = (Math.Abs(BitConverter.ToInt32(bytes, 0)) & bitmask) - 1;
}
return result + minValue;
}
}
public class CryptoRandomSource : RandomSourceBase
{
private RNGCryptoServiceProvider _RandomProvider;
public CryptoRandomSource()
{
this._RandomProvider = new RNGCryptoServiceProvider();
}
public override byte[] GetRandomBytes(int numberOfBytes)
{
var result = new byte[numberOfBytes];
this._RandomProvider.GetBytes(result);
return result;
}
}
class Program
{
static void Main(string[] args)
{
TestNextInt32(new CryptoRandomSource(), 50);
TestNextInt32(new CryptoRandomSource(), 64);
Console.ReadLine();
}
private static void TestNextInt32(RandomSourceBase randomness, int max)
{
var distributionTable = new Dictionary<int, int>();
for (int i = 0; i < max; i++)
distributionTable.Add(i, 0);
Console.WriteLine("Testing CryptoRandomStream.Next({0})...", max);
int trials = max * 50000;
for (int i = 0; i < trials; i++)
{
var choice = randomness.Next(max);
distributionTable[choice] = distributionTable[choice] + 1;
}
for (int i = 0; i < max; i++)
Console.WriteLine("{0}, {1}", i, distributionTable[i]);
Console.WriteLine();
}
}
}
Question 2: Assuming GetRandomBytes
is actually random, will my algorithm / implementation also be random (specifically a uniform distribution?).
I've done a few test runs and graphed the distribution in Excel. They look random-ish to me. But, well, I'm no security expert, and the stats course I did was in 2003 and my memory isn't very good! Specifically, I don't know if the variation of up to 800 or ~1.6% (point #3 on the 50 graph) is acceptable or if I've done something horribly wrong.
(Note, the Y axis isn't zeroed. 50,000 is the desired number).
Context: I'm building a plugin for KeePass and its RNG returns a byte[]
but most of my logic is tied up in choosing indexes from a collection, hence my need to convert random bytes to random int
s within a range.
Actual real life code (for those who are interested): http://readablepassphrase.codeplex.com/SourceControl/changeset/changes/aa085616bc23 Relevant code located in: trunk/ReadablePassphrase/Random
Int32.MaxVal ^ 1000000
gives an error in windows calculator and returnsDouble.Infinity
in .NET. Even 64^10 (10 of the same number in a row) is 1.15E+18 (an order of magnitude less than 2^64). I'd be highly suspicious of that generator! dilbert.com/strips/comic/2001-10-25 – ligos Nov 26 '11 at 9:11