Diffie Hellman Key Exchange Algorithm: An insight
” I propose to consider the question: Can machines think?” -Alan Turing
Our modern world runs on binary. It is all about ones and zeros. These two digits envelop our lives in more ways than we can visualize. From the notifications you check every morning to the way you commute to work; it all is made possible because of binary. But know, that it did not start out this way. World war compelled many inventions which form the pillars of today’s modern society. The conception of the Turing Machine was the one of the most ingenious inventions of all time. One can argue that it unlocked a new branch of study for the world to ponder upon and improve. Design and Analysis of Algorithms.
Fruits of advancement in this field are plenty. The primary example being that of Cryptanalysis and Cyber Security. We cannot depend on swords and shields in 2021 now, can we? The most sensitive data does not exist on paper. It is all on the digital libraries and that data needs to be protected. One of the simpler ways of doing that was concocted by joint efforts of three people: Ralph Merkle, Whitfield Diffie and Martin Hellman. Which we now know as Diffie Hellman Key Exchange Algorithm.
What is it though?
Well, it is basically used to convey messages between two people covertly so that a third party is not able to read into the message and it is delivered safely. Slightly technical term, it is an encryption-decryption routine.
The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher.
It is like using your own personal, self- devised code language. Seems cool, right?
What is language at its crux? No, I am not being philosophical. A language is a system of communication. You know that a round object which bounces is called a ball, because someone told you so. In other words, the description Round and Bouncy was given a key which you now know as ball. Similarly, Diffie Hellman Algorithm requires only one thing to work. A simple rule and key to decode the encrypted messages.
A Lay-readers’ example
A magician was called at a kids’ birthday party. He claimed that he could make 2 different mixtures of colors form a same color. For that he called 2 volunteers, Alex, and Bruce. This cryptographer (Part time magician) uses the design of color mixing key exchange scheme. This scheme assumes that if we have two liquids of different colors, we can easily mix the colors and obtain a new color, but the reverse operation is almost impossible: no way to separate the mixed colors back to their original color components.
Okay, now let us break it down into steps:
- Alex and Bruce, agree on an arbitrary starting (shared) color that does not need to be kept secret (e.g., yellow)
- Alex and Bruce separately select a secret color that they keep to themselves (e.g., red and sea green)
- Finally, Alex and Bruce mix their secret color together with their mutually shared color. The obtained mixed colors area ready for public exchange (in our case orange and light sky blue).
- Alex and Bruce publicly exchange their two mixed colors.
- We assume that there is no efficient way to extract (separate) the secret color from the mixed color, so third parties (the audience), who know the mixed colors cannot reveal the secret colors. (no, they cannot be blackmailed).
- Finally, Alex and Bruce mix the color they received from each other with their own secret color.
- The result is the final color mixture (yellow brown) which is identical to the partner’s color mixture.
It is the securely exchanged shared key.
Ta da. Magic.
The Math behind it
Just like in almost every other domain, we simply cannot avoid the math.
(gᵃ)ᵇ mod p = (gᵇ)ᵃ mod p (where g, a, b and p are positive integers.)
If we have A = gᵃ mod p and B = gᵃ mod p, we can calculate gᵃᵇ mod p, without revealing a or b (which are called secret exponents)
In computing theory, these is no efficient algorithm which can find a secret exponent. If we have m, g and p from the below equation:
m = gˢ mod p
there is no efficient (fast) algorithm to find the secret exponent s.
The theoretical formula will be much clearer with an example. Try to correlate the mathematical expressions with the color mixing example.
Alex and Bruce agree to use two public integers: modulus p and base g (where p is prime, and g is a primitive root modulo p).
For example, let p = 23 and g = 5.
The integers g and p are public, typically hard-coded constants in the source code.
Alex chooses a secret integer a (e.g., a = 4), then calculates and sends to Bruce the number A = gᵃ mod p.
The number A is public. It is sent over the public channel and its interception cannot reveal the secret exponent a.
In our case we have: A = 54 mod 23 = 4.
Bruce chooses a secret integer b (e.g., b = 3), then calculates and sends to Alex the number B = gᵇ mod p.
In our case we have: B = 53 mod 23 = 10
Alex computes s = Bᵃ mod p
In our example, s = 104 mod 23 = 18
Bruce computes, s = Aᵇ mod p
In our example, s = 43 mod 23 = 18
Alex and Bruce now share a secret number s
s = Aᵇ mod p = Bᵃ mod p = (gᵃ)ᵇ mod p = (gᵇ)ᵃ mod p = gᵃᵇ mod p = 18
The shared secret key s cannot be computed from the publicly available numbers A and B, because the secret exponents a and b cannot be efficiently calculated.
Okay, But why use it?
Answer to this question is simple. Because it is secure. The Discrete Logarithmic Problem makes the Diffie Hellman Algorithm almost uncrackable.
The Discrete Logarithm Problem (DLP) in computer science is defined as follows:
By given element b and value a = bx find the exponent x (if it exists)
The exponent x is called discrete logarithm, i.e., x = logb(a). The elements a and b can be simple integers modulo p (from the group ℤ/pℤ) or elements of finite cyclic multiplicative group G (modulo p), where p is typically a prime number.
In cryptography, many algorithms rely on the computational difficulty of the DLP problem over carefully chosen group, for which no efficient algorithm exists.
The two parties involved need not have prior knowledge of each other. Once the keys are exchanged, the communication of data can be done through an insecure channel. The sharing of the secret key is safe.
The concerning disadvantage of this algorithm is that it does not authenticate any party during communication. This encryption algorithm is susceptible to man in the middle attack, if the keys are not generated at random efficiently.
Wrapping it up
The Diffie Hellman Algorithm has proven to be useful due to its smart design and advantages. Both the parties should be vigilant and careful while exchanging sensitive information. This Scheme has enabled secure transfer and communication of sensitive data for many organizations and remains one of the most used methods in cryptanalysis till date.
Cheers.
