Introduction
A digital signature serves many purposes. It doesn't just validate data, but is truly a fingerprint from the sender. The digital signature depends on the key pair, the data of the message, and a signature. All these elements are mapped to each other so that if any item changes, the signature does not pass verification. The originator of the data hashes the data with his or her private key to create a signature. A specific public key that is generated from the private key can be used to verify the signature. Verifying the signature matches the data, signature, and public key.

If the signature passes verification, it is guaranteed that the message has not changed and that the public key used came from the user who generated the signature. The exchange of the private and public key becomes the crucial point in identifying the user. A person might deny that his or her private key encrypted the message and assert that someone else sent you the public key. If the exchange can be guaranteed and the message signature is verified, it is relatively easy to prove that a specific user sent the message and hard for the user to deny sending the message.

Because of this type of verification and the need to ensure authenticity of messages for legal reasons, state legislatures and many legal organizations have been looking at digital signatures to provide a means of identifying a message. Because more and more contract agreements are being handled electronically, many organizations need a way to verify the origin of a message from a person or an organization.

With the threat of hackers and others manipulating data, it becomes difficult to prove that a message originated from a specific user. Digital signatures offer a solution. Many companies are specializing in digital signatures for these reasons. The digital signature can be combined with other protocols such as Public Key Infrastructure (PKI) and the X.509 certificate.

The RSA Security Company, which provides the RSA key exchange algorithm, was one of the first vendors to provide digital signatures. While many vendors were working with RSA on a digital signature, the National Institute of Standards and Technology (NIST) decided to provide a standard for the community. The NIST published a proposed Federal Information Processing Standard (FIPS) for the Digital Signature Standard (DSS) in August 1991.

At the time of its conception, the DSS received a lot of criticism from RSA, simply because RSA was already trying to submit its own proposal for a digital signature standard using the RSA key exchange. The NIST did not adopt the RSA key exchange but instead introduced a new keying algorithm that was part of the Digital Signature Algorithm (DSA). A lot of companies at the time, such as IBM and Sun, invested a lot of time and money into the RSA Digital Signature Algorithm. The NIST received a lot of criticism because during this time, in January 1992, the NIST also invented the SHA-1 message digest to support the DSS. The criticism came from the fact that the SHA-1 was based on the MD4 algorithm, and now it seemed as though the DSS was being based on some of the work from RSA.

More criticism came from the fact that the National Security Agency (NSA) also worked with NIST to develop the algorithm, that it was a suggested public standard, and that the original key length was 512 bits. As with many other collaborations from the NSA, many organizations felt that the NSA had a crack for the algorithm so that it could maintain surveillance of data. There is still a lot of paranoia that the use of a public key and public variables can be used in combination to break the signature. Because some of the key exchanges, such as the RSA and Elliptic Curve key exchange, appear stronger, the NIST has added these algorithms to the DSS.

Even though there is paranoia surrounding some of the history of DSS, the DSS provides a global standard for exchanging signatures and for how the DSA works. Because of the DSS, many protocols such as X.509, Privacy Enhanced Email (PEM), and Pretty Good Privacy (PGP) have evolved. The digital signature, like so many other aspects of security, is not an entity unto itself but is used with several other building blocks of security.

The digital signature provides an organization the capability to protect itself with the combination of all the other building blocks.

Understanding the Digital Signature Algorithm (DSA)

The Digital Signature Algorithm is the algorithm specified for the DSS. 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.

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.

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 2159 and 2160.
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 = gx 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 = (gk 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.

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.

Getting the RSA Digital Signature Algorithm

The latest FIPS186-2 now lists the RSA digital signature (RSA ds) as one of the three recommended algorithms for digital signatures. The FIPS186-2 simply says to see the ANSI x9.31 for documentation.

Recall from the key agreement algorithm that RSA had three public variables called p, q, and the modulus n. The public key is represented by {n,e} and the private key is {n,d}. If the private key {n,d} is not available, it will have to be computed from the p, q, dP, dQ, and qInv variables with the Chinese Remainder Theorem (CRT) key. 
If the CRT key is used, the variable s can be generated from the following equations:

•    s2 = mdQ mod q.
•    h = qInv(s1 - s2) mod q.
•    s = s2 + hq.

When the signature is generated, a digest is computed for the data and returned as the variable m. The signature s is computed from the following equation:

s = md mod n

To verify the message, the algorithm will need the public key {n,e}, the capability to recompute the same digest from the data as m, and the signature s. The message digest is recomputed as the test variable a. The b variable will be generated using the following equation from the signature and the public key:

b = se mod n

The variables a and b match if the signature, keys, and data are valid. The a value is computed as the integer returned as the message digest. Unlike the DSS algorithm, the RSA algorithm may use the MD2, MD4, MD5, or SHA-1 digest. In order to account for the possibility of different message digests, the message digest algorithm identifier is returned as part of the signature information block.

Other variables that are included in the format of the signature are block type, encryption-block formatting, and a padding block. RSA not only has a key algorithm and signature algorithm, but also an encryption algorithm. Since RSA includes an encryption algorithm, the signature block may also be encrypted with the RSA cipher.

In order to format the signature block, the PKCS#1 includes a padding string and algorithm to ensure the correct format size when hashing and using the RSA encryption.

Understanding the Elliptic Curve Digital Signature Algorithm

The ECDSA generates a signature with a private key and verifies the signature with a public key. The ECDSA starts by selecting an integer value k to be multiplied by a Point P = (x1, y1) along the elliptic curve. Just like the DSS algorithm, an r and s variable is calculated and saved for the signature. Since x1 is an integer point on the x coordinate system, r can be computed by the following equation:

r = x1 mod n

The variable s is calculated by the SHA-1 hash on the message represented by h(m) and the private key d. The s equation becomes

s = k-1 (h(m) + dr) mod n

The signature is the r and s variable. To verify the signature, the ECDSA needs the r, s, the message for the digest, and the public key (E, P, n, Q). The verify method is initialized with the public key. Then the message needs to be passed through the algorithm's update method to store the hashed message. The verify method is then called, passing in the signature containing the r and s. The verify method hashes the message and converts the digest into an integer m. Just like the DSA algorithm the ESDSA contains multiple calculations. The next variable after m to be calculated is the variable w, which is calculated using the equation

w = s -1 mod n

The next two variables are u1 and u2 calculated by

u1 = mw mod n and u2 is u2 = rw mod n

The point along the elliptic curve is computed from these calculations. Taking the public key variables P and Q, the additive property is used from u1 and u2 to form u1P + u2Q. The point from u1P + u2Q is computed in the x-y coordinate system as the point (x0, y0). The x0 coordinate along the x-axis is used to find the result in v = x0 mod n. If the variable v in the verify method equals the variable r in the signature generator, the message and keys used are valid.

Some of the equations between the ECDSA and DSA appear similar because both algorithms are based on the ElGamal signature algorithm by signing the equation

s = k-1 {h(m) + dr} mod m

Both the ECDSA and DSA use the SHA-1 message digest as the defined digest to use. The ECDSA uses public variables from the public key (E, P, n, Q) that are used to compute the intermediate variables w, u1, and u2. Looking at DSA, similar calculations were accomplished using public variables p, q, and g. These values are needed to produce the algorithms without the private key. Both of these algorithms share the complexity of trying to generate the checks with just the public variables. The biggest difference that exists between these two algorithms is the type of equations. The ECDSA is elliptical and uses geometric properties. In other words, checks consist of checking if points fall on a curve as opposed to checking if the values are greater than 0 and less than q, as in the DSA.

The DSA is easier from a computational standpoint in that numbers can be checked to be less than, greater than, or equal to. The computational complexity of ECDSA makes the algorithms more secure. Also, because the numbers that can be used in ECDSA are limited to the points along a curve (versus the DSA using prime numbers that must fit together), the ECDSA is computationally faster.

Implementing the Digital Signature Algorithm (DSA)

The JDK 1.4 supports only the DSA and RSA out of the box for providing service providers. The JDK 1.4 is easily extensible to add more service providers from other vendors or to build a custom one for algorithms such as the ECDSA. The ECDSA is a very popular algorithm, and there are service providers for the algorithm from companies such as Certicom and Cryptix. For many organizations, using the DSA and RSA signatures is sufficient.

The first step in using the JDK 1.4 framework is to generate a key pair using the java.security.KeyPairGenerator class's getInstance method. By passing in the variable DSA, a key pair for the DSA algorithm is created. If RSA is passed in as the parameter, a pair of RSA keys is generated. Likewise, the java.security.Signature class's getInstance method initializes the signature class by passing in a SHA1withDSA parameter. To generate RSA signatures, the MD5withRSA, MD2withRSA, and SHA1withRSA parameters can be used depending on which message digest needs to be implemented. Whether the signature is being used for generating the signature or verifying the signature will determine which key, public or private, will be initialized into the algorithm.

All signature algorithms require that the data be passed through the update method for both verifying and generating the signature. After the message data has been updated, a signature can be returned from the sign method, or a signature can be verified by passing it in the verify method.

One of the features found in the JDK 1.4 is the java.security.SignedObject class. The SignedObject class is created with a digital signature passed into it and a serialized object. The purpose of the SignedObject class is to protect the runtime object with an associated signature. If the integrity of the object is compromised, then the signature detects it and an exception is thrown. The SignedObject provides a deep copy of the serialized object so a digest can be created and the integrity checked. Features like this one and the capability to use a DSA and RSA signature out of the box make Java a powerful programming language.

The essence of the digital signature is to provide a key pair that can verify a digest and generate a signature for verification. If the data, signature or key doesn't match, then the message is corrupted. The public key that can validate the message can only come from the specific person who signed the message using his or her private key. If a different public key is used, then the signature will not verify. The signature on the message, in most cases, will be unique and can easily verify whether changes have been made to the message in transit. Because the validation on the sender's private key, data, and signature can be accomplished, it is normally assumed that it can be guaranteed that the message came from a specific user.