# What happens when domain parameter $q$ in DSA is not prime number

Suppose that attacker creates domain parameters $(p,q,g)$ where $q$ is not prime number (but $q$ still divides $p-1$) and that signer generates new key pair using these domain parameters.

How exactly can an attacker take advantage of this situation?

The DSA private key is a value $k$, and his public key is the value $g^k \bmod p$. $g$ has order $q$; if $q = q_1 \cdot q_2$, then the attacker can compute $(g^k)^{q_2} = (g^{q_2})^k$. The value $g^{q_2}$ has order $q_1$, and so he can solve that problem in $O(\sqrt{q_1})$ time; that gives him the value $k \bmod q_1$. Similarly, he can recover the value $k \bmod q_2$ in $O(\sqrt{q_2})$ time; from that, he can reconstruct the original value $k$ in what turns out to be a total of $O(\sqrt{ max(q_1, q_2) })$ time, rather than the $O(\sqrt{q})$ time it would take if $q$ were prime.