So you can get random numbers, not just random bytes.
You can read other Turninger posts which outline my progress building a the Fortuna CPRNG.
So far, we have the PRNG
BlockCypherCprngGenerator, which has been verified as random, and a console app which outputs random data to file or stdout.
Programmers usually need random numbers rather than just random bytes.
So we’re going to write a bunch of helper functions to read bytes from any
IRandomNumberGenerator, and return a number meeting some critera.
We also need to check their outputs are uniformly distributed (although not to the same degree of rigour as testing the core generator).
All the helper methods will be extension methods, as we are adding value to anything which implements
IRandomNumberGenerator (and I’m expecting there to be several implementations in Terninger).
There is a (small) performance hit to this because we’ll always be calling through an interface. But that should be minor compared to the cost of generating random bytes using a block cypher.
Booleans are easy because there are only two options.
We read one byte, and check if its greater than or equal to 128.
Which gives a 50% chance of
(And yes, I had to think hard about whether 127 or 128 was the right number, and if I should use greater than or greater than or equal to).
And I’ve noted the allocation of an array as a future performance improvement.
Integers are more interesting, and more important to developers. The standard Random class will generate integers within ranges, which lets a programmer randomly chose an element in an array (among other things).
I’ve already implemented this in makemeapassword.org, but there was a little refactoring in order.
The most primitive method does not generate integers, but unsigned integers in the range 0..232.
So far, that’s pretty much the same as
To get a random integer (
Int32), we simply mask off to top bit of the
Again, this is easy enough.
But getting a random int with a maximum is more tricky. For powers of two, we’d just need to mask off the top bits. However, we don’t have that luxury; any int is a possible maximum.
I’m not going to pretend I understand how the modulus (
%) operator is working here; I think it is masking the top (unused) bits off the random number.
We still need to loop until we find a number less than our maximum, lest we end up with a skewed distribution above (or below) the nearest power of 2.
(Credit to Peter Taylor on StackOverflow Code Review for this concept).
Once we have a uniform distribution of ints from 0..n, it’s easy to allow the 0 to be arbitrary.
And we can use exactly the same concepts for generating
Random number generators tend to produce floats and doubles as values between 0 and 1. In many ways, the floating point helpers are the simplest to implement.
Although simple, it relies on at least two important things:
- That floating point numbers can represent really small values (that is,
1.0 / UInt64.MaxValueis usable and doesn’t get rounding into zero).
- That the .NET framework will magically convert an
Singlewithout me thinking about where the bits go.
Unlike the trick used for floating point numbers, the Decimal type has no such short cut.
To get maximum precision in a
Decimal we need three
Int32s (as decimals have around 96 bits of internal precision), and .NET has no
Int128 type to do the magic division and multiplication.
Here, we manually fill the content of a decimal with those 3 random
The masking of the
hi value is to ensure the values produced are not greater than 1.
However, that mask produces values between 0 and 0.25.
So, that magic
4.038m is a scaling factor to produce the required 0 to 1.0 range.
The really cool part about this implementation is there are no loops involved! And, you have around 94 bits of precision in the random number.
Guids can be generated as large random numbers. Effectively, they are a 122 bit random number, with 6 bits set as special ‘version’ or ‘variant’ markers.
Beyond masking out the special bits, there’s nothing unusual going on here: just generate random bytes and feed them into the Guid.
Guid.NewGuid(), I’m not sure if this helper is any better in terms of randomness or performance.
But it is an alternative that has no “magic” involved (that is, we can see all the source code).
So how do you test a random number generator? (Other than re-writing the more comprehensive test suites I already ran).
For the moment, I’ve settled on two basic tests.
The first is to hard code the first 10 values returned when using a null seed. This tests for determinism, and no silly exceptions, but not much else: its a very basic regression test.
The second is much harder to automate, and tries to make sure the distribution of numbers is uniform. This is of a particular concern when getting an integer in a non-power-of-two range. The results get dumped out to a text file as raw values and as a histogram, and I inspect them manually (and you can inspect them below).
For each different helper method, there’s a fuzzing test which dumps 10,000 results to a text file, which I can import into Excel to graph and check the distribution. Graphs follow:
These are obviously not as rigorous as the previous random test, but good enough to make sure there are no obvious distribution problems.
(Note that Excel’s numbers are always double precision floats, so we lose some precision for Decimal and Int64 tests).
I coded some basic benchmarks which ask for one number from each of the helper methods using Benchmark .NET. Here are the results on my laptop:
All helper methods are pretty similar in performance. Within a few microseconds of each other.
Because every time you call any of the numeric helpers the
BlockCypherCprngGenerator will generate 16 random bytes (usually only 8 or less bytes will actually be used), and then a further 32 random bytes to re-key the generator (in line with the strict forward secrecy requirements of Fortuna).
Basically, the expensive part of generating an random number is encrypting 3 blocks with AES and re-keying the cypher.
I’ll investigate how much I can mitigate and improve this in the future.
We’ve added an API to generate random numbers to make the core Fortuna / Terninger PRNG more useful to application developers.
You can see the actual code in BitBucket.
The next step will be to allow customising the PRNG. Some customisations will be to allow flexibility (different block cyphers), some for new functionality (adding small amounts of additional entropy), and some with performance in mind (larger buffer and block sizes).