Re: CONFIG_RANDOM (compromise?)

Andries.Brouwer@cwi.nl
Fri, 24 May 1996 17:01:01 +0200


Harald Anlauf:

:: It seems that most of the people who are flaming on this topic have no
:: idea how weak a pseudo-random number generator really is. Only a few
:: values is all you generally need before you can completely predict the
:: output of such a best.

: People seem to be too paranoid about the quality of pseudo random number
: generators, but why don't you just ask the experts out there?

: A friend of mine pointed me to the errata list of volume two of Donald
: E. Knuth's "The Art of Computer Programming". There, DEK has suggested
: a very good portable random number generator. It generates 30-bit
: integers with the following properties:

An interesting post. Does `the experts out there' refer to
`A friend of mine'?

Have you read Knuth's paper
Donald E. Knuth,
Deciphering a linear congruential encryption,
IEEE Trans. Inform. Theory 31 (1985), no. 1, 49--52
?

Just in case you haven't, let me include the summary.

"We show that the multiplier, the increment, and the seed value
of a linear congruential random number generator on a binary
computer can be deduced from the leading bits of the `random'
numbers that are generated."

So at least Knuth is very aware of the fact that pseudo random number
generators that are satisfactory for statistical purposes are very
weak for cryptographical purposes.

Andries