Public-Key Cryptography - Codes: The Guide to Secrecy from Ancient to Modern Times - page 189

In any case, a hash function h must be applied to the original message,
and the hash is signed. Thus, Mallory would have to find a message m such
that h ( m )= m , which he has a very low probability of doing if h is strongly
collision-resistant. However, if step 1 of the verification stage is not enforced,
then Mallory can forge certain signatures of his own choosing if he has a previous
legitimate message signed by Alice, as demonstrated in the following.
Suppose that a previous legitimate signature by Alice for a message m is
( β,γ ). Furthermore, suppose that Mallory is lucky and m − 1 (mod p

1) exists,
and Mallory chooses a message m 1 to forge. Mallory computes both congruences
t

−

m 1 m − 1 (mod p 1). By the Chinese remainder

theorem, he can also compute a solution x = β 1 to the congruences:

≡ − 1) and γ 1 ≡ tγ (mod p −

x ≡ βt (mod p − 1) and x ≡ β (mod p ) .

Thus,

α m 1 mm − 1 y β 1 β γ 1

1

α aβ 1 β tγ α aβt α rtγ α t ( aβ + rγ ) α tm α m 1 (mod p ) . ≡ ≡ ≡ ≡ ≡ ≡

Hence, ( β 1 ,γ 1 ) is accepted as a valid signature by the verification stage for m 1 ,
if step 1 in that stage is ignored. The essential nature of step 1 in the verification
stage was first observed in [26].
The value r chosen by Alice in the signing stage has to be kept secret, or
there is a total break of the system since Mallory can get a from knowledge of r .
Since β,γ , and m are known, then knowledge of r means that he may compute
a

≡ −

rγ ) β − 1 (mod p

−

1).
Also, if Alice is careless and uses r for the signing of two different messages,
then Mallory can get r and break the system as above. Here is how he gets r .
If sig k ( m 1 ,r )=( β,γ 1 ) and sig k ( m 2 ,r )=( β,γ 2 ), then
y β β γ 1

( m

α aβ + rγ 1 α m 1 (mod p ) ,

≡ ≡

and

y β β γ 2 α aβ + rγ 2 α m 2 (mod p ) .

≡ ≡

Therefore,

α m 2 − m 1 β γ 2 − γ 1 α r ( γ 2 − γ 1 ) (mod p ) .

≡ ≡

Hence,

m 2 − m 1 ≡ r ( γ 2 − γ 1 ) (mod p − 1) .

If gcd( p − 1 ,γ 2 − γ 1 )= g , then

m 2 − m 1 r ( γ 2 − γ 1 )

≡ (mod ( p − 1) /g ) .

g g

Thus,

m 2 − γ 2 − − 1

m 1 γ 1

r ≡ (mod ( p − 1) /g ) ,

g g

since gcd(( γ 2 − γ 1 ) /g, ( p − 1) /g ) = 1, and once we have r we can get a as above.