The Mathematics of Exponential Key-Agreement

            There is a lot of chatter right now concerning the “old” methods of handshakes for secure connections over a network. These are the RSA key exchange, and the Diffie-Hellman key exchange. This is the beginning of a multi-part series that will detail how these algorithms work, their weaknesses, and how they are currently defeated (if it is possible).

            In this first part I’m going to cover the Diffie-Hellman key exchange, also known as Exponential Key Agreement.

            The concept: The Diffie Hellman key exchange depends on the difficulty to solve the discrete logarithm problem using very large numbers. Two computers only reveal small initial pieces of the problem so they can come up with a mutual number, without ever transmitting the mutual number over the network. The math itself goes all the way back to Eudoxus in Greece around 300 BCE.

            The basic principal is an expansion on (Xa)b = (Xb)a

An example using simplified math:

You have two computers that want to establish a secure connection. You know that there are devices listening to your transmissions either for nefarious purposes or just via logging. Let’s call these computers Client-1 and VikingVPN-1.

It follows that:

Client-1 and VikingVPN-1 both have secret keys a and b respectively. These are large numbers that are not known to anyone but themselves.

Client-1 and VikingVPN negotiate a base number g and a prime number p (p is often called the public key) to use for calculations. This negotiation is transmitted over the insecure network. 

For this example we are going to say that Client-1’s secret key is 81, and VikingVPN-1’s secret key is 61.

They negotiate with one another that g = 3 and p = 37 for this session.

Now each client calculates numbers to transmit over the insecure network.

This is done by the following formula for each:

Client-1 calculates:

VikingVPN-1 calculates:

After the initial calculations are completed, B is sent to Client-1 and A is sent to VikingVPN-1.

Now Client-1 and VikingVPN-1 need to calculate their shared secret number “s”.

          VikingVPN-1 now takes A, (which it just received from the internet from Client-1) and calculates:

            Client-1 now takes B, (which it just received from the internet from VikingVPN-1) and calculates:

As you can see, Client-1 and VikingVPN-1 now have a mutual secret number s that was derived using the private keys “a” and “b”, without ever revealing the private keys to anyone.

Note how large and complex the numbers got while using relatively small original numbers (this example would be the equivalent of a 7 or 8-bit handshake, the current industry standard is 2048-bit). If we scaled this up to where computers are doing the math today (2048-bit keys) the numbers immediately become inconceivably large and hard to manage even for modern processors.

Because the mathematics is so complex for processing, this process is only used to initialize a connection between two computers. After the Exponential Key Agreement is completed, the client and server would normally transmit a symmetrical key like AES to one another to use for the rest of the session. This is to keep computing requirements down and speeds up.

You may also question if this process can be reverse engineered to get the private keys, or the mutual secret s, by an interloper on the network. Here is what an interloper that was listening would know:

The value of A, B, g, and p.

The best known formula to try to reverse engineer this handshake is called the Discrete Logarithm Problem, mentioned earlier. The next installment will be about applying the Discrete Logarithm Problem to try extract the keys that were used in this article. Stay Tuned!

(For the record, VikingVPN greatly exceeds the standard 2048-bit Diffie-Hellman strengths and uses 4096-bit keys, which are not twice as strong, but 2^2048 times as strong.)

< last
next >