Cryptography
rsa public-key key-size libsodium
Updated Wed, 22 Jun 2022 18:45:11 GMT

Why is the public/private key length used in libsodium so much shorter than needed for RSA


Reading the libsodium source I see that is uses a key length of 32 bytes (256 bit) for private/public key encryption.

For RSA private/public key encryption a key length of 2048 (or 4095) bit is suggested. Why is the key length in libsodium so much shorter? Is the used algorithm so much more "efficient"? Or is there something I am missing?




Solution

It's not the algorithm that's more "efficient" (that's just a welcome side-effect) but the security level.

Security levels are usually given in bits; to say that a cipher has 80 bits of security means that we assume it takes roughly $2^{80}$ effort to break it, for some definitions of "effort" and "break".

For RSA, the main problem is factoring large numbers. Factoring algorithms are a lot better than brute force - factoring a $n$-bit RSA modulus takes a lot less than $2^n$ operations. Based on the speed of current factoring algorithms, the latest guess (according to ENISA) is that for 80 bit security your $N$ should have around 1024 bits length and for 128-bit security you need a 3072 bit $N$.

For libsodium, the main problem is taking discrete logarithms over a particular elliptic curve group of order $2^{255}-19$. With the best-known algorithms today, taking a discrete log over such a group (where the elements have about 256 bits length) would take around $2^{128}$ operations, hence you get 128 bit security with a lot smaller elements.





Comments (2)

  • +0 – "For libsodium, the main problem is taking discrete logarithms"... libsodium (github.com/jedisct1/libsodium) is a cryptographic library which uses many primitives including (but not limited to) authenticated symmetric encryption, key agreement, public-key signatures, and key derivation. Do you mean Curve25519? — Jun 25, 2015 at 15:53  
  • +0 – Yes. I was thinking of the original NaCl lib, which is pretty much only Curve25519. — Jun 26, 2015 at 08:34  


External Links

External links referenced by this document: