# Why is the following RSA PRNG cryptographically secure?

One requirement states that the generator has to withstand the next-bit test.

Consider the following PRNG, where we calculate next output $x_i$ via the formula $x_i = x_{i-1}^ e\mod n$.

I can see that this PRNG withstands the "state compromise extensions" (can't guess previous states). However, given $x_i, e, n$ an adversary can easily compute all future numbers.

Why is this generator still considered cryptographically secure?

• If you mean algorithm 5.35 in HAC, you will only output the least significant bit of each intermediary $x_i$ value. – Henrick Hellström May 14 '13 at 6:01

Perhaps you are thinking of the Micali-Schnorr PRNG, as described in Algorithm 5.37 of the Handbook of Applied Cryptography? Algorithm 5.37 in HAC never states that $e$ is known to the adversary, or even that $n$ is known. Also, Algorithm 5.37 outputs only the least significant bits of the number, on each iteration. So I think you are confusing RSA as typically used and RSA as used in the Micali-Schnorr PRNG. What you describe does not match what is found in Algorithm 5.37. Yes, for the generator you describe, given $x_i$, $e$ and $n$, the adversary could compute $x_{i+1}$, but in the Micali-Schnorr PRNG, it appears that we assume that $e$ (and even $n$) is unknown to the adversary.
The PRNG you described is not secure, if each $x_i$ is output on each step. For instance, the Jacobi symbol $(x_i|n)$ will remain the same for all $i$. In other words, $(x_i|n)=(x_{i-1}|n)$. This shows that your PRNG fails the next-bit test: given $x_{i-1}$, we can predict one bit of information about $x_i$. Therefore, your PRNG is not secure.