Diffie–Hellman Key Exchange

1/8

1/12

This material was developed with funding from the National Science Foundation under Grant # DUE 1601612

Back

Next

Restart

Diffie–Hellman Key Exchange

The Problem

Bob and Alice Want to talk securely but they have never talked to each other before and have no other method of talking expect over an unsecure network. This is where the Diffie-Hellman Key exchange is used to create a secure communication method that can be established without a secure secondary communication network or trusted third party authentication.

Unsecure Network

2/12

3/12

Public transport

(assume that mixture separation is expensive)

Secret colors

Common secret

=

+

Analogy

There is a lot of complicated math and very large numbers that is not always easy to understand so lets look at an analogy to help explain how the exchange happens then we can go over the math. The analogy we use will be looking at paint instead of numbers. First Alice and bob will agree on a common starting place lets say green paint. They will then add their own secret paint to it creating a mixture. Once this mixture is made they will send to the other person. In this analogy it would be very hard and expensive to try to separate the paint into the two starting colors. Once each person has received the color from the other person they will add there secret color to it creating a common color/ This common color is a secret and that secret they can use to encrypt messages to each other.

Common paint

Common number

p = 23 g = 5

Math Part 1  The Common Number

Alice and Bob agree to use a modulus p = 23 and a base g = 5

5/12

6/12

A = ga mod p A = 54 mod 23 A = 4

4

Math Part 2 Alice’s Secret Integer

Alice chooses 4 as her secret number

A = 4

She then sends Bob the following formulas output A = ga mod p A = 54 mod 23 A = 4

Secret numbers

7/12

Math Part 3 Bob’s Secret Integer

B = gb mod p B = 53 mod 23 B = 10

Bob chooses 3 as his secret number

3

He then sends Alice the following formulas output B = gb mod p B = 53 mod 23 B = 10

B = 10

Alice has received 10 from Bob She uses the following formula to calculate the common secret S = Ba mod p S = 104 mod 23 S = 18 The common secret is 18

Math Part 4 Alice’s Common Secret

S = Ba mod p S = 104 mod 23 S = 18

S = 18

8/12

Math Part 5 Bob’s Common Secret

S = Ab mod p S = 43 mod 23 S = 18

9/12

Bob receives 4 from Alice He then sends Alice the following formulas output B = Ab mod p B = 43 mod 23 B = 18 The common secret is 18

Decryption

KU =    7,   187

KR =    23,    187

Plaintext 88

10/12

Ciphertext 11

887 mod 187 = 11

Encryption

Alice and Bob use the common secret 18 to encrypt a message and decrypt it saying hello to each other.

1123 mod 187 = 88

Alice and Bob Both Have the Common Secret

The reason this works is because it uses such large numbers. The common paint is prime number at least 2048 bits long with numbers this large it would be to costly for an attacker to attack the number that was shared and try to break it down to the two numbers that it is made of.

11/12

p = 13890143473829775722498011200310380316844447828814935927285432613507199159167722676657644390503254885067309729088246803976717186536237545696074407617252692272753523150095814175724095942210614670191629849771545994055456348662863125083954489746967620365631763638411626220580357256335085320237362476038814489657249198467580086057948518152187740483229396523233173271491163929243240236631349894842306615274693839354685812879841062224639585215273698139499197835540898969320991997758395568824475469359939378968115406019141601420464686230580766827389980948436032480690934398309104220456393444582655511612490684991989628173661

Actual Size of Numbers Used in the Exchange

The Main Vulnerability in this Exchange

12/12

A man in the middle attack would be able to sit in the middle and do the exchange on both sides decrypting both message going each way and then encrypting them or a new message to keep going to the intended person.

Hello! It’s Alice

wAxtB YisjrbF

Hello! It's Alice. What is your email?

jSgfhie lKshda iGjs rd oRhu vdLSi?

bob@ email.com

Jdb@ knsdlf.vds

Hi! This is Bob

uf! fKsh re Nxc

4/12