Intro
This is part of our ongoing series about encryption. Part 1 was boring, this is where it gets fun!
History
The most advanced method of encryption during WWII (the enigma machine) was broken by a guy who built a computer (Alan Turing).
In the decades following WWII the US was in a cold war with the USSR. Computers were being built in order to gain intelligence and monitor what the Soviets were doing. NORAD (part of the US and Canada's military complex) created the first networked computer system and they wanted secure communication so that no bad actors could eavesdrop on secret military communication.
Diffie Hellman
In 1976 Whitfield Diffie and Martin Hellman developed a method of key exchange where two parties could share public keys for encryption and decryption but nobody else would be able to see any messages because each party would also have a private keys
The Diffie-Hellman key exchange was the first ever devised asymmetric cipher. This means that a secret message can be sent from one party to another without the need to share the keys.
IMPORTANT NOTE: The basics of this methodology are still used today in many forms of communication, including SSH. Never EVER share your private key with anybody!
How Does It Work Conceptually?
Up until Diffie-Hellman all encryption was done with a symmetric key exchange. This means that the sender and receiver had to share an agreed upon key before they can send messages to one another. But what if the 2 parties have never met? Or what if they're far away?
The solution is a public key exchange. This is called asymmetric key exchange because each party has a different key. But how?
Each party has a private key and a public key. The private key is never shared. Both parties agree (publicly) on a prime modulus and a generator to the modulus. The prime modulus is just a large prime number and the generator is a number that when raised to the power off all numbers up to the prime number p (1, 2, 3, ... , p-1 , p), the solution set will include all numbers up to p (1, 2, 3, ... , p-1 , p). This allows for the same character to be encrypted to different values.
It's confusing- I know.
But when the public keys are exchanged the individuals can calculate their private keys raised to the power of their partner's public key and everything unravels to decrypt itself!
Khan Academy has a great video explaining it with paint.
How Does the Math Work?
The Diffie-Hellman key exchange algorithm is based on the difficulty of the discrete logarithm problem in modular arithmetic. The basic steps of the protocol involve:
Two parties agree on a large prime number p and a base g, where g is a primitive root modulo p.
Each party selects a private key (a secret number), let's say a and b, and computes their respective public keys as and .
They then exchange their public keys.
Each party raises the received public key to the power of their own private key to compute the shared secret: and .
Due to the properties of modular exponentiation, both parties arrive at the same shared secret.
Demonstration
This is a MarkDown version of a Jupyter Notebook that I created for this demonstration. Feel free to clone the repository and play with the key exchange yourself.
Helper Functions
These are not the most performant functions but that's not their intention. They are here so that the user can gain an understanding of how the encryption takes place.
First we need a function that tells us if a number is prime or not. This is because our modulus must be a prime number
# checks if number is prime or not
def is_prime(number):
factors = []
for i in range(2, int(number**0.5)+1):
if (number/i)%1 == 0:
factors.append(i)
if len(factors) > 0:
return False
else:
return True
Given a prime number $p$, the following function returns an array of all numbers that are primitive roots or generators of $p$. A primitive root is a number $a$ such that if you raise $a$ to all of the powers $(1, 2, 3, ... , p)$ the results will contain of the numbers $(1, 2, 3, ... , p)$, though not necessarily in order.
# returns array of generators of a prime number
def calculate_generator(prime):
if is_prime(prime) == False:
return False
generators = []
for i in range(2, prime):
results = []
for j in range(2, prime):
results.append(pow(i, j, prime))
if len(set(results)) == len(results):
generators.append(i)
return generators
Given a private key (usually a random number), the public key is determined by the following arithmetic function.
$$public _ key = generator^{private _ key} (mod\ p)$$
# creates public key
def create_pub_key(generator, private_key, prime):
# pow takes (base, exp, mod=None)
# is equivalent to base**exp % mod
return pow(generator, private_key, prime)
Encoding is not encryption. It simply converts the letter to its computer numerical value. Any computer can make this conversion, so it's not scrambled in any way. This function takes a string as an argument and returns an array of the encoded characters.
# encode a string into an array of each character's numerical value
def encode_string(string):
char_array = []
for char in string:
char_array.append(ord(char))
return char_array
Decoding is the opposite of encoding. This function is the opposite of the previous one.
# decode an array of numerical values to their corresponding character
def decode_string(arr):
decoded_arr = []
for i in arr:
decoded_arr.append(chr(i))
return "".join(decoded_arr)
Given a encoded array, a shared "super key", and a prime, we can encrypt the message. This is not technically part of the Diffie-Hellman process. We use the following mathematical function to encrypt each letter in the array, though others may be used.
$$num + super _ key (mod\ p)$$
# encrypts message
def encrypt_message(super_key, message_array, prime):
encrypted_array = []
for num in message_array:
encrypted_array.append(num + super_key % prime)
return encrypted_array
Decrypting the message is the inverse function:
$$num - super _ key (mod\ p)$$
# decrypts message
def decrypt_message(super_key, encrypted_array, prime):
decrypted_message = []
for num in encrypted_array:
decrypted_message.append(num - super_key % prime)
return decrypted_message
Implementing Diffie-Hellman
Now that we have all of our helper functions we can implement Diffie-Hellman. Obviously, this would be done from two different machines if it was sent over the internet (i.e. SSH).
Let's get 2 volunteers
p1 = input("Person 1's name: ")
p2 = input("Person 2's name: ")
Choose Numbers
We need to do is choose a publicly known prime number, and a generator of that prime. In the video the prime was 17 and the generator was 3.
prime = int(input("choose a shared prime number: "))
while is_prime(prime) == False:
prime = int(input("that's not prime, try again: "))
gen = int(input(f"select a shared generator from the list {calculate_generator(prime)}: "))
Choose a private key then autogenerate the public key
$$public _ key = g^{private _ key} (mod\ p)$$
p1private_key = int(input(f"{p1} select a private key: "))
p1public_key = create_pub_key(gen, p1private_key, prime)
print(f"{p1}'s public key: {p1public_key}")
p2private_key = int(input(f"{p2} select a private key: "))
p2public_key = create_pub_key(gen, p2private_key, prime)
print(f"{p2}'s public key: {p2public_key}")
Review so far:
Numbers that are known to everyone
print(f"prime number {prime}")
print(f"generator of {prime}: {gen}")
print(f"{p1}'s public key {p1public_key}")
print(f"{p2}'s public key {p2public_key}")
Numbers only known to their owners
print(f"{p1}'s private key {p1private_key}")
print(f"{p2}'s private key {p2private_key}")
The Super Key
The super key is the super-secret key that both parties calculate on their own but with different numbers. They should be equal otherwise this won't work. In the video the super key was 10
super_key = pow(p2public_key, p1private_key, prime)
super_key2 = pow(p1public_key, p2private_key, prime)
if super_key != super_key2:
print("Oops, something went wrong...")
print(f"super key: {super_key}")
print(super_key)
Sending a message
Step 1: encode the message into the computer numeric values
message = input(f"{p1}, what message do you want to send to {p2}? ")
message_array = encode_string(message)
print(message_array)
Step 2: encrypt message
encrypted = encrypt_message(super_key, message_array, prime)
print(encrypted)
Step 3: decrypt message
decrypted = decrypt_message(super_key2, encrypted, prime)
print(decode_string(decrypted))
Next Step
We learn how RSA encryption works!!!
Top comments (0)