$\begingroup$

The full question is: How to crack a Linear Congruential Generator when a, c and m in the LCG formula. I googled this question and I found what I wanted:

here is the question:

and here is the screenshot of the answer (you need to make an account, to see the answer):

The problem is that I don't understand the answer.

1.) I do not understand this equation from the answer (what is this equation and why is it used): $$Z_n = Y_nY_{n+2}- Y^2_{n+1}$$

2) And I don't understand how a and c are found afterwards.

Any help is apprecciated

Also I am aware that there are other methods to solve this question for example by using a matrix: Calculation for linear congruential generator: Setting up equations

Thank you

$\endgroup$ 1

1 Answer

$\begingroup$

Just use the formulas in the picture.

Part 1: With $Y_n \equiv a Y_{n-1} \pmod m$ you get
$$Y_{n+1} \equiv a Y_{n} \equiv a^2Y_{n-1} \pmod m$$ $$Y_{n+2} \equiv a Y_{n+1} \equiv a^3Y_{n-1} \pmod m$$ and therefore $$Z_n \equiv Y_{n}Y_{n+2} - Y_{n+1}^2 \equiv (a\cdot a^3 - (a^2)^2) Y_{n-1} \equiv 0 \pmod m$$

Thus $Z_n = m\times z_n$ is a multiple of $m$ and (as claimed in the image) for a sufficient number of samples $\{X_n\}$ the gcd of corresponding $Z_n$ is expected to be $m$.

---

Part 2: If you accept $m := 1000000007$ from the gcd calculation the two linear $$a X_1 + b \equiv X_2 \pmod m$$ $$a X_2 + b \equiv X_3 \pmod m$$ congruences can be solved as follows: First compute the modular multiplicative inverse $(X_1-X_2)^{-1} \equiv 560056067 \pmod m$ (this is usually done with the Extended Euclidean Algorithm or Euler's theorem, see Wikipedia, for single values you can use an online calculator, e.g. with the input $X_1-X_2 = 587411898, m=1000000007$ or with Wolfram Alphasolve (720555190-133143292)x = 1 mod 1000000007) and then $$a \equiv (X_2-X_3) (X_1-X_2)^{-1} \equiv 782674123\times 560056067 \equiv 1664525 \pmod m$$ $$b\equiv X_2 - a X_1 = 133143292 - 1664525\times 720555190 \equiv 13904216 \pmod m$$ This is done like the solving of a usual system of linear equations. Subtract the second from the first equation and get $a$ $$aX_1 - a X_2 \equiv a(X_1-X_2)\equiv X_2-X_3 \pmod m$$ $$a \equiv (X_2-X_3)(X_1-X_2)^{-1} \pmod m$$ and $b$ from the first equation.

$\endgroup$ 4

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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