4
\$\begingroup\$

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.

0..49 0..63

(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 ints 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

\$\endgroup\$
  • \$\begingroup\$ Fun part about real randomness: it's entirely possible (though "unlikely" is a severe understatement) for you to legitimately get the same number a million times in a row. I'd be a bit more skeptical of a flat line than one with spikes in it, unless the spikes always occurred in the same places. \$\endgroup\$ – cHao Nov 26 '11 at 6:41
  • \$\begingroup\$ @cHao - Just to point out how unlikely that scenario is, Int32.MaxVal ^ 1000000 gives an error in windows calculator and returns Double.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 \$\endgroup\$ – ligos Nov 26 '11 at 9:11
3
\$\begingroup\$

Yes, the algorithm as described is sound, although not the most efficient use of the random number source. However, there are a few surprises in the code. Making the default Next() capable of returning 2^31 - 1 distinct values is a bit unexpected, and slightly skews the distribution of the lower bits. It might be worth changing the names, too, in case you want to add more output types later. I would adjust as follows:

    public int NextInt32()
    {
        byte[] bytes = GetRandomBytes(4);
        int i = BitConverter.ToInt32(bytes);
        return i & Int32.MaxValue;
    }

    public int NextInt32(int maxExcl)
    {
        if (maxExcl <= 0) throw new ArgumentOutOfRangeException("maxExcl", maxExcl, "maxExcl must be positive");

        // Let k = (Int32.MaxValue + 1) % maxExcl
        // Then we want to exclude the top k values in order to get a uniform distribution
        // You can do the calculations using uints if you prefer to only have one %
        int k = ((Int32.MaxValue % maxExcl) + 1) % maxExcl;
        while (true)
        {
            int rnd = NextInt32();
            if (rnd <= Int32.MaxValue - k)
                return rnd % maxExcl;
        }
    }

    public int NextInt32(int minIncl, int maxExcl)
    {
        if (minIncl < 0)
            throw new ArgumentOutOfRangeException("minIncl", minIncl, "minValue must be non-negative");
        if (maxExcl <= minIncl)
            throw new ArgumentOutOfRangeException("maxExcl", maxExcl, "maxExcl must be greater than minIncl");

        return minIncl + NextInt32(maxExcl - minIncl);
    }
\$\endgroup\$
1
\$\begingroup\$

I think that looping until a number within range pops up is a very weird idea. The first potential problem that comes to mind is the possibility that under certain circumstances (say, max = min + 2) you might be looping for a long time. A closer examination of your code shows that such a possibility is taken care of, but at the expense of significant added complexity. Why not just apply the modulus operator between the generated random 32-bit integer and the desired range? This would simplify your code and greatly reduce its length. It is a lot easier to tell whether a short and simple piece of code is sound, than a long and complicated one.

\$\endgroup\$
  • \$\begingroup\$ Ahhh, modulus! Why didn't I think of that. I'm accepting Peter's answer because he supplied code I could test though. \$\endgroup\$ – ligos Nov 27 '11 at 3:44
  • 1
    \$\begingroup\$ Modulus wouldn't work because the lower numbers would appear more frequently. Consider generating a number in the range 0..200 from a 8 bit random number: x = random(256) % 200. P(x == 0) = 2/256 and P(x == 199) = 1/256 \$\endgroup\$ – Phil Nov 19 '12 at 14:25
  • \$\begingroup\$ @Phil Not that it matters much now that the question has an accepted answer, but I think that modulus will yield a skewed distribution favoring smaller numbers only if the desired range represents a significant portion of the original range. In other words, if you have random byte values and you need indexes between 0 and 200, then modulus is probably not a very good idea. But if you group every four random bytes into a random 32-bit integer, as I suggested, and then apply modulus, then you should be fine for any reasonable range of indexes. No? \$\endgroup\$ – Mike Nakis Nov 22 '12 at 23:09
  • 1
    \$\begingroup\$ In the end it will depend how much bias is acceptable for the application. If you assume that the OP is using RNGCryptoServiceProvider because it is security sensitive, then it is likely easier to have no bias than to work out how much is acceptable. \$\endgroup\$ – Phil Nov 23 '12 at 13:53
  • \$\begingroup\$ Need to reject values greater than the last modus to remove bias. Easy enough. \$\endgroup\$ – paparazzo Apr 29 '17 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.