FPX: Many applications require random numbers.
This includes -
The deterministic nature of computers makes it impossible for computer software to come up with truly random numbers.
Hardware devices exist that produce random numbers from unpredictable (or at least unpredictably complex) physical effects such as athmospheric noise or radioactive decay, or even the movement of liquids in a common lava lamp. Some operating systems (e.g., Linux) derive reasonably random numbers from user behavior, such as the time between keyboard inputs (i.e., something like "nanoseconds between hitting two keys"), or mouse movement.
True Random Numbers downloads true random numbers from a free internet service.
Without access to such a device, the best a software can do is to use pseudo-random numbers, which are produced by mathematical algorithms.
The canonical reference for pseudo-random numbers is Donald E. Knuth's The Art of Computer Programming, Volume 2: Seminumerical Algorithms.
Tcl provides a pseudo-random number generator as part of the expr command:
expr rand()
returns a random number between 0 and 1.
Tcl's random number generator highlights a weakness that applies to all pseudo-random number generators: it has to be initialized, or "seeded." The initial seed value fully determines the sequence of numbers that is generated. If the generator is seeded with the same value over and over, it will keep producing the same random numbers.
Tcl's random number generator is as bad as many, and worse than some, in that it only accepts a single 31 bit integer as a seed value. In other words, there are only 2^31 possible random number sequences, and they repeat after a period of 2^31. For applications that only care about the distribution of pseudo-random numbers across the value space, such as simulated dice, that can be considered good enough. In cryptography, such a random number generator is not considered cryptographically secure. An attacker could potentially make a brute-force attempt to recover a random number sequence by checking all 2^31 seed values.
Many applications, and Tcl's random number generator (when not seeded by the application), cheat by using something like the time of day (e.g., [clock seconds]) as a seed value. However, for cryptographical applications, that is about the worst thing that can be done. Because [clock seconds] returns a number in a very narrow range, so an attacker could make a good prediction of the values that need to be tested. Using a higher resolution timer, such as [clock clicks], improves the issue by a cryptographically insigngificant margin only.
Therefore, we have a chicken and egg problem: in order to have unpredictable random numbers, a pseudo-random number generator needs to be initialized with a random seed.
Thus we have two problems to solve, if we want to improve upon Tcl's pseudo-random number generator:
Two candidates for a better algorithm are