1
$\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: 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://imgur.com/a/RrxEU

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
  • $\begingroup$ This is an interesting question. You can improve it if you translate the image text into MathJax $\endgroup$ – gammatester Apr 6 '18 at 15:13
1
$\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. 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.

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ – George V Apr 9 '18 at 21:42
  • $\begingroup$ @george-v: See the edit (in the old version I swapped the indices, sorry for that). $\endgroup$ – gammatester Apr 10 '18 at 8:00
  • $\begingroup$ One last question :)) How did you solve this linear congruence: $$ (X_2−X_3) = 782674123 $$ $\endgroup$ – George V Apr 10 '18 at 10:45
  • $\begingroup$ @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. $\endgroup$ – gammatester Apr 10 '18 at 10:56

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.