- discrete-logarithm finite-field dsa
- Updated Fri, 20 May 2022 02:27:59 GMT

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.

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.

External links referenced by this document: