Digital signatures are a different application of the asymmetric algorithms that we discussed in Chapter 15. You use an asymmetric key pair to create a "signature" for a message by adding a signature function to the asymmetric algorithm. The recipient can verify the signature using a verification function. Asymmetric algorithms that support signature and verification functions are digital signature algorithms. Each digital signature is specific to an individual message or document, and if Alice signs a message, Bob can be confident that Eve has not sent him a forgery.
Figure 16-1 provides an overview of using digital signatures, which work as follows:
Figure 16-1. Using asymmetric signature algorithms to provide message authentication
Notice that Alice, the sender of the message, creates the key pair and retains the private key; this is different from asymmetric encryption, where the recipient (Bob) is responsible for key creation. Digitally signing a message creates a separate piece of data, which Alice sends to Bob along with the message.
The relatively slow performance of asymmetric algorithms means that Alice does not sign the entire message she wants to send; instead, she creates a cryptographic hash code for the message and signs this instead. Subject to the limitations of hash code security (discussed in Chapter 13), signing hash code for a message is equivalent to signing the message itself, but is much faster, because the hash code is less data to process with the asymmetric algorithm. Figure 16-2 illustrates the way that Alice creates the signature by using her private key, the data hash code, and the asymmetric signature function.
Figure 16-2. Using a hash code as the basis for creating a digital signature
Bob verifies the signature by creating his own hash code and using the asymmetric signature verification and Alice's public key. Bob cannot verify the signature if the message is altered in any way, meaning that Eve cannot secretly tamper with the contents and Bob cannot alter a message and later claim that Alice had signed the altered version. Alice and Bob must use the same hash code algorithm; otherwise, Bob will not be able to verify valid signatures. Figure 16-3 illustrates how Bob verifies a signature.
Figure 16-3. Using a hash code as the basis for verifying a digital signature
Digital signatures allow more than one person to sign a message or document, such as a contract. Each person signs the message using the basic protocol we described, and sends their signature to all of the other signatories. If Alice and Bob wish to sign a digital contract, the basic protocol that they use is as follows:
Should there be any dispute, a third party (perhaps a judge or other arbitrator) can use Alice and Bob's pubic keys to verify that both Alice and Bob have signed the same contract. Neither party can alter the contract (because then the hash code would not match) nor deny that they signed the contract (because the third party can verify each separate signature).
16.1.1 Digital Signature Security
Digital signatures have two objectives: they must be cryptographically secure and they must provide equivalent security features to an ink signature on a printed document. We summarize the security features of digital signatures as follows:
From these features, you can see that digital signatures provide a reasonable analogue to a physical signature. You can also see that the entire security of digital signatures is dependent on the following assumptions:
We know that these assumptions are optimistic. Eve can find Alice's secret key by testing every possible value and find a document that results in a specific hash code if she creates and tests enough variations. In Chapter 13 and Chapter 14, we found that Eve can do these things, but that they can take her a very long time to accomplish. The security of digital signatures, like every other aspect of cryptography, is based on probabilities and effective key management. When using digital signatures, you should be aware that they are susceptible to the same attacks as data hash codes and asymmetric keys.
The final point raises a very serious issue. Alice should not be able to sign a document and then later claim that she did not. Relying on digital signatures means making another assumption: Alice is responsible for all signatures created with her private key, even if Eve is able to guess the secret value.
The problem that this presents is that Eve may be able to guess Alice's private key by brute force without Alice being aware that her private key is compromised. Eve could then sign documents using Alice's signature, but Alice would not find out that this was happening until it was too late. For example, if Eve signs a digital money order to herself, Alice will not know that money is missing from her account until she receives her next bank statement.
We need Alice to be responsible for signatures created with her key; otherwise, digital signatures would be worthless, and Alice could simply deny signing documents that are not in her favor. On the other hand, because it is possible to guess the value of Alice's key, we run the risk of holding her responsible for signatures that she really did not create. There is currently no solution to this problem, which is a fundamental barrier to the adoption of digital signatures.
16.1.2 The .NET Framework Digital Signature Algorithms
The .NET Framework includes two asymmetric algorithms that support digital signatures, one is the RSA algorithm that we discussed in Chapter 15; this algorithm defines functions for both data encryption and digital signatures.
The second algorithm is the Digital Signature Algorithm (DSA), published as a U.S. FIPS in May 1994. DSA supports digital signatures but not data encryption. Initially created to provide a standard algorithm for digital signatures for federal projects, DSA has gained support in commercial projects gradually but still lags behind RSA in terms of adoption.
The creators of DSA based their design, in part, on the ElGamal algorithm that we introduced in Chapter 15. In Section 16.4 of this chapter, we add support for signatures and signature formatting to our ElGamal implementation.
All asymmetric algorithms include a key generation protocol, similar to the ones that we discussed in Chapter 15. If an algorithm supports both encryption and digital signatures, then the same keys can be used by the encryption, decryption, signature, and verification functions; following the key generation protocol results in keys that can be used for all asymmetric cryptographic tasks.
16.1.3 Creating Digital Signatures
The hash code created from the document to be signed is usually formatted before being processed by the algorithm's signature function; this ensures that the specified key pair pads the hash code to the maximum size that can be signed. See Chapter 15 for more information about how to determine the length of a key and how the length affects the amount of data that algorithm functions can process. The act of formatting a hash code before it is signed also protects the digital signature from certain types of cryptographic attack.
The most commonly used signature-formatting protocol is PKCS #1, which we summarize as follows:
Once you have created the formatted data, sign it using the signature function. In this section, we continue our illustrations using the RSA protocol. The RSA signature function is shown below, where s is the signature value and m is the formatted data to sign:
s = mdmodn
The values d and n are parameters of the RSA key; see the previous chapter for details about RSA key pairs and how to create them. The RSA key length required to create a digital signature depends on the size of the hash code that the selected hashing algorithm produces. For example, MD5 produces a 128-bit hash code, and with the 18 bytes of the algorithm ID and the 11 bytes of data that PKCS #1 formatting adds as a minimum, you need a key that is able to process 360-bits of data. Therefore, the smallest key length that you can use to sign a PKCS #1-formatted MD5 hash code is 368 bits.
We won't walk through the computation required to create a digital signature because the numeric values that make up a 368-bit key are simply too large to print on a page; see Chapter 15 for an example of using the RSA functions with small key lengths.
To verify a signature, take the document you have received and create a PKCS #1-formatted hash code, following the protocol we described previously. Use the RSA verification function, shown below, where m2 is the verification result, s is the digital signature, and e and n are the RSA public key parameters:
m2 = semodn
When you verify the signature, the value of m2 should be the PKCS #1-formatted hash code that you created from the document you received with the signature. If someone has tampered with the document in transit, the value of the hash code that you created will be different then the output of the verification function, and you should reject the signature.
Notice that the RSA signature and verification functions are the same as the encryption and decryption functions that we described in Chapter 15; the signature and decryption functions are identical, as are the verification and encryption functions. This relationship does not apply to all asymmetric algorithms, and we describe a very different approach when we extend our ElGamal implementation in the Section 16.4.
The DSA algorithm specification requires that PKCS #1 formatting is always used, and all hash codes are generated using the SHA-1 hashing algorithm. The SHA-1 algorithm ID is still included as part of the PKCS #1 formatting.