Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 ( 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.

share|improve this question
up vote 5 down vote accepted

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.

share|improve this answer
Thanks a lot!!! – user4811 Jan 27 '14 at 21:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.