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):

aa^(2)a^(3)a^(4)
1111
2431
34*21
4141

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).

D-H Key Exchange, Credit: pixelprivacy.com

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.pdfhttps://wiki.math.ntnu.no/_media/tma4160/2015h/dh.pdfhttp://homepages.math.uic.edu/~leon/mcs425-s08/handouts/el-gamal.pdf

One thought on “IX. Diffie-Hellman(-Merkle) Key Exchange

  1. It’s a pity you don’t have a donate button! I’d most certainly donate to this excellent blog! I suppose for now i’ll settle for bookmarking and adding your RSS feed to my Google account. I look forward to brand new updates and will share this blog with my Facebook group. Chat soon!

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s