Computer Science & Perl Programming

Chapter 27. Random Number Generators and XS

Otmar Lendl

This article is a follow-up to John Orwant’s article, Randomness. I’d like to give some more background, provide another code snippet for serious pseudorandom number generation, and give a tour of XS, the bridge between Perl and C.

Random Versus Pseudorandom Numbers

Cryptography is the classic example of a domain that requires a good source of truly random numbers. Random numbers are used as session keys, initialization vectors, seeds for RSA prime number generation, and myriad other applications.

The security of a cryptographic algorithm usually depends on the futility of guessing the random numbers chosen by the computer. The key concept is entropy, a measure of the uncertainty contained in a set of values. For example, a user asked to type some random characters is much more likely to type asdf than 9m]g; the entropy is thus not as high as it would be if all strings were equally likely. Thus, even though we type in seven-bit ASCII, we can’t generate 35 random bits from just five keystrokes; a common rule of thumb is that the entropy per keystroke is in the range of 1.0 to 1.5 bits.^[16] So to generate 35 truly random bits, we need to use at least 35 keystrokes.

We can use this rule to build a random number generator that combines the entropy inherent in various computer components. They’ll be deterministic, but unpredictable from the outside—people who don’t have physical access to the computer haven’t a prayer of guessing the ...