Do you like stories? We've got a good one. At its core, the story is about RSA encryption, but it has government secrets, a breakthrough discovery, and not one, not two, but four heroes who changed the history of cryptography.
This is the story of RSA, one of the first asymmetric, or public-key, cryptography algorithms.
What is RSA encryption?
RSA is the name of a public-key cryptosystem invented and named by Ron Rivest, Adi Shamir, and Leonard Adleman. They are the heroes of this story.
Wait. Didn't we say there were four heroes? Yes, we did. Here's the intriguing part.
The inventors of RSA worked at the Massachusetts Institute of Technology (MIT), where in 1977, they solved a crucial cryptography problem. As it turned out 20 years later, someone else had beaten them to it.
The history of RSA encryption
To understand what happened, we must leave the United States and go across the pond to South West England. Here, in 1969 professor James H. Ellis had an idea.
At the time, the only way to secure files was through symmetric encryption. In other words, the key is shared between different parties. The situation becomes much more problematic when you must send an encrypted message to someone who you haven't met before.
Ellis' idea was what is now known as a public key. He figured that parties could have a public key which, in combination with a secret key, could be used to encrypt and decrypt messages. While the professor couldn't find a way to implement his idea, he shared his thought process with colleagues at the Government Communications Headquarters (GCHQ). Luckily, our fourth hero came to the rescue.
Meet Clifford Cocks. He joined the GCHQ in 1973. After learning about Ellis' idea, Cocks realized that prime factorization could be the answer.
In case your 6th-grade math is a little rusty, a prime number is any number that has only two divisors (1 and itself). Therefore, 2, 3, 5, 7, 11, and 13 are all prime numbers. We'll show you why prime factorization was the right solution for RSA in a bit. First, let's finish the story.
According to Cocks, he came up with the solution, went home, did the calculations in his head, and didn't even write anything down. Soon after, Cocks presented his findings to the GCHQ.
The problem was the secret relationship between the GCHQ (the British intelligence agency) and the NSA (the US intelligence agency). Two agencies shared secrets and did not want their relationship to become public. Therefore, a decision was made to keep Cocks' encryption algorithm classified. It took 20 years for the GCHQ to publicize the work of professor Cocks.
So, what did Cocks discover? We'll explain that next.
How does RSA encryption work?
We already know that RSA uses prime numbers. The reason why prime factorization is so effective is that it's easy to calculate one way and incredibly hard to do in reverse. In cryptography, it's known as a trapdoor. We'll show you what we mean.
Let's multiply two prime numbers: 23 and 29. You may need a calculator, but you'll probably agree that the task is easy. But what if we did that in reverse? Could you find the prime numbers of 3,139? It's a lot harder, isn't it? Even a calculator isn't that useful.
That's the key to RSA encryption. If you expand the numbers enough, even a computer won't be able to find the solution. Consider that RSA deals with prime numbers hundreds of digits long. And the only way to solve this problem is through trial and error. Even today's supercomputer would take centuries to find the answer. Simple yet fascinating.
At its core, RSA is a combination of another public-key cryptography algorithm that was created at a similar time and a trapdoor function with supercharged prime numbers. Oh, and there was one other crucial component that made RSA into a stronghold.
Public-key cryptography
Around the time when RSA encryption was invented, another public-key cryptography algorithm was born. Named after its creators Whitfield Diffie and Martin Hellman, it's simply called the Diffie-Hellman key exchange. By using modular arithmetic, Diffie-Hellman allowed two or more parties to exchange secret messages without sharing a secret key in advance.
We'll illustrate the Diffie-Hellman key exchange with an example using two characters, Alice and Bob.
Fun fact: Alice and Bob were invented by the creators of RSA in one of their publications. These characters were then adopted by the cryptography community for use in most hypothetical cryptography situations.
Back to Diffie-Hellman. Here's how it works. Let's say Bob and Alice want to share a message. First, they exchange their public key. Then, Alice uses Bob's public key with her secret key to calculate a public result to share with Bob. Bob does the same with Alice's numbers. Due to the specifics of modular arithmetic, Alice can use her secret key in combination with Bob's public result to calculate the secret message and vice versa. The public keys alone do not enable an outside party to make the necessary calculations. To put it another way, just like Grandma's apple pie, you must have the secret ingredient to get the same result. Otherwise, it just doesn't work.
But there were two issues with the Diffie-Hellman key exchange. First, it didn’t have a trapdoor function — something that RSA encryption solves with prime numbers.
Another Diffie-Hellman weakness was authentication. Theoretically, even if you establish a secure channel, you couldn't confirm that you were talking to the intended party. As long as we're on the subject of parties, let's invite Alice and Bob for another example. But this time we'll add a hacker named Eve.
Let's say that Alice intends to contact her insurance company, where Bob works. First, Alice needs to send her public key to the insurance company. But what if Eve is not an idle listener, but a competent hacker? Eve could squeeze into the network before Alice and Bob exchange the keys and try to intercept the signal. If Eve succeeded, she would pretend to be Bob to extract as much personal information about Alice as possible. And Alice wouldn't suspect a thing.
That's where RSA encryption was superior. Its public key also included a digital signature.
Naturally, both Diffie-Hellman and RSA have seen lots of improvements since their invention as well as different uses. Today, the Diffie-Hellman key exchange is commonly used in the TLS (Transport Layer Security) protocol to encrypt website traffic.
Where is RSA encryption used?
RSA helps people online stay secure in many ways without them even noticing. SSL (Secure Sockets Layer), or TLS (Transport Layer Security), is the most common one. SSL/TLS is used to secure all kinds of private information like usernames or passwords. However, you may better know HTTPS, a way to make website data safer.
RSA is widely used because it can help protect digital signatures and certificates. In other words, RSA encryption confirms that someone you’re talking to is who they say they are.This type of encryption can be used by email providers, cloud storage services, VPNs (virtual private networks), and communication apps.
The only caveat is that public-key algorithms, including RSA, are not as efficient as symmetric keys that are commonly used for data storage. That's why messages and files are often encrypted with a symmetric key first, while a public key, like RSA, is used when that data is transferred.
How secure is the RSA algorithm?
RSA encryption is not unbreakable. In fact,at least four methods to crack the RSA algorithm over the years have been identified. One of them bypasses encryption altogether by finding the greatest common divisor of the two public keys. Whenever the divisor is not 1, it means that the result is a prime number that can break both public keys. A computer can calculate the greatest common divisor between two numbers in moments, but by using the Euclidean algorithm, you can even do it by hand.
That doesn’t mean there is something to worry about. After various modifications, RSA is one of the safest and most common encryption methods in the world. However, cryptologists agree that one slight problem with RSA remains. At its core, RSA is a simple multiplication equation. While a brute-force attack against RSA would take centuries, a sudden breakthrough in prime number factorization could render the whole technology useless virtually overnight. No matter how unlikely that might be.
At NordLocker, we use a new type of public-key encryption, elliptic-curve cryptography (ECC). It's considered faster and more secure than RSA.
But you know what? We've covered a lot of ground today. We've learned about RSA, its creators, prime number factorization, and the Diffie-Hellman key exchange. Let's leave ECC for another time.
If you found this article useful, please share it by clicking on the social media buttons below.
