Introduction to Diffie-Hellman Key Exchange

February 4, 2021 by

Nitesh Malviya

Encryption is the process of converting plaintext to encrypted text. Since encrypted text cannot be read by anyone, encrypted text hides the original data from unauthorized users.

Decryption is the process of converting encrypted data to plaintext. Basically, it is the reverse of encryption. It is used to decrypt the encrypted data so that only an authorized user can access and read the data. The process entailing encryption and decryption together is called cryptography.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

Private and public keys in cryptography

A key is a bit-valued string that is used to convert the plaintext into ciphertext and vice-versa. A key can be a word, number or phrase. Cryptography makes use of public and private keys. A public key is issued publicly by the organization and it is used by the end-user to encrypt the data. The encrypted data, once received by the organization, is decrypted by using a private key and the data is converted to plaintext.

Encryption types

Cryptography uses symmetric and asymmetric encryption for encryption and decryption of data. If the sender and the recipient of the data use the same key to encrypt and decrypt the data, it’s called symmetric encryption and if the keys are different for encryption and decryption then it’s asymmetric encryption. 

Now the basics are clear, let’s focus on the Diffie-Hellman algorithm in this post.

Diffie-Hellman Key Exchange

Diffie-Hellman algorithm was developed in 1976 by Whitfield Diffie and Martin Hellman. Thus, the name Diffie Hellman. Also, going by the name this algorithm is not used to encrypt the data, instead, it is used for generating the secret key between the sender and the receiver. 

Asymmetric Encryption requires the transfer of a private key between the sender and the receiver of data. One of the challenging parts of Asymmetric Encryption is the safe and secure transfer of the secret key between the sender and the receiver. No one should have access or intercept the secret key during the transfer. This transfer or rather generation of the secret key at both sides was facilitated by the Diffie-Hellman algorithm. 

Diffie-Hellman Algorithm

Let’s understand how the Diffie-Hellman Algorithm works. 

1. For the sake of understanding of the algorithm, let’s consider 4 variables - One prime number P and another number G which has no factor in common with P, 2 private values a and b. 
2. P and G publicly available. 2 users let’s say Alice and Bob choose private values a and b respectively and they generate their key for exchanging it publicly. The other person receives the key and generates a secret key from the received key. Now both Alice and Bob have the same secret key to encrypt.
3. Both Alice and Bob generates key as follows

• X = G^a mod P
• Y = G^b mod P

     4) Now the keys are exchanged. Alice receives Y and Bob receives X

     5) Secret key is generated as follows

• Ka = Y^a mod P
• Kb = X^b mod P

    6) Algebraically, Ka = Kb

Let’s understand this with an example:

Step 1: Alice & Bob chooses public numbers P = 23, G = 9 respectively.

Step 2: Following private keys are selected

 Alice a = 4 

 Bob b = 3

Step 3: Computing public values

Alice: x =(9^4 mod 23) = (6561 mod 23) = 6

Bob: y = (9^3 mod 23) = (729 mod 23)  = 16

Step 4: These public numbers are exchanged

Step 5: Now Alice has public key y =16 and Bob has public key x = 6

Step 6: Alice and Bob both of them compute symmetric keys as follows - 

        Alice: ka = y^a mod p = 65536 mod 23 = 9

        Bob: kb = x^b mod p = 216 mod 23 = 9

Step 7: 9 is the shared secret.

As explained, this is how the Diffie-Hellman algorithm works to generate shared secret keys which is used to encrypt the data being sent over a public channel.

Learn Applied Cryptography

Build your applied cryptography and cryptanalysis skills with 13 courses covering hashing, PKI, SSL/TLS, full disk encryption and more.

Start Learning

Sources

• http://www.crypto-it.net/eng/asymmetric/diffie-hellman.html 
• https://www.thegeekstuff.com/2013/01/diffie-hellman-key-exchange-algorithm/ 
• https://www.geeksforgeeks.org/implementation-diffie-hellman-algorithm/ 
• https://doubleoctopus.com/security-wiki/encryption-and-cryptography/diffie-hellman-algorithm
• https://www.gatevidyalay.com/diffie-hellman-key-exchange-asymmetric-encryption/