RSA Algorithm in Cryptography: Rivest Shamir Adleman Explained

RSA is a popular and secure cryptographic algorithm that encrypts and decrypts data. It provides a secure method for transmitting sensitive data over the Internet. While RSA has some vulnerabilities, it is still utilized for various applications, like digital signatures to authenticate the source of a message.

This article describes RSA, how it works, and its major applications. It also explains the security vulnerabilities of RSA and how to mitigate them.

What is RSA?

Rivest Shamir Adleman (RSA) is a well-known public-key or asymmetric cryptographic algorithm. It protects sensitive data through encryption and decryption using a private and public key pair.

Brief history of RSA

First introduced in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman of the Massachusetts Institute of Technology, RSA is named after their last initials.

The growing domain of computer networks required a solution to secure digital communication. RSA was initially developed in 1977 as one such solution. The primary focus of RSA was to allow data to be securely transmitted over unsecured networks, specifically to enable private communications over the Internet and other electronic systems.

In traditional cryptographic systems, secure key distribution was a challenge. It required both parties to share a secret key before sending or receiving a message. With RSA, public-key cryptography helps users to share their public key openly, while keeping their private key secret. This solved the problem of key distribution and allowed users to communicate securely without prior key sharing.

RSA today

This makes RSA one of the most widely used encryption mechanisms worldwide. However, the computational complexity of RSA, it is not ideal to encrypt a huge amount of data.

To manage this goal, RSA is used to encrypt a symmetric key. The key is then used to encrypt the actual huge data. This hybrid approach utilizes both asymmetric and symmetric cryptography for efficient encryption.

(Read our primer on AES, another common encryption standard.)

How does RSA work?

RSA is based on factorizing and factoring large integers. First, you must choose two large prime numbers for the key pair, which is difficult to factorize. Hence, the prime numbers must be selected randomly and with a substantial difference between them. For example, consider the two chosen prime numbers as p and q.

Then, the algorithm calculates their product, denoted by n = p * q. The values of p and q should be kept secret, while n, which is used as the modulus for public and private keys, must be made public.

Next, the Carmecheals’ totient function is calculated using p and q, and the integer e, whose value is used as the public exponent, is selected. Then the next step is calculating the value of d, which is used as the private exponent.

How do encryption and decryption happen in RSA?

The public key is the pair (n, e), while the private key is the pair (n, d).

• Encryption. When encrypting a message, the sender uses the public key (n, e) of the recipient to compute the ciphertext, where the ciphertext = m^e mod n. The m indicates the plaintext message.
• Decryption. When decrypting an RSA encrypted message, the recipient uses their private key (n, d) to compute the plaintext message, where the plaintext message = c^d mod n.

Can RSA be broken?

RSA relies on the difficulty of factoring large prime numbers. (More on this below.) The security of RSA relies on a key's size. Although RSA is currently considered to be secure, it is vulnerable to potential future threats like Quantum computing.

Quantum algorithms, for instance Shor's algorithm, can quickly factor large numbers, thus making RSA obsolete. Against traditional attacks, with large keys (2048 bit or more) RSA is secure. However, advancement in computing powers may prove to be a challenge to RSA's reliability in the future.

So, what happens if RSA is broken? The primary risk is obviously the exposure of sensitive data, like financial details or personal information. Digital signatures will no longer be trustworthy, negatively impacting financial and legal systems.

To handle this potential risk, post-quantum cryptography, like lattice-based encryption is currently being explored as a solution to ensure data security in a world where RSA is breakable.

Applications & use cases of RSA

RSA is used in several information security and cryptography applications. Some of the most widely used applications include:

Digital signatures

A digital signature is a technique that lets the recipient of a message verify its authenticity, integrity and non-repudiation. It proves that the message has not been altered in transit.

When creating digital signatures, the sender starts by generating a hash value of the message using a cryptographic hash function. Then, you sign it by applying the RSA algorithm using the private key, which generates the digital signature as the output. The recipient can then apply the RSA algorithm to the digital signature using the sender's public key.

Additionally, you can verify the signature by matching it with the hash value generated over the message.

Digital certificates

RSA is widely used in digital certificates, such as SSL certificates. These certificates can be used to verify the identity of individuals or organizations behind websites.

Digital certificates utilize RSA to encrypt the digital signature of the certificate issuer, which can be verified using his public key. The digital certificate consists of information such as the domain name and the organization that operates the website, proving the identity of the website to clients.

Secure communication protocols

RSA encrypts communication between two parties over an insecure network like the Internet. For instance, RSA is used with Transport Layer Security (TLS) to establish secure connections between web servers and web browsers. Moreover, RSA aids secure email communication by providing a way to encrypt and decrypt messages.

It is also used in Virtual Private Networks (VPNs). VPNs utilize TLS to facilitate a handshake between two parties exchanging information. The TLS handshake depends on the RSA algorithm to authenticate the identities of both parties involved in the exchange.

Secure key exchange

Another use case of RSA is to have a secure key exchange between two parties who have not previously shared a secret key. The two parties involved generate a public-private key pair using the RSA algorithm.

• The sender generates a symmetric key, encrypts it using the receiver’s public key, and sends the encrypted key to the receiver.
• The receiver then decrypts it using the private key.

Both sender and receiver have the same symmetric key, which they can use for secure communication.

Security vulnerabilities of the RSA algorithm

The RSA algorithm is difficult to crack, provided that it adheres to the recommendations. Several vulnerabilities in RSA have been discovered over the past few years. Those vulnerabilities are:

Side-channel attacks

A side-channel attack targets the vulnerabilities that arise when a computer system processes data — such as program execution time, power consumption, or electromagnetic radiation — rather than directly targeting the software or its code.

For instance, an attacker can reveal information from the electromagnetic radiation emitted by a computer while performing cryptographic operations.

Power analysis and timing attacks are the two most common side-channel attacks on RSA encryption:

• Power analysis attacks occur due to the computationally expensive operations of RSA, which can lead to varying power consumption.
• Timing attacks occur when attackers measure the time a device takes to perform RSA encryption.

Bad actors can use this data to derive the secret key used in RSA encryption. Thus, appropriate countermeasures should be taken to prevent side-channel attacks.

Inadequate key length

The security of the RSA algorithm heavily relies on large, difficult-to-factor prime numbers used for the key generation process. Factoring the product of two large prime numbers is more difficult when the key length is higher.

The key length should be increased as computing power increases. Robust computers can factor large numbers relatively easily and with less time. Thus, they can easily crack keys with shorter lengths.

Once recommended, a 1024-bit RSA key can be cracked and is no longer valid today. Therefore, it is best practice to use a minimum key length of 2048 bits for RSA.

Weaknesses in prime numbers

When we talk about prime number weaknesses, we can break it into:

• Randomness 
• Closeness

The randomness of prime numbers. The RSA algorithm depends on generating random prime numbers in the key generation process, which are then multiplied to produce the public and private keys.

Assume that the organization uses a weak random number generator or an algorithm that generates easily predictable or easy-to-factor random numbers. In that case, attackers can guess the pattern used to generate the primes and factor the keys easily.

The closeness of prime numbers.  In addition, the security of the RSA key can be compromised if the two prime numbers used in RSA are too close to each other in value or if one of them is too small. In such scenarios, attackers can easily determine the factors of the RSA modulus, which enables them to break the encryption and gain access to the private key.

Lost or stolen keys

Lost, stolen or compromised keys can be directly accessed by attackers, enabling them to decrypt encrypted messages using the corresponding public key. Therefore, the keys must be managed properly to avoid such vulnerabilities.

Fault-based attacks

Fault attacks are attacks where attackers deliberately introduce faults in the hardware or software used to implement the cryptographic application. For instance, an attacker can use a laser or a bit flip to create a fault in cryptographic functions, resulting in weaker keys with more predictable values.

RSA implementations can be vulnerable to fault attacks if you do not take appropriate countermeasures.

Avoiding the vulnerabilities of RSA

There are several things you can do to mitigate RSA vulnerabilities.

• Use a strong prime number generator to ensure that the prime numbers are unpredictable and cannot be easily guessed by an attacker.
• Avoid using weak prime numbers, such as small primes or primes too close to each other.
• Use a minimum length of 2048 bits for the RSA key.
• Take necessary actions to protect against fault-based attacks, such as using tamper-resistant hardware.
• Manage and secure the RSA keys properly using techniques like regular key rotation and different keys for different applications.
• Keep the RSA algorithm up to date by regularly monitoring for vulnerabilities and updates.

Summing up RSA

RSA is a widely used cryptographic algorithm that was first introduced in 1977. It uses public and private key pairs to encrypt and decrypt data. Though RSA can be used in several applications, its computational complexity makes it unsuitable for encrypting large messages or files. Currently, RSA creates digital signatures and certificates for secure authentication, communication, web access and email messages and key exchanges.

There are several vulnerabilities in RSA, such as side-channel attacks, inappropriate key lengths, weaknesses in prime numbers, fault-based attacks and risks introduced by stolen or lost keys. Thus, it is important to consider the recommendations described in the article when using RSA for your cryptographic applications.