A Quick Review of Diffie-Hellman

We will study a variant of Diffie-Hellman using Elliptic Curves. If you already know Diffie-Hellman, the core idea is very simple (it is difficult only in the details). So let’s have a quick review. In Diffie-Hellman, two parties want to have a number that is secret to themselves, using a physical medium which may be eavesdropped. Once that is achieved, the number may be used as symmetric key, dealing with the actual encryption quickly.

In Diffie-Hellman, we have a prime modulus p, and we have a generator g between 2 and p - 1, both large but known to everybody. Fermat’s Little Theorem dictates that g^{p-1} \equiv 1 \pmod p. We choose p and g so that g^k \not \equiv 1 \pmod p for any number between 1 and p - 2. (This is usually done by restricting the form of p, e.g., ensure that p = 2^x q + 1 for some prime q. Then we only need to check a few exponents of g to ensure that the above non-equivalence holds, in this case check g^2 \not \equiv 1 \pmod p and g^q \not \equiv 1 \pmod p.) This will ensure that the “discrete logarithm problem”, i.e., given k_x, find x, is hard to compute (i.e., takes an incredible amount of energy to compute given currently known algorithms).

Then two parties A and B wanting to communicate can share a common secret in the following scheme. First, they respectively generate their own secret a and b, and keep them secure. Then they independently calculate k_a = g^a \bmod p and k_b = g^b \bmod p, and call them public keys. Being public means that they can be published to the world, and because of the way g is constructed, doing so will not leak a and b.

Now A and B knows a secret that only they know, in particular g^{ab} \bmod p. A can calculate it as k_b^a \bmod p, and B can calculate it as k_a^b \bmod p. For everybody else, it doesn’t seem that there is a way to find that common secret without first computing either a or b, which is hard.

Suppose we want to have 128-bit security. The length required by a and b required would also be 128 bits. However, as good algorithms exists to solve discrete log in time less than exponential, the length required by p is 3072 bits. The two public keys would also be 3072 bits quantities.

We are going to study how to replace the discrete logarithm problem with another problem. As little as possible is changed on other parts of the above scheme, but it becomes vastly harder to find additional properties allowing algorithms like the general number field sieve. The key to the above is elliptic curves, which we will study next.

September 2017
Isaac To

Prev: Introduction    Up    Next: Elliptic Curve