Why does a non-prime DH modulus creates a "NOBUS" backdoor can't we do a nobus backdoor with DH modulus prime? Some have argued that with a prime modulus you can just get the order by doing p-1 and then factor it, thus it is easy to reverse. I argue that this is not true.

The prime case

Our modulus is a prime $p$ such that the order of the group is $p-1 = p_1^{k_1} \times \cdots \times p_n^{k_n}$

For the backdoor to work, the discrete log should be do-able in groups of order $p_i^{k_i}$

For the NOBUS to work, you shouldn't be able to find the factors $p_i^{k_i}$

The non-prime case

Our modulus is now a composite $n = p_1^{k_1} \times \cdots \times p_n^{k_n}$ such that the order of the group is $p_1^{k_1-1}(p_1-1) \times \cdots \times p_n^{k_n-1}(p_n -1)$

For the backdoor to work, the discrete log should be do-able in groups of order $p_i^{k_i-1}(p_i-1)$

For the NOBUS to work, you shouldn't be able to find the factors $p_i^{k_i}$

The difference?

I see almost no difference between these two problems. It seems like a NOBUS backdoor could as easily be created with a prime modulus as with non-prime one.

Thoughts?
[In the non-prime case] For the backdoor to work, the discrete log should be do-able in $p_i^{k_i-1}(p_i - 1)$


Actually, that's not quite correct, and that's relevant for the answer.

If the factorization of $p_i^{k_i-1}(p_i - 1)$ is $p_i^{k_i-1} q_1^a q_2^b ... q_n^z$, then for NOBUS to work, someone else shouldn't be able to find the factors $q_i$.

Here's why this distinction is important: in the prime case, everyone knows the size of the group $p-1$, and anyone can hand off that value to a factoring method that's good at finding small factors, such as Elliptic Curve Method.  That is an astoundingly good way for find small factors, and for ECM, small can be 128 bits...

So, if $p-1$ consists of factors that are small enough for us to use, ECM can find them without much difficulty.

However, if we use a composite modulus, the size of the group is now secret. In other words, we've shifted the problem to finding the $q_i$ values.  Here, ECM doesn't help us much; unlike the prime case, there isn't a convenient $p-1$ value we can hand to ECM.  And, by making the $p_1, p_2$ values comparatively large, ECM just doesn't work the modulus directly.

What would work (to some extent) is the $p-1$ factoring method.  There, we keep making guesses as to the various primes that make up $q_i$; if we guess all of them on one side (and there's no penalty, apart from wasting time, for incorrect guesses), then we factor.  So, if we have a 64 bit $q_i$ value (and assuming the attacker knows that), he can guess all 64 bit primes; however there's about $2^{58}$ of them, so it'll take a while...