10
\$\begingroup\$

I have a requirement to generate a uniform distribution of cryptographically secure random numbers. To generate these numbers I only know of the RNGCryptoServiceProvider class, that has the method GetBytes(byte[] data). This is good, but I have to then change this discrete uniform distribution ranging from 0 - 256 to a different discrete uniform distribution ranging from 0 - limit.

And so I thought of three ways to do this. The first two ways were using % and /, which don't work if limit is not a divisor of 256. As this leads to a non-uniform distribution. However filtering all numbers that a not less than the limit works and gives a uniform distribution, however has terrible performance problems when limit is a small number.

I'm currently using:

private static IEnumerable<object> Cycle(object value=null)
{
    while (true)
    {
        yield return value;
    }
}

private static IEnumerable<byte> RandomBytes(int chunkSize)
{
    return Cycle().SelectMany(unused =>
    {
        var b = new byte[chunkSize];
        new RNGCryptoServiceProvider().GetBytes(b);
        return b;
    });
}

private static IEnumerable<int> RandomFilter(int chunkSize, int limit)
{
    return RandomBytes(chunkSize).Where(n => n < limit).Select(n => (int)n);
}

Since I tried using % and /, below is the code that I used to check if there is a uniform distribution, and those two solutions.

private static IEnumerable<int> RandomModulo(int chunkSize, int limit)
{
    return RandomBytes(chunkSize).Select(n => n % limit);
}

private static IEnumerable<int> RandomResize(int chunkSize, int limit)
{
    var denom = 256.0/limit;
    return RandomBytes(chunkSize).Select(n => (int)(n / denom));
}

private static void TestDistribution(int limit, int amount, int chunkSize, Func<int, int, IEnumerable<int>> fn)
{
    var counter = new Dictionary<int, int>();
    foreach (var i in Enumerable.Range(0, limit))
    {
        counter[i] = 0;
    }

    foreach (var i in fn(chunkSize, limit).Take(amount))
    {
        counter[i] += 1;
    }
    Console.WriteLine($"{limit} {amount} {chunkSize} {counter.Select(kv => kv.Value).Aggregate(0, (acc, x) => acc + x)}");
    Console.WriteLine(string.Join(", ", from kv in counter select $"{kv.Key}"));
    Console.WriteLine(string.Join(", ", from kv in counter select $"{kv.Value}"));
    Console.WriteLine();

}

private static void Main()
{
    TestDistribution(45, 100000000, 1000, RandomFilter);
    TestDistribution(32, 100000000, 1000, RandomFilter);
    Console.WriteLine();

    TestDistribution(45, 100000000, 1000, RandomModulo);
    TestDistribution(32, 100000000, 1000, RandomModulo);
    Console.WriteLine();

    TestDistribution(45, 100000000, 1000, RandomResize);
    TestDistribution(32, 100000000, 1000, RandomResize);
    Console.ReadLine();
}
\$\endgroup\$
5
  • \$\begingroup\$ I wrote some extension methods for generating high entropy random numbers for a shuffle. I take the fewest bytes necessary for the range and reject at most 50% of the generated values. \$\endgroup\$ Commented Mar 6, 2017 at 13:22
  • \$\begingroup\$ Why not just use Random as it will take a range as input? \$\endgroup\$ Commented Mar 6, 2017 at 14:10
  • \$\begingroup\$ @Paparazzi maybe because Random is a PRNG and has low entropy. \$\endgroup\$ Commented Mar 6, 2017 at 14:34
  • \$\begingroup\$ Note that RNGCryptoServiceProvider implements IDisposable and therefore should be wrapped in a using construct to ensure a proper deterministic lifetime. \$\endgroup\$ Commented Mar 6, 2017 at 21:35
  • \$\begingroup\$ Drawing from a cryptographically secure source normally means relatively high cost compared to conventional PRNGs. Depending on how important performance is, you might want to use a bit recycling method. \$\endgroup\$ Commented Mar 7, 2017 at 6:19

2 Answers 2

Reset to default
3
\$\begingroup\$

There are things you can do to improve the efficiency of your filter solution with small values as the limit.

More efficient filtering

The most obvious one is actually given in the example of the function on the MSDN network - which is basically to extend the filter range to the highest multiple of limit, less than 256. I.e. if the limit is 20, then filter up to 240, and then the modulo is still uniformly distributed:

Copied from that page:

private static bool IsFairRoll(byte roll, byte numSides)
{
    // There are MaxValue / numSides full sets of numbers that can come up
    // in a single byte.  For instance, if we have a 6 sided die, there are
    // 42 full sets of 1-6 that come up.  The 43rd set is incomplete.
    int fullSetsOfValues = Byte.MaxValue / numSides;

    // If the roll is within this range of fair values, then we let it continue.
    // In the 6 sided die case, a roll between 0 and 251 is allowed.  (We use
    // < rather than <= since the = portion allows through an extra 0 value).
    // 252 through 255 would provide an extra 0, 1, 2, 3 so they are not fair
    // to use.
    return roll < numSides * fullSetsOfValues;
}

Statistically insignificant errors

You have another alternative too, which is to reduce any modulo bias to a statistically insignificant amount. You do this by using significantly bigger random numbers (bigger than 256). Combining multiple bytes for each output byte would accomplish this, for example, using 4 bytes. Using more bytes would further reduce any modulo bias:

/* Convert 4 bytes to a long */
private static IEnumerable<long> RandomLongs()
{
    var csrng = new RNGCryptoServiceProvider();
    return Cycle().Select(unused =>
    {
        var bytes = new byte[4];
        csrng.GetBytes(bytes);
        return  (long)(BitConverter.ToUInt32( bytes, 0));
    });
}

private static IEnumerable<int> RandomExtended(int chunkSize, int limit)
{
    var source = RandomBytes(chunkSize);
    foreach (long lng in RandomLongs())
    {
        var nxt = lng % limit;
        yield return (int)nxt;
    }

}

Using 4 bytes of source for your modulo (with max limit 256) will reduce the bias error to about 1 in \$2^{24}\$ ... which would be hard to measure.

This version is also shown here on ideone: https://ideone.com/maiQ70

Removed

On the other hand, there's a better way, that still guarantees uniform distribution, but relies on knowing what the previous value was. Conceptually, this solution relies on having uniform "gaps" between results, and so you can add a uniform random gap to the previous value, and then do the modulo on that.

I implemented it as:

private static IEnumerable<int> RandomWrap(int chunkSize, int limit)
{
    int prev = 0;
    foreach (byte b in RandomBytes(chunkSize))
    {
        prev = (prev + b) % limit;
        yield return prev;
    }

}

Note that it takes the byte-value as a "gap", adds it to the previous result, and then "wraps" it around in the limit range.

You can see the results here in ideone: https://ideone.com/BEbwsA

\$\endgroup\$
3
  • \$\begingroup\$ Do you have a source/proof for the second approach? \$\endgroup\$ Commented Mar 6, 2017 at 15:04
  • \$\begingroup\$ @AJMansfield - No, not yet, I have looked, but my google-fu is lacking this time, so I have also asked here crypto.stackexchange.com/q/44470/11006 \$\endgroup\$ Commented Mar 6, 2017 at 15:49
  • 1
    \$\begingroup\$ @AJMansfield - as per the answer I've accepted on Crypto.se the concept of using uniformly distrributed "gaps" has a flaw in that each value will have a bias you can predict from the previous value. I am adjusting my answer to correct it. \$\endgroup\$ Commented Mar 6, 2017 at 19:30
0
\$\begingroup\$

As mentioned by Jesse C. Slicer, I should wrap RNGCryptoServiceProvider in a using. And so I should change RandomBytes to something like:

private static IEnumerable<byte> RandomBytes(int chunkSize)
{
    using (var rng = new RNGCryptoServiceProvider())
    {
        while (true)
        {

            var b = new byte[chunkSize];
            rng.GetBytes(b);
            foreach (var i in b)
            {
                yield return i;
            }
        }
    }
    // ReSharper disable once IteratorNeverReturns
}

This requires me to use a while, so that the rng doesn't expire whilst generating numbers, and will only be removed by the using when the while is stopped. This should happen if the garbage collector removes the function before the program ends, or when the program ends.

As commented by sh1, there's another way I can acheave this:

Bit recycling method

The following algorithm uses a similar (but slightly different) idea. It uses two internal integer variables, m and r, which are not reset at the beginning of the algorithm (in C, you would declare them as "static"). Initially, m = 1 and r = 0. We also have a parameter N, which is a large integer such that 2N can still be represented exactly in the computer. As said before, n is the modulus of the numbers you want to produce (they will be between 0 and (n - 1)), we must have n < N, and we have a function NextBit() that returns a truly random bit.

  1. WHILE m < N DO r : = 2*r + NextBit(); m = 2*m; (r is a random variable of modulus m)

  2. Divide m by n : m = n*q + b

  3. IF r >= n*q, let m : = m - n*q, r : = r - n*q (r is still a random variable of modulus m), and go to step 1.

  4. Otherwise, let x : = r mod n, r : = [r/n], and m : = q, and return x

There's a bug with step 3, it should use r = r % (n*q) this is as some inputs go out of bounds, such the source: 10011111111110110100110110011010111011011000010000010101, when \$N=64\$, and \$n=45\$. And so to test this function I used the following code. I do however not wrap source.GetEnumerator(), with a using, as this is a simple POC, and I'd go into fixing if I were to use it.

public class DiscreteUniformDistribution
{
    private readonly IEnumerator<bool> _source;
    private readonly int _max;
    private int _m;
    private int _r;

    public DiscreteUniformDistribution(IEnumerable<bool> source, int max = 256)
    {
        _source = source.GetEnumerator();
        _max = max;
        _m = 1;
        _r = 0;
    }

    private int _Next()
    {
        if (!_source.MoveNext()) {
            throw new IndexOutOfRangeException("source has nomore values.");
        }
        return _source.Current ? 1 : 0;
    }

    public int Next(int limit)
    {
        if (limit >= _max) {
            throw new ArgumentOutOfRangeException($"limit is not less than the max of this class. {limit} >= {_max}.");
        }

        while (true) {
            while (_m < _max) {
                _r = 2 * _r + _Next();
                _m *= 2;
            }
            var q = _m / limit;
            var nq = limit * q;
            if (_r > nq)
            {
                _m -= nq;
                _r %= nq;
            }
            else
            {
                var ret = _r % limit;
                _m = q;
                _r /= limit;
                return ret;
            }
        }
    }

    public IEnumerable<int> Iter(int limit)
    {
        while (true) {
            int ret;
            try {
                ret = Next(limit);
            } catch (IndexOutOfRangeException) {
                break;
            }
            yield return ret;
        }
    }
}

This however is slower than rolfls "more efficient filtering" method by about five times. But is faster than "statistically insignificant errors" by about 75%. And so I'm using "more efficient filtering" with RNGCryptoServiceProvider.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.