We are now ready to state the RSA problem. Suppose you create a set of variables consisting of , , , , , , and . Call this set . It is created as follows:

The RSA problem consists of finding an such that , while only being given a subset of information regarding , namely the variables , , and . When and are very large, typically it is recommended that they are 1024 bits in size, the RSA problem is thought to be hard. You can see now why this is the case given the foregoing discussion.

An easy way to calculate when is simply by calculating . We know by the following calculations:

The problem is that we do not know the value , as it is not given in the problem. Hence, we cannot directly calculate to produce .

We might be able, however, to indirectly calculate from the order of , , as we know that . But by assumption the problem does not give a value for either.

Finally, the order could be calculated indirectly with the prime factors and , so that we can eventually calculate . But by assumption, the values and were also not provided to us.

Strictly speaking, even if the factoring problem within an RSA problem is hard, we cannot prove that the RSA problem is also hard. There may namely be other ways to solve the RSA problem than through factoring. However, it is generally accepted and assumed that if the factoring problem within the RSA problem is hard, that the RSA problem itself is also hard.

If the RSA problem is indeed hard, then it produces a one-way function with a trapdoor. The function here is . With knowledge of , anyone could easily calculate a value for a particular . However, it is practically impossible to calculate a particular value just from knowing the value and the function . The exception is when you are given a piece of information , the trapdoor. In that case, you can simply calculate to give .

Let's walk through a specific example to illustrate the RSA problem. I cannot select an RSA problem that would be considered hard under the conditions above, as the numbers would be unwieldy. Instead, this example is just to illustrate how the RSA problem generally works.

To start, suppose you select two random prime numbers 13 and 31. So and . The product of these two primes equals 403. We can easily calculate the order of 403. It is equivalent to .

Next, as dictated by step 3 of the RSA problem, we need to select a coprime for 360 that is greater than 2 and less than 360. We do not have to select this value randomly. Suppose that we select 103. This is a coprime of 360 as its greatest common divisor with 103 is 1.

Step 4 now requires that we calculate a value such that . This is not an easy task by hand when the value for is large. It requires that we use a procedure called the extended Euclidean algorithm.

Though I do not show the procedure here, it yields the value 7 when . You can verify that the pair of values 103 and 7 indeed meets the general condition through the calculations below.

Importantly, given Proposition 4, we know that no other integer between 1 and 360 for will produce the result that . Additionally, the proposition implies that selecting a different value for , will yield a different unique value for .

In step 5 of the RSA problem, we have to select some positive integer which is a smaller coprime of 403. Suppose that we set . Exponentiation of 2 by 103 yields the result below.

The RSA problem in this particular example is now as follows: You are provided with , , and . You now have to calculate such that . That is, you must find that the original value before exponentiation by 103 was 2.

It would be easy (for a computer at least) to calculate if we knew that . In that case, you could just determine as below.

The problem is that you have not been provided the information that . You could, of course, calculate from the fact that . The problem is that you are also not given the information that the order of . Finally, you could also calculate the order of 403 by calculating the following product: . But you are also not told that and .

Of course, a computer could still solve the RSA problem for this example relatively easily, because the prime numbers involved are not large. But when the primes become very large, it faces a practically impossible task.

We have now presented the RSA problem, a set of conditions under which it is hard, and the underlying mathematics. How does any of this help with asymmetric cryptography? Specifically, how can we turn the hardness of the RSA problem under certain conditions into an encryption scheme or a digital signature scheme?

One approach is to take the RSA problem and build schemes in a straightforward manner. For instance, suppose that you generated a set of variables as described in the RSA problem, and ensure that and are sufficiently large. You set your public key equal to and share this information with the world. As described above, you keep the values for , , , and secret. In fact, is your private key.

Anyone that wants to send you a message which is an element of could simply encrypt it as follows: . (The ciphertext here is equivalent to the value in the RSA problem.) You can easily decrypt this message by just calculating .

You might attempt to create a digital signature scheme in the same manner. Suppose that you want to send someone a message with a digital signature . You could just set and send the pair to the recipient. Anyone can verify the digital signature just by checking whether . Any attacker, however, would have a really difficult time creating a valid for a message, given that they do not possess .

Unfortunately, turning what is on its own a hard problem, the RSA problem, into a cryptographic scheme is not this straightforward. For the straightforward encryption scheme, you can only select coprimes of as your messages. That does not leave us with many possible messages, certainly not enough for standard communication. In addition, these messages have to be selected randomly. That seems somewhat impractical. Finally, any message that is selected twice will yield the exact same ciphertext. This is extremely undesirable in any encryption scheme and does not meet any rigorous modern standard notion of security in encryption.

The problems become even worse for our straightforward digital signature scheme. As it stands, any attacker can easily forge digital signatures just by first selecting a coprime of as the signature and then calculating the corresponding original message. This clearly breaks the requirement of existential unforgeability.

Nevertheless, with adding a bit of clever complexity, the RSA problem can be used to create a secure public key encryption scheme as well as a secure digital signature scheme. We will not enter into the details of such constructions here. [4] Importantly, however, this additional complexity does not change the fundamental underlying RSA problem on which these schemes are based.

[4] See, for example, Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, CRC Press (Boca Raton, FL: 2015), pp. 410–32 on RSA encryption and pp. 444–41 for RSA digital signatures.