How to generate a cryptographically secure random integer within a range?

Question

I have to generate a uniform, secure random integer within a given range for a program that generates passwords. Right now I use this :

RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
byte[] rand = new byte[4];
rng.GetBytes(rand);
int i = BitConverter.ToUInt16(rand, 0);
int result = i%max;   //max is the range's upper bound (the lower is 0)

Is this method safe to use for cryptographic purposes ? If not, how should I do it ?

Solution 1

You can have a look to CryptoRandom class taken from https://gist.github.com/1017834 which is the Original version by Stephen Toub and Shawn Farkas. In this class they implement several random generators that seem to be cryptographically secures.

I have used the following version in my projects for random int generation.

public class RandomGenerator
{
    readonly RNGCryptoServiceProvider csp;

    public RandomGenerator()
    {
        csp = new RNGCryptoServiceProvider();
    }

    public int Next(int minValue, int maxExclusiveValue)
    {
        if (minValue >= maxExclusiveValue)
            throw new ArgumentOutOfRangeException("minValue must be lower than maxExclusiveValue");

        long diff = (long)maxExclusiveValue - minValue;
        long upperBound = uint.MaxValue / diff * diff;

        uint ui;
        do
        {
            ui = GetRandomUInt();
        } while (ui >= upperBound);
        return (int)(minValue + (ui % diff));
    }

    private uint GetRandomUInt()
    {
        var randomBytes = GenerateRandomBytes(sizeof(uint));
        return BitConverter.ToUInt32(randomBytes, 0);
    }

    private byte[] GenerateRandomBytes(int bytesNumber)
    {
        byte[] buffer = new byte[bytesNumber];
        csp.GetBytes(buffer);
        return buffer;
    }
}

Solution 2

There are two issues in the accepted answer.

• It does not dispose the disposable csp correctly
• When minvalue equals to maxvalue, it throws error (standard random method does not)

Revised code

using System;
using System.Security.Cryptography;

namespace CovidMassTesting.Helpers
{
    /// <summary>
    /// Secure random generator
    /// 
    /// https://stackoverflow.com/questions/42426420/how-to-generate-a-cryptographically-secure-random-integer-within-a-range
    /// </summary>
    public class RandomGenerator : IDisposable
    {
        private readonly RNGCryptoServiceProvider csp;
        /// <summary>
        /// Constructor
        /// </summary>
        public RandomGenerator()
        {
            csp = new RNGCryptoServiceProvider();
        }
        /// <summary>
        /// Get random value
        /// </summary>
        /// <param name="minValue"></param>
        /// <param name="maxExclusiveValue"></param>
        /// <returns></returns>
        public int Next(int minValue, int maxExclusiveValue)
        {
            if (minValue == maxExclusiveValue) return minValue;

            if (minValue > maxExclusiveValue)
            {
                throw new ArgumentOutOfRangeException($"{nameof(minValue)} must be lower than {nameof(maxExclusiveValue)}");
            }

            var diff = (long)maxExclusiveValue - minValue;
            var upperBound = uint.MaxValue / diff * diff;

            uint ui;
            do
            {
                ui = GetRandomUInt();
            } while (ui >= upperBound);
            return (int)(minValue + (ui % diff));
        }

        private uint GetRandomUInt()
        {
            var randomBytes = GenerateRandomBytes(sizeof(uint));
            return BitConverter.ToUInt32(randomBytes, 0);
        }

        private byte[] GenerateRandomBytes(int bytesNumber)
        {
            var buffer = new byte[bytesNumber];
            csp.GetBytes(buffer);
            return buffer;
        }
        private bool _disposed;
        /// <summary>
        /// Public implementation of Dispose pattern callable by consumers.
        /// </summary>
        public void Dispose()
        {
            Dispose(true);
            GC.SuppressFinalize(this);
        }
        /// <summary>
        /// Protected implementation of Dispose pattern.
        /// </summary>
        /// <param name="disposing"></param>
        protected virtual void Dispose(bool disposing)
        {
            if (_disposed)
            {
                return;
            }

            if (disposing)
            {
                // Dispose managed state (managed objects).
                csp?.Dispose();
            }

            _disposed = true;
        }
    }
}

Usage

/// <summary>
        /// Generates a Random Password
        /// respecting the given strength requirements.
        /// </summary>
        /// <param name="opts">A valid PasswordOptions object
        /// containing the password strength requirements.</param>
        /// <returns>A random password</returns>
        public static string GenerateRandomPassword(PasswordOptions opts = null)
        {
            if (opts == null) opts = new PasswordOptions()
            {
                RequiredLength = 10,
                RequiredUniqueChars = 4,
                RequireDigit = true,
                RequireLowercase = true,
                RequireNonAlphanumeric = true,
                RequireUppercase = true
            };

            string[] randomChars = new[] {
                "ABCDEFGHJKLMNOPQRSTUVWXYZ",    // uppercase 
                "abcdefghijkmnopqrstuvwxyz",    // lowercase
                "0123456789",                   // digits
                "!@$?_-"                        // non-alphanumeric
            };

            using RandomGenerator rand = new RandomGenerator();
            List<char> chars = new List<char>();

            if (opts.RequireUppercase)
                chars.Insert(rand.Next(0, chars.Count),
                    randomChars[0][rand.Next(0, randomChars[0].Length)]);

            if (opts.RequireLowercase)
                chars.Insert(rand.Next(0, chars.Count),
                    randomChars[1][rand.Next(0, randomChars[1].Length)]);

            if (opts.RequireDigit)
                chars.Insert(rand.Next(0, chars.Count),
                    randomChars[2][rand.Next(0, randomChars[2].Length)]);

            if (opts.RequireNonAlphanumeric)
                chars.Insert(rand.Next(0, chars.Count),
                    randomChars[3][rand.Next(0, randomChars[3].Length)]);

            for (int i = chars.Count; i < opts.RequiredLength
                || chars.Distinct().Count() < opts.RequiredUniqueChars; i++)
            {
                string rcs = randomChars[rand.Next(0, randomChars.Length)];
                chars.Insert(rand.Next(0, chars.Count),
                    rcs[rand.Next(0, rcs.Length)]);
            }

            return new string(chars.ToArray());
        }

Comments

[wablab]

I notice that you're generating a 4-byte random sequence, but then converting that to a 2-byte integer (ushort / UInt16). Perhaps generate either a 2-byte sequence or convert the 4-byte sequence to uint / UInt32. I'm not sure whether the modulo affects cryptographic security in this instance.

[wablab]

This post seems to indicate that what you're doing is pretty good: stackoverflow.com/questions/5008804/…. Or follow this post to create a cryptographically secure double between 0 and 1, and then multiply the result by your upper max? stackoverflow.com/questions/2854438/…

[Artjom B.]

Modulo doesn't lead to cryptographically secure random numbers. There are many examples over on Cryptography. This is the one I found quickly: crypto.stackexchange.com/q/22767/13022

[afonte]

I posted an asnwer, but I realised that I was not giving any help. So I deleted it, Im sorry.

[afonte]

I think I posted a better answer now :)

[Maarten Bodewes]

@wablab Double and secure don't go together well, rounding issues will make it almost 100% sure that the result is biased, even ever so slightly (but ever so slightly is very dangerous when it comes to cryptography.

[Hey]

Thank you. I'm not sure I understand what it does, because it uses functions defined elsewhere and is further complicated to be thread-safe, but once I understand it I'll consider using it.

[Jon Hanna]

Something to pay particular attention to is the way the loop gets rid of bias; it works out the largest range that could be moduloed without bias and then loops until it gets a number in that range. It costs to do those loops, but every time it has to is a time that just moduloing would have bias. Calculating the largest range that would work reduces how often that happens.

[afonte]

Thank you so much for your explanation.

[Maarten Bodewes]

@JonHanna But it is not particularly efficient when it comes to ranges that are slightly over $2^31$ for the value of diff, as the change of the while loop repeating is almost 50%. This can be avoided by asking for 5 bytes, converting those to a long and then performing the algorithm.

[Jon Hanna]

@MaartenBodewes but then that's less efficient in other cases, so it's swings and roundabouts.

[Maarten Bodewes]

@afonte I'd answer without the buffering implementation for random numbers - it's simply spurious for this question. Also note that GetRandomUInt depends on the rest of the class to function.

[Maarten Bodewes]

@JonHanna You can tweak that by asking for e.g. 1 byte more than the minimum of bytes required. There are certainly ways to have less severe worse case scenarios.

[afonte]

@JonHanna and MaartenBodewes thank you for your wise advises. I like this topic but you certainly have much more experience than me. In order to improve my answer I implemented GetRandomUInt inside a smaller class adapted to this question. I will try to improve the algorithm in the future following your points of views. If you have a better approach for doing this please share it, it will be appreciated.

[Maarten Bodewes]

@afonte Be very careful about doing so - easy to make mistakes. I tried to find the Java code for it (SecureRandom has a nextInt(int) method that is pretty efficient, but it is too much oriented to solve the sign issues in Java (in Java all integers are signed). I see some issues with the code above, I wanted to upvote, but I guess some things need to be resolved first.

[Maarten Bodewes]

Above code is at least faulty when 0 or 1 bytes of randomness is requested. GetRandomUInt should probably be replaced with a non-optimized version that directly uses RNGCryptoServiceProvider, without the rest of the implementation, the code cannot be used directly.

[afonte]

@MaartenBodewes I added a second option using RNGCryptoServiceProvider as you suggested. Do you think I should delete the first one?

[Maarten Bodewes]

You should probably integrate the two. The first one is wrong for range sizes 1 & 2 and doesn't use the RNG directly. The new one results in biased output. You do need at least the trick with the upperbound.

[afonte]

@MaartenBodewes I made the integration. I also decided to remove the thread safe part because it is spurious for this question as you said before. Feel free to edit my answer or to give me more advises if you see any improvements to do.

[Maarten Bodewes]

Looks OK now. It's a bit spurious to ask for a random if the range is [N, N+1) as N is the only viable option, but that's not a big issue - the code should still run.

[Brian]

Note: If you're using this as a drop-in replacement for Random, you'll want minValue == maxExclusiveValue to return minValue. This incorrectly treats maxExclusiveValue as an inclusive value...but that's how System.Random.Next(Int32,Int32) is implemented.

[Matt]

Yes, according to the link you provided, RNGCryptoService provider is indeed obsolete. But the example you gave doesn't work, it brings up the error CS1503 Argument 1: cannot convert from 'int' to 'byte[]'. If you just want to get a random integer, use RandomNumberGenerator.GetInt32(...) - either with one GetInt32(toMaxExclusive) or two arguments GetInt32(min, toMaxExclusive).