1
$\begingroup$

What is the security level of DSA algorithm when $q$ is a 224 bit prime?

Is it always a simple rule that the security level is the bit length of $q$ divided by two ?

$\endgroup$
4
  • $\begingroup$ 112, see page 67 $\endgroup$ – kelalaka Feb 27 at 0:04
  • $\begingroup$ Thank you for that link. I think you mean page 54. $\endgroup$ – Gabi23 Feb 27 at 0:18
  • $\begingroup$ Yes, I've given the pdf page, and you see the doc page, :) $\endgroup$ – kelalaka Feb 27 at 0:20
  • $\begingroup$ Does 112 mean it takes $2^{112}$ operations to solve the discrete logarithm problem in the DSA algorithm? $\endgroup$ – Gabi23 Feb 27 at 18:15
5
$\begingroup$

What is the security level of DSA algorithm when q is a 224 bit prime?

About 112-bit, at most. More precisely, there's an attack recovering the private key from the public key, by solving a Discrete Logarithm Problem, costing roughly $2^{113}$ modular multiplications, and little else: the attack can be efficiently distributed and requires little memory. See Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

Is it always a simple rule that the security level is the bit length of $q$ divided by two ?

No. That rule applies unless there's another weakness:

  • The public prime $p$ is too small (or of a special form facilitating attack). As a rule of thumb, size (and requirement to not be too close to an exact power) are comparable to that of $n$ in RSA for the desired security level, in order to resist index calculus and GNFS variants. That would make about 2048-bit a minimum. See KeyLength.com for more precise advice on size.
  • The random generator used for signing has an exploitable weakness.
  • The private key leaks, e.g. by power analysis or timing attack.
$\endgroup$
3
  • $\begingroup$ Thank you. Does $2^{113}$ operations refer to the number of operations needed to solve the discrete logarithm problem which cracks the DSA algorithm? $\endgroup$ – Gabi23 Feb 27 at 17:36
  • $\begingroup$ @Gabi23: Yes. I added that in the answer. $\endgroup$ – fgrieu Feb 28 at 2:15
  • $\begingroup$ Could you please point to the place in the paper where this is mentioned? I don’t see where it mentions the number of operations. $\endgroup$ – Gabi23 Feb 28 at 16:16

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.