What is RSA encryption, and how does it work?

RSA encryption definition

RSA is a public-key cryptography system for establishing secure connections and creating digital signatures.

RSA encryption got its name from the surnames of its creators, Rivest, Shamir, and Adleman, who described the algorithm while working at the Massachusetts Institute of Technology back in 1977.

RSA uses a public key for the encryption of the message and a private key for its decryption. The math behind the RSA encryption algorithm includes a one-way function – it’s easy to calculate but challenging to reverse. That makes RSA a secure encryption algorithm that’s practically impossible to brute-force.

How does RSA encryption work?

RSA is a type of asymmetric cryptography (public-key encryption) requiring the use of public and private keys.

• You need a public key to encrypt the message – to turn the plain text message into a ciphertext. The public keys can be shared and accessed openly.
• You need a private key to decrypt the encrypted message – to turn the ciphertext back into a plain text message. You must keep your private key secret at all times.

Symmetric encryption (like AES and Twofish), on the other hand, uses the same private key to encrypt and decrypt the message. It works well when there’s a chance to share the private key with the recipient of the message securely beforehand. Public-key cryptography, including RSA, is excellent when such an opportunity is unavailable.

Asymmetric encryption algorithms involve four parts: the generation of public and private keys, (public) key exchange (via key exchange algorithm), encryption, and decryption.

Key generation

Key generation is the procedure of calculating the RSA keys – a private and public key pair. The process consists of the following steps:

1. Choosing two prime numbers (p and q)

For encryption to be secure, the chosen prime numbers must be distinct and large.

For example, 2048-bit RSA encryption uses prime numbers that are 308 digits in size. Since coming up with such large numbers is not easy, a primality test is used for their generation.

2. Calculating the modulus (n)

The first half of your private and public key is the modulus (n) – the product of p and q:

While it’s easy to calculate, it needs to be practically impossible to estimate which numbers were multiplied to get the product.

For example, if your p is 6,637 and q is 8,971, the calculator app on your phone will tell you that the product is 59,540,527. But if you see 59,540,527 in front of you, can you tell or use the same calculator to determine which exact numbers were multiplied to get the product?

Probably not. And that’s the idea behind RSA encryption – the algorithm needs to be simple to compute but not feasible to reverse.

The numbers from the example above would be easy to decompose for a factoring calculator. However, as mentioned, RSA encryption uses prime numbers, 308 digits in size, which are a lot bigger and more difficult to compute.

3. Generating the public key (e)

The RSA public key consists of the modulus (n) and the public exponent (e). Before you can get e – the second half of your public key, you need to calculate φ – the totient for n:

Then you can choose e – an arbitrary integer higher than 1 but lower than and relatively prime to φ. Usually, 65,537 is used as e in the RSA encryption.

4. Generating the private key (d)

The RSA private key consists of the modulus (n) and the private exponent (d). d is calculated from p and q and involves finding these numbers’ greatest common divisor (GCD). This procedure is called an Euclidean algorithm, and it’s easier to leave it to online calculators.

Key distribution

If someone wants to use RSA to encrypt the message for you, they need to know your public key. You can share the public key in any reliable way; it doesn’t necessarily have to be a secret route.

Encryption

Let’s say the person on the other end got your public key (e and n) and wants to send you a message (M). What happens next?

To turn that plain text message into a cipher text (C), they need the following function:

Mod stands for modulo operation and refers to the remainder left after one side is divided by the other, e.g., 11 mod 3 = 2 (3 fits within 11 three times, and 2 is left).

If the message you want to send is a number, you replace the M with your number, and the function has all the missing pieces. If it’s a text message, you’d need to convert the text to the numbers first. For example, using the ASCII alphabet, the message “NORDVPN” would be “78798268868078” in numbers.

Decryption

To decrypt the ciphertext you receive, you will need to dig up your private key (d and n) from the secret location, take the received cipher text (C), and use the following function:

It will convert the cipher text back to the original message.

Where is RSA encryption used?

As public-key cryptography, RSA comes in handy when you send information securely to people or servers you haven’t had any contact with before and, thus, don’t have the private keys for symmetric encryption. So you can find it in browsers, email providers, chat applications, cloud services, VPNs, P2P systems, and other communications channels.

However, as far as digital encryption goes, RSA is ancient now, so it’s usually used together with other encryption schemes. A basic example would be using RSA to encrypt the private key for symmetric encryption – to share the key securely while protecting the actual sensitive data with symmetric encryption.

The main RSA uses include establishing a secure connection and creating digital signatures. RSA is not used for encrypting messages or files because other encryption systems are more secure, faster, and require fewer resources.

Establishing a secure connection

Web browsers use RSA to establish secure internet connections, which help prevent sniffing or man-in-the-middle attacks. Most internet connections use SSL to secure traffic, and the RSA is a part of SSL/TLS handshakes. You can find it in cryptographic libraries, such as OpenSSL.

OpenVPN uses RSA for the key exchange and secure communications between the VPN client and the VPN server when the VPN connection is established. However, VPNs usually protect the actual data with different encryption ciphers. For example, NordVPN’s next-generation encryption uses AES-256-GCM.

RSA was also the first algorithm used in PGP encryption to encrypt session keys.

Creating digital signatures

You can use the private key to sign your message or document, while the other party can use the public key to verify the authenticity of that message or document.

It’s a versatile function, so when it comes to digital signatures, RSA can be used everywhere, from email to banking to online shopping.

For example, emails are often digitally signed using PGP encryption which uses the RSA algorithm for digital signature creation.

Pros and cons of RSA encryption

The RSA cryptosystem has advantages and disadvantages that you should consider before implementing RSA encryption.

• RSA algorithm is easy to implement and understand. The algorithm is pretty basic, and the functions are not too complicated compared to other algorithms, such as elliptic curve cryptography and its most popular algorithm – ECDSA. Choosing between RSA and ECDSA, many services are shifting to ECDSA because it’s more efficient in terms of resources management.

• RSA encryption is pretty versatile, so it can (and is) widely used.

• When implemented correctly, RSA encryption is impossible to brute-force, at least with current computing capabilities.

• When implemented incorrectly, RSA is vulnerable to many different attacks.

• RSA key length is crucial for encryption security, but longer keys require a lot of computing power to generate, so they are not always sustainable.

• The decryption also takes long and requires a lot of resources.

• The increasing number of available RSA public keys makes it easier for attackers to devise ways to break or overcome the encryption.

RSA algorithm vulnerabilities

RSA security heavily depends on its implementation. Each part of the process may involve vulnerabilities that impact the outcome of encryption.

Weak random number generators

The RSA algorithm starts with choosing the prime numbers, and this first step may be the vulnerable part. If the prime numbers are not random enough, it’s easier to factor the modulus and crack the encryption.

Weak random number generators are usually at fault here, so you can avoid the vulnerability using pseudo-random number generators instead.

Faulty key generation

Prime numbers may be random enough but too small or close to each other. And that’s another problem.

Since the RSA algorithm uses a public key for encryption, the key size is critical to prevent factoring. Uncovering prime numbers (p and q) is easier when the numbers are smaller. And if the numbers are too close to each other, then the private key (d) ends up being relatively small.

That’s why security experts recommend the minimum key size of 2048-bit, while newer RSA keys usually go for 4096-bit.

Attacks on RSA encryption

Ignorance of the mentioned RSA vulnerabilities leads to easy RSA attacks.

Factorization attack

If you don’t address the vulnerabilities, cybercriminals can take advantage of them to perpetrate factorization attacks.

RSA encryption is only secure if no one can discover the prime numbers p and q from their product n. However, if the prime numbers are too close to each other or are not random and big enough, attackers can factor them, and then it takes little to expose the private key.

Side-channel attack

In side-channel attacks, attackers analyze the extra information gathered about the decryption process instead of cracking the encryption key. For example, they examine how much power the algorithm uses, or even the sounds computers make during it.

A timing attack is also an example of side-channel attacks. In RSA timing attacks, the attackers analyze how long decryption takes for different known ciphertexts to deduce the private key (d).

Plaintext attack

If the attacker matches any part of a plaintext message to the cipher text, they can carry on plaintext attacks:

• Short message attack. An attacker has access to some parts of the plaintext message and encrypts it to get ciphertext. They can then use it to deduce other parts of the plaintext message. You can avoid this plaintext attack by using paddling – including extra data in the plaintext message before encrypting it.
• Cycling attack. An attacker tests permutation operations that could have been done to create the ciphertext. If it works, they can then reverse the process to obtain the plaintext message from the ciphertext.
• Unconcealed message attack. It’s rare, but in theory, some encrypted ciphertext can be identical to the original plaintext message. If that happens, attackers can deduce other parts of the encrypted message and carry unconcealed message attacks.

Chosen cipher attack

As mentioned before, you use the Euclidean algorithm to generate the private key. As the algorithm is no secret, attackers can use the extended Euclidean algorithm to get the plain text message from the ciphertext. That’s how you get chosen cipher attacks.

Is RSA encryption secure?

Considering RSA vulnerabilities and attacks, asking whether RSA encryption is secure is natural. The answer is “it depends.”

More precisely, it depends on the implementation.

If you implement the algorithm without considering the vulnerabilities, then RSA encryption will not be strong enough to withstand the attacks. Unfortunately, many RSA users ignore the vulnerabilities quite often, as research shows.

In 2012, researchers collected 5.5 million public keys and discovered that RSA 1024-bit encryption keys provided 99.8% security at best. In other words, it would be easy to crack almost 13,000 keys.

More recently, researchers from Keyfactor discovered that 1 in every 172 RSA certificates is vulnerable to factorization attacks.

However, if you prevent RSA algorithm vulnerabilities, use adequate key length, and take extra measures to increase security (e.g., paddling), RSA encryption is secure and unbreakable for most modern computers.

At least for the time being.

The future of RSA encryption

RSA encryption is not the best encryption algorithm for security or efficiency, so its future is rather bleak.

Traditional computers would take 300 trillion years to break RSA encryption. However, the emergence of quantum computing makes it possible in just 10 seconds. Since such computers aren’t yet widely available, you’d think RSA encryption is good for now. But it’s not the only thing pointing to the bleak future of the RSA algorithm.

According to the National Institute of Standards and Technology recommendations, RSA encryption with 2048-bit encryption keys is safe to use until the end of 2030. While you can always choose the 4096-bit key length that would stay relevant a bit longer, longer keys are not sustainable.

After all, it’s not just security that makes an encryption algorithm a good choice. It’s also the efficiency of encryption. And that’s where RSA falls short.

The RSA algorithm requires a lot of resources to run. It’s slow, especially if you use longer keys, but using shorter keys makes the cryptosystem insecure. So while 4096-bit keys are okay for now, anything beyond that will cost too much computational power.

RSA use has been gradually declining for years now. It’s too much hassle when you have better alternatives – systems that are more secure and efficient, such as Elliptic Curve Cryptography. So it’s only a matter of time before RSA becomes obsolete.