3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – khaled Feb 6 '17 at 17:55
  • $\begingroup$ 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) $\endgroup$ – poncho Feb 6 '17 at 18:15
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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