Rock Around the Clock: Part 1: The Diffie-Hellman Key Exchange

In this article, I will discuss the Diffie-Hellman Key Exchange (DFKE), a public key algorithm based on Discrete Logarithm Schemes. Other examples of such algorithms include ElGamal encryption and the Digital Signature Algorithm.

I will start by providing the historical context of DFKE and explaining how it works, showcasing how simple mathematics can lead to powerful ideas. Finally, I will summarise some key points on group theory and its relationship with the discrete logarithm problem (DLP).

Background

The dawn of the computer age at Bletchley Park ushered in a new era of cryptanalysis. In the 1960s and 1970s, innovative forms of symmetric-key encryption, such as the Data Encryption Standard (DES), made strong encryption a part of everyday life. However, although the algorithms were unbreakable, a problem remained regarding how to share keys used for encryption and decryption. Every link in the transportation chain was a possible attack vector.

Humpty Dumpty Functions

Whitfield Diffie and Martin Hellman developed an asynchronous key exchange protocol that relied upon one-way functions to securely transmit a key without interception. The correct one-way process would be easy to compute but difficult to undo. The analogy of mixing paint is an excellent way to think about a one-way function. Whilst it is simple to mix colours together to create new colours, it is hard to reverse this process to see what colours were combined to create the colour.

One way functions have been nicknamed ‘Humpty Dumpty functions’ after the well-known nursery rhyme because once Humpty falls down, ‘all the king’s horses and all the king’s men, couldn’t put Humpty back together again’.

Modular mathematics, also known as clock arithmetic, is a branch of mathematics widely used in computer science and has a specific relevance in cryptology. It is rich in one-way functions, making it a valuable tool for encryption and decryption. Modular functions follow particular laws that allow for predictable results when used by the sender and receiver. These functions are commutative, associative, and distributive. The DFKE is one example of an encryption algorithm that uses modular mathematics. Additionally, modular functions are also used in integer factorization schemes like RSA.

The Diffie-Hellman Key Exchange

Let’s break down the DFKE to understand it better. Let’s use the colour analogy we used in the previous section to simplify things. It’s also the right time to introduce Alice and Bob.

Alice and Bob are fictional characters often used in thought experiments related to cryptography. They first appeared in the paper introducing RSA asymmetric cryptography, ‘A Method for Obtaining Digital Signatures and Public-key Cryptosystems’. In DFKE, Alice and Bob need to exchange a message, which is a cryptographic key.

We also need to add another character to the story, and her name is Eve. Eve is a passive attacker who wants to listen to Alice and Bob’s communication and steal the message. A passive attacker in network security is an attacker who tries to break a system based on observed data.

A Colourful Conceit

Phase 1: The setup

During the first phase of DFKE, Alice and Bob will agree to use two numbers over an insecure channel. To use a mixing paint analogy, they would choose two colours, such as blue and yellow. However, as the line is insecure, Eve also takes note of the values.

Phase 2: The exchange

Next, Alice and Bob pick their secret colour; in the diagram below, I labelled them A and B. They will not share these values with anyone:

Alice and Bob both need to create a colour that can be shared. They blend the initial values Y and P with their secret colours, A and B. This results in Alice having the colour AYP and Bob having BYP.

Now, Alice and Bob can exchange AYP and BYP. Eve can listen but cannot deduce A and B.

Finally, Alice and Bob add their secret to the exchanged value:

Alice and Bob have successfully exchanged values over an insecure communication line and ended up with the same secret key. The reason for this is that both keys are constructed by using the same colours. This is an example of the power of one-way functions, as Eve, who does not know A and B, would have no way of deriving the key.

I’ve got your number

It’s time to show how modular arithmetic makes this possible, starting with phase 1. Instead of two colours, Alice and Bob choose a large prime for Y and a number less than Y for P. Here are the steps

Diffie-Hellman Set-up

• Choose a large prime Y

• Choose an integer P less than Y. P should also be a primitive element to Y.

• Publish P and Y

The parameters P and Y are sometimes referred to as the domain parameters. Once the domain parameters have been agreed upon, Alice and Bob can generate the secret key using the following technique:

Diffie-Hellman Exchange

• Alice and Bob both choose numbers a and b that are less than the large prime Y:

• Alice and Bob now calculate P to the power of their numbers and work out the modulo of Y. Alice stores the result in a variable called aδ and Bob stores the result in a variable called bδ:

• Alice and Bob can now exchange aδ and bδ.
• Alice and Bob raise the exchanged numbers to their private ones and calculate the modulo:

This works because modular arithmetic is commutative:

To help illustrate this, let’s take out the modulo Y from the equations and work through an example using the most minor possible numbers:

As we took out the modulo we are now just calculating:

If we add back in the modulo operator we still have the same commutative relationship.

It may seem like we don’t need the modulo group. If Eve wants to steal Alice and Bob’s numbers, she can easily reverse-engineer them. In the first case, if Eve knows that aδ is (2³) = 8, to calculate a, she would simply work out 3 = log2 8. In the second example, if Eve knows that aδ is 7^a mod 11 = 2, she would need to run through powers of P mod 11 until she arrives at 2.

Both examples are equally insecure. When dealing with the set of all numbers, some strategies allow for the logarithm to be quickly computed even for large numbers. However, for a large prime number Y and a number P that is primitive to it, there is no easy way to compute the logarithm for the set of numbers of powers of P mod Y. This is commonly known as the discrete logarithm problem.

The Discrete Logarithm Problem

The discrete logarithm problem is a mathematical concept that falls under group theory. To better understand this problem, let me first provide examples of finite cyclic groups and their properties, such as the generator and identity element.

A group in maths is a group of numbers and an operator that abides by specific rules. An additive group uses the additive operator, and a multiplicative group uses the multiplication operator. We will look at multiplicative groups. The multiplicative group of powers 2’s would look like:

Cryptography is primarily concerned with bounded groups. A group is said to be bounded when its elements are constrained within a given range. An example of a bounded group is the additive group mod a number n, denoted as (Z/nZ). Here’s an example of how this group works:

The cardinality of a group is the maximum number of unique elements. In the group above, the cardinality would be 2. The order of a group is the number of times the group operation needs to be executed to return the identity element. In group theory, the identity element (or neutral element) is the unique element in a group that, when combined with any group element using the group operation, results in the same element. The identity element is practical when finding the order of an element in a group. To find the order of an additive group, you calculate n multiplied by e until the result equals 0.

The identity element of multiplicative groups is 1. To find the order for a given element we raise that element to incrementing powers until we reach 1.

So, the order of 2 in the multiplicative group mod 5 is 4 as 2⁴=1. An attractive property of this group is that it contains all the natural numbers of mod 5 (1, 2, 3, 4), and it generates them in a seemingly random order. A number that generates all group members is known as a generator or primitive element.

Euler’s totient function, or phi (φ) function is a way to find the maximum order of a group.

For any given group, if the operator is modulo a prime number, it will have an order of that number minus one. Prime numbers always contain at least one number that generates the entire group. For example, we saw that with number 5, the powers of 2 mod 5 generated the whole group. Groups formed by calculating the mod of a prime number are called prime fields.

Another attractive property of these groups is that the order of the subgroups within them will contain orders that are divisors of the order of the group. For example, 5 has an order of 4, and multiples of 4 are 1, 4 and 2. So we know that the order of the subgroups will be 1, 4 and 2. We can prove this out:

Here, we can see that for mod 5, we have groups of order 1 (powers of 1), groups of order 4 (powers of 2 and 3) and groups of order 2 (powers of 4).

These cyclic subgroups have a particular property. If a cyclic subgroup has φ(order), which is prime, then every group member that is not 1 will be a generator for that group.

The discrete logarithm problem states that given a finite cyclic group over a prime field and a primitive element of that group as well as another number. Calculate the primitive element raised to that number mod the field’s prime.