Opening a linear congruent pseudorandom number generator

For training purposes, I want to hack the simplest RNG.

Even those who do not know about the linear congruent generator or about the RNG in principle can help here, because the question is a misunderstanding of the English text and a little mathematics.

For you in short: There is such a thing as a pseudorandom number generator. i.e. random, if easier. They are "pseudo-random" because they are not random, but they are similar to them. One of the implementations of such a generator:

Xn+1=(aXn+c) mod m

Where Xn is the n th term of the sequence. a, c and m - constants: a - multiplier, c - increment, m - modulus. X0 – initial value.

My hacking conditions:

  1. We know that the generator is based on the linear congruent method.
  2. We don't know a, c and m.
  3. We can get any members sequences.

Task: define a,c,m (more likely).

I found several ways in the English version. I need either of them or another one that I do not know.

This site solves this by brute force. The only thing is that it does not give the entire sequence, but every second term. Therefore, as far as I understand, you do not need to do PowerMod. Questions about this method are as follows:

  1. Did I understand correctly, that the second code is implemented because the first one produced two results, and we need one?
  2. Question on modular arithmetic: How did you get that c = X2 - ((X1 * a) % m) (in the first code)?
  3. Why m < 10*M_START?
  4. What happens in the second code?

Here here is Plumstead's algorithm. And here is the algorithm of J. Marsagli Please explain who understood, from a mathematical point of view.

Other links :

Author: Дух сообщества, 2016-03-27
Source

1 answers

Okay, look.

  1. Here the authors of the solution reduced the problem to the previous one. Indeed, x[n + 2] = a * x[n + 1] + c = a * (a * x[n] + c) + c = (a * a) * x[n] + (a * c + c) (mod m), so that the problem reduces to cracking a linear congruent generator with coefficients a' = a * a and c' = a * c + c. Therefore, we believe that we have each member of the new sequence, and we find the new coefficients a', c', and then we will calculate the old ones from thema, c.

    The first solution was quadratic by а, m (busting all of them a/m and checking that they give the first few terms of the sequence correctly), which means it won't work on large modules, so the author gives the second solution, which is linear.

  2. We assume that we know every member of the sequence. Since by the condition x[2] = a' * x[1] + c' modulo m, then c' = x[2] - a' * x[1] modulo m.
  3. The constant 10 looks random. The minimum possible value of m is 3159 (because there is a member of the sequence with the value 3158). Author the solution simply iterates over a certain number of possible m.

  4. The second code is more interesting. To begin with, the author gets rid of c, moving on to the differences (for the sequence of differences y[i] = x[i] - x[i - 1], we have y[i + 1] = a * y[i] (mod m)). Next, he uses the function to find the multiplicative inverse of (that is, for a given k it is l such that k * l = 1 (mod m)), based on the extended Euclid algorithm. It exists, if k and m are mutually simple.

    So, y[2] = a * y[1] (mod m), multiplying this by the inverse of r to y[1], we get a = y[2] * r. (If the opposite is not found, we skip this value m.) If m was guessed correctly, we should get the correct sequence of differences, which is checked by further code.

 7
Author: VladD, 2016-06-22 18:52:59