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?

  • $\begingroup$ They likely aren't using RSA. Likely some sort of elliptic curve cipher. $\endgroup$ – mikeazo Jun 25 '15 at 13:26
  • 3
    $\begingroup$ libsodium uses curve25519, which is based on elliptic curve cryptography — it is an entirely different algorithm to RSA (and yes , ECC key sizes are much smaller... see here for a reference... linuxjournal.com/content/elliptic-curve-cryptography). Aside from that, your question is broad - you should do some reading. $\endgroup$ – hunter Jun 25 '15 at 13:26
  • $\begingroup$ This question appears quite off-topic, since only guesswork can be done to answer this. Anyway, public key crypto with 256 bit can be done - just not with RSA and dlog-based crypto in $\mathbb{F}_p$. $\endgroup$ – tylo Jun 25 '15 at 13:30

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.

  • $\begingroup$ "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? $\endgroup$ – hunter Jun 25 '15 at 15:53
  • $\begingroup$ Yes. I was thinking of the original NaCl lib, which is pretty much only Curve25519. $\endgroup$ – user2552 Jun 26 '15 at 8:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.