Cryptography Reference
In-Depth Information
key.
9
Such a hash function is called a
full domain hash
, since the hash output is the
entire domain of the RSA trapdoor permutation. Constructing such a hash function is not
completely trivial; we refer to Section
3.6
. The signature on a message
m
in this case is
s
H
(
m
)
d
(mod
N
). These ideas were formalised by Bellare and Rogaway, but we present
the slightly improved security result due to Coron.
=
Theorem 24.6.1
RSA signatures with full domain hash (
FDH-RSA
) haveUF-CMA security
in the random oracle model (i.e., where the full domain hash function is replaced by a
random oracle) if the RSA problem is hard.
Proof
(Sketch) Let
A
be an perfect
10
adversary playing the UF-CMA game. We build a
simulator that takes an instance (
N,e,y
) of the RSA problem and, using
A
as a subroutine,
tries to solve the RSA problem.
The simulator in this case starts by running the adversary
A
on input (
N,e
). The
adversary will make queries to the hash function
H
, and will make decryption queries. The
adversary will eventually output a pair (
m
∗
,
s
∗
) such that
s
∗
is a valid signature on
m
∗
.To
explain the basic idea of the simulator we remark that if one could arrange that
H
(
m
∗
)
=
y
then (
s
∗
)
e
y
(mod
N
) and the RSA instance is solved.
The simulator simulates the random oracle
H
in the following way. First, the simulator
will maintain a list of pairs (
m
,H
(
m
)) where
m
was a query to the random oracle and
H
(
m
)
≡
)
∗
was the value returned. This list is initially empty. For each query
m
to the random oracle the simulator first checks if
m
has already been queried and, if
so, responds with the same value
H
(
m
). If not, the simulator chooses a random element
1
<r<N
, computes gcd(
r,N
) (and if this is not 1 then factors
N
, solves the RSA instance
and halts), computes
z
∈
(
Z
/N
Z
r
e
(mod
N
) and with some probability 1
p
(we determine
p
at
the end of the proof) returns
z
as
H
(
m
) and with probability
p
returns
yz
(mod
N
). The
information (
m
,H
(
m
)
,r
)isstored.
When the simulator is asked by the adversary to sign a message
m
it performs the
following: first, it computes
H
(
m
) and the corresponding value
r
.If
H
(
m
)
=
−
r
e
(mod
N
)
=
yr
e
(mod
N
) then the simulator fails.
Eventually, the adversary outputs a pair (
m
∗
,
s
∗
). If
H
(
m
∗
)
then the simulator returns
s
=
r
.If
H
(
m
)
=
yr
e
(mod
N
) where
r
is
=
known to the simulator, and if (
s
∗
)
e
(
s
∗
r
−
1
)
e
(mod
N
) and
so the simulator returns
s
∗
r
−
1
(mod
N
). Otherwise, the simulator fails.
To complete the proof it is necessary to argue that the simulator succeeds with non-
negligible probability. If the adversary makes
q
S
signing queries then the probability that
the simulator can answer all of them is (1
≡
H
(
m
∗
)(mod
N
), then
y
=
p
)
q
S
. The probability that the message
m
∗
corresponds to a random oracle query that allows us to solve the RSA problem is
p
. Hence,
the probability of success is (ignoring some other negligible factors) (1
−
p
)
q
S
p
. Assume
−
that
q
S
≥
1 and that
q
S
is known (in practice, one can easily learn a rough estimate of
q
S
by
experimenting with the adversary
A
). Choose
p
=
1
/q
S
so that the probability of success
9
In practice, one designs
H
:
{
0
,
1
}
∗
→{
0
,
1
,...,N
−
1
}
since the probability that a random element of
Z
/N
Z
does not lie in
(
Z
/N
Z
)
∗
is negligible.
10
The proof in the general case, where the adversary succeeds with non-negligible probability
, requires minor modifications.
