Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers 2

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.

share|improve this answer
1  
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.