In the world of computer science, there are many moving parts, with updates and new theories being established all the time. One such algorithm that surprisingly doesn’t fit this mold is the RSA algorithm. RSA has actually been around for almost 50 years and has remained virtually unchanged during this time. As one of the most commonly used encryption algorithms, it’s something all programmers should know, especially those working in cybersecurity. In this article, we’ll explain what RSA is, how it works, and the principles behind it.
What is the RSA Algorithm?
RSA was introduced in 1977 and is named after its founders – Ron Rivest, Adi Shamir, and Leonard Adleman. It was a revolutionary algorithm at the time and continues to be widely used today. The basic principle behind it is using a pair of keys, known as public and private keys. While the public key is used for encryption, the private key is responsible for decryption. The sender encrypts the message, and the receiver decrypts it using the private key. By using the product of two prime numbers as the encryption key, a high level of security is achieved. This is because it’s extremely computationally intensive to try to calculate the private key just using the public key. Because it works on two different keys, RSA is called an asymmetric cryptography algorithm.
How Does the RSA Algorithm Work?
As mentioned, there is a public key and a private key involved. The public key consists of a modulus of the product of prime numbers, and what is called an encryption exponent. The modulus is calculated as the remainder when one number is divided by another. In this case, we raise the numerical representation of the message to the power of the exponent and divide it by the product of the prime numbers. The decryption key has a decryption exponent and modulus. When the message is raised to the power of the decryption exponent, the original message is decoded.
As a simple example, consider a webpage that is requesting data from a server. The server receives the public key from the website, which encrypts it using a public key. This message is sent back to the website, which decrypts it using its private key. Somebody else may have access to the public key, but without having the private key, the data is secure and can’t be decrypted by a third party.
Since the security relies on the fact it’s hard to factorize a particularly large integer, it’s very dependent on the key size. Encryption strength exponentially increases with key size. Currently, keys are typically 1024 or 2048 bits in length, which are unfeasible to decrypt as it stands.
Step-By-Step Process of the RSA Algorithm
The steps of the RSA algorithm can be summarized as such:
- Key generation
- Encryption
- Decryption
Let’s examine these in order to see how they work.
Key Generation
First, we need to generate both the public and private keys using prime numbers. We must choose two distinct primes, which are denoted as p and q.
The product of these is called n so we have n = p * q. We then use Euler’s totient function to determine the range of possible values we can have for the exponent part of the key. Euler’s totient function is given as:
φ(n) = (p-1) * (q-1)
where φ(n) is the function.
The chosen exponent, e, must be relatively prime to the function, which means that it doesn’t have any common factors with p and q except for 1.
An example
For example, let’s consider p = 11 and q = 3.
In this case, n = 11 * 3 = 33.
Therefore, φ(n) = 10 * 2 = 20.
We can choose 3 as a relatively prime number for e.
Next comes a relatively complicated step. We need to calculate the modular multiplicative inverse of e modulo φ(n). This will be our private exponent, used for decryption. In simple terms, modulo calculates the remainder when one number is divided by another, in this case, e by φ(n). Using e as 3 and φ(n) as 20, we would obtain a remainder of 3, as 3 cannot divide into 20.
The modular multiplicative inverse, d, of e modulo φ(n), is a number that when multiplied by e and divided by mod φ(n), the remainder is 1.
This can be written as:
ed / mod φ(n) ≡ 1 or ed ≡ 1 mod φ(n), where ≡ means these terms are congruent. This means that both ed and 1 have the same remainder when divided by φ(n).
In other words, there exists a value for d where ed is divisible by φ(n). If we subtract 1 from ed, we get:
ed – 1 = 0 mod φ(n)
We know e = 3, so therefore 3d – 1 must be divisible by φ(n), which is 20.
If we test out integers starting at 1, we find that the smallest value of d is 7. We can check this by calculating (7 * 3) – 1, which equals 20.
Therefore, we have our public key (n, e), or (33, 3), and our private key (n, d), or (33, 7).
Extended Euclidean Algorithm
Alternatively, we can use the Extended Euclidean Algorithm to find d, which is ideal for more complicated cases. This algorithm gives the coefficients of Bézout’s identity and computes the greatest common divisor of two integers, a and b, such that:
ax + by = gcd(a,b)
We know that in our case, the gcd must be equal to 1 for e and φ(n) to be relatively prime. By substituting a with e and b with φ(n), we get:
3x + 20y = 1
We start by dividing 20 by 3, which can be written as such:
20 = 3(6) + 2, where 2 is the remainder.
Next, we continue by moving the divisor to the left, and the remainder to where the divisor was, and doing the same calculation:
3 = 2(1) + 1
Once we have a remainder of 1, the process is complete. Now, we need to substitute to find the value of d.
3 = 2(1) + 1 can also be written as 3 – (20 – 3(6)) = 1, because 2 = 20 – 3(6), as per the previous equation.
We can now simplify this to 3(7) – 20 = 1. Therefore, we can deduce that d = 7, which matches up with the value from before.
Now we have our public and private keys, we can move on to the next step – encryption.
Encryption
First, we need an example message to encrypt. For simplicity’s sake, let’s go with “HELLO”. We can’t use ASCII representation here, since the resulting messages would be larger than the modulus, n. So, let’s go with a simpler representation, using the standard alphabet. We can’t use 0 or 1 here, because these will give the same cipher value. Therefore, we’ll begin at 2. This message would then be equivalent to H = 9, E = 6, L = 13, and O = 16.
The encryption formula is ciphertext = (plaintext^e) mod n, where e = 3.
So, for example, ciphertext_H = (9^3) mod 33, which is equal to 3.
The rest of the letters are equal to 18, 19, and 4.
We concatenate these, which basically means combining them, to give “3 18 19 19 4”.
Next, let’s move on to how this message would be decrypted.
Decryption
The process for decryption is essentially the reverse of encryption and uses our decryption exponent, d. Continuing with the previous example, we have “3 18 19 19 4”, and calculate:
plaintext = (ciphertext^d) mod n, where d = 7.
For example, for “H”, we have (3^7) mod 33, which is equal to 9. This is our original message.
Continuing with the rest gives us the rest of our original characters – 6, 13, 13, and 16.
What Are the Uses of the RSA Algorithm?
The RSA algorithm isn’t perfect, but it has many uses, as long as it’s implemented properly. Some of the most common uses are:
- Securely communicating over the internet, email, and storing data. RSA is used as part of the SSL/TLS protocols for secure exchange between web servers.
- Exchanging secret keys to be used for symmetric encryption.
- Digital signatures, to verify that a message hasn’t been tampered with.
Implementation in Python
Here’s an example of a simple RSA implementation in Python:
import rsa
(public_key, private_key) = rsa.newkeys(256)
message = "Hello, RSA!"
encrypted_message = rsa.encrypt(message.encode(), public_key)
decrypted_message = rsa.decrypt(encrypted_message, private_key)
decrypted_message = decrypted_message.decode()
print("Original Message:", message)
print("Encrypted Message:", encrypted_message)
print("Decrypted Message:", decrypted_message)First, we import the rsa module, then generate public and private keys using the “newkeys()” function. We input the message “Hello, RSA!”, and encode it into byte form using “encode()”. The message is then encrypted using “rsa.encrypt()”, then decrypted using “rsa.decrypt()”. The original message, encrypted message, and decrypted message can be seen in the image output.
©History-Computer.com
What Are the Disadvantages of the RSA Algorithm?
As previously mentioned, the security of RSA heavily depends on the key size. Using as large a key size as possible is recommended, but this can lead to slower performance. What’s more, the current consensus is that 1024-bit keys, which are commonly used, may no longer be sufficient to guard against potential attacks. This is because computing power keeps increasing, along with the ability to implement stronger factoring algorithms to break the ciphers. 4096-bit keys have actually been successfully created, but the principle stands that any encryption algorithm is theoretically vulnerable. Even when using proper padding, an error message will be received when the padding is incorrect. This can help hackers deduce the plaintext after enough iterations.
However, it should be said that any algorithm is potentially vulnerable, and a lot of the issues that arise with RSA are due to improper implementation. This often includes generating keys randomly, using an insufficient key size, using primes of a specific form, using the same key for encryption and signing, or using small exponents (3 is commonly chosen).
There are some alternatives that are often preferred over RSA. These include elliptic curve cryptography (ECC), the Diffie-Hellman (DH) algorithm, advanced encryption standard (AES), and digital signature algorithm (DSA).
Wrapping Up
RSA is one of the most established and used encryption algorithms and has been around since the late 70s. If used correctly, it provides a relatively simple and secure way for encrypting, mostly in internet communications and digital signing. The algorithm uses modular arithmetic and prime numbers to create a secure pair of keys. Best practices include using a large key size, implementing the algorithm correctly, not using primes of a specific form or randomly generated keys, and using padding.
The image featured at the top of this post is ©Thapana_Studio/Shutterstock.com.
