As electronic commerce grows, so does the need for a provably high degree of authentication. Think of Alice's signature on a contract with Bob. Bob not only has to know that Alice is the other signer and is signing it; he also must be able to prove to a disinterested third party (called a judge) that Alice signed it and that the contract he presents has not been altered since Alice signed it. Such a construct is called a digital signature.

A digital signature is a construct that authenticates both the origin and contents of a message in a manner that is provable to a disinterested third party.

The "proof " requirement introduces a subtlety. Let m be a message. Suppose Alice and Bob share a secret key k. Alice sends Bob m || { m }k (that is, the message and its encipherment under k). Is this a digital signature?

First, Alice has authenticated the contents of the message, because Bob deciphers { m }k and can check that the message matches the deciphered one. Because only Bob and Alice know k, and Bob knows that he did not send the message, he concludes that it has come from Alice. He has authenticated the message origin and integrity. However, based on the mathematics alone, Bob cannot prove that he did not create the message, because he knows the key used to create it. Hence, this is not a digital signature.

Public key cryptography solves this problem. Let dAlice and eAlice be Alice's private and public keys, respectively. Alice sends Bob the message m || { m }dAlice. As before, Bob can authenticate the origin and contents of m, but in this situation a judge must determine that Alice signed the message, because only Alice knows the private key with which the message was signed. The judge merely obtains eAlice and computes { { m }dAlice } eAlice. If the result is m, Alice signed it. This is in fact a digital signature.

A digital signature provides the service of nonrepudiation. If Alice claims she never sent the message, the judge points out that the originator signed the message with her private key, which only she knew. Alice at that point may claim that her private key was stolen, or that her identity was incorrectly bound in the certificate. The notion of "nonrepudiation" provided here is strictly abstract. In fact, Alice's key might have been stolen, and she might not have realized this before seeing the digital signature. Such a claim would require ancillary evidence, and a court or other legal agency would need to handle it. For the purposes of this section, we consider the service of nonrepudiation to be the inability to deny that one's cryptographic key was used to produce the digital signature.

Classical Signatures

All classical digital signature schemes rely on a trusted third party. The judge must trust the third party. Merkle's scheme is typical.

Let Cathy be the trusted third party. Alice shares a cryptographic key kAlice with Cathy. Likewise, Bob shares kBob with Cathy. When Alice wants to send Bob a contract m, she computes { m }kAlice and sends it to Bob. Bob sends it to Cathy, who deciphers m, enciphers it with kBob, and returns { m }kBob to Bob. He can now decipher it. To verify that Alice sent the message, the judge takes the disputed messages { m }kAlice and { m }kBob and has Cathy decipher them using Alice's and Bob's keys. If they match, the sending is verified; if not, one of them is a forgery.

Public Key Signatures

In our earlier example, we had Alice encipher the message with her private key to produce a digital signature. We now examine a specific digital signature scheme based on the RSA system.

We observe that using RSA to authenticate a message produces a digital signature. However, we also observe that the strength of the system relies on the protocol describing how RSA is used as well as on the RSA cryptosystem itself.

First, suppose that Alice wants to trick Bob into signing a message m. She computes two other messages m1 and m2 such that m1m2 mod nBob = m. She has Bob sign m1 and m2. Alice then multiplies the two signatures together and reduces mod nBob, and she has Bob's signature on m.The defense is not to sign random documents and, when signing, never sign the document itself; sign a cryptographic hash of the document.

A second problem demonstrates that messages that are both enciphered and signed should be signed first, then enciphered. Suppose Alice is sending Bob her signature on a confidential contract m. She enciphers it first, then signs it and sends the result to Bob. However, Bob wants to claim that Alice sent him the contract M. Bob computes a number r such that Mr mod nBob = m. He then republishes his public key as (reBob, nBob). Note that the modulus does not change. Now, he claims that Alice sent him M. The judge verifies this using his current public key. The simplest way to fix this is to require all users to use the same exponent but vary the moduli.

This attack will not work if one signs first and then enciphers. The reason is that Bob cannot access the information needed to construct a new public key, because he would need to alter Alice's public key.