3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Relates to this question, which unfortunately has received no answer. I wish I knew! $\endgroup$
    – fgrieu ♦
    Commented Feb 16, 2021 at 11:56
  • $\begingroup$ @fgrieu we will learn, I hope. $\endgroup$
    – kelalaka
    Commented Feb 16, 2021 at 12:19
  • 1
    $\begingroup$ 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... $\endgroup$
    – Marc Ilunga
    Commented Feb 16, 2021 at 12:32
  • 2
    $\begingroup$ 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. $\endgroup$
    – Samuel Neves
    Commented Feb 16, 2021 at 17:46

0

Reset to default

Your Answer

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