Cryptography: Theory and Practice:Signature Schemes | Modern Cryptography: Theory and Practice

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

Another misuse of the system is to use the same value k in signing two different messages. This also makes it easy for Oscar to compute a and hence break the system. This can be done as follows. Suppose (γ, δ₁) is a signature on x₁ and (γ, δ₂) is a signature on x₂. Then we have

and

Thus

Writing γ = α^k, we obtain the following equation in the unknown k:

which is equivalent to

Now let d = gcd (δ₁ - δ₂, p - 1). Since d | (p - 1) and d | (δ₁ - δ₂), it follows that d | (x₁ - x₂). Define

Then the congruence becomes:

Since gcd(δ′, p′) = 1, we can compute

Then value of k is determined modulo p′ to be

This yields d candidate values for k:

for some i, 0 ≤ i ≤ d - 1. Of these d candidate values, the (unique) correct one can be determined by testing the condition

6.3 The Digital Signature Standard

The Digital Signature Standard (or DSS) is a modification of the ElGamal Signature Scheme. It was published in the Federal Register on May 19, 1994 and adopted as a standard on December 1, 1994 (however, it was first proposed in August, 1991). First, we want to motivate the changes that are made to ElGamal, and then we will describe how they are accomplished.

In many situations, a message might be encrypted and decrypted only once, so it suffices to use any cryptosystem which is known to be secure at the time the message is encrypted. On the other hand, a signed message could function as a legal document such as a contract or will, so it is very likely that it would be necessary to verify a signature many years after the message is signed. So it is important to take even more precautions regarding the security of a signature scheme as opposed to a cryptosystem. Since the ElGamal Scheme is no more secure than the Discrete Logarithm problem, this necessitates the use of a large modulus p. Certainly p should have at least 512 bits, and many people would argue that the length of p should be 1024 bits in order to provide security into the foreseeable future.

However, even a 512 bit modulus leads to a signature having 1024 bits. For potential applications, many of which involve the use of smart cards, a shorter signature is desirable. DSS modifies the ElGamal Scheme in an ingenious way so that a 160-bit message is signed using a 320-bit signature, but the computations are done using a 512-bit modulus p. The way that this done is to work in a subgroup of of size 2¹⁶⁰. The assumed security of the scheme is based on the belief that finding discrete logarithms in this specified subgroup of is secure.

The first change we make is to change the “-” to a “+” in the definition of δ, so

This changes the verification condition to the following:

If gcd(x + aγ,p - 1) = 1, then δ^-1 mod (p - 1) exists, and we can modify condition (6.1), producing the following:

Now here is the major innovation in the DSS. We suppose that q is a 160-bit prime such that q | (p - 1), and α is a qth root of 1 modulo p. (It is easy to construct such an α: Let α₀ be a primitive element of , and define α = α₀^(p-1)/q mod p.) Then β and γ will also be qth roots of 1. Hence, any exponents of α, β and γ can be reduced modulo q without affecting verification condition (6.2). The tricky point is that γ appears as an exponent on the left side of (6.2), and again — but not as an exponent — on the right side of (6.2). So if γ is reduced modulo q, then we must also reduce the entire left side of (6.2) modulo q in order to perform the verification. Observe that (6.1) will not work if the extra reductions modulo q are done. The complete description of the DSS is given in Figure 6.3.

Notice that is necessary that (mod q) since the value δ^-1 mod q is needed to verify the signature (this is analogous to the requirement that gcd(δ, p-1) = 1 when we modified (6.1) to obtain (6.2)). If Bob computes a value δ ≡ 0 (mod q) in the signing algorithm, he should reject it and construct a new signature with a new random k. We should point out that this is not likely to cause a problem in practice: the probability that δ ≡ 0 (mod q) is likely to be on the order of 2^-160, so for all intents and purposes it will almost never happen.

Figure 6.3 Digital Signature Standard

Here is a small example to illustrate.

Example 6.3

Suppose we take q = 101 and p = 78q + 1 = 7879. 3 is a primitive element in , so we can take

Suppose a = 75; then

Now, suppose Bob wants to sign the message x = 22 and he chooses the random value k = 50, so

Then

and

The signature (94, 97) on the message 22 is verified by the following computations:

Hence, the signature is valid.

When the DSS was proposed in 1991, there were several criticisms put forward. One complaint was that the selection process by NIST was not public. The standard was developed by the National Security Agency (NSA) without the input of U. S. industry. Regardless of the merits of the resulting scheme, many people resented the “closed-door” approach.

Of the technical criticisms put forward, the most serious was that the size of the modulus p was fixed at 512 bits. Many people would prefer that the modulus size not be fixed, so that larger modulus sizes could be used if desired. In reponse to these comments, NIST altered the description of the standard so that a variety of modulus sizes are allowed, namely, any modulus size divisible by 64, in the range from 512 to 1024 bits.

Table of Contents