7 - DH Key Exchange Flashcards
Based on what problem?
The difficulty of the discrete logarithm problem
DH Paint analogy
- Common paint
- Alice and Bob pick another colour and mix
——- Paint separation is expensive - Transport mixes to each other
- Alice and Bob mix received paints with colour they choose (2 to 1)
- The final paint is the same
Paint analogy, why is it resilient to hackers
Hacker only has the common paint, so they cannot mix either received paint to get the correct one
DH Mathematical Method
p is a public prime and g is a primitive root
- Alice and Bob pick secret integers a, b (one each)
- They compute g^a mod p or g^b mod p and send
- On receive, they compute y^a mod p or x^b mod p
Public Prime 23
Primitive root 7
Alice chooses 9
Bob chooses 4
Complete DH key echange
Alice: 7^9 mod 23 = 15 … send to Bob
Bob: 7^4 mod 23 = 9 … send to Alice
Alice: 9 ^ 9 mod 23 = 2
Bob: 15 ^ 4 mod 23 = 2
The number is the same
What does an attacker know listening in to DH exchange?
p, g, x, y
public prime
primitivie root
x from alice
y from bob
What equation does DH reduce down to
g^(ba) mod p
Integers used in DH should be small or large?
Each prime should be at least ? bits
p-1 must have a ???
Large
prime p (at least 2048bits)
p-1 must have a large prime factor
Safe Prime p
a Sophie Germain prime.
If a prime p is still prime after 2p+1 then p is a safe prime
DH terminology in public/private
a Alice’s private key
x Alice’s public key
b Bob’s private key
y Bob’s public key
Static vs Ephemeral
Static - Same keys for long time/many sessions
Ephemeral - changed for each session
Forward Secrecy
Ephemeral DH - next session invalidates compromised previous information, compared to static DH
Does RSA have forward secrecy?
No, they are kept for a long time.
So a compromise once is a consistent compromise.
Post quantum crypto - RSA and DH
Both algos will be vulnerable to sufficiently powerful quantum computers.