Cryptography Reference
In-Depth Information
7.8 Attacks
There have been numerous attacks proposed against RSA since it was invented in
1977. None of the attacks are serious, and moreover, they typically exploit weak-
nesses in the way RSA is implemented or used rather than the RSA algorithm itself.
There are three general attack families against RSA:
1. Protocol attacks
2. Mathematical attacks
3. Side-channel attacks
We comment on each of them in the following.
Protocol Attacks
Protocol attacks exploit weaknesses in the way RSA is being used. There have been
several protocol attacks over the years. Among the better known ones are the attacks
that exploit the malleability of RSA, which was introduced in the previous section.
Many of them can be avoided by using padding. Modern security standards describe
exactly how RSA should be used, and if one follows those guidelines, protocol
attacks should not be possible.
Mathematical Attacks
The best mathematical cryptanalytical method we know is factoring the modulus.
An attacker, Oscar, knows the modulus
n
, the public key
e
and the ciphertext
y
.His
goal is to compute the private key
d
which has the property that
e
·
≡
(
n
).
It seems that he could simply apply the extended Euclidean algorithm and compute
d
. However, he does not know the value of
d
mod
Φ
(
n
). At this point factoring comes in:
the best way to obtain this value is to decompose
n
into its primes
p
and
q
. If Oscar
can do this, the attack succeeds in three steps:
Φ
Φ
(
n
)=(
p
−
1)(
q
−
1)
d
−
1
≡
e
mod
Φ
(
n
)
y
d
x
≡
mod
n
.
In order to prevent this attack, the modulus must be sufficiently large. This is the
sole reason why moduli of 1024 or more bit are needed for a RSA. The proposal of
the RSA scheme in 1977 sparked much interest in the old problem of integer fac-
torization. In fact, the major progress that has been made in factorization in the last
three decades would most likely not have happened if it weren't for RSA. Table 7.3
shows a summary of the RSA factoring records that have occurred since the begin-
ning of the 1990s. These advances have been possible mainly due to improvements
in factoring algorithms, and to a lesser extent due to improved computer technology.
