Digital Signatures - Understanding Cryptography - page 272

Existential Forgery Attack Against Elgamal Digital Signature

Alice Oscar Bob

k pr = d
k pub =( p , α , β )

)
←−−−−−−

( p , α , β )

←−−−−−−

( p , α , β

1. select integers i , j
where gcd( j , p − 1)=1
2. compute signature:
r

i j

≡ α β mod p

rj − 1

s ≡− mod p −

1
3. compute message:
x ≡ si mod p − 1

( x , ( r , s ))
←−−−−−−

verification:
t

r

r s ≡ β · mod p

x mod p :
valid signature!

since t ≡ α

The verification yields a “true” statement because the following holds:

r

r s t ≡ β · mod p

dr

r s

≡ α ·

mod p

dr ( i + dj ) s

≡ α · α mod p

( i + dj )( − rj − 1 ) dr

≡ α · α mod p

· α − ri j − 1

dr − dr

≡ α mod p

si mod p

≡ α

Since the message was constructed as x ≡ si mod p − 1, the last expression is equal

to

si x

α ≡ α mod p

which is exactly Alice's condition for accepting the signature as valid.
The attacker computes in Step 3 the message x , the semantics of which he cannot
control. Thus, Oscar can only compute valid signatures for pseudorandom messages.
The attack is not possible if the message is hashed, which is, in practice, very
often the case. Rather than using the message directly for computing the signature,
one applies a hash function to the message prior to signing, i.e., the signing equation
becomes:

r ) k − 1
E

s ≡ ( h ( x ) − d · mod p − 1 .