How Prime Numbers Keep the Internet Secure

RubyConf 2020

by Sun-Li Beatteay

In the video, "How Prime Numbers Keep the Internet Secure," Sun-Li Beatteay presents an insightful exploration of the crucial role prime numbers play in internet security, particularly through encryption. He begins by sharing his background as a software engineer at DigitalOcean and his journey of understanding the complexities of the internet. Beatteay aims to simplify complex encryption concepts, making them accessible to all viewers.

Key Points Discussed:
- Introduction to Prime Numbers:
- Prime numbers are unique and easy to generate, making them exceptionally useful for encryption processes.
- Their unique property of having exactly two distinct positive divisors contributes to security in encrypted communications.

Concept of Encryption:
- Encryption transforms readable data into ciphered text, enabling secure data transmission across the internet. The reverse process is decryption.
- Beatteay differentiates between symmetric and asymmetric encryption, outlining their respective strengths and weaknesses.
Types of Encryption:
- Symmetric Encryption: Utilizes the same key for both encryption and decryption, leading to security risks if the key is compromised; suited for data at rest.
- Asymmetric Encryption: Involves a public key for encryption and a private key for decryption, allowing secure communication without prior key exchange.
- An engaging analogy with colors illustrates how the encryption process works using keys.
The RSA Algorithm:
- Beatteay dives deep into RSA, a widely-used asymmetric encryption algorithm. He outlines the process of generating public and private keys using two prime numbers, demonstrating each step simplistically.
- Includes a simplified demonstration of how the RSA algorithm encrypts and decrypts messages, highlighting the mathematical operations involved, such as modular exponentiation.
Security Considerations:
- The presentation wraps up by addressing the security of encryption. Although RSA is currently secure due to the challenges of prime factorization, potential threats like quantum computing are noted. Beatteay emphasizes the ongoing need for secure methods in data transmission and suggests exploring elliptic curve cryptography as a future topic.

Conclusions and Takeaways:
- By utilizing prime numbers, the RSA algorithm leverages their complexity to enhance internet security.
- Understanding the foundations of encryption can demystify how private communication works over the internet and reassures users about data security.
Beatteay concludes by inviting viewers to further explore encryption concepts, leaving them with a clearer perspective on internet security as a whole.

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!