2
$\begingroup$

Let's consider generator:

$x_{n+1} = (a \cdot x_{n} + c) \mod m$

And let's assume we will meet three requirements known as Hull–Dobell Theorem. Also consider only $m=2^{i}$ (then $c$ has to be odd).

Now let's consider $a$, $c$ and $x_{0}$ are 256-bit keys ($c \neq 0$). Could this generate secure pseudorandom numbers? Wikipedia says: if $m$ is a power of $2$, then $a−1$ should be divisible by $4$ but not divisible by $8$. Let's say we will meet also this requirement. By the way what will happen if we will not?

Are there any other problems which can make such a generator insecure? Is there also requirement that $a−1$ can't be divisible by $16$, $32$ and so on? Anywany it is not a big problem to choose $a$ this way.

$\endgroup$
1
  • 3
    $\begingroup$ No, LCGs cannot be made secure. They're entirely linear, and solving systems of linear equations is very fast. It is always easy to recover the modulus m, as seen in [the answers to this question][1], and from there to recover A and C. [1]: security.stackexchange.com/questions/4268/… $\endgroup$ Dec 29, 2020 at 21:23

1 Answer 1

4
$\begingroup$

Public m private a,c

If the attacker gets some $x_i$ in sequential

\begin{align} x_{i+1} &= a \cdot x_{i} + c &\bmod m\\ x_{i+2} &= a \cdot x_{i+1} + c &\bmod m\\ \end{align}

Then subtracts the two

$$x_{i+1} - x_{i+2} = a ( x_{i} - x_{i+1}) \bmod m$$

this will lead to the exposition of the $a$, the rest is there.

In short the next-bit test is failed.

By the way what will happen if we will not?

No maximal period!

Private m,a,c

The attacker still can recover the $m$ then the rest as following D.W.'s steps;

Define a new sequence $t_n = x_{n+1} - x_{n}$ and with some operation;

$$t_{n+1} = x_{n+2} - x_{n+1} = a x_{n+1} + b - a x_{n} -b = a x_{n+1} - a x_{n} = a t_{n} \bmod m$$

So we have $t_{n+1} = a\cdot t_{n} \bmod n$, then we have $t_{n+2} = a^2\cdot t_{n} \bmod n$ and $t_{n+i} = a^{i}\cdot t_{n} \bmod n$. From this one can notice that $$t_{n+2}\cdot t_n - t_{n+1}^2 = 0 \bmod m,$$ i.e. $|t_{n+2}\cdot t_n - t_{n+1}^2|$ is a multiple of $m$

Now call $U_n = |t_{n+2}\cdot t_n - t_{n+1}^2|$ and consider $\gcd(U_i,U_j)$ where $i \neq j$

Now, we will use a fact that Dirichlet showed in 1849

The probability of two random numbers being relatively prime is $\frac{6}{\pi^2}$

Consider two multiples $k$ and $\ell$ of $m$, then there are $u$ and $v$ such that $k = u \cdot m$ and $\ell = v \cdot m$. This will turn the question of $\gcd(k,\ell) = m$ to $\gcd(u,v)=1$ and this is the Dirichlet's result. If you are lucky with 5 outputs from LCG to from two $U_i$ than with $\frac{6}{\pi^2} = 0.607927101854027$ you will find $m$. If you have more output, you can calculate $\gcd(U_i,U_j,...,U_r)$ to increase to finding probability close to 1.

$\endgroup$
6
  • $\begingroup$ But do we need maximal period? If it will be enough long it could be fine, isn't it? Of course if it failed next bit test it cannot be secure (but is short period itself big issue?). $\endgroup$
    – Tom
    Dec 29, 2020 at 21:42
  • $\begingroup$ If there is no maximal period then some numbers cannot appear. At least to be a good pseudo-random number generator, it should generate all possible values. $\endgroup$
    – kelalaka
    Dec 29, 2020 at 21:44
  • $\begingroup$ So without maximal period it can be also easy or easier to broke? But if we will use it to generate very short sequences (let's say period is m/4 but we are using only 1024 first numbers) and often change the keys it could be not so easy. $\endgroup$
    – Tom
    Dec 29, 2020 at 21:49
  • $\begingroup$ It doesn't matter for breaking, it just produces a bad sequence. This attack needs three outputs to find the others if you continue to use more than 3, then your CBC IV will become predictable and there is t, the attack occurs. Changing the key? Chicken-Egg? If you already a reliable source for the uniform random key generation, use it for random, too! $\endgroup$
    – kelalaka
    Dec 29, 2020 at 21:53
  • $\begingroup$ To explain why I'm asking about that - I'm working on similar PRNG, so I want to better understand issues with LCG. Of course I'm not crazy and not trying to go against the well constituted knowledge of cryptography. I'm just trying to investigate the details. $\endgroup$
    – Tom
    Dec 29, 2020 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.