RSA Calculator

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!

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.

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.

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 $1$. 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 $1$ 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!

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:

1. Choose two prime numbers with the same or similar number of digits and call them $p$ and $q$.

2. Compute their product: $N = p\times q$.

3. Compute the Carmichael function for the number $N$. The mathematics of this step is not straightforward, but it luckily reduces to a simple operation: $\lambda(N) = \mathrm{lcm}(p-1,q-1)$, where the $\mathrm{lcm}$ function finds the least common multiple of the two arguments.

4. Choose $e$, an integer number such that $2< e<\lambda(N)$ and that $e$ and $\lambda(N)$ 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 $e$: good values are tabulated, and you can choose from them. Typical values for $e$ are $3$ (though this choice weakens the safety), $17$, and $65537$.

5. Find $d$ as the modular multiplicative inverse of $e\ \mathrm{mod}\ \lambda(N)$. This corresponds to solve the equation $e\times d = 1\ \mathrm{mod}\ \lambda(N)$ for $d$. You can use the extended Euclidean algorithm in this step.

You are all set; now, follow the last two steps:

• Keep $d$ secret: this is the decryption exponent and you should never share it with anyone.
• Publish both $N$ and $e$: these are both necessary parts of the public key. $e$ is also known as encryption exponent.

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 $M$ (in plaintext). How should he encrypt the message to make the transmission safe? The required operation is:

where $C$ 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 $C$ by computing:

where $C_\mathrm{prev}$ is the result of the same operation, but the step before, starting with $C_\mathrm{prev}=1$. Do this $e$ times.

Bob can transmit $C$ 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 $N=p\times 1$ in size. If your message is larger than $N$, 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.

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 $e$ suffers from our less-than-perfect skills and comfort: while smaller $e$ 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.

Our RSA calculator implements the RSA algorithm in its entirety. To use it, follow these instructions:

• Input $p$ and $q$. You can use our prime number calculator to find suitable values.
• We will calculate $N$ and $\lambda(N)$.
• Choose a suitable value of $e$ from the drop-down menu.
• We will generate $d$ 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 message.
• 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.

Let's follow the RSA algorithm step by step, but this time we will give some values to our parameters. Set:

• $p = 89$; and
• $q = 67$.

Let's start by computing the product of $p$ and $q$:

Now we can calculate the Charmichael function. As $p$ and $q$ 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 $e=17$. To find $d$ we need to compute the modular multiplicative inverse of $e$ modulo $\lambda(N)$:

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: $M=1415$. Notice how, due to the nature of the encryption process, we can't use messages greater than $N$: 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 $1,\!032$? Try the decryption routine using the decryption exponent:

As we expected, it works!

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.

To calculate d, the private key of the RSA algorithm, you must know two values:

1. λ(N), the value of the Carmichael function for the primes p and q used to generate the keys. This number is equal to lcm(p,q); and
2. e, the encryption public key of the algorithm.

d is the modular multiplicative inverse of e modulo λ(N): find it by solving the equation e × d = 1 mod λ(N), or by using the extended Euler's algorithm.

The keys are, for example, d = 145 and e = 17. To find these numbers:

1. Calculate the product of p = 17 and q = 23:

   N = 17 × 23 = 391.

2. Calculate the Charmichael function:

   λ(N) = lcm(17,23) = 176

3. Choose e = 17 (e and λ(N) must be coprimes).

4. Calculate d as the modular multiplicative inverse of e modulo λ(N): solve e × d = 1 mod λ(N). The result is d = 145.

The number e and N are the public key. d is the private key.

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.