Digital Signatures - Introduction to Cryptography with Maple - page 541

been proved. Moreover, in Elgamal signatures, another possible source of insecurity
is the random element k

← Z p − 1 which is sometimes called an 'ephemeral key'. It
can be shown that if this element is not properly chosen, the scheme is insecure.
For example, if the adversary gains knowledge of the value of k used to sign the
message m , then it can compute rx mod ( p − 1 ) = ( H ( m ) − ks ) mod ( p − 1 )

and if gcd ( r , p − 1 ) = 1, which holds with high probability, it can compute the

r − 1 secret key x = ( H ( m ) − ks ) mod ( p − 1 ) thus obtaining a total break of the

scheme (if gcd )

has several solutions and the adversary can still find the correct one by trying all
of them in the equation y

( r , p − 1 ) = 1, then the equation rx ≡ ( H ( m ) − ks )( mod p − 1

g x mod p ). Also, if the same value of k is chosen

=

for two different messages m = m 1 (which happens with negligible probability if

k is randomly chosen), then r = r 1 and the two signed messages will be ( m , r , s ) ,

( . Thus the adversary may detect that the same value of k is used and, again,

it may compute it because s

m 1 , r , s 1 )

k − 1 − s 1 ≡ ( H ( m ) − H ( m 1 )) ( mod p − 1 ) and hence,

if gcd 1 (otherwise the adversary may check all the solutions of

this equation), the value of k is obtained as:

( s − s 1 , p − 1 ) =

s 1 ) − 1

k = ( s − ( H ( m ) − H ( m 1 )) mod ( p − 1 ).

Another thing that is very important for the security of Elgamal signatures is the
check that 0 p . As Bleichenbacher observed in [28], if this check is not

performed and a signature

< r <

h
is accepted, then the adversary can forge a signature on an arbitrary message m 1 with
H

( r , s ) corresponding to a message m such that H ( m ) =

(

m 1 ) =

h 1 , by carrying out the following computations:

h 1 h − 1 mod

• Set u := ( p − 1 ) (we assume here that h is invertible in Z p − 1 ).

• Set s 1 := su mod ( p − 1 ) .

• Use the Chinese remainder theorem to compute r 1 such that:

r 1 ≡ ru ( mod p − 1 )

(9.1)

r 1 ≡ r ( mod p )

Then ( r 1 , s 1 ) is accepted as a valid signature for m 1 because we have:

g h 1 g hu g ( ks + rx ) u g x

ru

g k

su

y ru r su ≡ ≡ ≡ ( ) ( ) ≡ ( mod p ), (9.2)

where all exponents may be regarded modulo p − 1, which is the order of g . Then the

congruences r 1 ≡ entail that we can replace

the terms ru and su appearing in the exponents by r 1 and s 1 , respectively. Similarly,
the congruence r 1

ru ( mod p − 1 ) and s 1 ≡ su ( mod p − 1 )

implies that we can replace the element r su mod ≡ r ( mod p )

Z p , appearing in ( 9.2 ), by r s 1 mod p . Thus the congruence ( 9.2 ) r s 1 mod p of p =

becomes:

y r 1 r s 1

g h 1 ≡ ( mod p ),

and the forged signature is accepted by the verification algorithm.