1
$\begingroup$

I've noticed that on every site I checked I kept finding the relationship between D-H key size and symmetric encryption equivalent as a table, like:

384 - 56

768 - 80

1792 - 112

2304 - 128

10753 - 256

...

But I never found the formula that is actually used to calculate this equivalence. From what I can see by key size growth there is some square root of asymmetric key employed, multiplied by something, but I couldn't reverse engineer the formula myself.

Could anyone point me in the right direction? Thank you.

$\endgroup$
3
  • $\begingroup$ You mean the size of the group or the modulus? Because for the private key (i.e. the secret exponent) this question has the answer: crypto.stackexchange.com/questions/1975/… $\endgroup$
    – otus
    Commented Feb 11, 2016 at 10:11
  • 2
    $\begingroup$ should not the 256-bit security be 15360-bit RSA, and 128-bit security be 3072-bit RSA, etc? I have not seen the values in your question with the given security levels $\endgroup$ Commented Feb 12, 2016 at 2:13
  • $\begingroup$ @TheWiddwEggan, With search in Wikipedia you can see "128-bit security be 3072-bit RSA, etc". Where do you see your numbers in question? See en.wikipedia.org/wiki/Key_size $\endgroup$ Commented Feb 12, 2016 at 8:42

2 Answers 2

2
$\begingroup$

Your intuition is correct: for the same security parameter, the size of asymmetric keys of symmetric keys is (at least) proportional to twice the size of a symmetric key, or equivalently, 2^{sym. key} is proportional to the square root of 2^{asym. key}.

The reason for that is that symmetric cryptography does not need any particular structure for the operations involved - in fact, it tries to avoid any kind of structure. As a consequence, a symmetric scheme with a key of size k will be brute-forced in time O(2^k), by searching for all the possible keys.

Asymmetric schemes, however, do heavily rely on algebraic structure. And this structure gives more power to an adversary: a computational problem in a group of order p with no more structure (a generic group) can be solve in time O(sqrt(p)). This is related to the birthday paradox. A classical example is Shank's baby-step giant-step algorithm (or its space-efficient variant, the Rho-Pollard algorithm), which allows to solve the discrete logarithm problem in a group of size p in time O(sqrt(p)).

Hence, if your public key scheme works over a group, you cannot avoid using keys at least twice bigger than in the symmetric case. This size of the keys will be sufficient if there is no better attack than the generic attack (the baby-step giant-step approach) in the group you use. This is the case, for example, for well-chosen elliptic curves; hence the ElGamal cryptosystem over suitable elliptic curves might use keys "only" twice bigger than standard symmetric keys. But in some other groups, like finite fields, or the RSA group, the group has more structure than a "generic" group, and there exist way better attacks on problems, such as factorization and discrete logarithm, than the baby-step giant-step attack. Hence, for cryptosystems based on such groups, the keys will in general be way bigger - and that time, the recommended size of the key does simply depends on the best know attack.

$\endgroup$
1
$\begingroup$

For comparing security level of cryptography systems we need to fix criterion.

Let $s$ be security level for symmetric encryption methods, then recommended key size for other methods such are:

  • RSA, ElGamal, Diffie-Hellman: $\frac{0.05~{(s+14)}^3}{(\log_2(s+14))^2}$

  • ECIES: $2s$

  • McEliece: $2.25s^2{\log_2(s)}^2$

  • NTRU: $3 s \log_2(s)+1000$

  • $\mathcal P\epsilon$ (type of Isogeny based cryptography): $4s-8\log_2(s)-16$

Note that these values are approximation.

$\endgroup$
2
  • $\begingroup$ Can you provide references? $\endgroup$
    – cygnusv
    Commented Feb 11, 2016 at 15:31
  • $\begingroup$ @cygnusv, Yes, you can see "Cryptographic Schemes Based on Isogenies", page 2. $\endgroup$ Commented Feb 11, 2016 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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