How Prime Numbers Keep the Internet Secure

Whether you know it or not, you use prime numbers every day. Do you see that lock symbol in the address bar of your web browser? The one that looks like this:

That lock means youre using prime numbers at this very moment. Thats because the internet uses prime numbers. In fact, prime numbers are so ingrained into the fabric of our daily lives that the world would be a drastically different place without them. Wed still be doing all our banking in person and buying everything in cash. And forget about texting, because wed still all be pen pals.

So what is it about prime numbers that make them so special?

Firstly, theyre unique. There arent any combination of numbers that can be multiplied together to create a prime number.

Secondly, every number can be broken into its prime components. For example, 10 can be broken down into:

10 = 2 * 5

Lastly, while the average human might not be able to look at this number and immediately detect if its prime

9307398526401816703683197763617206082269079617576835286211259044095385462270542532346398139788788003092515521098292832872130802035097419307557532476688659

its relatively simple for computers. You mightve written your own primality checker in the past, similar to this

// shout out to Reddit for the correctionfunction isPrime(a) {    const n = BigInt(a);    const zero = BigInt(0);    if (n <= BigInt(3)) {        return n > BigInt(1);    } else if (n % BigInt(2) === zero || n % BigInt(3) === zero) {        return false;    }    let i = BigInt(5);    while ((i*i) <= n) {        if (n % i === zero || n % (i + BigInt(2)) === zero) {            return false;        }        i += BigInt(6);    }    return true}

and know that many conventional methods for checking prime numbers is slow. But there are more advanced methods, such as the Miller-Rabin primality test, that make it very fast.

Its for all of these reasons that prime numbers are the perfect tools for encryption!

Encryption

For those who dont know, encryption is the act of turning information into an unreadable format called a cipher. Decryption is the opposite process of turning a cipher back into the original information.

In other words, encryption allows us to keep information private and out of the hands of people who might use it for malicious purposes. Thats why it has become a cornerstone of the modern internet.

Without encryption, I wouldnt be able to do most of the things I do online, such as buy groceries, pay off debts, or message my friendsat least not securely. Encryption prevents hackers from stealing my banking information and spying on my private conversations.

Its not just the internet that uses encryption but many modern devices, such as computers, smartphones, or even smart fridges. They all use encryption. Suffice it to say, encryption is important and everywhere.

But how does encryption work?

Encryption algorithms use keys to encrypt and decrypt data. How those keys are used depends on the type of encryption, of which there are two: symmetric and asymmetric. Both of which have different use cases.

Symmetric encryption

Symmetric encryption gets its name because it uses the same key for both encryption and decryption. Since it uses a single key for both encryption and decryption, symmetric encryption is very fastbut fragile. The key must always be kept private and only shared between trusted parties.

Because of this, one of the main uses for symmetric encryption is securing data at rest. This means encrypting devices like computers, databases, or IoT devices. If you remember the drama that occurred between Apple and the FBIthat was a battle over iPhone encryption.

While symmetric encryption works well, it has an inherent flaw. In order for multiple parties to have encoded communication via symmetric encryption, they must all agree on a key ahead of time. And in the context of the internet, where youre communicating with hundreds of servers a day half-way across the world, thats not possible.

Thats where asymmetric encryption comes in.

Asymmetric encryption

Asymmetric encryption uses two keys, one for encryption and one for decryption. This works because the keys are complements of one another. When theyre used together, they cancel each other outsimilar to how complement colors cancel one another out into white.

Correction on the above image: Cipher should be orange

The key used for encryption is known as the public key. As you might guess, its safe to share this key with anyone.

The decryption key, on the other hand, is called the private key because it must be kept private. Only the holder of the private key can decrypt ciphers that were encrypted with the public key. Even if a malicious user were to intercept a ciphertext, theyd just see gibberish.

This makes asymmetric encryption an ideal tool for sharing sensitive data. Not only that, but since a private key should only be owned by a single entity, it works well for authentication as well. Thats exactly how its used in the TLS handshake.

The trapdoor

One of the reasons that asymmetric encryption is as important as it is is because it works as a trapdoor functionv.

This means its very simple to execute in one direction but very difficult to reverseunless you have special information, otherwise known as the trapdoor or secret.

In the context of asymmetric encryption, its very simple to encrypt data but very difficult to decrypt it using only the public key. It becomes simple again with the private key.

But not all asymmetric-encryption algorithms are built the same. How laborious it is to reverse the trapdoor function determines an algorithms security. To see just how secure asymmetric encryption can be, let's explore one of the most popular algorithms in use today: RSA.

RSA encryption

RSA was invented in 1977 by three cryptographers: Ron Rivest, Adi Shamir, and Leonard Adlemanhence the name. Since its inception, it has spread to nearly every corner of the earth.

If youve ever used Secure Shell (SSH)

or GNU Privacy Guard (GPG)

you have RSA to thank for it. However, its most known for its use in TLS and HTTPS to prevent man-in-the-middle attacks.

While RSA is nearly half a century old, its one of the most commonly used asymmetric-encryption algorithms in the world. Its ubiquity is a testament to its security.

But why is it so secure? Short answer: prime numbers. Long answer? Thatll involve some math. But the best answer would be to try and break it ourselves.

Breaking RSA

Heres the scenario: Were hackers trying to impersonate Mediums server. We want to intercept all traffic going to Mediums website in order to steal user credentials and ransom their data.

Using Wireshark, were able to get a copy of Mediums RSA public key and website certificate.

But in order to impersonate Medium and fool users into connecting to our phishing server, we need the private key. Luckily, all is not lost.

One thing I havent mentioned is that RSA keys are just numbers. An RSA private key is just a single number, which well call d. The public key is made up of two numbers, e and N. And N is the product of two more numbers, p and q.

I know, thats a lot of numbers to track of. But its just those last two numbers, p and q, that we need to focus on. Because according to RSAs key-generation algorithm, if we know e, p, and q, we can recreate the private key.

Well, perfect, one might say. Since we have the public key, we know e and N. And since we know N, we just need to split it apart to get p and q. How hard could that be?

Not so fast, person I just made up to ask loaded questionsp and q are prime numbers. Gasp!

I mentioned before that detecting that generating prime numbers and checking if theyre prime are relatively simple for computers. However, what isnt simple is prime factorization.

How hard, you might ask?

RSA typically uses numbers 1024, 2048, or 4096 bits long. As you can see in the graph above, it only takes seconds to minutes to create N, but itd take millions to billions of years to factor it apart.

The reason for this isfor average, nonquantum computersthere isnt a fast method for factoring a number into its prime components. One of the best methods we know is the Number Field Sieve, but even then, for a number like this, it will take a while:

12647218591793774062037539860814590913847656969568852342569985866826731647633698490555162899129013020883082990527279827064849704038819915244363097120031062841681483530795022535252488366169730386558454292994968234214045666016756933262308367238453012386845278265898125397947728757013541963782671274800429212175737617916738370351721854897974375037404102868790995317383226110430324268401945063200233204784127599950729869495397377610047121343931821194220803396259107891220452870079636709770538139479748696178546655932056530040495898965404702415803790560056325250086900175615221136804225865647753477561884491932551643726743

While its not impossible, the level of effort is astronomical and not worth it. Wed all be long dead by the time we could generate Mediums private key.

So long story short, prime numbers are pretty darn hard to break. And thats how they keep the internet secure.

Parting Thoughts

As a software developer, Im often intimidated by all the different moving parts on the internet. It can feel like a magical and bewildering place. And as a result, I usually feel like I have no idea how any of it works or what Im doing.

But any time I learn something new about the systems I use on a daily basis, the world becomes just a little less chaotic and magical. I hope this article has helped demystify some of the mysteries of the internet for you as well.