What is RSA Algorithm in Cryptography?

RSA (Rivest–Shamir–Adleman) is one of the most commonly used encryption methods. It uses two keys, one to lock (encrypt) the message and another to unlock (decrypt) it, which makes it perfect for keeping information safe online. From protecting websites to verifying digital signatures, RSA is a key part of internet security.

In this blog, we’ll break down how the RSA algorithm works in a simple, step-by-step way. You’ll see a real example, learn where RSA is used in real life, understand the types of attacks it can face, and how it compares to other methods like AES. Let’s dive in!

Table of Contents

• What is RSA Algorithm?
• RSA Encryption Algorithm
• RSA Algorithm Example
• Application of RSA Algorithm
• Possible Attacks on RSA Algorithm
• Difference Between AES and RSA Algorithm
• Advantages of RSA Algorithm
• Disadvantages of RSA Algorithm
• Conclusion

What is RSA Algorithm?

RSA Algorithm (Rivest Shamir Adleman) was introduced in 1978 by Rivest, Shamir, Adleman as an asymmetric encryption algorithm. There are both public and private keys involved in this algorithm. RSA Algorithm in cryptography is based on the fact that you can find and multiply large numbers easily but finding the factor of their product is difficult.

Mathematical research estimates that if the key value is 100 digits, it would take attackers more than 70 years to find its value. The most difficult part of the algorithm probably is choosing and generating the public and private keys.

RSA Encryption Algorithm

In the RSA Encryption Algorithm, a public key is used for encryption and a private key, different from the public key and only known to the recipient, is used for decryption. The public key would be the product of two large prime numbers. That product is made public. The decryption would require knowledge of the two prime factors of that number and there is no known method to find the prime factors of such numbers. This means that only the person who created the public key will be able to generate the private key as well.

Let’s look at the RSA Algorithm Steps:

1. You can choose any two large prime numbers, say A and B.
2. Next, you can find the product of A and B, say N.
   N = A*B
3. You have to select a public key, say E, for encryption. You have to make sure this key isn’t a factor of (A-1) and (B-1).
4. Now you can select the private key for decryption say, D. The private key should match this equation:
   (D*E) mod (A-1)*(B-1) = 1
5. You can calculate the ciphertext from the plaintext using this equation:
   Ciphertext = Plaintext^E mod N
6. Once the ciphertext is generated, it should be sent to the recipient.
7. You can decrypt the plaintext from the ciphertext using this equation:
   Plaintext = Ciphertext^D mod N

RSA Algorithm Example

For this example, let’s try and work the RSA Encryption Algorithm with random prime numbers, say 7 and 17. So,

A = 7, and B = 17
N = A*B
N = 7*17
N = 119
Now, we have to select a public key, say p, so that isn’t a factor of (A-1) and (B-1).
(7-1)*(17-1) = 6*16 = 96
Now, the factor of 96 is 2*2*2*2*2*3.
So, we can choose our public key, E as 5 since it isn’t a factor of 2 or 3.
Now, to select the private key, we have to make sure it matches this equation:
(D*E) mod (A-1)*(B-1) = 1
(D*5) mod (6)*(16) = 1
(D*5) mod 96 = 1
Now, we can choose D as 77 to satisfy the equation.
(77*5) mod 96 = 1
385 mod 96 = 1
1 = 1
It satisfies the equation so we can move on.
Now, we have to calculate the ciphertext.
Let’s take our plaintext to be 10.
Ciphertext = Plaintext^E mod N
Ciphertext = 10^5 mod 119
Ciphertext = 40
Once, we have the ciphertext we can send it to the recipient.
We can also check the value by decrypting it with the equation:
Plaintext = Ciphertext^D mod N
Plaintext = 40^77 mod 119
Plaintext = 10

That is the plaintext we chose.

Application of RSA Algorithm

Let’s look at some applications of the RSA Algorithm:

• Sending Information Safely: RSA is used to protect important data when it’s sent over the internet, so only the right person can read it.
• Digital Signatures: It lets people “sign” documents or messages in a digital way, so others can be sure it came from them and wasn’t changed.
• Secure Websites (HTTPS): RSA helps websites create a safe connection with your browser, which is why you see a lock icon when visiting secure websites.
• Safe Email Communication: RSA is used in tools like PGP to keep your emails private and also to prove who sent them.
• Logging into Remote Computers (SSH): It helps people securely connect to another computer from far away, like IT admins working on servers.

Possible Attacks on RSA Algorithm

Here’s a list of the possible attacks on the RSA Algorithm:

1. Plaintext Attack

A plaintext attack is when a hacker has some original messages (plaintext) and their encrypted versions (ciphertext). The hacker tries to study these pairs to find out the encryption key or figure out how to decode other messages without needing the key.

There can be three types of Plaintext Attacks:

a. Short Message Attack

In short message attacks, it is generally assumed that the attacker already knows some of the plaintext messages. Now, if an attacker knows some blocks of plaintext, they could try to encrypt the blocks using the information. Padding bits of encryption is used to prevent a short message attack.

b. Cycling attack

The reverse process takes place in a cycling attack. The attacker assumes some permutations for the ciphertext. If this assumption is true, they can try and reverse the process to generate the plaintext using the ciphertext.

c. Unconcealed Message Attack

There are some rare times when, for some reason, the encrypted ciphertext is the same as the plaintext. The plaintext isn’t concealed and this type of attack is called an unconcealed message attack.

2. Chosen Cipher Attack

A Chosen Ciphertext Attack (CCA) is a type of cyber attack where a hacker chooses a specific encrypted message (ciphertext) and gets it decrypted to learn how the system works. This helps them find weaknesses and possibly break the encryption. It’s a serious threat in cryptography, especially for RSA and other public key systems. Protecting against CCA is important for keeping sensitive data safe in secure communication and online transactions.

3. Factorization Attack

In a factorization attack, the attacker can impersonate the owners of the key. They can use the information to decrypt sensitive data bypassing the system’s security. The attackers aim at an RSA cryptographic library. This library is used to generate the RSA key. This gives the attackers access to private keys of various security tokens, Motherboard Chipsets, and smartcards because they have the target’s public key.

Difference Between AES and RSA Algorithm

Let’s look at the differences between the AES and RES Algorithms:

Advantages of RSA Algorithm

There are some advantages of the RSA Algorithm over other algorithms. Here are some of them:

1. Easy to Implement: RSA is based on well-understood mathematical principles and is relatively straightforward to code and integrate into security systems.
2. Strong Data Security: It provides a high level of security by using large prime numbers and mathematical complexity, making it highly effective for secure data transmission.
3. Hard to Break: The algorithm’s reliance on complex number factorization makes it extremely difficult to crack using brute-force or analytical attacks, especially with long key sizes.
4. Public Key Distribution is Simple: RSA uses a public key that can be freely shared with anyone, eliminating the need for a secure key exchange channel.
5. Widely Adopted and Trusted: RSA is a proven and widely accepted standard in the industry, used in everything from SSL/TLS certificates to secure emails and digital signatures.

Disadvantages of RSA Algorithm

1. Slow Performance: RSA is significantly slower than symmetric algorithms (like AES) for both encryption and decryption, making it less efficient for encrypting large volumes of data.
   
2. High Computational Cost: RSA operations require heavy mathematical computations involving large prime numbers, which consume more CPU and memory resources.
   
3. Large Key Size Requirement: RSA needs very large keys (typically 2048 bits or more) to be considered secure, which increases storage and transmission overhead.
   
4. Inefficient for Bulk Data Encryption: RSA is not suitable for encrypting large datasets directly. It is typically used only for encrypting small pieces of data or symmetric keys.

Conclusion

RSA is one of the most widely used encryption algorithms and has played a key role in securing digital communication for decades. Its use of public and private keys makes it great for protecting sensitive data and verifying identities. While it’s powerful and reliable, RSA isn’t perfect—it can be slow, resource-intensive, and may face challenges from future technologies like quantum computing. Still, when used correctly, especially alongside other encryption methods, RSA is a solid choice for keeping information safe. 

Understanding how it works and where it fits best helps us make smarter decisions about digital security