Predicting nonlinear pseudorandom number generators

Abstract:

Let $p$ be a prime and let $a$ and $b$ be elements of the finite field $\mathbb {F}_p$ of $p$ elements. The inversive congruential generator (ICG) is a sequence $(u_n)$ of pseudorandom numbers defined by the relation $u_{n+1} \equiv a u_n^{-1} + b \bmod p$. We show that if sufficiently many of the most significant bits of several consecutive values $u_n$ of the ICG are given, one can recover the initial value $u_0$ (even in the case where the coefficients $a$ and $b$ are not known). We also obtain similar results for the quadratic congruential generator (QCG), $v_{n+1} \equiv f(v_n) \bmod p$, where $f \in \mathbb {F}_p[X]$. This suggests that for cryptographic applications ICG and QCG should be used with great care. Our results are somewhat similar to those known for the linear congruential generator (LCG), $x_{n+1} \equiv a x_n + b \bmod p$, but they apply only to much longer bit strings. We also estimate limits of some heuristic approaches, which still remain much weaker than those known for LCG.