What is RSA encryption and why it matters to you?
Jan 09, 2020
Do you like stories? We've got a good one.
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.
he 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). 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 (British intelligence agency) and the NSA (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 3139? It's a lot harder, isn't it? Even a calculator isn't that useful.
That's the key. 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.
Around the time when RSA 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. Since then, these characters were adopted by the cryptography community for 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 numbers. Then, Alice uses Bob's public number with her secret number to calculate a public result to share with Bob. Bob does the same with Alice's numbers. Due to specifics of modular arithmetic, Alice can use her secret number in combination with Bob's public result to calculate the secret message and vice versa. The public numbers 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 doesn't have a trapdoor function — something that RSA was able to solve 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 even suspect a thing. That's where RSA was superior. Its public key also included a digital signature.
Naturally, both Diffie-Hellman and RSA have seen lots of improvements since their invention and saw different uses. Today the Diffie-Hellman key exchange is commonly used in the TLS (Transport Layer Security) protocol to encrypt website traffic.
RSA is also used in TLS handshakes, but it's more common in web browsers, email clients, as well as VPN servers. Public-key algorithms, including RSA, are not as efficient as symmetric keys. That's why you can often see a message encrypted with a symmetric key, which in turn is encrypted with a public key. NordLocker does it, too. But instead of RSA, we're using a new asymmetric encryption algorithm.
How secure is the RSA algorithm?
RSA is not unbreakable. In fact, there have been at least 4 recorded methods to crack the RSA algorithm over the years. But there is no need to worry. 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. If you take away Superman's cloak, 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 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 in the near future.
If you found this article useful, please share it by clicking on the social media buttons below.
John believes that the best things in life are simple. He uses the same approach when he’s writing about online security. John says that his #1 pet peeve is phishing scams. Ironically, his favorite non-work related activity is fishing.