1
$\begingroup$

I was reading the book "Cryptographic engineering", one of the variation of linear congruential formula is as follow: $X_n = a_1X_{n-1} + a_2X_{n-2} \pmod {2^{31}-1}$

$a_1$ and $a_2$ are two prime numbers respectively

Given 50 scaled consecutive number $[s_{1}, s_{2}, ... s{50}]$, is there an efficient way to work backward?

If brute forcing is used, it will need to go through $2^{64}$ numbers.

What would be the efficient way to solve the formulas?

$\endgroup$
  • 1
    $\begingroup$ Solve it like any other system of linear equations. The extended euclidean algorithm can compute multiplicative inverses which you need to use where you'd use normal division when working with rationals/reals. $\endgroup$ – CodesInChaos Mar 2 '17 at 9:14
  • 3
    $\begingroup$ Hint: suppose you're given $X_n$ and $X_{n-1}$ and this was an ordinary equation of the real numbers, how would you recover $X_{n-2}$? $\endgroup$ – SEJPM Mar 2 '17 at 12:00
6
$\begingroup$

Given an equation (for any modulus $Y$)

$$X_n = a_1 X_{n-1} - a_2 X_{n-2} \mod Y$$

you can just transform it into:

$$X_{n-2} = a_2^{-1}(a_1 X_{n-1} - X_n) \mod Y$$

So with $X_n,X_{n-1},a_1,a_2$ you can calculate $X_{n-2}$ directly. Furthermore: $a_2^{-1}$ is not division in the real numbers, but the multiplicative inverse in a finite group / ring, also called modular multiplicative inverse. If $a_2$ is coprime to $Y$, this inverse exists.

| improve this answer | |
$\endgroup$

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.