Diffie-hellman key exchange is a crypto that is widely used. You can see it everywhere:
- SSL/TLS: web
- IPsec: IPpackets
In this blog, we are looking into DHKE, to see how it works. Moreover, EL Gamal PKE is a crypto that is based on DHKE, we will learn this as well.
How DHKE works
Let’s say we have Alice and Bob will use their public keys to encrypt a message and private keys to decrypt a message.
Alice’s public key: A
Alice’s private key: a
Bob’s public key: B
Bob’s private key: b
public parameters: p and g, p is a prime number, g<p
According to the formulas above, we can see that Alice and Bob will communicate the public keys and the shared keys they generate will be the same. Since there are some mathematical relationships between a private key and a public key, Alice or Bob can use their private keys and others’ public keys to get the shared key.
Then this shared key could be used in any symmetric cipher(like AES).
There’s a discrete log problem that prevents the shared key from being deduced by an attacker.
EL Gamal PKE
For PKE, both Alice and Bob will need to publish their public keys, while for EL-Gamal PKE, we only need one of them(receiver) to publish the public key.
For DHKE, it only explains how a shared key is generated, EL-Gamal PKE shows how a message could be encrypted and decrypted using DHKE.
A very strong and solid explanation here:
How it works
Asymmetric crypto to generate a shared key
symmetric crypto to encrypt a message
Bob published his key to his website, and was happy with receiving messages from all.
Alice is sending a message to Bob.
Generate Public Key B(Bob)
- pick a random Prime(
p), and a
- pick a random private key
Bob’s public key set will be like
Now Bob’s waiting for someone who is sending a encrypted message to him.
Alice picks a random private key
a, then calculate the shared key
K by using Bob’s public key
Generate public key
Then Alice uses the shared key
K to encrypt a plaintext P to get a ciphertext
This actually used the symmetric crypto
Then Alice sends <A, C>(public key, ciphertext) to Bob
According to Alice’s public key
A, Bob can calculate the shared key
Then Bob decrypts the message by using the shared key
Square & Multiply Algorithm
From the most left number(ignore it)
binary 0: square
binary 1: square then times
RSA key generation
choose two primes:
p = 5 and q = 11
n = p*q = 5 * 11 = 55
Find two numbers e and e according to
(e*d) mod ϕ(n) = 1, thus,
e = 3, d = 27
Public key: (e,n)=(3, 55)
Private key: (d,n)=(27, 55)
s = m^(e)mod n
m = s^(d)mod n
Monash Uni FIT2093