1

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: https://brilliant.org/problems/breaking-linear-congruential-generators/

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

https://i.stack.imgur.com/eYzqF.jpg

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

George V
  • 13

1 Answers1

1

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. https://planetcalc.com/3311/ with the input $X_1-X_2 = 587411898, m=1000000007$ or with Wolfram Alpha solve (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.

gammatester
  • 18,827
  • hello again. I don't understand part 2 mainly because I don't know anything about modular inverses. Can you show me any links that could help me with this topic or elaborate on how you found that: $$ (X_2 - X_1)^{-1} = 560056067 \hspace{0.2cm} (mod \hspace{0.2cm} m) $$

    and why for finding "a" you need to calculate: $$ (X_2−X_3)*(X_2 - X_1)^{-1} $$

    Thanks

     – George V Apr 09 '18 at 21:42
  • @george-v: See the edit (in the old version I swapped the indices, sorry for that). – gammatester Apr 10 '18 at 08:00
  • One last question :)) How did you solve this linear congruence:

    $$ (X_2−X_3) = 782674123 $$

     – George V Apr 10 '18 at 10:45
  • @george-v: This is simple modular arithmetic: $X_2-X_3 = -217325884$ is negative, so add $m$ and get $$X_2-X_3 \equiv -217325884 \equiv -217325884 + 1000000007 = 782674123.$$ This is the manual calculation, actually I did it using Maple. You can use other programs, e.g. Python, Pari/GP etc. – gammatester Apr 10 '18 at 10:56