Digital Signature Systems - Contemporary Cryptography - page 386

Algorithm 15.2 The DSA Sign algorithm.

( p, q, g, x, m )
k ∈ R Z q
r

≡ ( g k (mod p )) (mod q )

≡ ( k − 1 ( h ( m )+ xr )) (mod q )
( r, s )

s

Z q .

• First, a number k must be randomly selected from

( g k (mod p )) (mod q ).

• Second, k must be used to compute r ≡

•

Third, the message m must be hashed with h , and the result h ( m ) must be
used to compute s

≡

( k − 1 ( h ( m )+ xr )) (mod q ). In this case, k − 1 is the

inverse of k modulo q .

Z q represents the digital signature for
m (or h ( m ), respectively). Note that r and s are both 160-bit numbers. This is in
contrast to an ElGamal signature, in which r and s are both of the size of p and m
(e.g., 1,024 bits). Consequently, a DSA signature is about 320 bits long, which is
more than six times shorter than a corresponding ElGamal signature.
In our toy example, we assume that the signatory wants to digitally sign a
message m with a hash value h ( m )=6.TheDSA Sign algorithm then randomly
selects k =7, computes r

The pair ( r, s ) with r and s elements of

(2 7 (mod 23)) (mod 11) = 2, determines 7 − 1 (mod

≡

11) = 8, and computes s ≡ (8(6 + 3 · 2)) (mod 11) = 8. Consequently, the DSA

signature for h ( m )=6is (2 , 8).

15.2.3.3 Signature Verification Algorithm

The DSA Verify algorithm is deterministic and can be used to verify DSA signatures.
It takes as input a verification key ( p, q, g, y ), a message m , and a DSA signature
( r, s ), and it generates as output one bit saying whether ( r, s ) is a valid DSA
signature for m with respect to ( p, q, g, y ). The algorithm first verfies that r, s

∈ Z q

(i.e., 0 <r

Z q , then the signature
is considered to be invalid and must be rejected accordingly. If, however, the two
conditions are satisfied, then the algorithm must compute the following values:

<q and 0 <s <q ). If r or s is not in

s − 1 (mod q ) w ≡

u 1 ≡ h ( m ) w (mod q )

u 2 ≡ rw (mod q )