10
$\begingroup$

Suppose I knew that a random number sequence was generated by a linear congruential generator. That is,

$x_{n+1}=(aX_n+c) \bmod m$

If I am given the entire period (or at least a large contiguous subsequence of it), how can I reconstruct the parameters $a,c,m$ and $x_0$ that produced this sequence? I'm looking for a general method that will be able to determine the initial parameters if the pseudo-random number generator is known.

$\endgroup$
  • $\begingroup$ What precisely is known? From a contiguous subseqence you cannot tell where the sequence began $x_0$, unless the items are indexed in sequence. If $m$ is known, then $a$ and $c$ are readily discovered. $\endgroup$ – hardmath Apr 3 '12 at 15:28
10
$\begingroup$

See the paper How to crack a Linear Congruential Generator, Haldir ("Reverse Engineering Team", Dec. 2004):

In this paper I will present a method which will solve all values of the LCG including the modulus with six or more consecutive numbers of PRNG output.

The paper includes "proof of concept" source code written in C, using Victor Shoup's NTL for extended precision arithmetic.

$\endgroup$
  • $\begingroup$ That was a great paper! :) Do you know of a more general method that could apply to other random number generators, not just linear congruential? $\endgroup$ – Paul Apr 3 '12 at 15:58
  • $\begingroup$ @Paul: One can of course find RNGs that are easily "solved" for their parameters from sufficient output data (inverse problem), but it would seem that the better the RNG (more random the appearance of output), the more difficult that inverse problem would be. The solution of the LCG case is related to certain dimensional clustering effects that are well-known, making pairs of generated values nonuniformly distributed. For more see Design of Cryptographically Strong Generator By Transforming Linearly Generated Sequences $\endgroup$ – hardmath Apr 3 '12 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.