Penguin
Blame: RandomNumberGenerator
EditPageHistoryDiffInfoLikePages
Annotated edit history of RandomNumberGenerator version 15, including all changes. View license author blame.
Rev Author # Line
5 AristotlePagaltzis 1 A RandomNumberGenerator is either a piece of hardware or software that generates random numbers in the widest sense. A good one is crucial to applications in [Cryptography]: if an attacker can guess the sequence of "random" numbers used to generate keys or other variables for your algorithm, he gets an important foot in the door for cracking your communication -- or can even walk right in. There are many different approaches for [RandomNumberGenerator]s, however, the biggest distinction is between true vs pseudorandom number generators.
1 StuartYeates 2
3 AristotlePagaltzis 3 !!! True random number generators
1 StuartYeates 4
5 AristotlePagaltzis 5 These __must__ be hardware by definition. A variety of approaches for their design exist, but listening to white noise or radioactive decay seem to be the most popular ones. There are a number of publicly queriable true random number generators on the web, such as [http://www.random.org/] and [http://www.fourmilab.ch/hotbits/].
3 AristotlePagaltzis 6
7 !!! Pseudorandom number generators
8
6 AristotlePagaltzis 9 A pseudo random number generator such as offered by the random(3) and rand(3) functions of the standard [C] library generates numbers using mathematical [Algorithm]s.
3 AristotlePagaltzis 10
13 AristotlePagaltzis 11 ;: ''Anyone attempting to produce random numbers by purely arithmetic means is, of course, in a state of sin.'' %%% --JohnVonNeumann
3 AristotlePagaltzis 12
10 AristotlePagaltzis 13 An inevitable consequence is that such a generator has a "period", which means that it produces a repeating sequence of numbers. The proof of this derives from the fact that computers are [FiniteStateMachine]s. With a good algorithm though, the period length can well reach billions of numbers.
6 AristotlePagaltzis 14
15 However, designing such an algorithm is difficult terrain which requires thorough understanding of statistics and very sharp math skills. __Do not attempt to roll your own.__ Most naive attempts at handrolled pseudorandom number generators have alarmingly short period lengths. Often, hapless programmers will try to make a "better" generator by lumping together two different algorithms with decent period lengths each -- but the result is almost invariably a generator with a ''shorter'' period!
16
17 Another problem in cryptographical applications of pseudorandom numbers is that the algorithm is known. If you know a long enough sequence of generated numbers, you can simply solve the resulting equations yourself and then predict the numbers the generator will be producing next. There is an obvious solution: the algorithm must include enough hidden state so that a solvable set of equations cannot be formulated just by looking at a number sequence it generated.
18
19 But note that true randomness still is not always desirable. Random number sequences often have certain specific characteristics which make them better suited as input to certain kinds of statistical algorithm, because they cause a far faster convergence toward the same final result than truly random numbers could. Truly random numbers also make debugging much harder for obvious reasons; if you want to verify an algorithm, you want to be able to replay "random" number sequences as necessary. On the other hand, you will usually need a statistically decently random sequence to examine the longterm behaviour of the algorithm, so just using a sequence with regular characteristics wouldn't work.
3 AristotlePagaltzis 20
21 So there are many areas where pseudorandom numbers are actually more desirable than truly random ones.
10 AristotlePagaltzis 22
23 See also: srand(3), srandom(3), drand48(3), erand48(3), jrand48(3), lrand48(3), mrand48(3), nrand48(3), srand48(3)
3 AristotlePagaltzis 24
25 !!! Hybrids
26
11 AristotlePagaltzis 27 In [Unix] systems, there are commonly random(4) and urandom(4) devices. They are regular pseudorandom number generators, but include a twist that lets them generate higher quality random numbers than otherwise expected: their seed is periodically perturbed using using low-level timing information from entropy sources which only the [Kernel] has proper access to, such as the network, mouse, and keyboard. These generators are considered a sufficient for everything except highly sensitive cryptographic applications such as PublicKey generation (see RFC:1750 on best practices).
14 AndersGreen 28
15 AristotlePagaltzis 29 ;: ''The generation of random numbers is too important to be left to chance.'' %%% -- Robert R. Coveyou
8 StuartYeates 30
10 AristotlePagaltzis 31 In [Java] systems, instances of the class __java.security.!SecureRandom__ operate in a similar fashion. Making instances of this class can take several seconds while the [JVM] tries to russle up entropy.
8 StuartYeates 32
13 AristotlePagaltzis 33 The weakness of such a hybrid approach is that while its inputs are hard to predict from outside or spy on from inside the system encapsulated by the [Kernel] or the [Java] VirtualMachine, it may itself may be separated from the hardware by a middle man. A [JVM] commonly runs as a regular process under control of an OperatingSystem. So does the [Kernel] of a VirtualPrivateServer. In such a situation it is possible predict the generated sequence or even to force the generator to produce repetitive results.
8 StuartYeates 34
35 ----
36 CategoryCryptography