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?


1 Answer 1


Well, it makes the discrete log problem easier; hence it makes recovering the private key easier

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.