Digital signatures are a different
application of the asymmetric algorithms . 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 1 provides an overview of using digital
signatures, which work as follows:
Alice selects an asymmetric signature algorithm and follows the key
generation protocol to create a new pair of keys. She keeps her
private key secret and sends the public key to Bob.
Alice composes a message and creates a signature using her private
key.
Alice sends the message and the signature to Bob.
Bob uses Alice's public key to verify the signature.
If the signature is valid, Bob can be confident that:
Alice is truly the author of the message.
Eve has not altered the message contents.
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 , 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 2 illustrates the way that Alice creates
the signature by using her private key, the data hash code, and the
asymmetric signature function.
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 3 illustrates how Bob verifies
a 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:
Alice and Bob agree on the contents of the contract they will sign.
Alice creates a hash code for the contract and signs it with her
private key.
Bob creates a hash code for the contract and signs it with his
private key.
Alice and Bob exchange digital signatures and public keys.
Alice checks that Bob has used the correct hash code (and therefore
has signed the expected version of the contract) and verifies the
signature using his public key.
Bob checks that Alice has used the correct hash code and verifies the
signature using her public key.
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).
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:
Eve should not be able to forge Alice's digital
signature.
Eve cannot create a fake signature unless she
knows
Alice's private key; as in almost all aspects of
cryptography, digital signatures rely on the careful protection and
management of keys. If Eve could forge Alice's
signature, Eve could make it appear that Alice has signed any
document.
Eve should not be able to reuse one of Alice's
digital signatures.
Eve can only take Alice's signature from
one
document and associate it with another if both documents produce the
same data hash code.
Eve should not be able to alter a signed document.
If Eve alters the content of a document, then
Alice's signature will no longer be valid, because the
altered document will produce a different data hash code to the one
that Alice signed. Eve could alter a document successfully if it
resulted in the same data hash code as the original (which is, in
effect, the same as reusing Alice's signature).
Alice should not be able to deny that she has signed a document.
Alice cannot sign a document and then later claim that she did not,
because we assume that she is the only person who knows her secret
key. If she suspects that her key has been compromised, then she must
create a new key pair.
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.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.
2. The .NET Framework Digital Signature Algorithms
The .NET Framework includes two asymmetric algorithms that support
digital signatures; 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, we add support for signatures and signature
formatting to our ElGamal implementation.
All asymmetric algorithms include a key generation protocol. 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.
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. 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 signatureformatting protocol is PKCS
#1, which we summarize as follows:
Create H, the cryptographic hash code for the
document. SHA1 and MD5 are the most commonly used hashing
algorithms;
Concatenate the hashing algorithm ID and the hexadecimal
representation of the hash code together to form the
DigestInfo value. Each hashing algorithm has a
unique identifier. Table 1 lists the hexadecimal
IDs for each of the algorithms that the .NET Framework supports.
Create an array of padding bytes, PS; the value of
each byte is 255. The number of bytes to create depends on the length
of the key and the length of DigestInfo. The
number of bytes is , where the lengths DigestInfo and the key are expressed in bytes. The length of PS will be at least 8 bytes.
Combine the following to form the formatted data:
One byte with a value of 0
One byte with a value of 1
DigestInfo, represented as bytes
The acronym PKCS stands for Public Key
Cryptography Standard, which is a series of documents published by
RSA Security, whose founders developed the RSA Algorithm.
Each PKCS standard addresses a specific aspect of asymmetric
cryptography, and PKCS #1 describes how to use the RSA algorithm for
encryption and digital signatures. The PKCS #1 data padding and
signature formatting techniques we describe are both contained in the
PKCS #1 document.


Table 1. Hexadecimal IDs for hashing algorithms
Algorithm

Hexadecimal ID


MD5

30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10

SHA1

30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14

SHA256

30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20

SHA384

30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30

SHA512

30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40

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 =
m^{d}modn
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
128bit 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 360bits of data. Therefore, the
smallest key length that you can use to sign a PKCS #1formatted 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
368bit key are simply too large to print on a page;
To verify a signature, take the document you have received and create
a PKCS #1formatted hash code, following the protocol we described
previously. Use the RSA verification function, shown below, where
m^{2} is the
verification result, s is the digital signature,
and e and n are the RSA
public key parameters:
m_{2} = s^{e}modn
When you verify the signature, the value of
m^{2} should be the PKCS
#1formatted 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 ; the signature and decryption functions are
identical, as are the verification and encryption functions.
The DSA algorithm specification requires that PKCS #1 formatting is
always used, and all hash codes are generated using the SHA1 hashing
algorithm. The SHA1 algorithm ID is still included as part of the
PKCS #1 formatting.