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 '21 at 0:04
  • $\begingroup$ Thank you for that link. I think you mean page 54. $\endgroup$
    – Gabi23
    Feb 27 '21 at 0:18
  • $\begingroup$ Yes, I've given the pdf page, and you see the doc page, :) $\endgroup$
    – kelalaka
    Feb 27 '21 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 '21 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 '21 at 17:36
  • $\begingroup$ @Gabi23: Yes. I added that in the answer. $\endgroup$
    – fgrieu
    Feb 28 '21 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 '21 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.