- What is the RSA algorithm for encryption and decryption?
- The elements of the RSA cryptography system: how does the RSA algorithm work
- The RSA algorithm: calculate RSA keys
- Calculate RSA encryption and decryption
- Weaknesses of RSA cryptography
- How to use our calculator for the RSA cryptosystem
- A complete example of calculating the RSA algorithm: from generating the keys to calculating the RSA decryption process
Our RSA calculator is a comprehensive tool to guide you in discovering the fundamental public key cryptosystem. In this article, you will learn:
- The basis of distributed key cryptography;
- What the RSA algorithm is;
- The operating principles of the RSA cryptography system;
- How to generate the RSA key (public and private); and
- How to calculate the decryption in the RSA algorithm.
The topic may look complex, but trust us: apart from some math (which we'll take care of), there's nothing to worry about! Let's go!
What is the RSA algorithm for encryption and decryption?
The RSA algorithm is an asymmetric cryptography protocol used to transmit data between two parties in a secure way. When properly configured, the RSA algorithm is theoretically unbreakable with current technology. However, it does lend itself to misuses that allow malicious parties to exploit some of its intrinsic weaknesses.
🙋 The RSA algorithm takes its name from the initials of the surnames of the three scientists that developed it: Rivest, Shamir, and Adleman. The trio created the algorithm in 1977 — Rivest and Shamir proposed functions for the computation of the keys to Adleman, the mathematician, who in turn validated them.
But what is asymmetric cryptography? Asymmetric cryptography, or public-key cryptography, is a class of protocols that employ two sets of keys to encrypt and decrypt a message. These two types are:
- Public keys, which are freely available; and
- Private keys, which are only known to the agent tasked with decrypting a message.
Asymmetric cryptography differs from symmetric cryptography — in the latter, there is a single private key (shared by both the sender and the receiver) used to encrypt and decrypt the message. In an asymmetric system, the fundamental decryption key never has to be transmitted and can be safely stored locally, removing the possibility of it being intercepted.
The elements of the RSA cryptography system: how does the RSA algorithm work
As with every asymmetric cryptography system, the RSA algorithm involves a set of defined elements:
- A sender (let's call her Alice, as the tradition goes); and
- A receiver (we'll call him Bob).
Alice generates the RSA keys: the public key (the encryption key) that she can set free for everyone to know and use, and the private key (the decryption key) that Alice will keep exclusively for her. Together with the public key, Alice also releases one number: a product of two prime numbers that were used in the RSA key generation. Bob receives both these values and can use them to answer Alice with encrypted messages that she alone can decrypt.
We mentioned prime numbers — we need them to calculate the RSA algorithm. Prime numbers are "special" numbers that you can divide only by themselves and by . Each and every positive integer can be written as a product of a set of prime numbers: we call this factorization of the number. Since prime numbers have no factors except and themselves, the product of two prime numbers has a very specific factorization: only those two prime numbers!
The factorization of the product of two large prime numbers with similar sizes is an extremely long task: in the worst case, we would have to check all the numbers up to the smaller prime factor. The inverse problem (multiplying two prime numbers) is straightforward. This is what makes this concept so appealing to cryptographers. As of factorization, the current record (as of February 2020) is the factorization of RSA-250, a 250 digits prime number: the endeavor took almost three thousand years of computational time, divided over multiple CPUs. State-of-the-art technology can't do much better!
However, the relatively recent field of quantum computing promises exciting breakthroughs: with the possibility of a "probabilistic" approach to computation, the future of factorization is yet to be decided!
🙋 If you are interested in the topic of factorization, visit our prime factorization calculator! There, we explain everything you need to know about how to perform this complicated mathematical operation.
The RSA algorithm: calculate RSA keys
Here we will discover how to calculate RSA keys! Let's be Alice for a while. Follow with us the steps to calculate the RSA cryptosystem keys:
Choose two prime numbers with the same or similar number of digits and call them and .
Compute their product: .
Compute the Carmichael function for the number . The mathematics of this step is not straightforward, but it luckily reduces to a simple operation: , where the function finds the least common multiple of the two arguments.
Choose , an integer number such that and that and are coprimes (which means they don't share any factor: learn more at the relatively prime calculator). Usually, you don't have to search for : good values are tabulated, and you can choose from them. Typical values for are (though this choice weakens the safety), , and .
Find as the modular multiplicative inverse of . This corresponds to solve the equation for . You can use the extended Euclidean algorithm in this step.
You are all set; now, follow the last two steps:
- Keep secret: this is the decryption exponent and you should never share it with anyone.
- Publish both and : these are both necessary parts of the public key. is also known as encryption exponent.
Calculate RSA encryption and decryption
Now that you generated your RSA private key and public keys, we can try our hand at RSA encryption and decryption. Both these operations will use modular exponentiation. Let's see how!
Suppose Alice wants to send you a message (in plaintext). How should he encrypt the message to make the transmission safe? The required operation is:
where is the encrypted message.
Modular exponentiation is a specific and neat mathematical operation. To compute it without making your head (or computer) explode, gradually build the encrypted message by computing:
where is the result of the same operation, but the step before, starting with . Do this times.
Bob can transmit freely, as breaking the encryption is theoretically impossible. Once you receive the message, decrypt it using the following operation:
Note that the RSA algorithm has an intrinsic limitation: the message can't exceed in size. If your message is larger than , you can break it into parts and send them separately. Once the transmission comes to an end, Bob would patch the received fragments of the message back together.
Weaknesses of RSA cryptography
Eve, the eavesdropper of many cryptography problems, can be a nuisance even for the RSA algorithm. Let's see some of the weaknesses that a malicious party can use to break your encryption:
Calculating the RSA encryption is a deterministic problem: encoding the same message with the same key always returns the same result. A solution to this problem is padding: adding random bytes at the beginning of your message to prevent the exploitation of repeated patterns.
The choice of RSA prime numbers and the key suffers from our less-than-perfect skills and comfort: while smaller make encryption easy, they also make cracking the message a far less challenging task!
The RSA algorithm is vulnerable to the padding oracle attack, a strategy that allows Eve to deduce the plaintext message or parts of it by interrogating one of the RSA agents about the veracity of a slightly modified version of the original padded message.
As the RSA algorithm turned 40 in 2017, we can find better and more secure encryption methods. The RSA algorithm remains a pillar of cryptography, and it's a perfect tool to showcase the power of this class of algorithms, but it's time to move on.
How to use our calculator for the RSA cryptosystem
Our RSA calculator implements the RSA algorithm in its entirety. To use it, follow these instructions:
- Input and . You can use our prime number calculator to find suitable values.
- We will calculate and .
- Choose a suitable value of from the drop-down menu.
- We will generate in the blink of an eye.
Now we can move on to the encryption and decryption protocols of the RSA algorithm.
- To calculate the RSA encryption, type your unencrypted numerical message in the field
- To calculate the decryption in our RSA, make sure that you generated the decryption exponent first, then write in the appropriate field the encrypted message: we will decrypt it and print you the original message.
A complete example of calculating the RSA algorithm: from generating the keys to calculating the RSA decryption process
Let's follow the RSA algorithm step by step, but this time we will give some values to our parameters. Set:
- ; and
Let's start by computing the product of and :
Now we can calculate the Charmichael function. As and are prime numbers, the operation is straightforward:
Phew, the first part is done. Let's generate the RSA keys now! Our modulo calculator can help you with these steps. First, choose the encryption key: we will go for . To find we need to compute the modular multiplicative inverse of modulo :
The result is not easy to find: you can use our inverse modulo calculator for a quick solution! In our case:
That's it! It's time to encrypt our first message. Let's take the first four decimal digits of pi: . Notice how, due to the nature of the encryption process, we can't use messages greater than : splitting them would be a reasonable option if this is the case. The encrypted message is:
Can we recover the original message from the number ? Try the decryption routine using the decryption exponent:
As we expected, it works!
Why is RSA public key?
The RSA algorithm is a public-key algorithm since it uses two keys in the encryption and decryption process:
- A public key for the encryption, available to everyone; and
- A private key for the decryption, this one accessible only by the receiver.
This method is much different from symmetric key cryptography, where both the sender and the receiver use the same key: this involves, at least once, the communication of the key, exposing it to potential attacks. The RSA algorithm is often used to communicate this key as it's deemed highly secure.
How do I calculate d in the RSA algorithm?
d, the private key of the RSA algorithm, you must know two values:
λ(N), the value of the Carmichael function for the primes
qused to generate the keys. This number is equal to
e, the encryption public key of the algorithm.
d is the modular multiplicative inverse of
λ(N): find it by solving the equation
e × d = 1 mod λ(N), or by using the extended Euler's algorithm.
What are the RSA keys for p = 17 and q = 23?
The keys are, for example,
d = 145 and
e = 17. To find these numbers:
Calculate the product of
p = 17and
q = 23:
N = 17 × 23 = 391.
Calculate the Charmichael function:
λ(N) = lcm(17,23) = 176
e = 17(
λ(N)must be coprimes).
das the modular multiplicative inverse of
e × d = 1 mod λ(N). The result is
d = 145.
N are the public key.
d is the private key.
Is the RSA algorithm secure?
Theoretically, the RSA algorithm is secure. As the key generation relies upon the product of two large prime numbers, we use the intrinsic difficulty of the factorization of such product to create a set of keys that is hard to crack even with complete knowledge of the public set of values. On the other hand, improper RSA algorithm implementations leave space for attacks.