IX. Diffie-Hellman(-Merkle) Key Exchange

After mentioned about Asymmetric Cryptography overview, with this article we are going to touch on D-H key exchange, at first, we are going to take a look at discrete logarithm.

Discrete Logarithm

We know that, for any numbers “a” & “b” and any function “y” such that y = a^(b) can be described as b = log_(a)[y]. Now let’s consider any numbers “a”, “b”, “p (any prime number)”, “d” and any function “y” such that y = a^(b) (mod p). This function can also be written as b = d*log_(a, p)[y] where “b” is called the discrete logarithm of “y” base “a (mod p)”.

If you consider, when does such “b” exist and unique ? The answer would be related with “a” and “p”. Moreover, there exist and unique such “b” when “a” is primitive root of “p” ,i.e., a^(1), … , a^(p-1) mod(p) produce distinct integers between 1, …, p-1. The main idea on D-H key exchange is simply about the difficulty of finding such “b”.

For instance,

Below table for (mod 5):

a	a^(2)	a^(3)	a^(4)
1	1	1	1
2	4	3	1
3	4*	2	1
4	1	4	1

Here, a = 4 isn’t a primitive root, since powers of 4 (mod 5) are only congruent to 1 or 4. However, a = 2 is primitive root for every number a relatively prime to 5,i.e., there is an integer “z” such that 2^(z) ≡ a. 

For 2 from a^(2) and a = 3, 2 = d*log_(3,5)[4] where 4 comes from 4*, is exist and unique.

The main idea on D-H key exchange is simply about the difficulty of finding such “b”.

D-H Key Exchange

As mentioned above, key exchange security relies on discrete logarithm problem. It’s practical method to perform exchange over insecure public channel (e.g. paper key lists transported by a trusted courier -physical channel).

Step by Step Key Setup:

• At first, to exchange secret key, Alice and Bob agree on parameters “a” and “p”.
• Both Alice and Bob randomly selects X, where X < p, then computes Y = a^(X) (mod p). Here, X and Y stand for private and public keys respectively. For instance, {X_(A), Y_(A)} and {X_(B), Y_(B)} are key pairs of Alice and Bob.
• Alice sends Y_(A) to Bob, Bob sends Y_(B) to Alice.
• Then, Alice computes the key “K” such that K = Y_(B)^(X_A) (mod p) and Bob computes K = Y_(A)^(X_(B) (mod p). Since, X_(A) and X_(B) are secret, K is also secret.

However, above process is vulnerable since there is no authentication. Can be authenticated by Alice and Bob (e.g. digital signatures), though.

Bonus: El Gamal Encryption

The El Gamal Algorithm provides an alternative way to the RSA for public key encryption, since security of the RSA depends on the difficulty of factoring large integers, El Gamal algorithm depends on the difficulty of computing discrete logarithms in a large prime modulus related to D-H key exchange.

O.S. Tapsin

Resources: https://d3c33hcgiwev3.cloudfront.net/_c9e2c60d142c0d9a9fe91ff804356e52_slides_diffie_hellman_key_exchange.pdf?Expires=1568764800&Signature=EWIiL4pQzCsLzHvocYXMqUUMO25D-HxrUyUOLSyX6qXpyZBCPfNxCGPOzBkUYOZ-7L99laI5-hIqmMD9UJTo3stGo6Uu-y4HTd3qOZjhyiFbNQ4ACRYmCfoE360LI-Pj5R7eQD7Ix3l9cs1oI~Mi4cKK-aLBXaR6IqTnk377AZo_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A  by Sang-Yoon Chang, Ph.D. — https://ee.stanford.edu/~hellman/publications/24.pdf — https://wiki.math.ntnu.no/_media/tma4160/2015h/dh.pdf — http://homepages.math.uic.edu/~leon/mcs425-s08/handouts/el-gamal.pdf —