# 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?

-
It's not cryptographically secure. Why do you think it is? Where did that premise come from? You might want to investigate where you got that assumption from -- that might help you answer your question yourself. –  D.W. May 13 '13 at 17:31
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.

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.

-
Note 5.39 states that the assumption required for the PRNG to be secure is stronger, i.e. intractability of the RSA problem is not sufficient. In general that's a bad thing. We want weak assumptions. I'm not sure if that's what you meant, I just wanted to clarify that. –  Maeher May 13 '13 at 14:15
@Maeher, yes, let me reword to make it clear. Thanks for pointing that out. –  mikeazo May 13 '13 at 14:41

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.)

-