The Linear Congruent random number generator is the simplest kind of pseudo random number generator. I know that its now long broken. But I am curious -- has it ever been used in any of the early crypto algorithms, say 70 years ago? Or has it been used for basic statistical simulations from day one. I read somewhere that it was used in the old IBM-360 computers. I am curious what it was used for.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It is indeed the case that the linear congruential generator was used—or at the very least suggested—for cryptographic purposes early on. Below are three examples, but it is likely that there are many more.
In 1982 Vahle and Tolendino broke an encryption scheme based on a linear congruential generator. However, no details about where this encryption was being used were given.
In 1965, Maclaren and Marsaglia proposed a generator that combined two congruential generators, which in their specific instantiation were $$ \begin{align} x_{i+1} &= (2^{17} + 3)x_i \bmod 2^{35}, \text{and}\\ y_{i+1} &= (2^7 + 1)y_i + 1 \bmod 2^{35}, \end{align} $$ after which the output $z_i$ is computed as $y_{x_{i \bmod 128}}$. This was, however, not meant as a cryptosystem by its authors. Nevertheless, in 1984 Retter did find this system used to encrypt real-world data at Data General, and furthermore broke it by reducing its strength to just one of the generators. He also found that another system, the CSI-10 cryptographic unit, using the same kind of encryption scheme.
Perhaps more famously, in 1980 Knuth devised a method to break truncated linear congruential generators. The paper starts by saying
Therefore, it has been suggested that the leading bits of such a sequence might be useful for enciphering data.
There is no associated citation, but it is not unreasonable to deduce that this was a popular idea during this time period. Other contemporary attacks on LCGs include Reeds and Plumstead.
Another class of random number generators very popular during this period were ones based on LFSRs, which are more hardware friendly. Many LFSR-based schemes appeared in the 60s and 70s, the vast majority of which ended up broken. Ritter's survey, starting with the Twigg generator, is a good place to start.
