Generate cryptographically secure random numbers in a specific range

Question

A project I'm working on requires generating a random number of \$N\$ length to a very high degree of fair distribution between digits \$[0, 9]\$.

That said, I used the RNGCryptoServiceProvider in the .NET framework, and built my own window restriction / clamping.

First, we have the clamping. This clamps the values to the range from \$[lower, upper)\$, allowing the user to specify what range of values they want. For me, it's \$[0, 9]\$.

Mathematically speaking, using a cryptographically secure random number generator should yield a truly random set. The problem is clamping: if we simply take val % 10 to reduce it to our desired \$[0, 9]\$ range, we'll find that we have a slight favoritism / bias towards numbers at the lower end of the set. In fact, we should have the most bias towards the set \$[0, 5]\$.

To reduce, or even eliminate, this bias I took a previously working algorithm and modified it slightly to create a bounded number of loops. The idea is simple: to generate a random value in the domain \$[0, 9]\$ take the random value from the set \$[0, 255]\$ and test that it is within the range \$[0, 249]\$. If it is within that range, take \$value \mod 10\$ as the result. If it is in the range \$[250, 255]\$ then we draw a new number. This can be expanded to define the following general-purpose formula:

$$upperLimit = 256 - (256 \mod modulo)$$

We can then define the number to take the modulo by as:

$$modulo = upper - lower$$

We set the loop up to bound to a specific value, in this case I'm creating the loop

So far, my results have yielded almost perfect distribution of the values \$[0, 9]\$, when generating \$1,000,000\$ values.

I have run this several times, and each time I get a slightly different distribution, by a very small margin. That is perfect, as it demonstrates that the RNG is not predictable by any manner.

Value 0: 100090 occurrences (10.009%)
Value 1: 100298 occurrences (10.0298%)
Value 2: 100034 occurrences (10.0034%)
Value 3: 99996 occurrences (9.9996%)
Value 4: 100042 occurrences (10.0042%)
Value 5: 99912 occurrences (9.9912%)
Value 6: 99506 occurrences (9.9506%)
Value 7: 99971 occurrences (9.9971%)
Value 8: 99801 occurrences (9.9801%)
Value 9: 100350 occurrences (10.035%)

The code to clamp values is as follows:

int ModuloLimit(int modulo) => 256 - (256 % modulo);

int ClampDigit(byte[] bytes, int lower, int upper)
{
    var result = -1;
    var modulo = upper - lower;
    var upperLimit = ModuloLimit(modulo);

    for (int i = 0; i < bytes.Length; i++)
    {
        if (bytes[i] < upperLimit)
        {
            result = bytes[i] % modulo + lower;
        }
    }

    if (result == -1)
    {
        result = bytes[bytes[0] % bytes.Length] % modulo + lower;
    }

    return result;
}

Next we have our function which gets a random digit within \$[0, 9]\$ using the RNGCryptoServiceProvider. It creates a new instance each time, since the RNGCryptoServiceProvider is supposed to be unpredictable, this should suffice.

int RandomDigit(int tries = 10, int lower = 0, int upper = 10)
{
    var bytes = new byte[tries];
    using (var csp = new RNGCryptoServiceProvider())
    {
        csp.GetBytes(bytes);
    }
    return ClampDigit(bytes, lower, upper);
}

Finally, I have the RandomNumber method which generates the series of digits with length \$N\$.

string RandomNumber(int numDigits)
{
    var sb = new StringBuilder(numDigits);
    for (int i = 0; i < numDigits; i++)
    {
        sb.Append(RandomDigit());
    }
    return sb.ToString();
}

The only public members would be RandomNumber(int) and RandomDigit(int, int, int).

Finally, I have a TestDistribution method which I use to test the distribution of our randomly generated values in \$[0, 9]\$.

void TestDistribution(int generatedValues, int upperLimit = 10)
{
    var value = generatedValues;
    var results = new int[upperLimit];
    while (value > 0)
    {
        value--;
        results[RandomDigit(upper: upperLimit)]++;
    }

    Console.WriteLine("Expect " + Math.Round(100.0 / upperLimit, 2) + "% for each value");
    for (int i = 0; i < upperLimit; i++)
    {
        Console.WriteLine("Value " + i + ": " + results[i] + " occurrences (" + ((double)results[i] / (double)generatedValues * 100) + "%)");
    }
}

The distribution has been consistently variant in my testing, and has been predictable within \$[9.93\%, 10.08\%]\$ for \$1,000,000\$ generated numbers.

When testing with \$10,000,000\$ numbers, the distribution consistently falls within \$[9.975\%, 10.025\%]\$, furthering the demonstration that no number is favored consistently. (When testing across multiple runs, the favored and unfavored digits varied entirely.)

Just for comparison, if the entire ClampDigit method is replaced with a simple return bytes[0] % (upper - lower) + lower; the result distribution is roughly as follows:

Value 0: 101535 occurrences (10.1535%)
Value 1: 101851 occurrences (10.1851%)
Value 2: 101675 occurrences (10.1675%)
Value 3: 101262 occurrences (10.1262%)
Value 4: 101426 occurrences (10.1426%)
Value 5: 101295 occurrences (10.1295%)
Value 6: 97704 occurrences (9.7704%)
Value 7: 97501 occurrences (9.7501%)
Value 8: 97988 occurrences (9.7988%)
Value 9: 97763 occurrences (9.7763%)

This is entirely consistent for the general distribution: every tested run had digits in the range \$[0, 5]\$ appear more than 10% of the time, and digits \$[6, 9]\$ appeared less than 10% of the time.

When testing the edge case (if the iteration count exceeds tries value) it was hit 0 times across \$1,000,000\$ runs when tries was in the interval \$[4, 10]\$. For a tries value of 3, there were 13 occurrences on average across multiple runs that it was hit, meaning \$0.0013\%\$ of the time. For a tries value of 2 it was roughly \$0.0521\%\$, a tries value of 1 was roughly \$2.3223\%\$. (The final value makes complete sense, \$2.34375\%\$ of the values from \$[0, 255]\$ are within the edge case.)

Mathematically speaking, the code should hit the edge case once every

$$\frac 1 {0.0234375^N}$$

Where \$N\$ is the tries or number of bytes to test before the loop terminates. For a tries of 1, that's \$42.\bar6\$, for tries of 5, that's \$141,398,100.2798\$.

Answer 1

Firstly, related to the mathematical aspect I see how the bias could be leaning towards \$[0, 5]\$, but I don't quite get the connection why you are using 256 afterwards. You could possibly get even better distribution by changing form bytes to the next storage level available.

Depending on your range, the distribution could be affected severly if the \$modulo\$ gets close to 256, if I've understood your algorithm correctly.

I've sadly not gotten a C# compiler available, so the following points are made untested:

• In general your code looks goods – Nice spacing, nice variable names, and so on. Not a whole lot of comments explaining the reasoning for your methods, but in general it looks good. Personally I'm not all in favor of capitalizing both Function Names, like ClampDigit(), so I kind of read most of your function names as class names, but this is personal preferences.
• Cost of initializing RNGCryptoServiceProvider? – I'm wondering what the cost of constructing this all the time is. Some random generators are somewhat expensive to initialize, but a lot cheaper to use. There could be a possible gain of creating this once, and reusing it later on.
• Multiple call with same parameters -> Class? – You call the ClampDigit() quite a few times with the same parameters. Not expensive as such, but possibly it could be better to have a class where you reuse the instantiation for new random digits with the same parameters?
• Why does RandomNumber() return a string? – It kind of baffles me that the RandomNumber() returns a string, and not an actual number. It would make more sense that it actually returned a number.

• Edge case never reached, and doesn't generate new number – Within ClampDigit() your description says you should generate a new number, but the code simply reuses one of the number which has proven to be above the upperLimit (and are potentially biased).

  However, as you describe, this edge case is not met when the tries is sufficiently high. Not sure if this would have any influence on the distribution with a lower number of tries, or not.

• No bailing out of for loop within ClampDigit() – Potentially your for loop resets result 10 (or bytes.Length times to be exact) before it continues and returns a result. By adding && result == -1 to the end condition you could bail out once you find a candidate. Could potentially reduce the running speed down to 1/10th of current speed.

So in general your code looks good, and seems to give a better distribution than the default distribution when reducing the range significantly. But I'm a little unsure about the performance speed and cost if the range is increased, and why you've chosen to return the number as a string. All in all, interesting and well written code!

Answer 2

I believe one can avoid the bias problem by generating a random float between [0..1) and then normalizing the value between x and y instead of clamping:

private static RandomNumberGenerator Rng = new RNGCryptoServiceProvider();
private const double ReciprocalOf256AsDouble = 1d / 256d;

public static double Random() {
    var buffer = new byte[sizeof(double)];

    Rng.GetBytes(buffer);

    return ReciprocalOf256AsDouble
        * (buffer[0] + ReciprocalOf256AsDouble
        * (buffer[1] + ReciprocalOf256AsDouble
        * (buffer[2] + ReciprocalOf256AsDouble
        * (buffer[3] + ReciprocalOf256AsDouble
        * (buffer[4] + ReciprocalOf256AsDouble
        * (buffer[5] + ReciprocalOf256AsDouble
        * (buffer[6] + ReciprocalOf256AsDouble
        * buffer[7]
    )))))));
}
public static int Random(int x, int y) {
    var min = Math.Min(x, y);
    var max = Math.Max(x, y);

    return (int)Math.Floor(min + (((max - min) + 1.0d) * Random()));
}

I also went ahead and hoisted up the RNGCryptoServiceProvider into a static field since there's no real security benefit gained by allocating a new one on every call. Usage in your current RandomNumber function is straightforward:

string RandomNumber(int numDigits) {
    var sb = new StringBuilder(numDigits);

    for (int i = 0; i < numDigits; i++) {
        sb.Append(Random(0, 9));
    }

    return sb.ToString();
}

---

Random(0, 9) testing results, two passes of twenty million:

Testing code:

static void Main(string[] args) {
    var count = 20000000;
    var x = Sample(count, 9);
    var y = Sample(count, 9);

    for (var i = 0; i < x.Length; i++) {
        Console.WriteLine($"    {i} | {x[i]}");
    }

    Console.WriteLine("-------------------");

    for (var i = 0; i < y.Length; i++) {
        Console.WriteLine($"    {i} | {y[i]}");
    }

    Console.ReadKey();
}

static int[] Sample(int count, int maxValue) {
    var results = new int[maxValue + 1];

    Parallel.For(0, count, (index) => {
        Interlocked.Increment(ref results[Random(0, maxValue)]);
    });

    return results;
}

Answer 3

It is not truly random. It is cryptographically strong. The regular Random is going to be pretty close for what you are Doing here.

This is confusing to me

int ClampDigit(byte[] bytes, int lower, int upper)

lower is included but upper is not

I think this would be more consistent

var modulo = upper - lower + 1;

Why are you using a suspect / biased result?

if (result == -1)
{
    result = bytes[bytes[0] % bytes.Length] % modulo + lower;
}

Why mess with passing around data that is out of range?

int RandomDigit(int tries = 10, int lower = 0, int upper = 10) does not really care about lower and upper other than pass it to another function.

I would break this down differently.

public static byte[] RandomNumbersInRange(byte count, byte lower, byte upper )
{
    if (count == 0)
        throw new IndexOutOfRangeException();
    if (lower >= upper)
        throw new IndexOutOfRangeException();
    byte modulo = (byte)(upper - lower + 1);
    if (modulo > byte.MaxValue / 2)  //for bigger numbers I would not use byte 
        throw new IndexOutOfRangeException();
    byte[] randomNumbersInRange = new byte[count];
    byte upperLimit = (byte)(byte.MaxValue - byte.MaxValue % modulo - 1);  
    byte[] bigRandomsInRange = RandomsInRange(upperLimit, count);
    for (int i = 0; i < count; i++)
    {
        randomNumbersInRange[i] = (byte)((bigRandomsInRange[i] % modulo) + lower);
    }
    return randomNumbersInRange;
}
public static byte[] RandomsInRange(byte upperLimit, byte count)
{
    if (count == 0)
        throw new IndexOutOfRangeException();
    if (upperLimit == byte.MaxValue)
        throw new IndexOutOfRangeException();
    byte[] workingBytes = new byte[1];
    byte workingByte;
    byte[] randomsInRange = new byte[count];
    using (var csp = new System.Security.Cryptography.RNGCryptoServiceProvider())
    {
        for (int i = 0; i < count; i++)
        {
            workingByte = byte.MaxValue;
            while (workingByte > upperLimit)
            {
                csp.GetBytes(workingBytes);
                workingByte = workingBytes[0];
            }
            randomsInRange[i] = workingByte;
        }
    }
    return randomsInRange;
}

Random is generating results that look as good to me and 100 times faster.

public static uint[] TestRandomsInRange(byte upper)
{
    byte modulo = (byte)(upper + 1);
    if (modulo >= byte.MaxValue / 2)  //for bigger numbers I would not use byte 
        throw new IndexOutOfRangeException();
    byte upperLimit = (byte)(byte.MaxValue - byte.MaxValue % modulo - 1);
    byte[] workingBytes = new byte[1];
    int workingByte;
    UInt32[] randomsInRange = new UInt32[modulo];
    UInt32 count = 10000000;
    Stopwatch sw = new Stopwatch();
    sw.Start();
    using (var csp = new System.Security.Cryptography.RNGCryptoServiceProvider())
    {
        for (int i = 0; i < count; i++)
        {
            workingByte = byte.MaxValue;
            while (workingByte > upperLimit)
            {
                csp.GetBytes(workingBytes);
                workingByte = workingBytes[0];
            }
            workingByte = workingByte % modulo;
            //Debug.WriteLine(workingByte);
            randomsInRange[workingByte]++;
        }
    }
    UInt32 min = UInt32.MaxValue;
    UInt32 max = UInt32.MinValue;
    UInt32 value;
    for (int i = 0; i < modulo; i++)
    {
        value = randomsInRange[i];
        Debug.WriteLine("i {0}  count {1}  pct {2}", i, value.ToString("N0"), (100m * value / count).ToString("N4"));
        if (min > value)
            min = value;
        else if (max < value)
            max = value;
    }
    Debug.WriteLine("diff {0}  pct {1} ", (max - min), (100m * (max - min) / count).ToString("N6"));
    Debug.WriteLine("done RNGCryptoServiceProvider milli " + sw.ElapsedMilliseconds.ToString("N2"));
    Debug.WriteLine("");
    sw.Restart();

    randomsInRange = new UInt32[modulo];
    Random rand = new Random();
    using (var csp = new System.Security.Cryptography.RNGCryptoServiceProvider())
    {
        for (int i = 0; i < count; i++)
        {
            workingByte = rand.Next(modulo);
            //Debug.WriteLine(workingByte);
            randomsInRange[workingByte]++;
        }
    }

    min = UInt32.MaxValue;
    max = UInt32.MinValue;
    for (int i = 0; i < modulo; i++)
    {
        value = randomsInRange[i];
        Debug.WriteLine("i {0}  count {1}  pct {2}", i, value.ToString("N0"), (100m * value / count).ToString("N4"));
        if (min > value)
            min = value;
        else if (max < value)
            max = value;
    }
    Debug.WriteLine("diff {0}  pct {1} ", (max - min), (100m * (max - min) / count).ToString("N6"));
    Debug.WriteLine("done Random milli " + sw.ElapsedMilliseconds.ToString("N2"));
    return randomsInRange;
}