# State recovery of Micalli-Schnorr random number generator modulo a prime

Let $p$ be a public prime of $n$ bits. Define the sequence $x_i=z_{i-1}^e \bmod p$, where $z_i$ is the $k$ high-order bits of $x_i$, and $r_i$ the remaining $n-k$ bits of $x_i$ (thus $z_i=\Big\lfloor\frac{x_i}{2^{n-k}}\Big\rfloor$ and $r_i=x_i\bmod2^{n-k}$). Suppose $k>\max(2n/e, s)$, for some security parameter $s$ and $e$ is public with $\gcd(e,p-1)=1$.

I'm looking for an efficient algorithm to recover $x_0$ from the sequence $r_0, r_1, \ldots r_n$, or to predict remaining terms in the sequence.

• Yes, I want p prime. The reason is I am trying to determine if knowing the factorization of the modulus helps recover the state, and this is an easier problem that I don't know how to do. – Watson Ladd May 9 '16 at 21:35
• What is $z_0$? That is, what is the initial value of the recurrence? – pg1989 May 10 '16 at 0:58
• Out of curiosity, is it known that such an algorithm exists or is this a research question? – pg1989 May 10 '16 at 18:27
• Research question as far as I know. Maybe the answer is out there but my literature search found nothing. – Watson Ladd May 11 '16 at 3:31
• Prime-modulus variant was introduced as an open problem at Micali and Schnorr, "Efficient, Perfect Polynomial Random Number Generators", chapter 4. static.aminer.org/pdf/PDF/000/120/238/… – Vadym Fedyukovych May 18 '16 at 20:58

There is some related discussion in the answers to the Crypto.SE question “Why is the following RSA PRNG cryptographically secure?”.

Edit: As pointed out in comments, this answer is about the zRSA The consensus among the answers seems to be that the required security assumption is too strong (strong RSA assumption) and the generator is too slow for practical use.

Here is a paper "On the Provable Security of an Efficient RSA-Based Pseudorandom Generator" by Steinfeld et. al. on this generator.

Let $N$ be the RSA modulus involved, $e$ the RSA public exponent, and $k$ the number of MSB bits taken from the generator at each iteration.

Basically the authors suggest that under the strong RSA assumption it is possible to extract $$k= ((1/2)-(1/e))\log N$$ bits per iteration, without affecting the security.

And there is more recent work, behind a Springer paywall (see preprint here) "Time/Memory/Data Tradeoffs for Variants of the RSA Problem" by Fouque et. al. LNCS vol. 7936, proposing Time/Memory/Data attacks on the generator, which for practical choices of the parameters is of course not a feasible attack. This latter paper also cites a paper by Hermann and May from ASIACRYPT 2009 in the introduction, where it has apparently been shown that if $$k\geq (1-(1/e))\log N$$ bits are extracted per iteration, the generator can be broken.

• But this is the RSA/factoring based algorithm, not the prime-based variant in the question. You can't make the RSA assumption if you have a prime modulus... – otus May 20 '16 at 13:25
• I know about this work: the question is on the other side, namely breaking beyond the Hermann and May bound when the factorization is known. – Watson Ladd May 24 '16 at 15:45