# How can the Number Field Sieve attack the discrete log in $\mathbb Z_p^*$ of DSA?

The Digital Signature Algorithm (DSA) uses $$L$$-bit prime $$p$$ and $$N$$-bit prime $$q$$ with $$q| p-1$$, i.e., $$p = r\cdot q +1$$ ( Schnorr group if $$r>2$$ and safe prime if $$r=2$$).

In a way, the security of DSA relies on the hardness of the discrete logarithm on $$\mathbb{Z}^*_q$$ that is given by $$y = g^x \bmod \mathbb{Z}^*_q$$ to find the $$x$$. This explains the choice of the size of $$q$$ on the standards, due to the generic discrete log attacks that have cost $$\mathcal{O}(\sqrt{q})$$.

DSA uses $$p$$ as a huge prime compared to $$q$$, NIST SP 800-57 Part 1 Revision 5.

• (L = 3072, N = 256),(L = 7680, N = 384), or (L = 15360, N = 512)

I've searched for the reason behind the large $$p$$, but couldn't find an explanation--neither the NIST documents nor the RFCs offer an explanation. I've only seen Poncho's answer.

Use the Number Field Sieve algorithm to attack the discrete log problem in $$Z^∗/p$$. NFS is typically seen as a way to attack the factorization problem; it can also be applied (with some additional complexity) to compute discrete logs.

How can the Number Field Sieve algorithm be used to attack the discrete logarithm in $$\mathbb{Z}^*_p$$ of DSA?

• Relates to this question, which unfortunately has received no answer. I wish I knew!
– fgrieu
Feb 16 at 11:56
• @fgrieu we will learn, I hope. Feb 16 at 12:19
• I don't really know about NFS but I was told that the justification for the large $p$ is the function field sieve by Adleman et al. Which has complexity $\exp[(1+o(1))(32/9)^{1/3}(\log p)^{1/3}(\log\log p)^{2/3}]$ that is sub-exponential in $\log p$. That would justify the need for $3072$ bits for $p$ and $256$ bits for $q$ when targeting $128$ bits security. But I am not really certain... Feb 16 at 12:32
• The number field sieve, as applied to discrete logarithms, is an advanced form of index calculus. One of my old answers describes how it works, at a high level. Feb 16 at 17:46