# How to Backdoor Diffie-Hellman: quick explanation

## posted August 2016

I've noticed that since I published the **How to Backdoor Diffie-Hellman** paper I did not post any explanations on this blog. I just gave a presentation at Defcon 24 and the recording should be online in a few months. In the mean time, let me try with a dumbed-down explanation of the outlines of the paper:

I found many ways to implement a backdoor, some are **Nobody-But-Us** (NOBUS) backdoors, while some are not (I also give some numbers of "security" for the NOBUS ones in the paper).

The idea is to look at a natural way of injecting a backdoor into DH with Pohlig-Hellman:

Here the modulus \(p\) is prime, so we can naturally compute the number of public keys (elements) in our group: \(p-1\). By factoring this number you can also get the possible subgroups. If you have enough small subgroups \(p_i\) then you can use the **Chinese Remainder Theorem** to stitch together the many partial private keys you found into the real private key.

The problem here is that, if you can do Pohlig-Hellman, it means that the subgroups \(p_i\) are small enough for anyone to find them by factoring \(p-1\).

The next idea is to **hide** these small subgroups so that **only us** can use this Pohlig-Hellman attack.

Here the prime \(n\) is not so much a prime anymore. We instead use a **RSA** modulus \(n = p \times q\).
Since \(n\) is not a prime anymore, to compute the number of possible public keys in our new DH group, we need to compute \((p-1)(q-1)\) (the number of elements co-prime to \(n\)). This is a bit tricky and **only us**, with the knowledge of \(p\) and \(q\) should be able to compute that.
This way, **under the assumptions of RSA**, we know that no-one will be able to factor the number of elements (\((p-1)(q-1)\)) to find out what subgroups there are. And now our small subgroups are well hidden for us, and only us, to perform Pohlig-Hellman.

There is of course more to it. Read the paper :)