Diffie-Hellman Key Exchange
The Problem of Key Exchange
• One of the main problems of symmetric key
encryption is it requires a secure & reliable
channel for the shared key exchange.
• The Diffie-Hellman Key Exchange protocol
offers a way in which a public channel can
be used to create a confidential shared key.
Modular what?
• In practice the shared encryption key relies
on such complex concepts as Modular
Exponentiation, Primitive Roots and
Discrete Logarithm Problems.
A Difficult One-Way Problem
• The first thing we require is a simple real-
world operation that is easy to Do but hard
to Undo.
• You can ring a bell but not unring one.
• Toothpaste is easy to squeeze out of a tube but
famously hard to put back in.
• In our example we will use Mixing Colors.
• Easy to mix 2 colors, hard to unmix
Alice & Bob with Eve listening
wish to make a secret shared color
Step 1 - Both publicly agree to a
shared color
Step 2 - Each picks a secret color
Step 3 - Each adds their secret
color to the shared color
Step 4 - Each sends the other
their new mixed color
Each combines the shared color from
the other with their own secret color
Alice & Bob have agreed to a
shared color unknown to Eve
• How is it that Alice & Bob’s final mixtures
are identical?
• Alice mixed
• [(Yellow + Teal) from Bob] + Orange
• Bob mixed
• [(Yellow + Orange) from Alice] + Teal
Alice & Bob have agreed to a
shared color unknown to Eve
• How is it that Alice & Bob’s final mixture is
secret?
• Eve never has knowledge of the secret
colors of either Alice or Bob
• Unmixing a color into its component colors
is a hard problem
Alice & Bob have agreed to a
shared color unknown to Eve
• How is it that Alice & Bob’s final mixture is
secret?
• Eve never has knowledge of the secret
colors of either Alice or Bob
• Unmixing a color into its component colors
is a hard problem
Diffie-Hellman Key Exchange
Adding Mathematics
Let’s get back to math
• We will rely on the formula below being an
easy problem one direction and hard in
reverse.
• s = gn mod p
• Easy: given g, n, & p, solve for s
• Hard: given s, g, & p, solve for n
• And the property of
• ga*b mod p = gb*a mod p
Step 1 –Publicly shared
information
• Alice & Bob publicly agree to a large prime
number called the modulus, or p.
• Alice & Bob publicly agree to a number
called the generator, or g, which has a
primitive root relationship with p.
• In our example we’ll assume
• p = 17
• g=3
• Eve is aware of the values of p or g.
Step 2 – Select a secret key
• Alice selects a secret key, which we will
call a.
• Bob selects a secret key, which we will
call b.
• For our example assume:
• a = 54
• b = 24
• Eve is unaware of the values of a or b.
Step 3 – Combine secret keys
with public information
• Alice combines her secret key of a with the
public information to compute A.
• A = ga mod p
• A = 354 mod 17
• A = 15
Step 3 – Combine secret key with
public information
• Bob combines his secret key of b with the
public information to compute B.
• B = gb mod p
• B = 354 mod 17
• B = 16
Step 4 – Share combined values
• Alice shares her combined value, A, with
Bob. Bob shares his combined value, B,
with Alice.
• Sent to Bob
• A = 15
• Sent to Alice
• B = 16
• Eve is privy to this exchange and knows the
values of A and B
Step 5 – Compute Shared Key
• Alice computes the shared key.
• s = (B mod p)a mod p
• s = gb*a mod p
• s = 354*24 mod 17
• s=1
• Bob computes the shared key.
• s = (A mod p)a mod p
• s = ga*b mod p
• s = 324*54 mod 17
• s=1
Alice & Bob have a shared
encryption key, unknown to Eve
• Alice & Bob have created a shared secret
key, s, unknown to Eve
• In our example s=1
• The shared secret key can now be used to
encrypt & decrypt messages by both parties.
• See the Youtube video on this example at:
[Link]
Limitations of Diffie Hellman
Algorithm
• Lack of authentication procedure.
• Algorithm can be used only for symmetric key exchange.
• As there is no authentication involved, it is vulnerable to
man-in-the-middle attack.
• As it is computationally intensive, it is expensive in terms
of resources and CPU performance time.
• Encryption of information cannot be performed with the
help of this algorithm.
• Digital signature cannot be signed using Diffie-Hellman
algorithm.
Applications of Diffie Hellman
Algorithm
• Secure Shell (SSH): SSH uses the Diffie-Hellman algorithm to allow secure
key exchange between client and server and secure data transfer.
• Transport Layer Security (TLS) / Secure Sockets Layer (SSL): These
protocols use the Diffie-Hellman algorithm to safely exchange encryption
keys, preventing data manipulation and eavesdropping.
• Public Key Infrastructure (PKI): To secure communication over the internet,
PKI uses a system of digital certificates, certificate authorities, and public key
encryption.
• Internet Key Exchange (IKE): IKE is a protocol that is used to establish a
secure virtual private network (VPN) connection. IKE uses the Diffie-Hellman
algorithm to create a secure VPN connection and securely exchange
encryption keys.
• Internet Protocol Security (IPSec): The security protocol known as Internet
Protocol Security (IPSec) is used to protect online communication. IPSec uses
the Diffie-Hellman algorithm to exchange encryption keys securely while
preserving the confidentiality and integrity of data transmission.
MITM in Diffie Hellman
2 private keys , 12,9
B’= 5^12 % 23
=18
A’= 5^9%23
Shared key =11 Shared key
= A’^15 % = B’^6 % 23
23 = 4 =4
A a=6, B b=15,
Ka= 2 Kb=2
P=23, g=5, A=8,
B= 19
Prevent MITM in Diffie hellman
Key Exchange