Public-Key Encryption - Everyday Cryptography - page 165

are thus assuming that we do not know the trapdoor. Thus to assess the difficulty
of determining the plaintext directly from the ciphertext, we need to assess the
effectiveness of the one-way function that lies at the heart of RSA.
We need to take a closer look at the function that is being used for RSA
encryption. The encryption process in RSA involves computing the function:
C P e mod n = .

An attacker who observes C , and has knowledge of e and n (but not d ), needs to
work out what the value P is. Computing P from C , e and n is regarded as a hard
problem (fortunately!) and thus the encryption function of RSA is believed to be
a one-way function.
Although this hard problem might look familiar, it is in fact the first time
that we have come across it. It is commonly referred to as the RSA problem .
It superficially resembles the discrete logarithm problem that we discussed in
Section 5.1.4, however, there are two subtle differences:

1. In the discrete logarithm problem we are given C , P and n and we try to find e .
In the RSA problem we are given C , e and n and we try to find P .
2. In the discrete logarithmproblem that we discussed in Section 5.1.4weworked
modulo a prime, whereas in the RSA problem our modulus is the product of
two primes.

These are important differences. Hence the RSA encryption function andmodular
exponentiation are regarded as two different one-way functions. In fact the RSA
encryption function is more closely related to the one-way function consisting of
squaring a number modulo n that we mentioned in Section 5.1.4. In this case we
are not squaring, but we are raising numbers to the power e . The difficult reversal
in this case is not taking the square root, but taking the e th root modulo n .
Nobody knows precisely how difficult the RSA problem is to solve, but it is
widely believed to be equivalent in difficulty to factoring. Thus the RSA encryption
function is widely believed to be a trapdoor one-way function, where the trapdoor
is knowledge of the private key d .

DETERMINING THE PRIVATE KEY DIRECTLY FROM THE PUBLIC KEY
There is one way in which an attacker could determine an RSA private key d from
an RSA public key ( n , e ). This is by:

1. factoring n , in other words working out what p and q are;
2. running the Extended Euclidean Algorithm to determine d from p , q and e .
In fact it can be shown that the problem of factoring and the problem of
determining an RSA private key directly from an RSA public key are equivalent
in the sense that if we can solve one of these problems then we can solve the other
problem.
Consequently, in order to obtain a private key using mathematical techniques
(rather than doing something much easier such as stealing a hardware token that