Understanding the Digital Signature Algorithm (DSA)

The Digital Signature Algorithm is the algorithm specified for the DSS ( http://www.itl.nist.gov/fipspubs/fip186.htm ). The DSA's objective is to provide a signature and verify it in the form of two variables , r and s . A private key is needed in order to sign the data. In order to verify the signature, the public key is needed. There are generally three major steps that must be accomplished before signing data or verifying the signature:

The private and public keys must be available.
The parameters must be initialized (for DSA, they are called DSA parameters).
Before signing and verifying, the data must be passed through the update methods .

Figure 11-2 illustrates these steps.

Figure 11-2: Digital signature steps

Note	Recall from Chapter 7 that the DSA algorithm uses three integers, p , q , and g, and the signature variables r and s .

The first step in the algorithm is to initialize the DSA parameters p , g , and q along with the private key x and the public key y . The public variables p , q , and g are needed to compute and verify the signature. These variables are used to help compute the hash value with the private key and to verify the hash value with the public key. If the computation for verification does not work with the public variables p , q , and g , the public key y , the signature variables r and s , or the integer value representing the hash, the data is non-trustworthy. The public variables p , q , and g are considered public because they can be distributed to an entire group without compromising the algorithm. The signature variables r and s need the public variables plus the hash value and a randomly generated k value that is generated specifically for every signature. The private variable k must always be newly generated for each signature, and the hash value is taken from the data that is updated for the SHA-1 digest. Figure 11-3 shows the association of the signature generation variables.

Figure 11-3: Signature generation variables

Listing 11-1 (later in the chapter) demonstrates the algorithms for generating the variables. There are some things that must be emphasized . One thing to note is that there are many papers, algorithms, and specifications that list algorithms for probabilistic primality testing - used to generate and test for a prime number. The java.math.BigInteger class uses the isProbablePrime method to test the number for its primeness to a degree of specified certainty . The java.security.SecureRandom class will also generate a prime number guaranteed to the specified primeness. The higher the degree of certainty, say 90%, the longer the algorithm takes to ensure the number is prime. Many encryption algorithms require prime numbers or the algorithms will not work.

The p , g and q must satisfy the following requirements:

The public variables p and q must be prime numbers.
The q number is a randomly generated prime divisor, and p is its associated prime modulus .
The p must be a number with the length between 512 and 1024 bits. Most algorithms will denote the length by the letter l .
The q must fall between 2 ¹⁵⁹ and 2 ¹⁶⁰ .
The p and q numbers must have an association in which they can generate an integer g in the form g = h ^(p-1)/q mod p . The variable h is normally a randomly generated integer between 0 and p - 1.

The sample program tries many combinations until the numbers can fit into the preceding restrictions. Many algorithms generate the public variables when the keys are generated and pass them through the public and private key classes. After the public variables are generated, the public and private keys can be generated. The private key, represented by x , is a randomly generated integer greater than 0 and less than q . The public key y is generated by the equation

y = g ^x mod p

The public key is a product of the private key and forms a relationship where only x can be associated with y and vice versa. After the keys and public variables are formed , a message can be signed. The verification and signing of the message cannot be accomplished without most of these variables. The verification requires the public variables and the public key y . The signing of the message requires the public variables and the private key x . The message signature and verification are dependent on one other variable besides the public variables and keys, and that is the message itself. The signature is an r and s variable. The r variable is calculated from the equation

r = (g ^k mod p) mod q

These are the public variables and a randomly generated integer k . The s variable is calculated by the using the message hash with the SHA-1 message digest in SHA(M) and the private key x as in the following equation:

s = (k ^-1 (SHA(M) + xr)) mod q

The verification of the message fails without the correct private key and the correct message digest. The goal of the signature verification is to generate a verification value represented by v and to compare it to the variable r of the signature. If they are not equal, the verification fails. See Figure 11-4 for the verification generation variables.

Figure 11-4: Verification generation variables

The variable v does not need the private variable k and the private key that were used to generate the digital signature. The associated public key and the message digest, generated again by the SHA-1 algorithm with the message, are the only new variables needed. The calculation of v is quite lengthy and is broken down into multiple steps.

The first step is to compute the variable w , which is from the signature s variable from the equation w = (s) ^-1 mod q .
The next step is to use the message digest to calculate the u1 variable in the equation u1 = ((SHA(M)) w) mod q , which is used to verify the message digest.
The next equation is used to add the signature r in the calculation to produce the u2 variable with the equation u2 = (( r )w)mod q .
Finally, all these calculations, including the public variables and the public key, are used to calculate the v variable with the equation from the previous steps with v = (((g) ^u1 (y) ^u2 )mod p)mod q .

The variable v is checked against the signature variable r, and they should be equal unless something has been altered or used incorrectly, such as the associated public key. If the variable v matches the variable r , the correct digest and public key were used in the calculation. If the correct public key was used in the calculation, the matching private key was used to generate the signature. By knowing that the public key matches a specific user's private key, there is a guarantee that the message came from that user .

If the message digest computed from the data checks - that is, it validated - there is a guarantee that the data has not changed. The only piece missing from DSA is the guarantee that the key came from a specific user, but that is the purpose of the key exchange. The DSS may embed the public key in a message, such as in Pretty Good Privacy (PGP) or many other means. For this reason, the NIST has updated the DSS to include the RSA digital signature and ECDSA with their appropriate key exchanges ( http://cscr.nist.gov/ publications /fips/fips186-2/fips186-2-change1.pdf ).

Table of content

Java Security Solutions

ISBN: 0764549286
EAN: 2147483647

Year: 2001
Pages: 222

Authors: Rich Helton, Johennie Helton

BUY ON AMAZON

Building Web Applications with UML (2nd Edition)

SQL Hacks

Postfix: The Definitive Guide

An Introduction to Design Patterns in C++ with Qt 4

File System Forensic Analysis

.NET-A Complete Development Cycle