Cryptography Reference
In-Depth Information
use of the random oracle model, which entails the assumption that the functions
G
and
H
in Definition 8.13 are random oracles. We have already mentioned that the
proof thus obtained is heuristic but it is nowwidely accepted that it provides valuable
evidence for the security of the scheme. This proof shows that a successful attack on
RSA-OAEP must either break the RSA assumption or exploit some particular prop-
erties of the functions
G
,
H
. Thus it can also be interpreted as providing assurance
of security under the hypothesis that the adversary is generic and does not exploit
any specific weaknesses of the hash functions used in practice. In addition, RSA-
OAEP has for now resisted attack and, for example, it has proved to be resistant to
Bleichenbacher's and similar attacks, which were not known at the time OAEP was
designed.
The other factor that must be taken into account in order to evaluate the level
of security provided by the proof in [80] is that, unfortunately, the reduction in this
proof is not tight. This means that the proof does not give assurance that breaking
RSA-OAEP with a 2048-bit modulus will require an amount of work similar to
that required for breaking the RSA assumption with the same modulus. Hence, as
mentioned in [155], in practical terms the proof is only meaningful for huge RSA
moduli with more than 4096 bits (in contrast with the fact that the smaller moduli
currently in use, such as 2048 bits, seem to be large enough to prevent breaking
of the RSA assumption). We stress, however, that the fact that the proof allows the
existence of a large gap between the hardness of the two problems does not mean
that such a large gap must actually exist and, so far, breaking RSA-OAEP in practice
seems no easier than breaking the RSA assumption (or even than factoring the RSA
modulus). As a consequence, although from a strict security-theoretic viewpoint it
would be perhaps advisable to use RSA moduli more than 4096 bits long, smaller
moduli continue to be used for efficiency and there is a certain consensus that, even
with these smaller moduli, RSA-OAEP is probably safe.
In conclusion, RSA-OAEP provides a good compromise between security and
efficiency and, although its security proof is heuristic, it adds confidence in the
scheme which, because of this fact, becomes preferable to other schemes for which
no such proof exists, and it is currently being extensively used in practice.
8.3.6.2 RSAES-OAEP from PKCS #1 v2.1
We are now going to describe the specific implementation of RSA-OAEP contained
in PKCS #1 v2.1 (called RSAES-OAEP, where the initials RSAES stand for "RSA
Encryption Scheme", see [154]), with a view towards its implementation in Maple
which is given below in
8.3.7
. Although the scheme fits in the general framework
described in Definition 8.13, there are some differences and specific requirements
that we are going to make explicit. We start with the following ingredients that will
be needed (here we use notation similar to that in [154]):
•
An RSA public key
and its corresponding private key. The modulus
n
will
be assumed to have byte length
k
. This scheme is byte-oriented, so that the length
of all bit strings will always be a multiple of 8 and these strings will be regarded
(
n
,
e
)
