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$
  • $\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 Feb 11 '16 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$ – Richie Frame Feb 12 '16 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$ – Meysam Ghahramani Feb 12 '16 at 8:42
2
$\begingroup$

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

The reason for that is that symetric 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 symetric scheme with a key of size k will be bruteforced in time O(2^k), by searching for all the possible keys.

Asymetric 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 symetric 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 exemple, for well-chosen elliptic curves; hence the ElGamal cryptosystem over suitable ellipic curves might use keys "only" twice bigger than standard symetric 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 recommanded 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$
  • $\begingroup$ Can you provide references? $\endgroup$ – cygnusv Feb 11 '16 at 15:31
  • $\begingroup$ @cygnusv, Yes, you can see "Cryptographic Schemes Based on Isogenies", page 2. $\endgroup$ – Meysam Ghahramani Feb 11 '16 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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