Introduction to Diffie-Hellman
Alice and Bob - two friends from IRC (Internet Relay Chat) just learned about this powerful cipher that no computer can ever crack. As they're concerned about privacy of their conversations they want to implement it for everyday use. But they encountered one problem - they need to come up with secret key and as they are living 13516 km from each other they just can't talk about it in real life. They need to come up with a key through their messages. That's where Diffie-Hellman key exchange comes in.
Diffie-Hellman is a key exchange protocol developed by Ralph Merkle and named after Whitfield Diffie and Martin Hellman - two cryptographers. The purpose of Diffie-Hellman is to allow anybody to exchange a secret over a public channel without having anything shared beforehand, and without the possibility of someone eavesdropping. Let's explore basics behind this concept.
- Alice comes up with two prime numbers g and p and sends them to Bob.
- Bob then picks a secret number a. Then he calculates ga mod p and sends that result (which we're going to call "A") back to Alice.
- Then Alice does the same thing gb mod p but with her own secret number (b) and sends the result (which we're going to call "B") to Bob.
- Now, Bob takes the number Alice sent him and does the Ba mod p.
- Finally Alice does the same operation with the result Bob sent her Ab mod p.
What the trick does is that both final calculations that Alice and Bob do, will end up with same results for both of them. If you don't believe me, let's perform this operations with some example numbers.
- Alice: g = 5 and p = 7
- Bob: a = 11 and operaton A: ga mod p --> 511 mod 7 = 3
- Alice: b = 13 and operation B: gb mod p = 513 mod 7 = 5
- Bob: Ba mod p = 511 mod 7 = 3
- Alice: Ab mod p = 313 mod 7 = 3
If you still don't understand check out this paint analogy ;)
That's it! Now both Alice and Bob have the same private key. But you can ask, is it really that secure? Here's when we add the third person - Eve - our malicous spy that wants to get encryption key.
Eve was pretty lucky to intercept key exchange between Alice and Bob. Firstly she gets two prime numbers - p and g, then she is also able to get two other numbers A and B. What she can do with it? Nothing, she has their public keys but she still needs their private keys which are safely in Alice's and Bob's houses, and she can't calculate the secret key.
For better security, numbers used for there operations are very big prime numbers, which simply makes this process impossible to reverse for the eavesdropper.
The beauty of Diffie-Hellman is that after each person does this independently, they will both end up with the exact key which they can later use for any encryption algorithm they want to use for their communication, without sharing it over the wire. Beautiful, right?
Modern version of Diffie-Hellman key exchange is used in the PGP (Pretty Good Privacy), with much more complex keys. Let's see how to generate PGP key for yourself with GNU/Linux.
Let's start by opening terminal and installing two tools: GPA and GNUPG2, essential for process of creating PGP keys. You can do this by typing this command in any Debian based distribution.
After that we are ready to generate our first key.
Now let's walk through the process. First thing you are going to be asked is what type of key you want to use.
We will go with RSA and RSA, option (1). RSA is another form of encryption that is also public-key based similar to the concept of Diffie-Hellman’s key exchange.
gpg (GnuPG) 1.4.20; Copyright (C) 2015 Free Software Foundation, Inc. This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law.
After that it will ask you about the length of the key. Obviously, we will choose 4096 bits as nowadays most people use it.
Next step is to choose how long the key should be vaild. If you want to create key that does not expire enter 0, otherwire go with other options.
Then enter your credentials such as your name, mail address and comment and your passphrase to protect your key.
Last step before key is done is to generate entrophy essential for generating random key. If you somehow have problems with collecting it, you can make use of rng-tools before generating keys.
And we've generated our key!
But what to do next?
Let's obtain our secret key using GPA tool.
Now you should be able to view all your keys.
Press the one you have made, click Keys and then Export Keys and then enter the directory where you want your key to be saved. To view it navigate to that directory and view it with any text editor like Gedit.
That's how your key should look like. But what if you want to commicate with somebody. How can you use this tool to encrypt your conversations?
First agree on a shared key, it can be your public key or their public key. Let's pretend it's theirs public key.
Import their public key by pressing Keys and then Import Keys
Select Windows and then Clipboard. This window will show up:
Then write the message you want to hide, and press Encrypt the buffer text, which is the blue envelop and choose their public key. You can also sign it with your key for additional safety.
And we're ready, that's how the message should look like. Now you're ready to send sensitive information without possibility that someone may read this.
I hope you enjoyed this topic, and it gave you some insight in how Diffie-Hellman works, how to create PGP keys, and how to encrypt messages using PGP. Always send sensitive information over PGP as it gives you certainty that no one will ever read this message.
Keep learning and stay safe!