L U N I V E R S E
Diffie-Hellman
Diffie-Hellman key exchange process

Alice wants to send a secret message to Bob. However, there is an eavesdropper (Eve) listening to the conversation overhead. How can Alice send her message securely without the message being exposed to Eve?

Suppose that Alice first met Bob at the 11th street, and she wants to send a message that tells Bob to meet at 832nd street. One possible way is for Alice to send an encrypted message:

“Street number of the meeting location: add 721 from the street number that we first met”

This way, there is no way for Eve to decrypt the message. However, this method is not always useful as there is an underlying assumption that Alice and Bob has a shared key that is agreed beforehand. In this example, the shared key is “721”.

But what if Alice and Bob never met or communicated before?

Diffie-Hellman key exchange protocol is an algorithm that securely establishes a shared secret between two parties over a public (i.e. insecure) channel.

Unique feature of the DH protocol is that doesn’t require parties to have a pre-agreed key that is shared via direct communication. How DH protocol works is that it generates a single public key and private keys (one key for each communicating party) to generate a shared key.

In this article, we will look at the key exchange process, specifically how the shared key is generated without Eve being able to deduce it.

Diffie-Hellman
Source: Diffie-Hellman Key Exchange- Real Insight Comes From Fixing Error

Scenario

Suppose Alice and Bob wishes to exchange the key before they start communicating. However, Eve the intruder somehow got access to the communication channel and is listening to the conversation and intercepting the keys being sent. If Eve can intercept the key, then encrypting the data with that key is pointless.

Step 1. Choose a public key

Alice and Bob agrees on a large prime p and a nonzero integer g modulo p (primitive root modulo p)* . Note that g and p is publicly announced, so that anyone including Eve can see the keys.

p = 17
g = 3

*Definition) A primitive root modulo a prime p is an integer g in Z𝑝 = {0, 1, … , p-1} such that every nonzero element of Z𝑝 is a power of g.

** In this example, we are going to use small numbers for convenient computation. In practice, it is a good idea to choose p such that (p-1)/2 is also prime.

Step 2. Alice and Bob each choose a private key

Now, Alice picks a secret integer a that she does not reveal to anyone, while at the same time Bob picks an integer b that he keeps secret.

a = 15
b = 13

Step 3. Alice and Bob computes X ≡ gˣ(mod p) where x = private key

Alice computes the following:

A ≡ gᵃ (mod p) 
≡ 3¹⁵ (mod 17)
≡ 6 (mod 17)
∴ A = 6

Now, Bob computes:

B ≡ gᵇ (mod p)
≡ 3¹³ (mod 17)
≡ 12 (mod 13)
∴ B = 12

Step 4: Alice and Bob exchanges their private key and generate a shared key.

Alice sends computed value of A to Bob, and Bob sends B to Alice (Note that since Alice and Bob are communicating through an insecure channel, Eve gets to see the values of A and B).

Finally, Alice and Bob use their secret integers to compute the following:

Alice computes:

A’ ≡ Bᵃ (mod p)
≡ 12¹⁵ (mod 17)
A’ = 10

Bob computes:

B’ ≡ Aᵇ (mod p)
≡ 6¹³ (mod 17)
B’ = 10

Notice that A’ = B’ = 10. Alice and Bob have successfully generated a shared key!

Luniverse 'Trace' Service Launching Event!

Provide free 100 days to use Luniverse 'Trace', Blockchain based event tracking service

But how do we know that Eve cannot deduce this key from known information?

Let’s write down the information Eve has access to.

a = ?
b = ?

A = 3ᵃ (mod 17) = 6
B = 3ᵇ (mod 17) = 12

Shared key = 12ᵃ (mod 17) = 6ᵇ (mod 17) = ?

In order for Eve to find out what the shared key is, she must solve for a and b. However, it is very difficult and time consuming process to solve for these numbers, due to mathematical one-way action.

For example, it is easy to compute 3¹⁵ (mod 17); on the other hand, if we were to solve for a that satisfies the equation 3ᵃ (mod 17) = 6, it becomes computationally unsolvable. Diffie-Hellman key exchange method uses the property of modular arithmetic that is easy to solve in one direction, but extremely difficult to solve in the other.

Generalizing the DH algorithm, we have the following:

Source: Hoffstein, J. An Introduction to Mathematical Cryptography (2008)

Conclusion

The most prevalent problem in cryptography today is the exchange of keys between communicating parties. The ultimate goal is not just to exchange the keys, but to do it in such a way that anyone who is listening to the communication should not get a hold of the shared key.

Diffie-Hellman key exchange protocol is a method of digital encryption that uses modular arithmetic to produce decryption keys on the basis of components that are not directly transmitted, making the task of a would-be code breaker mathematically overwhelming. The Diffie-Hellman key exchange method allows parties who have no prior knowledge of each other to jointly establish a shared secret key over an insecure channel.

→  Cryptography 101 : RSA Algorithm

열번 읽는것보다 한번 보고 듣는게 이해하기 쉽습니다.

루니버스는 블록체인을 서비스에 쉽고 빠르게 도입할 수 있는 BaaS(Blockchain as a Service)입니다.
간단한 데모를 보시면 루니버스를 더 쉽게 이해하실 수 있습니다.
지금 바로 데모를 신청해 보세요.
Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn

Related Posts

4F, 14 Teheran-ro 4-gil, Gangnam-gu, Seoul, Korea, 06232
Ceo. Park Jaehyun
Business Registration No. 694-86-01434
Online Marketing Report No. 2019-Seoul Gangnam-02255

ⓒ Lambda256 Inc, All Rights Reserved.