Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
Note 5.39 states that the security of this PRNG is based on stronger assumptions than just the intractability of the RSA problem. In general, this is not a good thing. In crypto we generally want as weak of assumptions as possible.
If you're trying to describe the Micali-Schnorr PRNG (Algorithm 5.37 in HAC), you have not accurately described the Micali-Schnorr PRNG. The Micali-Schnorr PRNG is cryptographically secure, but yours is not. Where did you get the PRNG you described, and why do you think your PRNG is secure?
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.
The Micali-Schnorr PRNG is apparently cryptographically secure, under some strong assumptions. If you want to find out why, you'll probably need to find and read their research paper.
In any case, these PRNGs are not a good choice for practical use. Do not use either of them in any real system. (AES-CTR would be a better choice.)
