Mathematical Foundations For Cryptography: Part III

In part II of this series, we looked at how two entities could share a secret in a public space using a key exchange. In this final part, we will look at authentication.

PART III: AUTHENTICATION AND RSA

Asymmetric Encryption

Faced with two cloaked figures who both are both claiming to be Beta, Alpha must find a way to determine which one is actually Beta. In order to do this, we are going to need to introduce some form of higher “authority”. Before going into what that means, let’s outline the general flow. We are going to be using asymmetric keys. This means that the key used to encrypt our text will be different than the key used to decrypt it. Contrast this with symmetric encryption, such as Diffie-Hellman, where we used the same key to encrypt and decrypt.

Beta is going to have two keys. One will be public, and known to everyone else, and one will be private, known only to him. If a message is encrypted with the public key, then it can only be decrypted with the private key. Conversely, If a message is encrypted with the private key, then it can only be decrypted with the public key.

The reason we take this approach is for authentication. If Beta’s public key is known to everyone, then she can encrypt using her private key. The private key is only known to her, so no one else can encrypt with the same private key as her. So suppose Beta and Omega are both trying to convince Alpha that they are the true Beta. Alpha now has a way of knowing who is the real Beta. Alpha asks both Beta and Omega to encrypt the word “HELLO” using their own private keys. They do so, and they present two different pieces of ciphertext on their whiteboards. Alpha will then take Beta’s public key, and decrypt both messages. One of the messages will be gibberish — that’s from Omega. The other will be decrypted back to the initial text “HELLO”. The one who wrote that ciphertext is Beta.

The Higher Authority

So now you might be wondering — what about this public key? Isn’t that information that needs to be shared in advance? And if so, aren’t we back at square one, since we need a way for Beta to share that, but we have no way of knowing if it’s Beta sharing the public key, or if it’s Omega planting a trap. This is where we must bring in a higher authority. We need a way to definitively ascribe a public key to Beta and another to Omega, and another to Alpha, and so on. We want to minimize the need for this authority, but we can’t do proper authentication without it. We need to adjust our microcosm slightly, so let’s rewind…

Suppose a group of mathematicians, tired of a world where math is under-appreciated, blah blah blah… There are no secrets. Since they are cloaked, the only way one could tell who is writing is if they sign their name.

Ok, now for the new info: Before they are let loose into this new world, a higher authority, perhaps the trustworthy custodian of the temple, asks each mathematician, in private, to remove their hood, verify their identity, and etch their public key into a stone tablet. The authority ensures that each mathematician has a unique public key. Note however, that the authority still does not get access to their private key — that remains private to each individual. We just need a way to ascribe a public key to each person.

So with this information, Alpha can look at this stone tablet containing 24 different public keys, find the one that belongs to Beta, and decrypt both ciphertexts using that public key, and learn which cloaked figure is the real Beta. Once that is complete, Alpha and Beta can continue along by generating a shared key. We have both authentication and encryption. Now let’s get into the mathematical details of how this works.

Phi function

Our big question now is — how do we make this happen? How do we reliably generate a pair of keys (one public, one private) such that one is able to decrypt the other, and vice versa? The strategy we are going to use is called RSA, which stands for Rivest-Shamir-Adleman, the names of the three scientists who described the algorithm in 1977.

In order to understand RSA, we are going to need to learn a few more important mathematical concepts. The first is the phi (φ) function. The φ value of a given number x is the amount of numbers between 1 and x that do not share a factor with x. Let’s look at some examples:

Phi of 8, aka φ(8): Let’s take all the numbers between 1 and 8, including 1, but not 8:

1 2 3 4 5 6 7

Now let’s look at each number to see if it shares factors with 8.

• 1: No factors in common with 8 (or any number, for that matter)
• 2: This shares a factor of 2 with 8: 2 = 2 * 1, 8 = 2 * 4, so 2 is common
• 3: Nothing in common
• 4: Shares a factor of both 2 and 4 with 8
• 5: Nothing in common
• 6: Shares a factor of 2: 6 = 2 * 3, 8 = 2 * 4. So 2 is common
• 7: Nothing in common

So after removing the numbers that share a factor with 8, we are left with: 1 3 5 7

We have 4 numbers in total, so we say the value for phi of 8, or φ(8) = 4

Let’s do another example, φ(15). Again, we start by writing all the numbers from 1–14.

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Now let’s look at each of these to see if they have a factor in common with 15:

• 1: As always, nothing in common
• 2: Nothing in common
• 3: 3 is a factor of 15, so cross it out
• 4: Nothing in common
• 5: 5 is a factor of 15, so cross it out
• 6: 6 = 3 * 2, and 15 = 3 * 5, so 3 is common. Cross it out
• 7: Nothing in common
• 8: Nothing in common
• 9: 9 = 3 * 3, 15 = 3 * 5, so 3 is common. Cross it out
• 10: 10 = 5 * 2, and 15 = 5 * 3, so 5 is common. Cross it out
• 11: Nothing in common
• 12: 12 = 3 * 4, and 15 = 3 * 5, so 3 is common. Cross it out
• 13: Nothing in common
• 14: Nothing in common

Now we are left with: 1 2 4 7 8 11 13 14

We have 8 numbers remaining, so φ(15) = 8

One more example: φ(11). If you try out numbers from 1 to 10, you will see that none of them share any factors with 11. This is because 11 is a prime number! So by definition, it has no factors in common with any other number, so we don’t cross out any numbers, and φ(11) is equal to 10. In fact, with any prime number P, φ(P) = P — 1. The numbers 7, 13, 43, and 991 are all prime numbers, so their phi values are 6, 12, 42, and 990 respectively. If you know that your number is prime, then the phi value is trivial to calculate.

One other important fact about the phi function. Suppose we asked for φ(88). This is a bit bigger than 8 and 15, so it might take a while to calculate. But we can actually use an important property of the phi function to make it easier. First, we note that 88 = 8 * 11. Now to find φ(88), we can take the phi of those two smaller numbers, and multiply their results together:

φ(88) = φ(8 * 11) = φ(8) * φ(11) = 4 * 10 = 40

This is much easier than going through all the numbers from 1–87.

Ok, so we have a grasp on the phi function. Now we can briefly go back to our temple and see what Beta might be doing to generate his public and private keys. Beta is going to start by choosing two prime numbers, say 11 and 13 (we’ll see why he chooses primes later on). He is going to multiply them together to get 11 * 13 = 143. Let’s call this number N. N = 143. Next he is going to calculate φ(N). Based on what we just learned, this shouldn’t be too hard, since both 11 and 13 are primes:

φ(143) = φ(11 * 13) = φ(11) * φ(13) = (11–1) * (13–1) = 10 * 12 = 120

Back to the modulus

Ok, let’s keep N = 143 and φ(N) = 120 in the back of our head for now, and turn back to the modulus and powers. Beta wants to encrypt the text “HELLO”. Here is the encryption scheme he will use. He is going to start with the letter H, and convert that to the number 8, like before. Now he comes up with a formula to encrypt that number to a new number, for which we will use the placeholder ‘c’. That formula is as follows:

8ᵉ mod 143 = c

He is going to pick some value for e, say 3, and then apply the formula: 8³ mod 143. 8³ = 512, so we have 512 mod 143. The answer is 83: 8³ mod 143 = 83. He obviously can’t turn this back into a letter, unless he applies a modulus of 26. We are not going to worry about converting back into letters for this encryption. Beta is just going to encrypt into a new collection of numbers. Assuming Alpha has the public key, she can then decrypt those numbers back into the original numbers, which will correspond to “HELLO”. So Beta ends up with 83 as the first number in his ciphertext.

Now what he needs is a way to get back to that original value of 8, starting with 83. This is the decryption process. He will use a similar formula: 83ᵈ mod 143 = 8. So he needs to find a value d that will do this for him. The number 7 works. So this could be an example of a public-private key pair. Beta can keep 3 as his private key, and share 7 as the public key. He will encrypt his message with the formula x³ mod 143 = c, and Alpha can then decrypt using c⁷ mod 143 = x. Here is what would happen with the word “HELLO”:

• H = 8: 8³ mod 143 = 83
• E = 5: 5³ mod 143 = 125
• L = 12: 12³ mod 143 = 12
• L = 12: 12³ mod 143 = 12
• O = 15: 15³ mod 143 = 86

So the ciphertext becomes “83 125 12 12 86”. Notice that 12 maps to 12 in this case. This could potentially be a weakness with the encryption, but we will be looking at a more complex scenario later. Now let’s see what happens when Alpha tries to decrypt:

• 83⁷ mod 143 = 8 = H
• 125⁷ mod 143 = 5 = E
• 12⁷ mod 143 = 12 = L
• 12⁷ mod 143 = 12 = L
• 86⁷ mod 143 = 15 = O

So we’ve successfully found a pair of numbers that could work as a public-private key pair. Let’s go into more detail about what Beta is looking for when making his public and private key pair. He wants to find values for e and d so that:

xᵉ mod N = c AND cᵈ mod N = x

We can actually put these two formulas together. If xᵉ mod N = c, then we can replace c in the second equation with xᵉ and we get xᵉᵈ mod N = x, as follows:

xᵉᵈ mod N = x. So x to the power of the product of e*d will give x itself back when applying mod N. So we are looking for e and d.

To understand the mechanics of how these can be found, we need to look at one more important mathematical concept, Euler’s Theorem:

Euler’s Theorem

First off — out of the box, Medium doesn’t support the ability to put special characters like φ into superscript to represent a power. So I’m going to switch to a slightly clunkier notation, using the ^ symbol to represent a power. 5^3 is the same as 5³. y^(3x) is the same as y³ˣ. And x^(φ(N)) means x to the power of φ(N).

Euler’s Theorem can be stated as follows: x^(φ(N)) = 1 mod N. This is true as long as the values for x and N do not share any common factors. Start with some numbers x and N. Find the phi value for N, and raise x to that power, and you will end up with 1 mod N. Let’s look at some examples:

Suppose x = 3, and N = 5: 3^(φ(5)) mod 5 = 3⁴ mod 5 = 81 mod 5 = 1. This works.

Suppose x = 7, and N = 18: 7^(φ(18)) mod 18 = 7⁶ mod 18 = 1. This also works

Suppose x = 3, and N = 6: 3^(φ(6)) mod 6 = 3² mod 6 = 9 mod 6 = 3. This does not work, because 3 and 6 share a common factor of 3.

Let’s plug in our value of N = 143 into this function now: x^(φ(143)) = 1 mod 143, or x¹²⁰ = 1 mod 143.

Now using mathematical rules, we can alter Euler’s theorem slightly:

Let’s set both sides to the power of k: x¹²⁰ᵏ = 1ᵏ mod 143.

Recall that if we put 1 to the power of ANY value, then the result is still 1, so we can actually just drop the k from the right side of the equation, and the sides are still equal:

x¹²⁰ᵏ = 1 mod 143

Now let’s multiply both sides by x: x * x¹²⁰ᵏ= x * 1 mod 143

If we’re multiplying x¹²⁰ᵏ by another x, that is equivalent to x¹²⁰ᵏ + 1, so let’s put that on the left side. The right side simply becomes x * 1 = x:

x¹²⁰ᵏ⁺¹ = x mod 143

Now this is actually starting to look a little bit like what Beta was aiming for: xᵉᵈ = x mod 143. Looking at the powers on both of these, we just need e*d = 120k + 1.

Beta can start by choosing a value for e. Let’s use a value of 23. We now have:

23d = 120k + 1

Using a bit of algebra, we can work out some possible values for d and k. We get a value of d = 47, and k = 9. The value of d is the one we are interested in. The process to find these values is called the Extended Euclidean algorithm, but we won’t be covering it here.

23 * 47 = (120 * 9) + 1 = 1081

So we have values for e, d, and k where e*d = 120k + 1. e = 23, and d = 47. These are our two keys. Let’s say e is the private key, which will be used by Beta to encrypt, and d is the public key. If we try this on the text “HELLO”, we would actually map to the same values as we had with the 3 and the 7.

Cracking the code

So Beta has a private and a public key, and they can be used for encrypting and decrypting each other. He generates these before initially entering the temple and shares the public key with the custodian, who also verifies that he is in fact, Beta. After that, Beta’s hood goes up, and is no longer distinguishable from the others.

Once again, let’s look at things from Omega’s perspective. On the whiteboard, Alpha writes:

Alpha: I want to talk to Beta

At this point, Omega and Beta approach the whiteboard, both claiming to be Beta. Alpha now writes

Alpha: Say HELLO using your private key

Both Beta and Omega use the private keys they have memorized to encrypt the word HELLO.

Beta writes the following:

Beta: 83 125 12 12 86 … Use Mod 143

Omega, also posing as Beta, writes (these numbers are arbitrary — the point is that they are different than the real Beta’s):

Beta: 67 89 45 45 99 … Use Mod 4661

Alpha takes both texts and uses Beta’s public key of 47 to decrypt both messages. Omega’s ciphertext decrypts to gibberish and Beta’s decrypts to “HELLO”, and the real Beta has been identified.

Now what if Omega keeps track of what Beta wrote, so that for a future interaction, she can try to crack his private key. Omega knows that the original message is “HELLO”, so the first number is generated from 8 using Beta’s private key is 83: 8ᵉ mod 143 = 143. So Omega knows this, and Omega also knows that the public key is 47. Omega just needs to know what e is. So there are two possibilities for attacking.

First of all, she can use trial and error. She can cycle through all the numbers from 1–143 and try to learn what value gives 8ᵉ mod 143 = 83. 143 is not that huge a number, so this may not take too long. As with the shared secret, the way around this is to pick a large number for N, so that Omega decides it will take too long to even try to crack.

The other way to attack is a little more subtle. Omega knows that they used the phi function to generate these numbers, and she knows that they used 143 in the modulus. So all she needs to do is take the φ(143), which is 120, and then work backwards from 120k + 1 = 47e, and solve for e. This appears to be even easier to crack! Once again, this is true for smaller numbers, but will become a very different story as the numbers get bigger.

Prime Factorization

The reason that this will work lies in the phi function. It was very important that we pick our value of N to be made up of two prime numbers. To calculate φ(143), we just had to break 143 up into its two primes, 11 and 13. This seems simple, right? Yes, but only for small numbers. If we were to use a higher value of N, say 26797, then it’s harder to figure out the prime factors. There are tricks that can be used to make the process easier, but ultimately the prime factorization relies on trial and error — you must test a bunch of different prime numbers to see if they are a factor of 26797. By hand, this would be very tedious. After much trial and error, you would eventually find that the answer is 127 * 211. Back in the real world, if we want to authenticate over a computer network, we would need even bigger prime numbers, since a computer could crack 26797 in under a second. Our N (which is composed of two primes) needs to be so big that it would take way too long for even a powerful computer to factor a number into primes. And this inability to easily factor primes is the underlying mechanism behind the effectiveness of the RSA algorithm.

Back to our microcosm. When generating their public-private key pairs, each mathematician will select their own two large prime numbers, which will be multiplied to get N, and will then be used to generate their two keys. The public key is shared on a board for all to see, and the private keys are kept private.

Let’s go through the process once more, supposing Beta were to use 127 and 211 as his prime numbers:

• Pick two primes for N: N = 127 * 211 = 26797
• Calculate the phi: φ(26797) = φ(127) * φ(211) = 126 * 210 = 26460
• Apply Euler’s Theorem: x^(φ(26797)k + 1) mod 26797= x mod 26797
• So we need to find e*d = 26460k + 1
• Choose e to be 823, for example
• Now we need values for d and k where 823d= 26460k + 1
• The value 1181 works for d (k = 42). This is done using the Extended Euclidean Algorithm
• So the private key is e = 823, and the public key is d = 1181

Now when Alpha makes her request on the whiteboard, asking Beta to encrypt “HELLO” with this private key, he does the following:

• H = 8: 8⁹⁴¹ mod 26797 = 16133
• E = 5: 5⁹⁴¹ mod 26797= 23711
• L = 12: 12⁹⁴¹ mod 26797= 16920
• L = 12: 12⁹⁴¹ mod 26797= 16920
• O = 15: 15⁹⁴¹ mod 26797= 23196

Then on the whiteboard he writes:

16133 23711 16920 16920 23196. Use mod 26797

Then Alpha uses Beta’s public key of 1181 to decrypt:

• 16133¹¹⁸¹ mod 26797 = 8 = H
• 23711¹¹⁸¹ mod 26797 = 5 = E
• 16920¹¹⁸¹ mod 26797 = 12 = L
• 16920¹¹⁸¹ mod 26797 = 12 = L
• 23196¹¹⁸¹ mod 26797 = 15 = O

Again, consider this from Omega’s point of view. Supposing she wants to discover Beta’s private key of 941. She knows she needs to find the value for x in the equation x¹¹⁸¹ mod 26797 = 8. She’ll either need to step through all the numbers up to 26797 until she finds the one that results in 8. This will take a veeeery long time. The other option is if she knows the phi value of 26797. She knows it is composed of two primes, but she doesn’t know which ones. She will need to do more trial and error with different primes until she figures it out. Again, this will take too long for her to do, so Alpha and Beta can be sure that they have both authentication and encryption.

CONCLUSION

Now we’ve seen the entire process. Let’s do a recap of all the steps involved, this time in the right order. Underneath each step is the “roughly equivalent” step in modern web technology.

The mathematicians decide to live in a temple in the Himalayas.

• We connect to the world wide web through a browser, such as Chrome or Firefox. We want to go to Wikipedia.

Each mathematician will choose two large prime numbers, and use the RSA algorithm to generate a key-pair.

• Wikipedia generates a key-pair using the RSA algorithm.

The custodian of the temple will verify the identity of each person and etch their public keys onto a stone tablet for all to see. The private keys are kept private.

• Wikipedia shares it’s public key with a higher authority, called a “Certificate Authority”, who verifies that they are indeed Wikipedia. The public key is shared publicly across browsers.

Each mathematician dons a robe, concealing their identity. They take their vow of silence and agree to only communicate on the whiteboard.

• We browse the web, communicating with a bunch of different websites.

Alpha makes a request on the whiteboard to speak with Beta.

• We want to make a donation with our credit card to Wikipedia.

This message is seen by all, including Omega. Omega decides she wants to try to intercept the message, so she poses as Beta by approaching Alpha at the whiteboard, alongside the real Beta.

• A hacker on the network sees this communication, and they try to insert themselves in the middle of our communication by posing as Wikipedia. They’ve also gone through the process of generating a key-pair).

Alpha cannot tell them apart at this point, so she asks both of them to send some sort of greeting. Both Beta and Omega encrypt the message “HELLO” using their private keys, and show them publicly, for Alpha to see.

• Wikipedia sends a message encrypted using their private key. The impostor tries the same thing using their private key.

Alpha takes these two messages and attempts to decrypt both of them using Beta’s public key.

• The browser is going to look at the publicly available public key for Wikipedia, and use it to decrypt all messages from the site that is claiming to be Wikipedia.

Omega’s message decrypts to gibberish, and Beta’s message decrypts to “HELLO”. Alpha identifies Beta.

• The public key for Wikipedia fails to decrypt the bogus message from the impostor and correctly decrypts the message from the real Wikipedia. Our browser stops communicating with the fraud.

Alpha publicly shares some information about how she will communicate with Beta: “Diffie Hellman, mod ##). They generate some numbers, share them, and then together they generate a shared secret.

• Our browser negotiates with Wikipedia on the details of how encryption will proceed.

Alpha and Beta encrypt their messages using the shared secret, so Omega cannot listen in.

• We send our credit card info to Wikipedia securely. A security icon near the URL (e.g. a padlock) indicates that the communication is authenticated and encrypted.

Important details were omitted for clarity and brevity, such as the extended Euclidean Algorithm, a proof of Euler’s Theorem, and the more technical details of web encryption, but I hope that this article has convinced you that it is possible for two parties to communicate securely over a public network using fundamental mathematics.

Thank you for reading!

USEFUL RESOURCES

• Computerphile: https://www.youtube.com/channel/UC9-y-6csu5WGm29I7JiwpnA
• Free Crypto 101 book by Laurens Van Houtven: https://www.crypto101.io/
• Khan Academy Cryptography course: https://www.khanacademy.org/computing/computer-science/cryptography
• Cybersecurity Udemy course: https://www.udemy.com/course/the-complete-internet-security-privacy-course-volume-1