00:00:01.280
Hey there! How's it going? My name is Sunny Beatteay, and today I'll be talking to you about how prime numbers keep the internet secure.
00:00:08.639
To give you a little background about myself, I am a software engineer at DigitalOcean, as you might have noticed.
00:00:16.240
I work on the managed storage products team, meaning that anything that has to do with managed storage products, I have my hand in it.
00:00:23.359
Suffice it to say, I work both with and on the internet every day.
00:00:27.920
While I've been using the internet for most of my life, as many of us have, there are still many parts of the internet that I don’t fully understand.
00:00:36.399
To me, the internet can seem like a chaotic place, filled with lots of moving parts and confusion.
00:00:44.799
There are days when I feel like I have no idea what I'm doing, and I'm sure that's a pretty common feeling.
00:00:47.280
However, there are other days where I learn a new bit of information, and things just seem to click together, making the internet seem a little less chaotic.
00:00:55.280
I actually had one of those 'click moments' about a year ago when I learned more about internet security and how it works in the context of the internet, particularly how prime numbers factor into all of this.
00:01:03.600
This presentation was essentially born from that click moment I had. As we go through this presentation, I hope that many of you will experience similar click moments.
00:01:14.880
By the end, I hope that many of you will not only have a better understanding of how internet security works but also how the internet as a whole operates, and hopefully, it will seem a little less chaotic to you.
00:01:37.200
Now, a question you may be asking yourself right now is, what is so special about prime numbers?
00:01:41.600
You know, the guy keeps mentioning prime numbers; what’s so special about them? Well, the first thing is that prime numbers are unique. For example, if I were to give you the number 24 and ask you how many different combinations of numbers can you multiply together to get 24, there would be quite a few answers.
00:01:56.400
You could answer with 8 times 3, 6 times 4, 12 times 2, or even 24 times 1. There are multiple answers. But if I give you the number 17 and ask the same question, there’s only one answer: 17 times 1.
00:02:16.800
The reason for that is that 17 is a prime number. While prime numbers are unique, they are also relatively easy to generate, meaning they do not require much CPU power.
00:02:38.640
For example, I could ask my computer to generate for me a large prime number on the order of thousands of bits long, and there’s a known way for my computer to do that relatively quickly.
00:02:53.040
Conversely, there’s a simple way for a computer to check whether a large number is prime, even for very, very large prime numbers.
00:03:04.800
These three properties—uniqueness, ease of generation, and ease of verification—make prime numbers quite special and, more importantly, very useful for something called encryption.
00:03:12.560
For anyone who is not aware, encryption is a process of turning data or a message into an unreadable format called a cipher.
00:03:19.600
The reverse process of encryption is called decryption, where you take the cipher and turn it back into the original message or original data.
00:03:29.200
Encryption is going to be the main focus of today’s talk because encryption is the foundation of internet security.
00:03:41.560
It allows us to perform many tasks such as online banking, messaging our friends, and even simple things like creating a username and password.
00:03:56.880
Today’s presentation will be a deep dive into encryption. I'm going to outline some objectives of what we'll be covering today.
00:04:15.680
As I mentioned, we'll cover different types of encryption, such as symmetric versus asymmetric encryption.
00:04:39.680
We will also discuss how keys are used in encryption, specifically public and private keys, and finally, we’ll explore how prime numbers factor into all of this.
00:05:00.000
By the end of this presentation, you will actually know how to implement encryption yourself using basic Ruby and some basic math.
00:05:13.440
So I’m pretty excited for that, and I hope you are too!
00:05:21.440
Before I dive too deeply into that topic, I want to step back and talk about how encryption works at a high level.
00:05:37.440
If you’re familiar with hashing, you might have heard of something called a one-way function. Encryption is a special type of one-way function known as a trapdoor function.
00:05:51.360
If you are not familiar with one-way functions, that’s okay! I will define them.
00:06:05.040
A one-way function is very simple to execute in one direction but extremely difficult to reverse in the opposite direction.
00:06:19.760
In the context of encryption, let’s say we had a message and an encryption key. It's relatively easy to use that encryption key to lock the message into a cipher.
00:06:49.600
Given only the cipher and the encryption key, it's very challenging to reverse that process and turn the cipher back into the original message. That is essentially what makes encryption a one-way function.
00:07:04.640
However, as I mentioned before, it is a special type of function called a trapdoor function.
00:07:18.640
A trapdoor function is a one-way function, but if you have some special information known as the trapdoor, it becomes relatively easy to reverse.
00:07:30.720
In this case, the special information is the decryption key. If you have the cipher and the decryption key, it is straightforward to reverse the encryption process and turn the cipher back into the original message.
00:07:47.680
This is how a trapdoor function works, and that is essentially how encryption operates at a high level.
00:07:57.760
As I previously mentioned, there are different types of encryption, and the type depends on how it uses these keys.
00:08:09.760
We'll start with symmetric encryption. Symmetric encryption gets its name because it uses the same key for both encryption and decryption.
00:08:27.680
Symmetric encryption tends to be very fast, which is why people often prefer using it. However, it can be fragile.
00:08:47.440
Since the same key is used for both encryption and decryption, if this single point of failure is compromised, the encryption process breaks down.
00:09:01.440
Therefore, since you have to use the same key for both operations, it becomes challenging to pass encrypted messages between two parties unless you trust each other.
00:09:11.680
For this reason, symmetric encryption is typically used for something called 'data at rest', meaning data that is stored somewhere, such as databases or files.
00:09:29.600
However, the issue arises when data is in transit. When data is moving over the internet, it is relatively insecure.
00:09:48.480
With symmetric encryption, if two different parties want to communicate securely, they would need to agree on a shared secret key ahead of time.
00:09:57.920
The most secure way to do that is for both parties to meet in person; however, it is challenging to accomplish in the context of the internet.
00:10:14.960
That is where asymmetric encryption comes in. Asymmetric encryption gets its name because it uses two different keys for encoding and decoding information.
00:10:39.680
It utilizes a public key for encryption and a private key for decryption.
00:10:50.080
You might have noticed the critical difference between asymmetric and symmetric encryption: the public key can be shared with anyone.
00:11:04.240
With symmetric encryption, we always have to keep the key secret; however, with asymmetric encryption, the public key can be freely shared, even with untrusted parties.
00:11:25.920
Now, let’s use an example with colors to illustrate how we can use these public and private keys. Imagine someone wants to send me a private message represented by the color yellow.
00:11:59.760
To enable secure messaging, I would give them my public key, represented by the color blue. They can then transform their yellow message into a green cipher using my blue public key.
00:12:17.920
They would then send that cipher across the internet, and once it arrives with me, I would use my private key to decrypt the message back into yellow.
00:12:38.080
The reason this method works is that even if a hacker were to intercept the green cipher, as long as they do not have the private key, they cannot decrypt it back into the original message.
00:12:54.960
Only I can do that because I possess the private key.
00:13:07.200
This illustrates how two different keys can work in this way. The fascinating part is that the public and private keys are considered inverse operations.
00:13:19.760
Hence, when we use them together, they effectively cancel each other out, allowing us to return to the original message.
00:13:32.000
Asymmetric encryption is vital for securely transmitting data. However, there are still challenges associated with asymmetric encryption.
00:13:43.440
In practice, both symmetric and asymmetric encryption algorithms are used to establish secure internet connections.
00:13:58.360
This leads us to wonder: how secure is encryption? Since we rely on it to protect our data, we should feel confident that it is secure.
00:14:12.960
The best way to answer the question about encryption's security is to dive into it and examine its implementation.
00:14:31.760
Therefore, we'll be selecting an encryption algorithm and implementing it ourselves to explore how it works and see how secure it truly is.
00:14:42.960
The element I've selected for this presentation is the RSA encryption algorithm. The reason for this choice is that it is among the most widely used asymmetric encryption algorithms today.
00:15:02.640
It's utilized for SSH keys, GPG for secure emails, and is most commonly recognized for its role in the TLS and HTTPS protocols.
00:15:20.760
If you're familiar with the TLS handshake or the TLS cipher suites, you've likely encountered RSA in action.
00:15:39.200
Interestingly, RSA is quite old in the context of the internet, created in 1977 by three cryptographers: Rivest, Shamir, and Adelman.
00:16:00.080
Fifty years is a long time in the internet age; many technologies become obsolete within five years. Yet, RSA has persisted because of its broad application.
00:16:21.680
RSA's longevity showcases its security; the question then arises: why is RSA so secure?
00:16:39.760
The brief answer is that RSA relies on prime numbers, but this isn’t quite sufficient for our purpose.
00:16:57.040
The longer explanation—but certainly key—is that understanding RSA will involve some math.
00:17:10.720
While many of us might not enjoy math, it is crucial in encryption.
00:17:21.760
For the sake of simplicity in this presentation, we will skip over much of the theoretical math related to RSA encryption.
00:17:38.240
What you need to know is that RSA consists of two main parts: the generation of the public and private keys, and the encryption and decryption processes.
00:17:54.760
To begin, we need to generate our public and private RSA keys. Up until now, we’ve discussed keys in an abstract sense, but in reality, keys are simply numbers.
00:18:16.320
In the context of RSA, the public key is composed of two numbers, which are denoted as e and n, while the private key is a single number d.
00:18:41.440
The public key contains the numbers e and n, while the private key consists of the number d.
00:18:50.240
To generate our public and private keys, we follow a simple five-step process. I know this may seem complicated at first, but don’t worry! We’ll break it down step by step.
00:19:07.760
The first step is to choose two prime numbers, denoted as p and q. RSA typically uses very large prime numbers, often in the thousands of bits.
00:19:19.360
However, to simplify this presentation, we’ll select smaller numbers—specifically, we’ll choose p as 13 and q as 17.
00:19:35.040
The next step is to compute n, which is defined as p multiplied by q.
00:19:47.040
So, in this case, n will be 13 times 17, which equals 221.
00:19:55.760
As you can see, n is the first half of our public key. Our public key will be composed of the numbers e and n.
00:20:05.920
So far, we have created one half of the public key by computing n. The third step is to calculate the totient (represented by the symbol φ).
00:20:18.640
The totient of n is defined as (p - 1) times (q - 1), and for our numbers, this is (13 - 1) times (17 - 1), which equals 192.
00:20:34.000
Now, in the fourth step, we need to select the value e. However, e cannot be any number; it must meet strict criteria.
00:20:48.560
Specifically, e must be between 1 and the totient of n (which is 192), and it must be relatively prime to n (which is 221).
00:21:07.040
For simplicity, the easiest choice would be a small prime number that meets both criteria. In this case, we will select e as 7.
00:21:29.200
Now that we have e, we can record our public key as (7, 221). The last step is to create our private key, denoted as d.
00:21:41.120
To find d, we need an equation. The equation is d * e mod totient of n = 1. This helps us find the inverse.
00:21:56.960
In our case, we have already determined e and the totient of n, so we know that d * 7 mod 192 = 1.
00:22:13.760
We can solve for d using the Extended Euclidean Algorithm, but for simplicity in our case, we can brute force our way to find the private key.
00:22:40.480
We'll start with a value of 1 and loop through all possible values of d until we find the correct one where d multiplied by e gives us a remainder of 1.
00:23:11.760
Following this process, we find that d equals 55 is our private key. Now that we have our public and private keys (7 and 221 for the public key, and 55 for the private key), we can move on to the exciting part: encryption and decryption.
00:23:51.760
Let’s consider how encryption might work. We know that encryption must involve a mathematical equation that is easy to compute but not easily reversible.
00:24:27.760
Thus, we can avoid using straightforward operations such as addition or multiplication, as these can be easily reversed. Instead, we rely on the modular operator, which does not offer a single answer back.
00:25:00.560
For instance, if I gave you the equation x mod 10 = 5, it could equate to 5, 15, 25, or so on; you could not determine a single value for x!
00:25:11.040
Thus, this explains why the modular operator is so significantly important. The encryption equation manifests itself as: m^e mod n = c, where m represents the message.
00:25:32.320
In this case, m must be represented as a number, and we can further explore ways to convert characters into numbers for encryption.
00:25:44.320
The forthcoming decryption process follows a similarly straightforward approach. The cipher raised to the power of d and mod n recovers the message.
00:26:00.160
This duality indicates that the encryption and decryption equations can indeed prove that they work.
00:26:22.080
To validate this, I will execute a test on my server, passing in my public key to encrypt a secret message.
00:26:38.560
Upon receiving the cipher in return, I will employ my private key for the decryption process.
00:26:58.960
Through this method, I would aim to uncover messages successfully, verifying our understanding of this encryption model.
00:27:19.680
I will forward a cURL request to my server endpoint with the public key of 721, expecting a cipher back.
00:27:39.360
If executed successfully, I should receive a result, say 185, and then run a similar decryption process to see the original message.
00:27:58.240
If the decryption works seamlessly and accurately reveals that the original message is, say, 42—the answer to the universe—then the encryption and decryption model has proved effective!
00:28:20.240
While I have now illustrated how both operations cooperate, we should address whether RSA can be broken.
00:28:39.760
Consider we are attackers capable of intercepting a cipher and a public key. To decrypt the intercepted cipher, we would require the private key, entailing our capacity to reverse engineer the prime factors.
00:29:01.760
However, the substantial challenge is that prime factorization, albeit simple to multiply two prime numbers to create n, is exceptionally difficult to reverse.
00:29:21.040
To exemplify, analyzing extensive numbers and reconstructing the original components of an encrypted number (like n) typically encounters significant computational hurdles.
00:29:43.360
For instance, when n is approximately a thousand bits long, multiplication is a swift operation, but factoring could take unthinkable amounts of time.
00:30:03.680
Hence, prime factorization serves as a one-way function when sufficiently large numbers are considered.
00:30:27.440
This framework succinctly depicts how prime numbers bolster internet security.
00:30:47.440
Prime number complexities enforce security since prime factorization remains exceedingly hard to achieve.
00:31:00.720
It’s important to note, however, that RSA is not flawless. Quantum computing could feasibly undermine RSA, while frequent developer errors also can compromise security.
00:31:16.080
Nonetheless, RSA is an integral component of contemporary internet security.
00:31:31.680
If you are curious about what lies ahead in cryptography, one of the emerging methodologies gaining interest is elliptic curve cryptography.
00:31:57.680
This topic will be reserved for another time.
00:32:06.160
If you're eager to learn more about RSA and cryptography, I have links available for you. Please take a moment to check them out.
00:32:25.840
Overall, I hope you had some meaningful insights during this talk and believe that, by now, the internet should make a little more sense to you. Thank you very much!
