Introduction
Diffie-hellman key exchange is a crypto that is widely used. You can see it everywhere:
- SSL/TLS: web
- IPsec: IPpackets
- Bluetooth
- 5G
- IOT
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: bpublic 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
Differences
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:
https://www.quora.com/What-is-the-difference-between-Diffie-Hellman-and-ElGamal
How it works
Asymmetric crypto to generate a shared key
symmetric crypto to encrypt a message
Scenario
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 ag
such thatg<p
- pick a random private key
b
Bob’s public key set will be like <p,g,B>
Now Bob’s waiting for someone who is sending a encrypted message to him.
Encryption(Alice)
Alice picks a random private key a
, then calculate the shared key K
by using Bob’s public key B
Generate public key A
Then Alice uses the shared key K
to encrypt a plaintext P to get a ciphertext C
This actually used the symmetric crypto
Then Alice sends <A, C>(public key, ciphertext) to Bob
Decryption(Bob)
According to Alice’s public key A
, Bob can calculate the shared key K
Then Bob decrypts the message by using the shared key K
Calculation Trick
Square & Multiply Algorithm
From the most left number(ignore it)
binary 0: square
binary 1: square then times a
RSA crypto
RSA key generation
choose two primes: p = 5 and q = 11
1 | 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)
RSA encryption
1 | s = m^(e)mod n |
RSA decryption
1 | m = s^(d)mod n |
Reference
Monash Uni FIT2093