Cryptography 101 (not crypto)
Not crypto, just cryptography. The mathematical field that allows us to make bank transactions, send emails, and yes... buy Bitcoin
Hello, Hypers!
Today I want to talk about an incredible field in Math: cryptography. It studies how we can send and receive messages securely. That is, how to be sure nobody but the intended receptor of the message understands it. I like this branch of Math a lot because of two things:
It involves Number Theory and Group Theory, two of the most beautiful theories in Math
It has changed the digital world. Without it, digital business and communications wouldn’t exist. Can you imagine a world without socials, e-commerces, and messaging apps?
This is an introductory post to understand Public Key cryptography. The specific part of cryptography that allows for wide and scalable security and identity in the digital world. I’ll be trying to explain everything without using any advanced Mathematical concepts.
Symmetric cryptography
Before understanding Public Key Cryptography let’s review symmetric cryptography. Imagine Alice wants to send a message to Bob. She doesn’t want anybody except for Bob can read the message. On the other hand, Bob would like to make sure that Alice was the person that sent the message.
Without cryptography, this is impossible!
The problem is that every channel Alice and Bob use for communication is insecure. For example, any message sent over a network can be intercepted and read by a bad actor. From now on, we’ll call this bad actor Evil.
Evil can intercept the message and read it no matter the channel Alice and Bob used (we are assuming Alice and Bob are at different geographical points and cannot whisper to each other’s ear). Then, how do they solve this problem?
Alice and Bob could agree on a way to encode the message so that they are the only ones that understand it. This way, Evil can intercept the message but won’t be able to read it. Also, Bob will know Alice is the sender since they are the only two persons in the world that can encode the message in that way.
For example, Alice and Bob could agree on a key phrase. This key phrase can be used for an encryption algorithm in such a way that only the people that know the key phrase can decode the message. It is important to note that the encryption algorithm could be public, but as long as the key stays private, nobody is able to decode the message.
Let’s see Symmetric Cryptography in action. We’ll use a very simple encryption algorithm that is not secure at all but it will illustrate how Symmetric Cryptography works.
Suppose the key phrase Alice and Bob agreed on is “foo“. Now, if Alice wants to send the message “hello“ to Bob, she will do the following.
Write the message and, under each letter of the message, write the corresponding letter from the key. Repeat the key as many times as needed.
Example:
hello
foofo
Substitute each letter for its corresponding number in the alphabet. The letter “a“ will have the number 0, the letter “b“ will have the number 1, etc.
Example:
7 4 11 11 14
5 14 14 5 14
Sum each column. If the result is greater than or equal to 26, subtract 26 from it.
Example:
7 4 11 11 14
+ 5 14 14 5 14
______________
12 18 25 16 2
Convert each number in the result to its corresponding letter
Example:
12 18 25 16 2
m s z q c
The resulting message (“mszqc“) doesn’t mean anything. But Bob can decode the message by using the key phrase (“foo“) and doing the inverse process. This way, he can read the original message (“hello“).
A little problem with Symmetric Cryptography
Alice and Bob are very happy sending messages to each other. They feel they are protected from Evil thanks to Symmetric Cryptography. But then Alice asks something to herself. How did Bob and I agree on a key phrase? Did I send it to him using a secure channel?
That’s one big problem with Symmetric Cryptography. It requires the two parties to agree on a key and such an agreement cannot be encrypted. We don’t have a key yet!
Also, imagine that Charles, an old friend of Alice and Bob, wants to chat with both of them. Now Charles needs to agree on a key with Alice and another key with Bob.
What would happen in a system with millions of people interacting with each other (like on the Internet)? Can you imagine creating a new e-mail account and having to agree on a key with each people around the world?
That’s when Public Key Cryptography comes to the rescue!
Public key cryptography
Now we’ll have a public generator algorithm G
. Anyone can execute G.
This algorithm gives us a pair of keys P
and Q
. We’ll say that P is the public key, and Q is the private key.
From the private key (Q), we can obtain the public key (P), but it is impossible to obtain the private key from the public one. That’s why everybody will keep the private key as secure as possible. In our example, Alice and Bob have a pair of keys each. Their public keys are, well… publicly known. But their private keys stay private no matter what. Alice doesn’t know the private key of Bob and Bob doesn't know the private key of Alice.
Note that Evil knows the public key of both.
A pair of keys P and Q has still one more property. There is a public algorithm H such that when we encode a message with P, the only way to decode it is by using Q and vice-versa! If we encode with Q, the only way to decode is by using P.
With all these components and properties, Alice can send a message to Bob. She will encode the message using the public key of Bob and then, only Bob will be able to read it since the only way to decode it is by using the private key of Bob. Problem solved!
Note that if Charles wanted to join now, he will just need to get his own pair of keys from G.
But there is still a problem! Bob can’t be sure Alice is the sender of the message. Evil can also encode messages with Bob’s public key and sent that message to Bob. Evil could impersonate Alice!
Well, not so fast Evil. Alice can make a second encoding. After encrypting the original message with Bob’s public key, she can encrypt it again with her own private key. This way, Bob can use the public key of Alice to make the first decoding. This first decoding shows that the message was encrypted with Alice’s private key so she must be the sender. Then, Bob decodes the message a second time by using his private key.
If, after that process, Bob can read the original message, he can be sure that Alice was the sender.
Conclusions
Yeah! We finally did it. It was a little bit tricky but I hope you liked it. In this post, we talked about cryptography. This field studies, among other things, how to send messages securely through an insecure channel.
We learned how to use Symmetric Cryptography to communicate with another person. This type of cryptography requires an initial agreement between every pair of participants. This poses an important scalability problem. Also, there is no way to protect these initial agreements.
With Public Key Cryptography (or Asymmetric Cryptography), we can overcome the previous problems. Now every participant has one public key and one private key. The most important trick here is that when we encode something with one of the keys, it can only be decoded with the other key of the pair. This allows each participant to send messages that can only be read by the desired receptor. But also, makes possible a digital signature.
This digital signature (encoding a message with our private key) serves as an identification throughout the internet. It protects us from impersonation and is the fundamental pillar of digital ownership. As our lives become more digital each day, cryptography will surely have an even bigger impact on the world.
And that’s it for this week. If you liked this post, consider sharing it with your peers. Don’t forget to subscribe and stay tuned for another week of Under the Hype!
See you!