Cryptography Reference
In-Depth Information
Remarks 8.9
1. OAEP can be used in combination with any one-way trapdoor permutation (not
necessarily RSA) to define an encryption scheme and RSA-OAEP is the result
of combining RSA with OAEP.
2. The requirement that 2
−
k
0
and 2
−
k
1
are negligible functions of
k
means that
neither
k
0
nor
k
1
should be 'too small' in comparison with
k
. For example, this
rules out the possibility that
k
0
=
O
(
ln
k
)
or
k
1
=
O
(
ln
k
)
, but the condition is
ln
2
k
satisfied whenever both
k
0
and
k
1
are
. For practical purposes, Bellare
and Rogaway mentioned in [19] that the adversary's running time should be
significantly smaller than 2
k
0
Ω(
)
160
(agreeing with the output length of the hash function SHA-1), which allows the
encryption, in a single operation, of messages of maximum length
l
equal to
k
steps and they suggested taking
k
0
=
k
1
=
−
321.
8.3.6.1 Security of RSA-OAEP
It is easy to realize that the previously described cryptanalytic attacks against plain
RSA no longer work against RSA-OAEP. Among other things, OAEP is probabilistic
and it does not preserve multiplicativity. Thus, neither the attack against small mes-
sage space nor the chosen ciphertext attack against plain RSA can be reproduced for
this scheme. The small encryption exponent attack is also prevented because OAEP
will produce a different encoding each time a given message is encrypted.
Observe that OAEP, defined by
(
,
)
→
||
m
r
s
t
, is an injective map:
k
−
k
0
−
k
1
−
1
k
0
k
−
1
OAEP
:{
0
,
1
}
×{
0
,
1
}
→{
0
,
1
}
(injectivity follows from the fact that, as seen in the description of
Dec
in Definition
8.13,
can be univocally recovered from
m
=
). Since the domain
of this function is a set of 2
k
−
k
1
−
1
elements and the codomain is a set of 2
k
−
1
elements, we see that the probability that a random string of
k
(
m
,
r
)
OAEP
(
m
,
r
)
−
1 bits belongs to
the image of OAEP (under the above parameters) is:
2
k
−
k
1
−
1
2
k
−
1
2
−
k
1
=
,
which, as we have mentioned, is negligible as a function of
k
. In addition, the
assumption that
G
and
H
are random oracles suggests that it may indeed be hard to
produce a
-bit string which is a valid OAEP encoding
m
(
−
)
=
||
k
1
r
s
of a mes-
1
without previous 'knowledge' of
m
. This property is called
plaintext awareness
and its precise formulation implies some subtleties whose details
we are not going to discuss here.
From the results in [19] it turns out that RSA-OAEP is only
weakly plaintext
aware
which, roughly speaking, means that the adversary cannot produce—without
knowing the plaintext—a valid ciphertext until it has seen another valid one. As a
k
−
k
0
−
k
1
−
∈{
,
}
sage
m
0
1
