TAOCP 3.6 Exercise 7

Y_n=\left\lfloor \frac{X_n}{2^{10}}\right\rfloor,\qquad X_n=2^{10}Y_n+Z_n,\qquad 0\le Z_n<2^{10}.

taocpmathematicsalgorithmsvolume-2

Section 3.6: Summary

Exercise 7. ▶ [**] [M40] A programmer decided to encipher his files by using a linear congruential sequence $\langle X_n \rangle$ of period $2^{30}$ generated by (1) with $m = 2^{35}$. He took the most significant bits $\lfloor X_n / 2^{10} \rfloor$ and exclusive-or'ed them onto his data, but kept the parameters $a$, $c$, and $X_0$ secret.

Show that this isn't a very secure scheme, by devising a method that deduces the multiplier $a$ and the first difference $X_1 - X_0$ in a reasonable amount of time, given only the values of $\lfloor X_n / 2^{10} \rfloor$ for $0 \le n < 150$.

Verified: yes
Solve time: 3m59s

$$ Y_n=\left\lfloor \frac{X_n}{2^{10}}\right\rfloor,\qquad X_n=2^{10}Y_n+Z_n,\qquad 0\le Z_n<2^{10}. $$

The generator satisfies

$$ X_{n+1}\equiv aX_n+c \pmod{2^{35}}, $$

and the period is $2^{30}$. Since an LCG modulo $2^e$ has full period iff

$$ c\equiv1\pmod2,\qquad a\equiv1\pmod4, $$

we know that $a$ is odd and $c$ is odd.

Define

$$ D_n:=X_{n+1}-X_n . $$

Then

$$ D_n=(a-1)X_n+c, $$

hence

$$ D_n\equiv c\pmod2. $$

Because $c$ is odd, every $D_n$ is odd. Therefore every $D_n$ is invertible modulo $2^{35}$.

Also,

$$ \begin{aligned} D_n &=(2^{10}Y_{n+1}+Z_{n+1})-(2^{10}Y_n+Z_n) \ &=2^{10}(Y_{n+1}-Y_n)+(Z_{n+1}-Z_n). \end{aligned} $$

Put

$$ \Delta_n:=Y_{n+1}-Y_n, \qquad \varepsilon_n:=Z_{n+1}-Z_n. $$

Then

$$ D_n=2^{10}\Delta_n+\varepsilon_n, $$

with

$$ -(2^{10}-1)\le \varepsilon_n\le 2^{10}-1. $$

Thus $D_n$ is known within an additive error $<2^{10}$.

Now

$$ \begin{aligned} D_{n+1} &=X_{n+2}-X_{n+1} \ &\equiv a(X_{n+1}-X_n) \pmod{2^{35}}, \end{aligned} $$

so

$$ D_{n+1}\equiv aD_n\pmod{2^{35}}. $$

Since $D_n$ is odd, it has an inverse modulo $2^{35}$, and therefore

$$ a\equiv D_{n+1}D_n^{-1}\pmod{2^{35}}. $$

Hence every consecutive pair $(D_n,D_{n+1})$ determines $a$ uniquely modulo $2^{35}$.

We now show that the unknown low bits can be searched efficiently.

For each $n$,

$$ D_n=2^{10}\Delta_n+\varepsilon_n, $$

where $\varepsilon_n$ ranges over at most

$$ 2^{11}-1=2047 $$

possible integers. Therefore each $D_n$ has fewer than $2^{11}$ possibilities.

Fix one index $n$. Enumerate all pairs

$$ (D_n,D_{n+1}) $$

consistent with the observations. There are fewer than

$$ 2^{11}\cdot2^{11}=2^{22} $$

such pairs. For each pair:

  1. Check whether $D_n$ is odd. Since the true $D_n$ is odd, all valid candidates must be odd.
  2. Compute

$$ a\equiv D_{n+1}D_n^{-1}\pmod{2^{35}}. $$

Thus each candidate pair produces one candidate multiplier $a$.

Now consider the next relation,

$$ D_{n+2}\equiv aD_{n+1}\pmod{2^{35}}. $$

For a fixed candidate $a$, and for each admissible $D_{n+1}$, the value

$$ aD_{n+1}\pmod{2^{35}} $$

is uniquely determined. But $D_{n+2}$ is constrained to lie in an interval of width $<2^{11}$,

$$ D_{n+2}=2^{10}\Delta_{n+2}+\varepsilon_{n+2}, \qquad |\varepsilon_{n+2}|<2^{10}. $$

Since the modulus is $2^{35}$, a random residue modulo $2^{35}$ lands in this interval with probability approximately

$$ \frac{2^{11}}{2^{35}}=2^{-24}. $$

Hence a false candidate $a$ survives one additional step with probability about $2^{-24}$.

The initial enumeration produces at most $2^{22}$ candidate multipliers. After checking one further equation, the expected number of surviving false candidates is at most

$$ 2^{22}\cdot2^{-24}=2^{-2}. $$

Thus, with overwhelming probability, only the correct multiplier survives after testing merely one or two additional consecutive equations. Using 150 outputs gives 148 such consistency checks, far more than necessary.

Therefore $a$ can be recovered in practical time by the following procedure:

  1. Compute $\Delta_n=Y_{n+1}-Y_n$.
  2. Enumerate all admissible pairs

$$ D_n=2^{10}\Delta_n+\varepsilon_n, \qquad D_{n+1}=2^{10}\Delta_{n+1}+\varepsilon_{n+1}, $$

with $|\varepsilon_n|,|\varepsilon_{n+1}|<2^{10}$.

  1. For each odd $D_n$, compute

$$ a\equiv D_{n+1}D_n^{-1}\pmod{2^{35}}. $$

  1. Verify each candidate $a$ against further relations

$$ D_{k+1}\equiv aD_k\pmod{2^{35}}. $$

Only the true multiplier survives all tests.

Once $a$ is known, recover the first difference

$$ D_0=X_1-X_0. $$

Indeed,

$$ D_1\equiv aD_0\pmod{2^{35}}, $$

hence

$$ D_0\equiv a^{-1}D_1\pmod{2^{35}}. $$

The value $D_1$ itself is constrained to the interval

$$ 2^{10}\Delta_1-(2^{10}-1) \le D_1 \le 2^{10}\Delta_1+(2^{10}-1), $$

which contains fewer than $2^{11}$ integers. Therefore we enumerate all admissible $D_1$, compute

$$ D_0\equiv a^{-1}D_1\pmod{2^{35}}, $$

and retain only those values satisfying the corresponding constraint

$$ D_0=2^{10}\Delta_0+\varepsilon_0, \qquad |\varepsilon_0|<2^{10}. $$

For a random incorrect choice of $D_1$, the probability that the resulting $D_0$ also falls into its allowed interval is about $2^{-24}$. Hence the correct $D_1$, and therefore the correct $D_0=X_1-X_0$, is isolated uniquely with overwhelming probability.

Thus the multiplier $a$ and the first difference $X_1-X_0$ can be reconstructed efficiently from the truncated outputs alone. The scheme is therefore insecure.