Cryptography Reference
In-Depth Information
contains a private key) it is necessary to be able to factor an RSA modulus. So
long as there remains no efficient method of factoring
n
pq
, obtaining an RSA
private key directly from an RSA public key will be regarded as hard.
=
RSA SECURITY SUMMARY
The security of RSA thus depends on two separate functions being one-way:
The RSA encryption function
. The RSA encryption function is a trapdoor one-
way function, whose trapdoor is knowledge of the private key. The difficulty
of reversing this function without the trapdoor knowledge is believed (but not
known) to be as difficult as factoring.
Multiplication of two primes
. The difficulty of determining an RSA private key
from an RSA public key is known to be equivalent to factoring the modulus
n
.
An attacker thus cannot use knowledge of an RSA public key to determine an
RSA private key unless they can factor
n
. Because multiplication of two primes
is believed to be a one-way function, determining an RSA private key from an
RSA public key is believed to be very difficult.
If either of these two functions turns out
not
to be one-way then RSA will be
broken. In particular, if someone develops a technique for factoring efficiently
(breaking the second of the one-way functions) then RSA will no longer be safe
for use. Such a situationwill arise if a practical quantumcomputer can be built (see
Section 5.4.4). It is for this reason that the latest results on progress in the design
of factorisation algorithms are often quoted in the press next to articles predicting
security disasters. Rather like the race between designers of machines that can
perform exhaustive key searches and the recommended length of symmetric
keys, there is a similar race between designers of factorisation algorithms and
the recommended length of the modulus
n
for use in RSA. We discuss how large
n
should be in Section 5.4.3.
5.2.4
RSA in practice
As with most of the cryptographic primitives that we discuss, our explanation
of RSA is simplified in order to emphasise the main design aspects. There are a
number of attacks on specific instances of RSA that we will not outline in any
detail here. For example, there are:
• attacks when
d
is very small;
• attacks when
e
is very small;
• attacks if the same message is sent to many receivers with the same low value
of
e
;
• various side-channel attacks (see Section 1.6.5).
Just as with other cryptographic primitives that we have discussed, it is essential
that RSA is not deployed in any real implementation in exactly the way that we
