 Cryptography

# 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 $$p1$$ is a multiple of $$q$$.
• Choose $$g$$, a number whose multiplicative order modulo $$p$$ is $$q$$. This may be done by setting $$g = h^{(p1)/q} \bmod p$$ for some arbitrary $$h (1 < h < p1)$$, 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. ## Solution

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.