Cryptography Reference
In-Depth Information
14.2.1.4
Security Analysis
Since its invention in 1977, the security of the RSA public key cryptosystem has
been subject to a lot of public scrutiny. Many people have challenged and analyzed
the security of RSA (e.g., [7]). While no devastating vulnerability or weakness has
been found so far, almost three decades of cryptanalytical research have still given
us a broad insight into its security properties and have provided us with valuable
guidelines for the proper implementation and usage of RSA. In this section, we
give a brief security analysis of the RSA asymmetric encryption system. We start
with some general remarks before we turn to specific attacks and provide some
conclusions and recommendations for the practical use of RSA.
General Remarks
If we ask whether the RSA asymmetric encryption system is secure, we must first
define what we mean with the term
secure
. Because an adversary can always mount
a chosen plaintext attack against an asymmetric encryption system, we must require
that the RSA asymmetric encryption system is secure under such an attack, meaning
that an adversary who is able to mount a chosen plaintext attack is not able to
decrypt a given ciphertext, or, equivalently, that it is computationally infeasible for
him or her to invert an RSA trapdoor permutation (without knowledge of the private
key that represents the trapdoor). This is known as the RSAP (see Definition 7.9),
and it is assumed to be intractable (if the modulus
n
is sufficiently large and the
plaintext message
m
is an integer between 0 and
n
1). Note that the two conditions
mentioned in parentheses are very important from a security point of view:
−
•
If
n
were small, then an adversary could try all elements of
Z
n
until the correct
m
was found.
8
•
Similarly, if the plaintext message
m
was known to be from a small subset of
[0
,n
1], then an adversary could also try all elements from this subset until
the correct
m
was found.
−
But even if
n
is sufficiently large and
m
is between 0 and
n
−
1, then the
adversary can still try to find the correct
m
(by a brute-force attack). In this case,
however, the adversary must employ a search algorithm that has a running time of
n
, which is exponential in the input length log
n
. Consequently, such a brute-force
This basically means that he or she can compute
m
e
(m o d
n
) for every possible plaintext
message
m
∈
Z
n
. If the resulting value matches
c
, then he or she has found the correct plaintext
message.
8
