Cryptography Reference
In-Depth Information
ing. In the random oracle model, all entities, including the adversary, have access to
one or several functions from
b
for certain specified values of
a
and
b
.
The security definitions are reformulated in this model in such a way that in the attack
experiment each of these functions is chosen at random from the set of all functions
from
a
{
,
}
{
,
}
0
1
to
0
1
b
(i.e., these functions are modeled as
random oracles
). In the
'real world' these random oracles are typically instantiated as cryptographic hash
functions but it is clear that the latter do not have the required randomness property.
Thus a security reduction in the random oracle model does not imply that an imple-
mentation of the scheme is actually secure. In fact, in [46] an example—admittedly
contrived and hard to imagine happening in practice—is given of a signature scheme
which is secure in the random oracle model, but insecure under any instantiation of
the random oracle.
Despite these reservations, the random oracle model is seen as a good heuristic.
A reductionist security proof in this model is considered better than no security
proof at all and designing systems based on such proofs when no other proofs are
available—or if they are, it is only for very inefficient schemes—is regarded as a
sound engineering principle (see [109, Chap. 13] for an in-depth discussion of these
issues).
We next describe the RSA-OAEP algorithm. The required ingredients are the
following:
a
{
0
,
1
}
to
{
0
,
1
}
•
The plain RSA encryption scheme.
Associatedwith a security parameter 1
k
, two parameters
k
0
,
k
1
such that 0
•
<
k
0
,
k
1
,
1, and both 2
−
k
0
, and 2
−
k
1
are negligible as functions of
k
.
k
0
+
k
1
<
−
k
l
, where
l
•
The plaintext space is
{
0
,
1
}
=
k
−
k
0
−
k
1
−
1. Thus
k
−
k
0
−
1
=
l
+
k
1
.
k
0
. These
functions are modeled as independent random oracles in the security analysis of
the scheme and in practice they are derived from a hash function such as SHA-256.
k
0
k
−
k
0
−
1
,
H
k
−
k
0
−
1
•
Two functions
G
:{
0
,
1
}
→{
0
,
1
}
:{
0
,
1
}
→{
0
,
1
}
Given these tools, a public-key encryption scheme may be constructed as follows:
Definition 8.13 RSA-OAEP
.
RSA-OAEP is the public encryption scheme
(
Gen
,
Enc
,
Dec
)
, where the algorithms
are defined as follows:
Gen
: On input 1
k
, with
k
even, run
Gen
RSA
(
1
k
/
2
•
)
to obtain
(
n
,
e
,
d
)
with
len
(here, for nota-
tional convenience and without loss of generality, the bit length of the modulus is
k
instead of 2
k
that we used in plain RSA).
(
n
)
=
k
. The public key is
(
n
,
e
)
and the private key is
(
n
,
d
)
l
and the public key
•
Enc
: Given the message
m
∈{
0
,
1
}
(
n
,
e
)
, the following values
are successively computed:
k
0
1.
r
←{
0
,
1
}
(so that
r
is a randomly chosen bit string of length
k
0
).
0
k
1
k
−
k
0
−
1
:=
(
)
⊕
(
||
)
∈{
,
}
⊕
2.
s
G
r
m
0
1
(where
denotes, as usual, the bitwise
Xor operation).
k
0
.
3.
t
:=
H
(
s
)
⊕
r
∈{
0
,
1
}
m
:=
k
−
1
.
4.
s
||
t
∈{
0
,
1
}
