QRN. Practical random numbers generation
Random numbers plays a significant role in modern cryptography. They are used to produce session keys, generate strong prime numbers, perform some numerical analysis, and many others. This is why creating a good random numbers is an important and a hard problem.
There are some pseudorandom number generators (PRNG) available that generate cryptographically secure random numbers by collecting samples from various entropy sources (such as user keystrokes, mouse events, etc.) to a distilling pool. One of the best examples for such PRNG would be Yarrow, designed by J. Kelsey, B. Schneier and N. Ferguson [1]. These PRNGs are excellent apart from a small thing - a proper amount of samples should be collected before start producing numbers.
Meantime I'd like to introduce another generator named QRN. It is extremely simple without slow pools and without mandatory initial seeding. QRN is suitable for applications that do not require cryptographically strong PRNG and where full featured generators like Yarrow would be an overkill.
All modern Intel processors (and most compatible ones like AMD) have a time stamp counter, a feature introduced since first Pentium [2]. This counter is a 64-bit value that increments every clock cycle while CPU is up. Taking low 8 bits of current counter value give a nice unpredictability, especially in a multitasking environment like Windows, Linux, etc. Please do not be fooled: this cannot be used as a proper PRNG because the resulting output would fail most of statistical and numerical analysis and tests on randomness. The output must be strengthened and this QRN is all about.
Linear feedback shift registers (LFSRs) are something known for ages. There is a nice coverage on these in [3], so I will skip the details here. An LFSR is very simple and is good enough from a mathematical point of view yet it is cryptographically insecure while used alone. QRN use an LFSR to strengthen the output of a time stamp counter by confusing them together.
The algorithm is easier to demonstrate than describe. Here is the C version and the code is quite straightforward:
#define LFSR(n) {if (n&1) n=((n^0x80000055)>>1)|0x80000000; else n>>=1;}
#define ROT(x, y) (x=(x<<y)|(x>>(32-y)))
unsigned long qrn(void)
{
static unsigned long rnd = 0x41594c49, x = 0x94c49514;
unsigned char y;
__asm
{
rdtsc;
mov [y], al;
}
LFSR(x); rnd ^= y ^ x; ROT(rnd,7);
return (rnd);
} /* qrn */
The output of QRN is a 32-bit random value. QRN passes all in the Diehard battery of tests of randomness [4]. It have a small footprint, high performance, and the generated output sequence is actually hard to reproduce.
The disadvantage of QRN is its platform dependency or, better say, dependency on a presence of a real-time stamp counter. Well, there is always Java and SecureRandom() for whom need a real cross-platform solution.
Why and what is "QRN" means? It is the abbreviation for Quite Random Numbers. It is also mean an atmospheric noise in Q-code, which is used in amateur radio communication.
References
- J. Kelsey, B. Schneier and N. Ferguson. Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator, http://www.schneier.com/paper-yarrow.html
- Intel Architecture Software Developer's Manual. Volume 2: Instruction Set Reference, http://developer.intel.com/design/pentium/manuals/
- B. Schneier, Applied Cryptography. 2nd Edition, 1996, John Wiley & Sons, ISBN 0-471-11709-9
- The Marsaglia Random Number CDROM with The Diehard Battery of Tests of Randomness, http://stat.fsu.edu/~geo/, http://www.csis.hku.hk/~diehard/cdrom/
