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.

Improve this question
$\endgroup$
1
  • $\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 ♦
    Commented Apr 3, 2012 at 15:28

1 Answer 1

Reset to default
11
$\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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Apr 3, 2012 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 ♦
    Commented Apr 3, 2012 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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