Cryptography Reference
In-Depth Information
attack is prohibitively expensive in terms of computational power even for a very
strong adversary.
Next, it is important to note that the security of the RSA asymmetric encryp-
tion system is intimately related to the IFA (see Definition 7.10) and the intractability
assumption of the IFP (see Definition 7.11). Clearly, the RSAP is not harder to solve
than the IFP, because an adversary who can factorize
n
(using, for example, a brute-
force attack) can also compute the private exponent
d
from the public key (
n, e
).
9
However, it is not known whether the converse is also true (i.e., whether an algorithm
to solve the IFP can be efficiently constructed from an algorithm to solve the RSAP).
There is some evidence that such a construction may not exist if the public exponent
is very small, such as
e
=3or
e
=17[8]. This result suggests that—for very
small public exponents—the RSAP may be easier to solve than the IFP. For arbitrary
public exponents, however, the question of computational equivalence between the
RSAP and the IFP remains unanswered.
Having in mind the notion of polynomial-time reductions (see Definition
6.10), we can say that the RSAP polytime reduces to the IFP (i.e., RSAP
≤
P
IFP), but that the converse is not known to be true. This suggests that the RSAP
and the IFP are not computationally equivalent, or at least that we cannot prove
such a relationship (this is why we don't prove a theorem about a computational
equivalence relationship between the RSAP and some other problem assumed to be
intractable, as we do for the other basic systems). The best we can do is to prove that
the following problems or tasks are computationally equivalent:
•
Factorize
n
;
•
Compute
φ
(
n
) from
n
;
•
Determine
d
from (
n, e
).
This means that an adversary who knows
φ
(
n
) or
d
can also factorize
n
.Italso
means that there is no point in hiding the factorization of
n
(i.e., the prime factors
p
and
q
) from an entity that already knows
d
. In either case, we conclude that if an
efficient algorithm to factorize
n
, compute
φ
(
n
), or determine
d
existed, then the
RSA asymmetric encryption system would be insecure.
Even if the RSA asymmetric encryption system were secure in the sense
discussed earlier (i.e., that the RSAP is computationally equivalent to the IFP), then
it could still be true that it “leaks” partial information about the plaintext messages
that are encrypted. For example, it may be the case that certain plaintext message
bits are easy to predict from a given ciphertext. Consequently, one may ask whether
the RSA asymmetric encryption system provides security to every individual bit of
9
Refer to Section 7.3 for an overview about the current state of the art of integer factorization
algorithms.
