Inferring sequences produced by pseudo-random number generators

Abstract

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 = Σ ^k _j-l α _j φ _j ( X _o , X _l , . . ., X _n-l ) (mod m ). In each case, we assume that the functions φ j are known and polynomial time computable, but that the coefficients aj 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.