Hmm. Maybe that's still too complicated, because it requires understanding additive groups and a little bit about elliptic curves and... ugh. OK. So, let me share with you an analogous: a PRNG that is just like Dual_EC_PRNG, except that it uses integers, instead of elliptic curves. In particular, everything will be conceptually basically the same -- the backdoor will be the same, the PRNG will be the same -- this will just be easier to understand without any background in elliptic curve cryptography. Hopefully this will give the intuition better.

• The PRNG. The algorithm specifies a prime number $p$, and two integers $g,h$ that are both less than $p$. The algorithm tells you that the state of the PRNG at each point in time is some number $s$ that satisfies $1\le s < p$. To step the PRNG forward by one iteration, you set $r = g^s \bmod p$, $s' = g^r \bmod p$, update the state to $s'$, and output $t = h^r \bmod p$.

• The backdoor. The backdoor is a secret number $e$ such that $g=h^e \bmod p$. The NSA, who created the algorithm specification, chose $g,h$ by picking $h$ randomly, picking $e$ randomly, setting $g=h^e \bmod p$, and then publishing $g,h,p$ (but keeping $e$ secret, since $e$ is the backdoor).

• Breaking the PRNG. Here's how the NSA can break this PRNG. Suppose they observe one output $t$ from the PRNG. They compute $t^e \bmod p$. Notice that

$$t^e = (h^r)^e = h^{re} = (h^e)^r = g^r = s' \pmod p.$$

This means they were able to compute $s'$, the next state of the PRNG. So, after observing just one output from the PRNG, they can infer the next state of the PRNG and thereby predict what all future outputs from the PRNG will be.

For instance, suppose you generate a random IV using this generator (and send it in the clear), then generate a session key using this generator, then encrypt stuff under that session key. The NSA (who is eavesdropping on your communication and thus can see the IV) knows that the IV was output from this PRNG and can use their backdoor to infer the state of the PRNG and predict its future outputs -- and thus they can predict your session key and decrypt all your subsequent traffic. You've been owned!

I hope this gives the intuition. The problem with Dual_EC_DRBG is exactly the same as the problem with this hypothetical PRNG that I just described. Hopefully this is simple enough to follow: if you understand how Diffie-Hellman works, you can understand why this is broken.

I see that you want to explain the mathematics. OK, here is an explanation. I'm going to attack a simplified version of Dual_EC_DRBG, but the simplification doesn't change any of the essence of the attack.

The algorithm specification specifies an elliptic curve, which is basically just a finite cyclic (and thus Abelian) group $G$. The algorithm also specifies two group elements $P,Q$. It doesn't say how they were chosen; all we know is that they were chosen by an employee of the NSA. In the simplified algorithm, the state of the PRNG at time $t$ is some integer $s$. To run the PRNG forward one step, we do the following:

• We compute $sP$ (recall we use additive group notation; this is the same as $P^s$, if you prefer multiplicative notation), convert this to an integer, and call it $r$.

• We compute $rP$, convert it to an integer, and call it $s'$ (this will become the new state in the next step).

• We compute $rQ$ and output it as this step's output from the PRNG. (OK, technically, we convert it to a bitstring in a particular way, but you can ignore that.)

Now here's the observation: we're pretty much guaranteed that $P=eQ$ for some integer $e$. We don't know what $e$ is, and it's hard for us to find it (that requires solving the discrete log problem on an elliptic curve, so this is presumably hard). However, since the NSA chose the values $P,Q$, it could have chosen them by picking $Q$ randomly, picking $e$ randomly, and setting $P=eQ$. In particular, the NSA could have chosen them so that they know $e$.

And here the number $e$ is a backdoor that lets you break the PRNG. Suppose the NSA can observe one output from the PRNG, namely, $rQ$. They can multiply this by $e$, to get $erQ$. Now notice that $erQ = r(eQ) = rP = s'$. So, they can infer what the next state of the PRNG will be. This means they learn the state of your PRNG! That's really bad -- after observing just one output from the PRNG, they can predict all future outputs from the PRNG with almost no work. This is just about as bad a break of the PRNG as could possibly happen.

Of course, only people who know $e$ can break the PRNG. So this is a special kind of backdoor: the NSA presumably knows how to break Dual_EC_DRBG, but it's very unlikely that anyone else knows how to break it. Even though we know now the backdoor exists, it's very hard to recover the secret backdoor $e$, because that requires solving a discrete log problem.