# Why do we use 1024 / 160 bit primes in DSA?

I am looking at DSA's parameter generation and don't understand why for $$p$$ a 1024 bit prime is needed if $$q$$ is chosen as a $$160$$ bit prime. I thought that the security of DSA relates on the discrete logarithm problem. A good protection against algorithms solving the DLP is to work in a big order subgroup. I would choose $$p$$ as a safe prime, so that $$p = 2q + 1$$. Then $$p$$ has a bit size of $$\approx 160$$ bit and the biggest sub group has size $$q$$. I guess I cannot do this but what is the explanation for this?

I have taken the variable names from Wikipedia (https://en.wikipedia.org/wiki/Digital_Signature_Algorithm). Here an excerpt of the parameter generation part:

• Decide on a key length $$L$$ and $$N$$. This is the primary measure of the cryptographic strength of the key. FIPS 186-3 specifies $$L$$ and $$N$$ length pairs of (1024,160), (2048,224), etc.
• Choose an $$N$$-bit prime $$q$$. $$N$$ must be less than or equal to the hash output length.
• Choose an $$L$$-bit prime modulus $$p$$ such that $$p–1$$ is a multiple of $$q$$.
• Choose $$g$$, a number whose multiplicative order modulo $$p$$ is $$q$$. This may be done by setting $$g = h^{(p–1)/q} \bmod p$$ for some arbitrary $$h (1 < h < p−1)$$, and trying again with a different $$h$$ if the result comes out as 1. Most choices of $$h$$ will lead to a usable $$g$$; commonly $$h=2$$ is used.

The algorithm parameters (p, q, g) may be shared between different users of the system.

• I am sorry to post in the answers section but i am not allowed to comment above. I would like to ask about the size of q? why wouldn't index calculus be used to calculate DLP modulo q? and why is it ok to choose q 160 bits ? thank you Feb 6, 2017 at 17:55
• This probably should be asked in a separate question; however, to give an answer, index calculus allows us to calculate DLP in $Z^*/q$, however we're not working in that group. Instead, we're working in a subgroup of $Z^*/p$ (and that subgroup size happens to be of size $q$); index calculus would apply only to $Z^*/p$ (and that's my second possible method) Feb 6, 2017 at 18:15

There are two ways to solve a discrete log problem over $Z^*/p$, that is, given $g$ and $h$, find $x$ with $h \equiv g^x \bmod p$:
• If the point $g$ generates a subgroup of size $q$, use a general Discrete Log algorithm (such as Pollard Rho) to recover $x$ in $O( \sqrt{q})$ time.
• 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.
Because of this second possible method, using $p \approx 2^{160}$ would be a serious weakness.