9.5. Digital Signatures

Definition 96. 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 d_Alice and e_Alice be Alice's private and public keys, respectively. Alice sends Bob the message m || { m }d_Alice. 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 e_Alice and computes { { m }d_Alice } e_Alice. 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 (see Chapter 13, "Representing Identity"). 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.

9.5.1. 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 [621].

Let Cathy be the trusted third party. Alice shares a cryptographic key k_Alice with Cathy. Likewise, Bob shares k_Bob with Cathy. When Alice wants to send Bob a contract m, she computes { m }k_Alice and sends it to Bob. Bob sends it to Cathy, who deciphers m, enciphers it with k_Bob, and returns { m }k_Bob to Bob. He can now decipher it. To verify that Alice sent the message, the judge takes the disputed messages { m }k_Alice and { m }k_Bob 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.

9.5.2. 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 (see Section 8.3.1).

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 m₁ and m₂ such that m₁m₂ mod n_Bob = m. She has Bob sign m₁ and m₂. Alice then multiplies the two signatures together and reduces mod n_Bob, and she has Bob's signature on m. (See Exercise 6.) The defense is not to sign random documents and, when signing, never sign the document itself; sign a cryptographic hash of the document [796].

EXAMPLE: Let nAlice = 95, eAlice = 59, dAlice = 11, nBob = 77, eBob = 53, and dBob = 17. Alice and Bob have 26 possible contracts, from which they are to select and sign one. Alice first asks Bob to sign contract F (05): 0517 mod 77 = 3 She then asks him to sign contract R (17): 1717 mod 77 = 19 Alice now computes 05 x 17 mod 77 = 08. She then claims that Bob agreed to contract I (08), and as evidence presents the signature 3 x 19 mod 77 = 57. Judge Janice is called, and she computes 5753 mod 77 = 08 Naturally, she concludes that Bob is lying, because his public key deciphers the signature. So Alice has successfully tricked Bob.

A second problem [31] 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 M^r mod n_Bob = m. He then republishes his public key as (re_Bob, n_Bob). 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.

EXAMPLE: Smarting from Alice's trick, Bob seeks revenge. He and Alice agree to sign the contract G (06). Alice first enciphers it, then signs it: (0653 mod 77)11 mod 95 = 63 and sends it to Bob. Bob, however, wants the contract to be N (13). He computes an r such that 13r mod 77 = 6; one such r is r = 59. He then computes a new public key reBob mod f(nBob) = 59 x 53 mod 60 = 7. He replaces his current public key with (7, 77), and resets his private key to 43. He now claims that Alice sent him contract N, signed by her. Judge Janice is called. She takes the message 63 and deciphers it: (6359 mod 95)43 mod 77 = 13 and concludes that Bob is correct.

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. (See Exercise 7.)