Cryptography Reference
In-Depth Information
9.3.1 Hashed RSA Signatures
A hashed version of RSA signatures is obtained by adding to the public key—or as
a system parameter which is publicly known—a hash function
H
}
∗
→ Z
n
,
where
n
is the modulus of the RSA public key (alternatively, one may consider a
family of hash functions indexed by the RSA moduli and such that the function
corresponding to the modulus
n
maps
:{
0
,
1
}
∗
Z
n
). The scheme is then similar to
the one in Definition 9.4, except that the signing and verification algorithms now act
as follows:
{
0
,
1
to
•
Sign
: On input a private key
sk
=
(
n
,
d
)
and a message
m
∈ Z
n
, compute the
signature:
d
mod
n
σ
:=
Sign
(
sk
,
m
)
=
H
(
m
)
∈ Z
n
.
•
Ve r
: On input a public key
pk
=
(
n
,
e
)
, a message
m
∈ Z
n
, and a signature
σ
∈ Z
n
, check whether
e
mod
n
H
(
m
)
=
σ
∈ Z
n
and set
Ve r
(
pk
,
m
,σ)
:=
1 if this condition holds and
Ve r
(
pk
,
m
,σ)
:=
0
otherwise.
We see that this scheme is very efficient—assuming that
H
is efficient—for it only
has to compute a hash operation and a modular exponentiation for both signature
and verification.
Let us now go back to security. A natural question is then: what have we gained,
from a security standpoint, by using the hashed version of these schemes? We can get
some insight by looking, for example at the two attacks against plain RSA described
above. The first one consisted simply of picking
σ
← Z
n
and computing
m
:=
e
mod
n
σ
. If an adversary
tries to repeat this key-only attack for the hashed version of RSA signatures, it runs
into trouble because in order to obtain a valid message/signature pair starting with
σ
∈ Z
n
, it now has to find a message
m
∈ Z
n
to obtain a valid message/signature pair
(
m
,σ)
∈ Z
n
such that
e
mod
n
H
(
m
)
=
σ
.
If we assume that the hash function
H
is preimage resistant, the forger will be unable
to find such an
m
with non-negligible probability and the attack will be unsuccessful.
Let us now consider the chosen message attack against plain RSA signatures that
allows the forger to obtain a selective forgery. The adversary chooses two messages
m
1
,
m
2
∈ Z
n
that are different from the message
m
it wants to sign and satisfy
m
1
m
2
mod
n
m
and queries the signing oracle about these messages, obtaining
two valid message/signature pairs
=
(
m
1
,σ
1
)
,
(
m
2
,σ
2
)
. But now it is no longer true
that
σ
:=
σ
1
σ
2
mod
n
is a valid signature for
m
because we have that
e
e
σ
1
σ
2
mod
n
=
H
(
m
1
)
H
(
m
2
)
mod
n
,
