DSA with composite p One of the basic requirements of DSA is to choose some prime $p$ of certain bit length. The security then lies in the intractability of solving $y = g^x \pmod{p}$ for $x$.

Is there any “easy” way to solve the discrete log problem when $p$ is composite? I thought about the Chinese Remainder Theorem but can't seem to figure out how it would work. If there is no obvious way to solve for $p$ composite then what is the need for $p$ to be prime?
Is there any “easy” way to solve the discrete log problem when $p$ is composite?


If you know the factorization of $p = rs$, then it can be reduced to solving the problem $y = g^x \pmod r$ and $y = g^x \pmod s$, and then combining the two solutions; hence you're reduced the hardness of the problem to the harder of the $r, s$ subproblems.

If you don't know the factorization of $p$, then it is at least as difficult as factoring $p$ (if you can solve arbitrary discrete logs modulo $p$, then you can factor $p$).

That would imply that the person who generated $p$ might be able to give himself a backdoor (as he'd have an easier time solving discrete logs than anyone else).

On the other hand, that's not the complete story.

You specified DSA; DSA places more requirements on the group it runs in.  For one, it actually operates in a prime-sized subgroup that is both considerably smaller than the modulus size, and which must be listed in the global parameters (as the verifier needs it).  And, in case you're wondering, the fact that the subgroup is prime is important, if it were composite, you could factor it, and attack each of the factors independently.

So, suppose we had $p = rs$ (where the factorization is secret), and we have a generator $g$ with $g^q = 1 \pmod p$ (for some moderate sized prime $q$).

That immediately implies that we have $g^q = 1 \pmod r$ and $g^q = 1 \pmod s$; however, if we have $g = 1 \pmod r$, then a simple computation of $\operatorname{gcd}(g-1, p)$ would reveal the factorization, and hence to be secure, we must have $g \ne 1 \pmod r$ and $g \ne 1 \pmod s$.

This implies that $r - 1 = 0 \pmod q$ and $s - 1 = 0\pmod q$, or in other words, we have:

$$p = (aq +1)(bq+1)$$

where $q$ is public, and $a, b$ are some unknown integers.

If we go through the size of $q$ (perhaps 256 bits), and the sizes of $r = aq+1$, $s = bq+1$ (perhaps 1024 bits each, hence $a, b$ may be 768 bits each), it's not immediately clear whether current lattice based factorization methods would work, but it's closer than anyone would trust.