ECDH vs DH secret key size

Question

In the past couple of weeks I have been reading about DH and ECDH which are key exchanging algorithm to compute a shared secret key. According to advices, it is better to use DH with key size 2048 bits and ECDH secp521r1 which results in 528 bits secret key. I confused about the strength of these two algorithm which results in the following questions:

• If ECDH secp521r1 has the equivalent strength of DH-2048 why there is smaller secret key for ECDH?
• If a person uses a well-known KDF such as HKDF-SHA-256 to derive a new key for encrypting; is ECDH secp521r1 better with regard to DH-2048 because it is faster to compute? As a result if something is faster to compute for both parties (client, server) so it would be for attacker?

Answer 1

AIUI (I am not a cryptographer)

We measure the security of cryptography by asking "given the best known attack how much computing power would it take to break this". This is clearly an imperfect measure, there may be a better attack that the mathematicians haven't figured out yet but sadly it's the best we have in most cases.

DH works in a "finite group". Such a group consists of a finite set of possible values along with an operator that works on two values from the set and returns another item from the set. The operator must also satisfy a series of axioms that I won't get into here. The number of elements in the set is known as the "order" of the group.

Confusingly there are two ways to write groups. Some groups are written "like addition" with the operator represented by "+" and the identity element represented by "0". Others are written "like multiplication" with the operator represented by a multiplication operator (".","*","×" or nothing at all) and the identity element represented by "1".

We can apply the operator repeatedly. If we are thinking of the group by analogy to addition then repeated application of the operator is analogous to multiplication. If we are thinking of the group by analogy to multiplication then repeated application of the operator is analagous to exponentiation. From here on I will refer to this repeated application of the group operator as discrete exponentiation. Thanks to associativity, discrete exponentiation can be computed in time proportional to the log of the exponent.

DH relies on discrete exponentiation being computationally infeasible to reverse. Specifically for "A = g^a" it should be infeasible to find "a" given "A" and "g". The problem of reversing discrete exponentiation is known as the discrete log problem.

The difference between traditional DH and ECDH is what group is used. Traditional DH uses the nonzero integers modulo p under multiplication. ECDH uses an elliptic curve.

---

The difficulty of solving the discrete log problem depends heavily on the particular group chosen.

Afaict for elliptic curve the best known algorithms have a complexity of roughly √n where n is the order of the group. So for 128 bits of security we need a group with roughly 2²⁵⁶ entries and our keys will be roughly 256 bits in length.

For traditional (modulo p) it is possible to use the general number field sieve to solve the discrete log problem. This algorithm has a much lower complexity for a given group size. So a much larger key is needed to push it into the realm of computationally infeasible.