Random Number Generator: Difference between revisions

Newer x86 and x86-64 processors have the instruction RDSEED for generating random numbers.

To use RDSEED you will first need to check if the instruction is available.

mov eax, 7 ; set EAX to request function 7

mov ecx, 0 ; set ECX to request subfunction 0

shr ebx, 18 ; the result we want is in EBX...

and ebx, 1 ; ...test for the flag of interest...

 

If EBX is set to 1 (or ZF is unset), the instruction is available. Then it can be used to generate a 16/32/64 bit random number (depending on the register size used as an argument). If a random number was generated, the Carry flag is set.

 

mov ecx, 100 ; number of retries

.retry:

.done:

; random number is in EAX

 

It is up to you and your users to trust RDSEED. Because it is implemented in hardware, it effectively is a black box that may contain all sorts of bugs, or worse, backdoors.

== Cryptographically secure pseudorandom number generators ==

 

 

=== x86 RDRAND Instruction ===

RDRAND is slightly older than RDSEED, and provides ([https://software.intel.com/content/www/us/en/develop/blogs/the-difference-between-rdrand-and-rdseed.html what Intel claims to be]) a CSPRNG.

Its presence is indicated by CPUID leaf 1, ECX bit 30:

mov eax, 1 ; set EAX to request function 1

mov ecx, 0 ; set ECX to request subfunction 0

shr ecx, 30 ; the result we want is in ECX...

and ecx, 1 ; ...test for the flag of interest...

 

If ECX is set to 1 (or ZF is unset), the instruction is available. Usage is identical to RDSEED:

 

mov ecx, 100 ; number of retries

.retry:

.done:

; random number is in EAX

 

It is automatically seeded by the same entropy source that RDSEED reads from, and cannot be seeded manually. It therefore is subject to the same caveats as RDSEED.

 

[https://www.bentasker.co.uk/blog/software-development/689-writing-a-chacha20-based-csprng Writing (and backdooring) a ChaCha20 based CSPRNG] may be an interesting article on the subject, and how it can go wrong in surprising ways.

== Pseudorandom number generators ==

 

Taken directly from the [http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf C standard document (p. 347)]:

 

// The following functions define a portable implementation of rand and srand.

 

next = seed;

}

 

This is a fairly standard but mediocre [https://en.wikipedia.org/wiki/Linear_congruential_generator Linear Congruential Generator] (LCG). It returns 15 random bits.

In 1982, Brian Wichmann and David Hill [https://doi.org/10.2307/2347988 proposed] to combine three linear congruential generators, then normalizing and summing the results to get a number uniformly distributed between 0 and 1. A common instance is:

 

static uint16_t seed[3]; /* seed with numbers between 1 and 30000 */

float wichmann_hill(void) {

return fmod(seed[0] / 30269.0 + seed[1] / 30307.0 + seed[2] / 30323.0, 1.0);

}

 

This version is known to have a period of just shy of of seven trillion (the least common multiple of 30268, 30306, and 30322).

Implementation according to Wikipedia:

 

#include <stddef.h>

#include <stdint.h>

index++;

return y;

 

Some implementations automatically seed the generator with seed 5489, but this will (obviously) lead to the same outputs at every initialization.

If you are still not satisfied, you may want to build your own PRNG. You can do this in a fairly trial-and-error way by writing something that looks good and subjecting it to automated statistical testing suites such as [http://simul.iro.umontreal.ca/testu01/tu01.html TestU01]'s SmallCrush, Crush and finally BigCrush. These tests are very easy to run and can quickly point out problems, for example:

 

#include <unif01.h>

#include <bbattery.h>

unif01_DeleteExternGenBits(gen);

}

 

SmallCrush will report that this generator failed 12 out of 15 statistical tests. The other tests, which are also much slower, are therefore not necessary.