Whether you’re browsing TikTok, Instagram, or scrolling through random Wikipedia articles, do you ever wonder if your internet browsing is secure? Probably not – but that’s okay! The world can peacefully rely on the wonders of mathematics to keep their data and internet browsing safe from peeking eyes. In fact, the entire safety of the internet primarily relies on a single mathematical algorithm to secure it all, ranging from state secrets in secret government databases – which are probably all about UFOs – to your grandmother’s email account. This algorithm was first developed in 1977; it’s so powerful that it still remains the primary public cryptographic algorithm today! It’s called the Rivest-Shamir-Adleman (RSA) cryptosystem.
Background
Developed in 1977 from a paper released by Ron Rivest, Adi Shamir, and Leonard Adleman, while they were at the Massachusetts Institute of Technology, RSA quickly became adapted to securing digital communication because of its robust mathematical properties that makes it virtually impossible to break.
Interestingly, the actual mathematics behind the RSA cryptosystem is rather simple. It’s based on the idea of prime factorization – it’s really easy to find the prime factors for a small number but becomes much harder as the numbers grow. For example, if I ask you to give me the two prime factors that multiply together to give the number 15, you would probably answer really quickly with “3 and 5”. Easy, right? Now, without a calculator, what if I asked you to give me the prime factorization for the number 414,863? You would answer with “577 and 719” right away, right? Unless you’re a super math genius or a human calculator, probably not.
Implementation Idea
The actual RSA algorithm is used in public-key cryptography, which is the process that secures data over the internet. It’s a complicated process but the basic idea is this: if Alice wants to send Bob a secret gift, Bob can send her a padlock that only he has the key to. Then, Alice can put her gift in a box and lock it with Bob’s padlock. Then, when Alice sends her package, if anyone tries to steal the gift, they can’t because only Bob has the key. Once Bob receives his gift, all he has to do is unlock the padlock that he gave to Alice. The padlock that Bob gave to Alice is called Bob’s public key, while the key that only Bob has is his private key.
In the real world, if my friend wants to send me a message, I will give them my public key (which is basically just a really large number). They can then use my public key to encrypt, or hide, the message. Then, in transit, the message is completely safe because I’m the only person that holds the key that decrypts, or unlocks, the message. The only tricky part about the process is making keys that are not able to be broken.
The Magic Behind It All
The RSA algorithm is responsible for creating the public and private keys. To create the actual keys, RSA relies on some basic math: modular arithmetic, Euler’s Theorem, and prime numbers.
To create my public key that I can give to anyone who wants to send me secrets, I do two things:
- First, I will choose two very large prime numbers, p and q. The multiplication of these two numbers, x = pq, is the first half of the key. The key take-away in this first portion is that the longer that x is, the more secure your key will be. As of 2020 practices, a length of 4096 bits (or characters) is recommended!
- Then, I calculate another number y by multiplying from the following: y = (p-1)(q-1). From here, I choose a number that is relatively prime to y and call it e. If you don’t recall what it means for two numbers to be relatively prime, it just means that two numbers have a greatest common divisor of 1. In practice, e is typically chosen to be 65,537 – e then becomes the other half of my public key.
Now, to create my private key that no one else knows about, I use modular arithmetic. If you’re not familiar with modular arithmetic, think of it as the remainder produced after dividing a small number into a big number – for example, 10 modulo 3 = 1 because 3*3 is 9, which leaves us with 1 left over. To create my private key, I calculate the modular inverse of the second half of my public key with the first half of my public key, e modulo x. That’s it! I have my private key! Now I can share my public key with friends, and they can share juicy, secret memes with me without the fear of someone else seeing!
Convinced?
What makes RSA so robust and secure is that, even as computers gain more processing power and become faster, all we have to do is increase the length of the key! Think about how fast and powerful our current computers are: our computers are solving problems in astrophysics, mathematics, and are beginning to become ubiquitous in controlling cars. Even with how advanced technology currently is, if someone uses a 4096-bit RSA key, it would take tens of thousands of years for computer to break the code! And even when that’s broken, all we have to do is increase the number of bits in the RSA key and it’s secure for another few thousand years or so!
If you’re not convinced by how amazing (and even basic) cryptography is, then I don’t think you’re someone who can be easily impressed!
The Process in Pictures
If you prefer pictures, here is a simple illustration of the process above:
Step 1:
Step 2:
Step 3:
Step 4:
Step 5:
Step 6:
