I liked math when I was young. When the challenging questions were things like long division. When my brother and I were memorizing the multiplication tables (not because we wanted, but mum made sure). I liked math back then. But then, math got complicated. We started studying squares, roots, and different types of numbers – like imaginary numbers! That’s when I, like many others, stopped paying attention. I could have tried harder, but I didn’t see how prime numbers were going to help me in everyday life. I preferred the Prime Minister’s number.
It never bothered me until end of 2023 when I studied Cryptography and Network Security. We looked at ways to communicate secretly and securely over any network like the internet. I saw the magic that allowed us to log in to our favorite social media and banking apps! That magic was math! I have to say, I was excited to see math in action as a Christian because it spoke so loudly of an orderly, creative, methodical and infinitely wise God! I thought about how He’d hidden these truths within creation and waited patiently for mankind to develop electronic communication and mathematical research to finally discover what He knew all along. It blew my mind!
Anyway, today, I want to walk through the Diffie-Hellman Key Exchange as an example of how math is used to keep our chats private and our shillings safe.
but first, some quick math
Modular arithmetic (aka modulus)
For modulus, just think of a clock. You start at 12, go to 1, then 2, and all the way to 11 and 12 again. When you want to say 13, it becomes 13\mod 12 = 1. Every time you reach 12, you reset and count again from 1.
Prime numbers
For a prime number, just think of how to break a number down into factors. If you have 2, the only factors of 2 are 1 and 2. But for 4, the options are 1×4 or 2×2 so its factors are 1, 2, and 4. If the number has more than two factors, not prime. Only two factors, prime.
Primitive roots of prime numbers
If a number g is a primitive root of a prime number p, all the answers you get from g^0 all the way to g^{(any\_number)} in the modulus of p will always be between 1 and p-1.
What is all that math for?
Using prime numbers means that a hacker won’t be able to find other factors that she can use to crack our passwords since prime numbers only have 1 and the prime number itself as factors. Using a modulus gives us a circular number space that we can control especially with primitive roots. We need to control our number space since we want two people to generate random numbers and have them fit within our space, and use its rules to combine them. (It’ll make sense when you see the example)
the example
The internet is like one big group chat. Alice and Bob want to text privately on it. Problem is that group chats aren’t private – if Alice sends a message to Bob, Eve can also read that message.
So Alice opens her notes app and stores two numbers; a prime number p and its primitive root g.
At this point, both Bob and Eve have nothing in their notes apps…
She sends p and its primitive root g to Bob on the group chat. Everyone else on the group can see them and take note of them.
So now, Alice, Bob, and Eve all have the same numbers saved in their notes apps. Nothing is secret yet.
Alice selects a secret random number \alpha and calculates fromAliceToBob = g^\alpha\mod p. She saves these to her notes.
Bob also chooses his own secret random number \beta and calculates fromBobToAlice = g^\beta\mod p. He also saves these numbers to his notes.
Alice sends fromAliceToBob to Bob on the group chat, but Eve also sees it. When Bob gets it, he also sends fromBobToAlice to Alice, but Eve also sees it.
Now, with the new information, Alice’s, Bob’s, and Eve’s notes look like this:
Alice uses what Bob sent her and calculates AliceKey = fromBobToAlice^\alpha which is AliceKey = g^{\beta \cdot \alpha}\mod p
Meanwhile, Bob also uses what Alice sent him and calculates BobKey = fromAliceToBob^\beta which is BobKey = g^{\alpha \cdot \beta}\mod p
So, let’s compare AliceKey and BobKey, shall we?
AliceKey = g^{\beta \cdot \alpha}\mod p
BobKey = g^{\alpha \cdot \beta}\mod p
Surprise, surprise, AliceKey = BobKey !! Now, what about Eve? Can she calculate AliceKey or BobKey? No. Why? Because she doesn’t have Alice’s secret nor Bob’s secret (they never sent them to the group chat).
Now, Alice can encrypt the private chats she wanted to send to Bob using AliceKey like this:
Encrypt “Hey Bob! This is an encrypted text!” with key “9” in a Caesar box encoder.
Result: “HTneeh·dyie··sntB·ceoirxbsyt!·p!·at·“
and Bob can decrypt it using BobKey since the keys are the same.
Decrypt “HTneeh·dyie··sntB·ceoirxbsyt!·p!·at·” with key “9” in a Caesar box decoder.
Result: “Hey Bob! This is an encrypted text!“
Bob can respond, too!
Encrypt “Hey Alice! This is an encrypted reply!” with key “9” in a Caesar box encoder.
Result: “H!·pye·at!yTne··h·d·Aie··lsnr·i·ce·cirp·esyl·“
and Alice will recieve Bob’s cipher and decrypt it
Decrypt “H!·pye·at!yTne··h·d·Aie··lsnr·i·ce·cirp·esyl·” in a Caesar box decoder.
Result: “Hey Alice! This is an encrypted reply!“
Meanwhile, Eve will ‘see’ all these messages and understand nothing of them!
So finally, Alice and Bob have managed to find a way to chat privately in a public group chat – all thanks to math!
wow, it’s perfect!
That’s what I thought. But unfortunately, there are ways for Eve to pretend to be Bob to Alice and pretend to be Alice to Bob. That is called the man-in-the-middle attack! Again, some people who didn’t give up in math class came up with a way to prevent this – the RSA cryptosystem! If you’ve read this far and want me to write about how RSA solves the challenges that Diffie–Hellman key exchange didn’t, let me know. For now, let’s give thanks to God for math and remind the students that prime numbers are cooler than the Prime Minister’s number 👍🏾
Leave a Reply