zbMATH — the first resource for mathematics

Inferring sequences produced by pseudo-random number generators. (English) Zbl 0667.94006
In this paper, efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators. The generators considered are all of the form \(X_ n=\sum^{k}_{j=1}\alpha_ j\phi_ j(X_ 0,X_ 1,...,X_{n-1})(mod m).\) In each case, we assume that the functions \(\phi_ j\) are known and polynomial time computable, but that the coefficients \(\alpha_ j\) and the modulus m are unknown. Using this general method, specific examples of generators having this form, the linear congruential method, linear congruences with n terms in the recurrence, and quadratic congruences are shown to be cryptographically insecure.

94A60 Cryptography
65C10 Random number generation in numerical analysis
Full Text: DOI