I'm not familiar with algorithm complexity so I'm asking here. I need help determining degital signature complexity, I did some research and all I found is complexity for the D.S.A only:

𝑂(𝐷𝑆𝐴 π‘†π‘–π‘”π‘›π‘Žπ‘‘π‘’π‘Ÿπ‘’) =𝑂(2 π‘™π‘œπ‘”π‘›).

𝑂(𝐷𝑆𝐴 Verification) = 𝑂(3π‘™π‘œπ‘” 𝑛).

I'm using RSA Signature and SHA-2 hush function.

  • 1
    $\begingroup$ since encryption and decryption of RSA trapdoor function is of logarithmic bit complexity (with respect to the binary length of the input message), you can expect the same for the RSA digital signature. $\endgroup$
    – 111
    Jul 22, 2020 at 23:34
  • $\begingroup$ Thanks for your answer but im hashing the input message then generating the signature $\endgroup$
    – Afaf Matg
    Jul 22, 2020 at 23:50
  • 1
    $\begingroup$ does not change anything (the message m is the h(m)) (sorry not logarithmic but polynomial bit complexity) $\endgroup$
    – 111
    Jul 23, 2020 at 11:20
  • $\begingroup$ If you include the normal padding (PKCS#1 / PSS) you have just one operation with a specific key size. The input size in that case doesn't matter, and the padding itself is symmetric (i.e. fast compared to RSA itself). As the hash will be much smaller than a secure RSA key size anyway, the hash size itself really doesn't play any part. $\endgroup$
    – Maarten Bodewes
    Jul 25, 2020 at 20:51


Browse other questions tagged or ask your own question.