# 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 (X^{a})^{b }= (X^{b})^{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.)