Encryption: Romeo Can Now Text Juliet

Keeping data safe is a huge issue.

What would happen if the leader of two countries’ messages got leaked? 😳 More importantly, how would you feel if your messages with everyone you have ever communicated with online got leaked? 😱

Whatever data you have on your phone, laptop, or any piece of technology can be hacked, and eventually (without security progression) it will be hacked. 💻🔒

We rely on so much data, that “90% of the world’s data was generated in the last two years alone.” (Duarte, 2023).

The need to secure our data has grown immensely in the last couple of years, as hackers are evolving at an ever-rapidly increasing speed.

Humans now rely on safe communication more than we have ever needed to, especially private communication. What would happen if the leader of two countries’ messages got leaked? More importantly, how would you feel if your messages with everyone you have ever communicated with online got leaked? 😱📨

The question that we need to answer is, “How do we keep all our information (data) safe?”

The answer is encryption. 🔐🔒

What is encryption?

In a loose sense, encryption is a way of mixing up messages so that no one else can read them. 🤐🔀

To understand it, let’s take two characters from the most iconic love story of all time: 💑❤️

Romeo and Juliet

Romeo obsesses over Juliet and wants to let her know that he has a huge crush on her. 😍

To avoid embarrassment, Romeo doesn’t want anyone to know and just wants Juliet to be able to read the message. 🤫

Romeo loves math, so he quantizes his problems. He thinks he can use a simple 1–1 encoding system to encrypt the message. This would follow the pattern of a = 1, b = 2, and you guessed it! c = 3! 🧮

For simplicity’s sake, a space is 0.

Romeo wants to tell Juliet, “I have a crush on you.” ❤️ With our encoding scheme, it would look something like this: 9 0 81225 0 1 0 31821198 0 1514 0 251521.

Great…!
Or not really… The problem now is that Juliet has some meaningless numbers in her mailbox that she has no idea how to read! 😕

So how will Romeo tell Juliet how to encrypt the message? Will he send her a paper with his 1–1 encoding scheme? If he does, that seems pointless because if the mailman gets the encoding scheme and the message, Romeo’s secret is revealed! 💌🙈

This is the shortcoming of the 1–1 encryption scheme and many simple encryption schemes. The flaw is that there is no way to send the common key without having an advanced encryption scheme. 🔑🔒

This rudimentary encryption can never work in any real-world application; however, this failure opens us to more complex systems that we can use. 💡

Romeo now reads my article and stumbles across public key information, which relies on the principle that there are two (private) keys: one used to encrypt and one used to decrypt. 📚🔐

Public key encryption is spectacularly difficult to understand, but here is something to help. 🤔🔓🔐

A Shakespearean encrypted mailbox

Juliet has a mailbox outside her house, and Romeo knows about the mailbox. 📬 For the old-timey romance, Romeo writes an exquisite letter and wants to send it privately. 💌

Juliet leaves a key (a public key) outside her mailbox 🔐 (so that everyone can deposit a letter, and no one can look inside the mailbox). 🙅‍♂️📭

Occasionally, Juliet checks her mailbox using her private key🔑, which no one else has. She keeps this key safe and private. 🤫

This key is called a private key that only Juliet has, and now Juliet can see Romeo’s letter. 💌💕

It turns out Juliet is also madly in love, and they live happily ever after. 🥰🏰🌟

Let’s get more formal…

RSA (Rivest-Shamir-Adleman) encryption relies on asymmetric keys. 🔐 These keys are deeply related, as one is responsible for encrypting, and one is responsible for decrypting. 📜🔓

It is important to note that if you have one key, it is very hard to derive the second key. (I’ll talk about this in my next blog.)

One of these keys is public, and one of them is private. The public key can be shared with anyone, and it doesn’t matter who has it. 🙌🗝️

The private key, on the other hand, is very private and should not be shared. 🤫🔒

This system is great for sending encrypted messages, but there is also, inadvertently, another application, one of many. 💌🔐

Let’s say that Juliet uses her private key to encrypt a message. Since everyone has her public key, anyone should be able to read the information, but the fact that it was decrypted using her public key means that the message originated from Juliet. 🙋‍♀️💬

Juliet can even encrypt data using her private key and then again with Romeo’s public key! This would mean that only Romeo can see the message, but he knows that Juliet sent it! This allows encrypted data, but you also know who sent the message! This is called signing. ✍💌

By now, you must be tired of Shakespeare, so let’s pick our next victim. 😄📖🔍

J.K. Rowling’s Harry Potter

Hermione, being the smart wizard that she is, comes up with a way to kill Voldemort (the heinous villain). She wants to send her wizard friend (and main protagonist) Harry a game plan but needs to make sure evil Voldemort doesn’t have access to the information.

Let’s say that Hermione’s message was “Cast Expelliarmus.”

Hermione is an RSA encryption nerd, so she encrypts it using her private key and then once again with Harry’s public key. She gives the letter to Dumbledore, who then passes it on (safely) to Harry.

Harry sees random text and knows that Hermione is the sender. Harry uses his private key to decrypt the message, then uses Hermione’s public key, and reads “Cast Expelliarmus.”

Let’s quantify this a bit.

Sure, here’s your message with emojis added:

Let’s say our original message is 𝑥. 📜

Hermione’s private key divides a number by 2, and her public key doubles a number. 🔒✌️

Harry’s private key divides a number by 3, and the public key triples a number. 🔑🔒✨

Encrypt: 🔐

First, Hermione uses her private key (divide x by 2) => 𝑥/2

Second, Hermione uses Harry’s public key (triples 𝑥/2) => (3𝑥)/2

Final encrypted message = (3𝑥)/2

Decrypt: 🔓

First Harry uses his private key (divides (3𝑥)/2 by 3) => 𝑥/2

Second Harry uses Hermione’s public key (doubles 𝑥/2) => 𝑥

In this case, let’s say a hacker intercepts the message right after encryption. They would see (3𝑥)/2. 👀

They know Hermione’s public key, so they can get to (3𝑥)/2 * 2 = 3𝑥

Now the hacker has no clue what they should do next. Remember that the hacker doesn’t know Harry’s private key, and they don’t know if they should double, triple, or do anything to the message.❓❓❓

You know the original message was 𝑥, but the hacker doesn’t know if the original message was 2𝑥, 3𝑥, 974𝑥, or something else. 🕵️‍♂️❌🤷‍♂️

This is a very simplified version of how RSA encryption works. 🔐🔢

Math, math, more math…

📚 This level of knowledge is where most people give up and claim that math is too complicated to go further — not you, though! 📖

You’ll read through the rest of the math and maybe even struggle a little, but I’ve dissected the methods greatly and linked a couple of 📚🌐 external resources if you’re confused.

If, however, you aren’t a math person at all, then I wouldn’t read on any further.

It gets a little scary and intimidating; however, I still believe in you! 🤯🙌

There are four main steps of RSA encryption.

1. Key generation
2. Key distribution
3. Encryption
4. Decryption

Public keys are often represented by two integers, and for simplicity (avoid the Greek), let’s use n and e. Your private key will be represented by d.

Note that key distribution is not related to the rest of the encryption process, so I won’t go into it. However, here is a great article that encapsulates it: https://www.hindawi.com/journals/mpe/2015/732609/.

Generating keys

Choose two random prime numbers, p and q. These prime numbers are usually around 100 digits long, and just for reference, some of the most secure servers (like crazy national-level military servers) use “22,338,618 digits” (Rowland, 2016).

To be honest, this number may seem impressive (and it is crazy impressive), but it’s not that hard to come up with a prime number. Prime numbers are fairly easy to come up with, and primality tests easily verify whether a number is prime or not.

Anyway, for blatant security purposes, the numbers should be chosen randomly, but since you are not a supercomputer, let’s choose small numbers to use.

I chose to use p = 5 and q = 7.

n = pq = 35

Now we take the totient of n. We will use Euler’s totient for simplicity, which returns the number of positive integers not exceeding n that have no common divisors with n (other than the common divisor 1).

For example, φ(6) = 2 because 5 is the only number that doesn’t have any factors with 6, including 1.

In our case, φ(35) = 24.

Trivially, φ(n) = (p — 1)(q — 1).

This is a verification of Euler’s totient.

This formula makes a lot of sense because we defined n as the product of p and q, so any other number than p, q, and the multiples of p and q smaller than pq would be coprime.

In our case, we are finding φ(pq) = φ(7*5) = φ(35) = (p — 1)(q — 1) = (5 — 1)(7 — 1) = 4 * 6 = 24.

We can verify this with this list of 24 primes:

1, 2, 3, 4, 6, 8, 9, 11, 12, 13, 16, 17, 18, 19, 22, 23, 24, 26, 27, 29, 31, 32, 33, 34

Now that you understand totients, we need to choose an integer (e) that abides by these restrictions:

1 < e < φ (n)

gcd(e, φ(n)) = 1

The second line eloquently means that e and the totient n are coprime. Relating it to RSA encryption, e is a public key exponent. In our example, e = 5. The GCD of 5 and 24 is 1 because there are no common factors (and 5 is the smallest possible positive integer).

Next, we take a variable d, which needs to have a very specific value:

de ≡ 1 mod φ(n)

Hold up!

Before we go any further, I want to congratulate you for really getting into this! 🎉👏 You are getting into the thick of things, so I want to congratulate you! 🙌😄

Understand totients.

I also want you to be completely clear about how the totient function works.

If you are even just a little unclear, watch this quick 2-minute video: https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/euler-s-totient-function-phi-function

Scary formulas

Let me explain this demonic-looking formula:

de ≡ 1 mod φ(n)

If m is our message, then m^φ(n) = 1 (mod n).

This means that if de = 1(mod φ(n)), then (due to some modulo properties):

m^de = (m^e)^d = m mod (n)

This means that since we already know e and n as the public keys, if we also know d, which is the private key, we can get our original message m from the encrypted message c = m^e (mod n) if we just raise it to the d-th power!

We need to apply this rule: de ≡ 1 mod φ(n)

However, it deals with something called modular arithmetic.

Mod is a concept that appears heavily in number theory. The three-lined sign means congruent.

Many people explain congruence as ‘clock time’. Here’s something that I find to be an ‘intuitive’ explanation of mod congruence.

“A familiar use of modular arithmetic is in the 12-hour clock, in which the day is divided into two 12-hour periods. If the time is 7:00 now, then 8 hours later it will be 3:00. Simple addition would result in 7 + 8 = 15, but 15:00 reads as 3:00 on the clock face because clocks ``wrap around” every 12 hours, and the hour number starts over at zero when it reaches 12. We say that 15 is congruent to 3 modulo 12, written 15 ≡ 3 (mod 12) so that 7 + 8 ≡ 3 (mod 12).” https://en.wikipedia.org/wiki/Modular_arithmetic

However, if you are anything like me and prefer solid proofs, I think the most mathematically sound way to define a mod would be by using this sample case:

a ≡ b mod n

By definition of congruent mods, we can derive this equation:

a = k(n) + b, where k is an integer and the value doesn’t matter.

Using this knowledge, we can conclude:

5 ≡ 1 mod 4 <=> 5 = k(4) + 1 => in this case, k = 1, but this doesn’t matter.

7 ≡ 3 mod 4 <=> 7 = k(4) + 3 => in this case, k = 1.

38 ≡ 14 mod 12 <=> 38 = k(12) + 14 => in this case, k = 2.

Understand mods.

Once again, if you are vaguely confused about how convergent mod works, watch this very helpful video: https://www.youtube.com/watch?v=6dZLq77gSGU&ab_channel=blackpenredpen

de ≡ 1 mod φ(n)

Putting everything together

As derived earlier, e = 5.

Hence, we have to find a number d so that when we multiply d by 3, we get a number that is 1 more than a multiple of 4. This is because we defined n = pq and analyzed this equation using the totient and congruent mod.

There is a very sophisticated algorithm, called the extended Euclidean algorithm, that can find the value for d trivially, but I won’t go into that. However, if you are interested, here is an extremely simplified version I found: https://www.educative.io/answers/what-is-extended-euclidean-algorithm

Regardless, d = 5, because 5*5 is 25, which is 1 more than 24. Let me illustrate this analytically:

de ≡ 1 mod φ(n), where d = 5, n = 35

5d ≡ 1 mod φ(35)

5d ≡ 1 mod 24

Using a = k(n)+b, where a = 5d, n = 24, and b = 1,

5d = k (24) +1; let’s assume k = 1. This will not work for all values of k, but we use something called the Extended Euclidean Algorithm to figure this out.

5d = 24+1

d = 25/5 = 5

d = 5

A much-needed recap

To recap, we have now found both the private and public keys.

d is the private key, so we have to keep that secret. The public key is the pair (n, e), which we need for encryption and decryption.

p and q also need to be kept secret because they are used for φ(n), which is the backbone of our equation.

Once d is calculated, the values of p and q will be forgotten, as they are not needed for encryption or decryption.

However, e is crucial for decryption.

Something important to realize is that creating a public key from two private keys is trivial, but doing the opposite is hard. I’ll talk about this in my next blog post.

Finding the private keys from the public keys is like having a short blast of music and determining the pitches, the instruments involved, and the decibel level. (It’s pretty hard.)

Now let’s go onto our next step.

Encryption

Let’s go back to our elementary encryption system, where a = 1, b = 2, and so on. This step is crucial because it allows us to manipulate our numbers by using our newly learned mathematical operators.

Let’s say Harry Potter is trying to send a message to Dumbledore. He has his text encoded in a sequence, so the next step is to encrypt! He needs to use Dumbledore’s magical key (if we were using the same example above: e). Now, let’s raise the numbers to the power of e.

Now, he performs the mod n function. Harry repeats this process many, many times to ensure encryption is secure. Because of the repetitive and straightforward logical sequence of these operations, they run crazily smoothly!

Now Dumbledore uses his private key d to decrypt, which will give us the original message.

A huge disclaimer

In the worked example, we used Euler’s totient, but actual RSA encryption uses Carmichael’s totient. Carmichael’s totient is slightly more complicated to understand, but it returns smaller (yet more complex) numbers. Euler’s totient is still mathematically sound; however, it is easier to crack, but even aside from that, our algorithm is fairly easy to crack.

Our basic algorithm has a couple of issues. Firstly, using a small exponent e weakens the encryption, but this issue arises from p and q being inherently small. Our message is raised to the power of e, making it easily breakable by taking the e-th root. However, if e exceeds a certain threshold, decryption without the private key becomes practically impossible. Note that e is usually about 75 digits. Here’s an example of what e would look like in RSA encryption:

128930584610239487562910438756129834501827350168945871092347928103750726890

A bigger flaw, however, is that we are vulnerable to chosen-ciphertext attacks. Chosen-ciphertext attacks are essentially graphing a pattern between encrypted and original messages that would easily break our encryption if we used the same numbers every time (this is a massive oversimplification).

This is why RSA encryption uses something called random padding, which means that the encryption process will be just a little bit different every time.

Congratulations! You’ve almost made it to the end!!!

Before making the next statement, I want you to promise me that you won’t freak out.

Your credit card information (in 5 years) will be the most accessible thing in the world.

This is because of something called Shor’s algorithm that makes factoring prime numbers trivial, hence being able to rip apart the RSA encryption system. However, the quantum technology required for Shor’s algorithm is nowhere where it needs to be to factor in the massive 70-digit prime numbers. Shor’s algorithm needs a perfect quantum (2,000,000+ entangled qubit) computer, which is nowhere close to where we are right now. Currently, we’re sitting at around 433 qubits, which is massively impressive.

If you’re interested, comment or clap on this post! I’d be delighted to write about how Shor’s algorithm will destroy RSA.

Key takeaways

• Encryption is all about scrambling a message in a way that only the recipient and spender can read.
• Cipher encryption (1–1 encryption) systems fail since the key also needs to be transmitted.
• Public-key encryption has two keys that are determined on the spot.
• RSA encryption is an algorithm that uses tents and congruent mods.
• The private key can only be found one way: by factoring a 75-digit prime number.
• QUANTUM COMPUTERS WILL DESTROY RSA ENCRYPTION.

Adieu, and see you next time! I hope that you liked this article, so please feel free to clap it up!