Diffie Hellman (DH) Key Exchange Algorithm

-Soujanya Barik

To read the article in odia click here.

• Cryptography is the study of methods of sending messages in ciphered form so that only intended recipients can read the message. 
• The message we want to send is called plaintext and the message in disguised /ciphered form is called ciphertext.
•  The process of converting plaintext to ciphertext is called encryption and the process of converting ciphered text to its original form (i.e. plaintext) is called decryption.

Let for e.g. Encryption algorithm follows ‘shifting of letters right by 2 ’, then decryption will follow ‘shifting the letters left by 2’

Then “hello world” (Plain text) becomes “jgnnq yqtnf”(Ciphered text)

Fig 1. The message exchange process between sender and receiver.

Cryptography techniques may be classified as Symmetric encryption and Asymmetric encryption .

While in Asymmetric encryption (public-key cryptography) is a process that uses a pair of related keys - one public key and one private key to encrypt and decrypt a message . 

If Alice wants to send Bob a confidential message without the invasion of any third party then she can either use Asymmetric or Symmetric encryption to send her message. 

In Asymmetric encryption Alice takes Bob’s public key which is known to all and encrypts her message to him. Then, when Bob receives the message, he uses his private key to decrypt the message from Alice.

While in symmetric encryption, only one key is used to encrypt and decrypt the message, it is needed to safely generate the same key on both Alice and Bob’s side.

In order to do so Diffie Hellman (DH) key exchange algorithm is used. It is a method for securely exchanging cryptographic keys. This algorithm is based on an asymmetric encryption technique.

The algorithm is as follows.

1. First they decide on a large prime number q mutually, and a generator/primitive root of q (say g) (where 0 < g < q). A primitive root “g” of a prime is an integer such that g (mod q), g^2 (mod q),…, g^(q-1) (mod q) should be equivalent to 1, 2,…, q-1 in some order .
2. Alice chooses a secret integer Xa (her private key) such that Xa < q and then calculates Xb = g^ Xa mod q (which is her public key).
3. Bob chooses his private key Ya such that Ya <q and calculates his public key Yb =  g^ Ya mod q .
4. Now for Key generation the following algorithm (K) is adopted by both Alice and Bob.

• Alice generates key K by calculating Yb^ Xa (mod q) as  Yb (the public key of Bob) and  Xa (her private key) is known to her.
• Similarly Bob generated key K by calculating Xb ^ Ya (mod q) .

Yb^ Xa (mod q) = Xb ^ Ya (mod q) which the common shared key of Alice and Bob as the following is true.

Yb^ Xa (mod q) = (g^ Ya)^ Xa (mod q)= g^ Ya Xa (mod q)

And 

Xb ^ Ya (mod q) = (g^ Xa)^ Ya (mod q)= g^ Xa Ya (mod q).

An eavesdropper Eve who was listening to the communication knows q, g, Xb and Yb , but it is impossible to find the values of Xa and Ya from Xb and Yb as the chosen number is sufficiently large enough making it impossible to calculate private keys.

The end-to-end encrypted calls in telegram are based on the DH algorithm to generate keys. Although Diffie–Hellman key agreement is not a authenticated key-agreement protocol, it provides the basis for a variety of authenticated protocols for Key exchange algorithms.

References:-

1. https://www.gatevidyalay.com/cryptography-symmetric-key-cryptography/
2. https://searchsecurity.techtarget.com/definition/Diffie-Hellman-key-exchange

Written By-

Soujanya Barik