RSA

RSA encryption is a system that solves what was once one of the biggest problems in cryptography: How can you send someone a coded message without having an opportunity to previously share the code with them?

This article will teach you everything you need to know about how RSA encryption was developed, how it works, the math behind it, what it is used for as well as some of the biggest security issues that it faces. Learning about RSA will give you some foundational knowledge that helps you to understand how many parts of our online life are kept secure.

What is RSA encryption?

Let’s say you want to tell your friend a secret. If you’re right next to them, you can just whisper it. If you are on opposite sides of the country, that obviously won’t work. You could write it down and mail it to them, or use the phone, but each of these communication channels is insecure and anyone with a strong enough motivation could easily intercept the message.

If the secret was important enough, you wouldn’t risk writing it down normally–spies or a rogue postal employee could be looking through your mail. Likewise, someone could be tapping your phone without your knowledge and logging every single call you make.

One solution to prevent eavesdroppers from accessing message contents is to encrypt it. This basically means to add a code to the message which changes it into a jumbled mess. If your code is sufficiently complex, then the only people who will be able to access the original message are those who have access to the code.

If you had a chance to share the code with your friend beforehand, then either of you can send an encrypted message at any time, knowing that you two are the only ones with the ability to read the message contents. But what if you didn’t have a chance to share the code beforehand?

This is one of the fundamental problems of cryptography, which has been addressed by public-key encryption schemes (also known as asymmetric encryption) like RSA.

Under RSA encryption, messages are encrypted with a code called a public key, which can be shared openly. Due to some distinct mathematical properties of the RSA algorithm, once a message has been encrypted with the public key, it can only be decrypted by another key, known as the private key. Each RSA user has a key pair consisting of their public and private keys. As the name suggests, the private key must be kept secret.

Public key encryption schemes differ from symmetric-key encryption, where both the encryption and decryption process use the same private key. These differences make public key encryption like RSA useful for communicating in situations where there has been no opportunity to safely distribute keys beforehand.

Symmetric-key algorithms have their own applications, such as encrypting data for personal use, or for when there are secure channels that the private keys can be shared over.

See also: Public key cryptography

Where is RSA encryption used?

RSA encryption is often used in combination with other encryption schemes, or for digital signatures which can prove the authenticity and integrity of a message. It isn’t generally used to encrypt entire messages or files, because it is less efficient and more resource-heavy than symmetric-key encryption.

To make things more efficient, a file will generally be encrypted with a symmetric-key algorithm, and then the symmetric key will be encrypted with RSA encryption. Under this process, only an entity that has access to the RSA private key will be able to decrypt the symmetric key.

Without being able to access the symmetric key, the original file can’t be decrypted. This method can be used to keep messages and files secure, without taking too long or consuming too many computational resources.

RSA encryption can be used in a number of different systems. It can be implemented in OpenSSL, wolfCrypt, cryptlib and a number of other cryptographic libraries.

As one of the first widely used public-key encryption schemes, RSA laid the foundations for much of our secure communications. It was traditionally used inTLS and was also the original algorithm used inPGP encryption. RSA is still seen in a range of web browsers, email, VPNs, chat and other communication channels.

RSA is also often used to make secure connections between VPN clients and VPN servers. Under protocols like OpenVPN, TLS handshakes can use the RSA algorithm to exchange keys and establish a secure channel.

The background of RSA encryption

As we mentioned at the start of this article, before public-key encryption, it was a challenge to communicate securely if there hadn’t been a chance to safely exchange keys beforehand. If there wasn’t an opportunity to share the code ahead of time, or a secure channel through which the keys could be distributed, there was no way to communicate without the threat of enemies being able to intercept and access the message contents.

It wasn’t until the 1970s that things really began to change. The first major development towards what we now call public-key cryptography was published at the start of the decade by James H. Ellis. Ellis couldn’t find a way to implement his work, but it was expanded upon by his colleagueClifford Cocks to become what we now know as RSA encryption.

The final piece of the puzzle is what we now call the Diffie-Hellman key exchange. Malcolm J. Williamson, another coworker, figured out a scheme that allowed two parties to share an encryption key, even if the channel was being monitored by adversaries.

All of this work was undertaken at the UK intelligence agency, the Government Communications Headquarters (GCHQ), whichkept the discovery classified. Partly due to technological limitations, the GCHQ couldn’t see a use for public-key cryptography at the time, so the development sat idly on the shelf gathering dust. It wasn’t until 1997 that the work was declassified and the original inventors of RSA were acknowledged.

Several years later, similar concepts were beginning to develop in the public sphere. Ralph Merkle created an early form of public-key cryptography, which influenced Whitfield Diffie and Martin Hellman in the design of the Diffie-Hellman key exchange.

Diffie and Hellman’s ideas were missing one important aspect that would make their work a foundation of public key cryptography. This was a one-way function that would be difficult to invert. In 1977, Ron Rivest, Adi Shamir and Leonard Adleman, whose last names form the RSA acronym, came up with a solution after a year of laboring on the problem.

The MIT-based academics made their breakthrough after a Passover party in 1977. After a night of drinking, Rivest went home, but instead of sleeping, he spent the eveningfeverishly writing a paper that formalized his idea for the necessary one-way function.

The idea was patented in 1983 by MIT, but it wasn’t until the early days of the internet that the RSA algorithm began to see widespread adoption as an important security tool.

How does RSA encryption work?

The following is going to be a bit of a simplification, because too many readers have probably been scarred by their high school math teacher. To keep the math from getting too out-of-hand, we will be simplifying some concepts and using much smaller numbers. In reality, RSA encryption uses prime numbers that are much larger in magnitude and there are a few other complexities.

There are several different concepts you will have to get your head around before we can explain how it all fits together. These include trapdoor functions, generating primes, Carmichael’s totient function and the separate processes involved in computing the public and private keys used in the encryption and decryption processes.