CODEWITHSUNDEEP
rsacomplexity-theorydsa
Yoda
Yoda

Reputation: 18068

What is DSA complexity?

I have made some testing and it came out that RSA is lot slower than DSA.

What is usual DSA time complexity?

RSA[ms] DSA [ms]    
1125    218 1KiB
1047    188 2KiB
594     17  4KiB
641     234 8KiB
2938    406 16KiB
9063    937 32KiB
39344   3406    64KiB

Upvotes: 1

Views: 549

Answers (2)

Tharushi Wadanambi
Tharushi Wadanambi

Reputation: 31

The results from your tests are consistent with what is expected: RSA is generally slower than DSA, especially as the data size increases. RSA’s complexity in operations like encryption and signing makes it less performant compared to DSA in scenarios where large files are involved.

If your use case involves primarily digital signatures and not encryption, DSA might be more suitable due to its better performance. However, if you require both encryption and signatures, RSA is still a solid choice despite being slower.

Upvotes: 0

AbcAeffchen
AbcAeffchen

Reputation: 14977

RSA and DSA using both exponentiation to generate the signature. This is what costs the most time, so they will basically have the same complexity. But the difference is the key length.

In cryptography you try to choose as small keys as possible, but big enough to get the security you want.

RSA needs quite long keys, sth. like 2048 bit or bigger.
DSA has one short (about 256 bit) and one long key (about 2048 bit). The exponent will be not bigger than the short key.

So for DSA you have to compute a 2048 bit number to the power of a 256 bit number (modulo a other number) and for RSA you have to compute a 2048 bit number to the power of an other 2048 bit number. This is why RSA is much slower than DSA.

Notice: If you choose for DSA a short key of length 2048 bit, it will be as slow as RSA.

Upvotes: 1

Related Questions