Digital Signatures - Introduction to Cryptography with Maple - page 540

σ

and hence, for to be a valid signature of m it would be necessary that

H ( m 1 ) H ( m 2 ) mod n = H ( m 1 m 2 ) mod n .

But any 'good' hash function is expected not to be multiplicative and hence this
equality does not hold except perhaps with negligible probability. Thus the chosen
message attack does not apply to the modified signature scheme.
Finally, one should also bear in mind that if an adversary is able to find a collision
for the hash function H , say messages m 1 , m 2 such that m 1

= m 2 and H ( m 1 ) =

, then it is also able to build a forgery under a chosen message attack. Indeed,
the adversary just queries the signing oracle on m 1 and, upon receiving

H ( m 2 )

σ as an answer,

outputs the forgery ( m 2 ,σ) . Since the pair ( m 1 ,σ) is accepted by the verification

algorithm and H . In order to prevent this

attack, whose practical version was presented in Example 5.12, the hash function H
must therefore be collision resistant.
Summing up these findings, we have that the hashed version of RSA signatures
is, in some sense, more secure than plain RSA signatures if a collision resistant hash
function is used (note that, except in pathological cases, a collision resistant hash
function will also be preimage resistant, see Sect. 5.6 ) . But this is only based on the
fact that certain obvious attacks against plain RSA are no longer applicable and it
is still a long way from allowing us to claim that these signatures are secure in the
formal sense we have defined. Therefore, even if we use the above constructions with
a hash function like SHA-256which is thought to be collision resistant in the practical
sense, we have absolutely no guarantee of security for the scheme. 2 However, this
construction points the way to other constructions that, as we shall see, may be shown
to be secure under suitable hardness assumptions.

( m 1 ) = H ( m 2 ) , so is the pair ( m 2 ,σ)

9.3.2 Hashed Elgamal Signatures

As in the case of RSA, a hash function may be used together with the Elgamal
signature scheme to obtain a “hashed version” in which messages are mapped by the
hash function into

Z p . We leave the details as an exercise.
Exercise 9.2 Write a detailed description of the Elgamal signature scheme that uses
a hash function H .

Let us now consider the security of the hashed version of Elgamal signatures. As
in the case of RSA signatures, it is easy to check that the simple key-only attack
that constructs an existential forgery is no longer possible with this version. Thus the
hashed version might be secure assuming that the DL problem is hard and that the
parameters and keys are properly chosen but, as happens in the RSA case, this has not

2 There is a theorem that ensures that if the underlying (not hashed) signature scheme is secure and
H is collision resistant, then the hashed signature scheme is also secure, but this is hardly of any
help in our examples because both plain RSA signatures and Elgamal signatures are insecure.