Digital Signatures - Understanding Cryptography - page 273

10.4 The Digital Signature Algorithm (DSA)

The native Elgamal signature algorithm described in this section is rarely used in
practice. Instead, a much more popular variant is used, known as the Digital Signa-
ture Algorithm (DSA) . It is a federal US government standard for digital signatures
(DSS) and was proposed by the National Institute of Standards and Technology
(NIST). Its main advantages over the Elgamal signature scheme are that the signa-
ture is only 320-bit long and that some of the attacks that can threaten the Elgamal
scheme are not applicable.

10.4.1 The DSA Algorithm

We introduce here the DSA standard with a bit length of 1024 bit. Note that longer
bit lengths are also possible in the standard.

Key Generation

The keys for DSA are computed as follows:

Key Generation for DSA

1. Generate a prime p with 2 1023 < p < 2 1024 .
2. Find a prime divisor q of p 1 with 2 159 < q < 2 160 . −

3. Find an element α with ord( α )= q , i.e., α generates the subgroup with

q elements.
4. Choose a random integer d with 0 < d < q .
5. Compute

d

β ≡ α mod p .

The keys are now:
k pub =( p , q , α , β )

k pr =( d )

The central idea of DSA is that there are two cyclic groups involved. One is the
large cyclic group

Z p , the order of which has bit length of 1024 bit. The second one
is in the 160-bit subgroup of Z p . This set-up yields shorter signatures, as we see in

the following.
In addition to the 1024-bit prime p and a 160-bit prime q , there are two other bit
length combinations possible for the primes p and q . According to the latest version
of the standard, the combinations shown in Table 10.1 are allowed.
If one of the other bit lengths is required, only Steps 1 and 2 of the key generation
phase have to be adjusted accordingly. More about the issue of bit length will be said
in Sect. 10.4.3 below.