Why elliptic curves are good

Image002

It’s commonly thought that elliptic curve cryptography is "more secure" than some alternatives. This may be true from a certain point of view, but probably not for the reason that most people probably first guess.

In a previous post, we talked about how the security of the Diffie-Hellman key exchange is based on the computational Diffie-Hellman problem (CDHP). We can summarize the CDHP like this:

CDHP: Given g, ga, gb, find gab

If it’s hard to solve the CDHP then it’s hard for an adversary to find a Diffie-Hellman shared secret from what he can observe in a Diffie-Hellman key exchange. In some cases, we’d like to make it even more difficult for an adversary. In some cases, we’d like to make it so that it’s even hard for him to guess a shared secret and check if it’s right or not. (The checking is the part that’s hard – not the guessing.) This can be summarized in what’s called the decision Diffie-Hellman problem (DDHP):

DDHP: Given g, ga, gb, gc determine whether or not gc = gab

Note that if you can solve the CDHP then you can solve the DDHP. If you can find gab by solving the CDHP, you just check to see if it’s equal gc. But if you can solve the DDHP that doesn’t mean that you can solve the CDHP.

If the DDHP is hard, things are even more difficult for an attacker. He can’t even guess a solution to the CDHP and check to see if it’s right. So if the DDHP is hard, then it’s hard to tell gab from a random value. This is a nice property to have, but it turns out that the CDHP is actually easy in the usual setting for the Diffie-Hellman key exchange.

The Diffie-Hellman key exchange is usually done using multiplication of integers modulo some large prime number. In this setting, the DDHP is actually easy to solve, which means that gab doesn’t really look random.

On the other hand, suppose that we replace multiplying integers modulo a large prime number by adding points on an elliptic curve. In this case we can create a scheme just the Diffie-Hellman key exchange that works like this:

  1. Alice picks a point P and uses her private key a to calculate aP, which she sends to Bob along with P
  2. Bob uses his private key b to calculate bP, which he sends to Alice
  3. Alice calculates the shared secret abP as a(bP)
  4. Bob calculates the shared secret abP as b(aP)

This is called elliptic-curve Diffie-Hellman (ECDH). The name’s different, but the idea is really the same as the integer version of Diffie-Hellman. On the other hand, it turns out that the DDHP is hard when you’re working with points on an elliptic curve. This means that using elliptic curves offers an additional bit of protection that doing operations in the integers doesn’t. Using elliptic curves, it’s even hard for an adversary to guess an ECDH shared secret and check to see if it solves the CDHP, which is written this way when we’re working with points on an elliptic curve:

CDHP: Given P, aP, bP, find abP

So there’s probably a good reason for claiming that elliptic curve cryptography is more secure that some alternatives, but the reason isn’t what most people probably think of. It’s fairly well known that elliptic curve cryptography lets you use a shorter key that other public key technologies and still attain the same level of security. It only takes 160 bits of elliptic curve key is roughly equal to 1,024 bits of Diffie-Hellman, for example. But that’s not really a basis for claiming that the elliptic curve alternative is more secure.

If the security attained by a fixed number of bits was a useful metric for security, then we’d be justified in claiming that all public-key algorithms are less secure than symmetric algorithms. It only takes 80 bits of symmetric key to provide the same security as 160 bits of elliptic curve key, for example.

So a good reason for claiming that elliptic curves are more secure than some alternatives is because they create a setting where the DDHP is hard while some alternatives create a setting where the DDHP is easy.

Leave a Reply

Your email address will not be published. Required fields are marked *