2 ms·

There is a massive performance difference—not just size, but computation as well. Especially if you want a constant-time implementation. There is also an order

There is a massive performance difference—not just size, but computation as well. Especially if you want a constant-time implementation. There is also an order of magnitude more ways to screw up and not do input validation correctly, thereby introducing vulnerabilities. For all these reasons there aren’t really good libraries for RSA outside of TLS implementations, and that’s a lot of baggage to inherit if you are not doing TLS.

upofadown 5y ago
RSA is faster for signature generation. RSA is faster by more than an order of magnitude for signature verification[1] and encryption[2]. All these libraries listed here are bad in some way for RSA? * https://en.wikipedia.org/wiki/Comparison_of_cryptography_libraries#Public_key_algorithms https://en.wikipedia.org/wiki/Comparison_of_cryptography_lib... [1] https://www.ijser.org/researchpaper/Performance-Based-Comparison-Study-of-RSA-and-Elliptic-Curve-Cryptography.pdf https://www.ijser.org/researchpaper/Performance-Based-Compar... [2] https://hal.archives-ouvertes.fr/hal-02926106/document https://hal.archives-ouvertes.fr/hal-02926106/document
- garmaine 5y ago
  Your own link [2] shows RSA being 10-50x slower than the EC algo they used, which itself is many factors slower than state of the art. Are you reading the table right?
  - upofadown 5y ago
    Table 3 (decryption) from link [2] shows that it took 1.265 seconds for 233 bit ECC and 0.031 seconds for 2240 bit RSA to encrypt something. The associated comment was: >We noted that the encryption by the RSA algorithm is faster than the one with ECC algorithm. While we are here, I will point out that the performance was almost the same for the same key lengths in the encryption case. So ECC seems to be faster for key generation but overall slower for everything else.
    - marcan_42 5y ago
      Those numbers are clearly nonsense; notice how the smaller ones don't even scale with key size, while they obviously should to some extent. That paper is flawed. They obviously made a mistake. Look at the ed25519 benchmarks: https://ed25519.cr.yp.to/ https://ed25519.cr.yp.to/ 71000 signature verifications per second and 109000 signature generations per second on a quad-core machine. That is much, much faster than RSA. It's well established that ECC is much faster than RSA in general. I suspect I know what happened. DSA signature schemes require randomness to generate signatures, unlike RSA. They probably were using an entropy-constrained random number generator. That bottlenecked ECDSA through no fault of the algorithm. Ed25519 does not suffer from this issue, since it is constructed in a way that requires no external source of randomness (the random part is substituted with a deterministic hash of the key and input).
      - upofadown 5y ago
        If you want to prove that ed25519 is generally faster than RSA for signatures I think you would have to find a benchmark that supports your contention.
        marcan_42 5y ago
        https://blog.cloudflare.com/ecdsa-the-digital-signature-algorithm-of-a-better-internet/ https://blog.cloudflare.com/ecdsa-the-digital-signature-algo... RSA 2048 bits: 1001 signatures per second ECDSA P-256: 9516 signatures per second Note that 256-bit RSA provides a higher security level than 2048-bit RSA, so this is biased in RSA's favor. https://connect2id.com/blog/nimbus-jose-jwt-6 https://connect2id.com/blog/nimbus-jose-jwt-6 That one has ed25519 signing 60x faster than RSA-2048. Verification is a bit slower with ed25519 (RSA is very asymmetric there due to the low hamming weight public exponents), but considering the difference in security level, it basically works out to about the same. So signature verification is about the same for EC vs RSA, while EC is much faster than RSA for signature generation, and ridiculously faster for key generation. EC certainly isn't significantly slower than RSA for any equivalent operation, and definitely not by 40x like the paper you linked claims. That is just wrong.

upofadown 5y ago

RSA is faster for signature generation. RSA is faster by more than an order of magnitude for signature verification[1] and encryption[2]. All these libraries listed here are bad in some way for RSA? * https://en.wikipedia.org/wiki/Comparison_of_cryptography_libraries#Public_key_algorithms https://en.wikipedia.org/wiki/Comparison_of_cryptography_lib... [1] https://www.ijser.org/researchpaper/Performance-Based-Comparison-Study-of-RSA-and-Elliptic-Curve-Cryptography.pdf https://www.ijser.org/researchpaper/Performance-Based-Compar... [2] https://hal.archives-ouvertes.fr/hal-02926106/document https://hal.archives-ouvertes.fr/hal-02926106/document

garmaine 5y ago
Your own link [2] shows RSA being 10-50x slower than the EC algo they used, which itself is many factors slower than state of the art. Are you reading the table right?
- upofadown 5y ago
  Table 3 (decryption) from link [2] shows that it took 1.265 seconds for 233 bit ECC and 0.031 seconds for 2240 bit RSA to encrypt something. The associated comment was: >We noted that the encryption by the RSA algorithm is faster than the one with ECC algorithm. While we are here, I will point out that the performance was almost the same for the same key lengths in the encryption case. So ECC seems to be faster for key generation but overall slower for everything else.
  - marcan_42 5y ago
    Those numbers are clearly nonsense; notice how the smaller ones don't even scale with key size, while they obviously should to some extent. That paper is flawed. They obviously made a mistake. Look at the ed25519 benchmarks: https://ed25519.cr.yp.to/ https://ed25519.cr.yp.to/ 71000 signature verifications per second and 109000 signature generations per second on a quad-core machine. That is much, much faster than RSA. It's well established that ECC is much faster than RSA in general. I suspect I know what happened. DSA signature schemes require randomness to generate signatures, unlike RSA. They probably were using an entropy-constrained random number generator. That bottlenecked ECDSA through no fault of the algorithm. Ed25519 does not suffer from this issue, since it is constructed in a way that requires no external source of randomness (the random part is substituted with a deterministic hash of the key and input).
    - upofadown 5y ago
      If you want to prove that ed25519 is generally faster than RSA for signatures I think you would have to find a benchmark that supports your contention.
      - marcan_42 5y ago
        https://blog.cloudflare.com/ecdsa-the-digital-signature-algorithm-of-a-better-internet/ https://blog.cloudflare.com/ecdsa-the-digital-signature-algo... RSA 2048 bits: 1001 signatures per second ECDSA P-256: 9516 signatures per second Note that 256-bit RSA provides a higher security level than 2048-bit RSA, so this is biased in RSA's favor. https://connect2id.com/blog/nimbus-jose-jwt-6 https://connect2id.com/blog/nimbus-jose-jwt-6 That one has ed25519 signing 60x faster than RSA-2048. Verification is a bit slower with ed25519 (RSA is very asymmetric there due to the low hamming weight public exponents), but considering the difference in security level, it basically works out to about the same. So signature verification is about the same for EC vs RSA, while EC is much faster than RSA for signature generation, and ridiculously faster for key generation. EC certainly isn't significantly slower than RSA for any equivalent operation, and definitely not by 40x like the paper you linked claims. That is just wrong.