Omni Calculator logo

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 11. 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 11 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:

  1. Choose two prime numbers with the same or similar number of digits and call them pp and qq.

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

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

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

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

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

  • Keep dd secret: this is the decryption exponent and you should never share it with anyone.
  • Publish both NN and ee: these are both necessary parts of the public key. ee 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 MM (in plaintext). How should he encrypt the message to make the transmission safe? The required operation is:

C=Me mod NC = M^e\ \mathrm{mod}\ N

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

C=(M×Cprev) mod NC = (M\times C_\mathrm{prev})\ \mathrm{mod}\ N

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

Bob can transmit CC freely, as breaking the encryption is theoretically impossible. Once you receive the message, decrypt it using the following operation:

M=Cd mod N=(Me)d mod N\begin{split} M &= C^d\ \mathrm{mod}\ N\\ &= \left(M^e\right)^d\ \mathrm{mod}\ N \end{split}

Note that the RSA algorithm has an intrinsic limitation: the message can't exceed N=p×1N=p\times 1 in size. If your message is larger than NN, 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 ee suffers from our less-than-perfect skills and comfort: while smaller ee 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 pp and qq. You can use our prime number calculator to find suitable values.
  • We will calculate NN and λ(N)\lambda(N).
  • Choose a suitable value of ee from the drop-down menu.
  • We will generate dd 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.

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:

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

Let's start by computing the product of pp and qq:

N=p×q=89×67=5, ⁣963N = p\times q = 89\times67=5,\!963

Now we can calculate the Charmichael function. As pp and qq are prime numbers, the operation is straightforward:

λ(N)=lcm(89,67)=264\lambda(N) = \mathrm{lcm}(89,67) =264

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=17e=17. To find dd we need to compute the modular multiplicative inverse of ee modulo λ(N)\lambda(N):

d=e1 mod λ(N)d = e^{-1}\ \mathrm{mod}\ \lambda(N)

The result is not easy to find: you can use our inverse modulo calculator for a quick solution! In our case:

d=171 mod 264=233d = 17^{-1}\ \mathrm{mod}\ 264 = 233

That's it! It's time to encrypt our first message. Let's take the first four decimal digits of pi: M=1415M=1415. Notice how, due to the nature of the encryption process, we can't use messages greater than NN: splitting them would be a reasonable option if this is the case. The encrypted message is:

C=Me mod N=1, ⁣41517 mod 5, ⁣963=1, ⁣032\begin{split} C &=M^e\ \mathrm{mod}\ N\\ &=1,\!415^{17}\ \mathrm{mod}\ 5,\!963\\ & = 1,\!032 \end{split}

Can we recover the original message from the number 1, ⁣0321,\!032? Try the decryption routine using the decryption exponent:

M=Cd mod N=1, ⁣03217 mod 5, ⁣963=1, ⁣415\begin{split} M &=C^d\ \mathrm{mod}\ N\\ &=1,\!032^{17}\ \mathrm{mod}\ 5,\!963\\ & = 1,\!415 \end{split}

As we expected, it works!

FAQ

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?

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.

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:

  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.

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.

Davide Borchia
Parameters
p
q
N
λ(N)
e
Select...
d
Encryption
Message
Encrypted message
Decryption
Received encrypted message
Decrypted message
Check out 661 similar math calculators
2D distance30 60 90 triangle3 sides triangle area… 658 more
People also viewed…

Free fall

Our free fall calculator can find the velocity of a falling object and the height it drops from.

Perpendicular line

Our perpendicular line calculator finds the equation of a line perpendicular to another.

Secretary problem (Valentine's day)

Use the dating theory calculator to enhance your chances of picking the best lifetime partner.

Standard form to general form of a circle

Standard form to general form of a circle calculator lets you convert the equation of a circle in standard form to general form.
Copyright by Omni Calculator sp. z o.o.
Privacy, Cookies & Terms of Service