Inferring sequences produced by pseudo-random number generators

Efficient algorithms are given for inferring sequences produced by certain pseudo-random number generators and specific examples of generators having this form are shown to be cryptographically insecure.

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.