A chosen-plaintext attack can be particularly effective if there are relatively few possible encrypted messages. For example, if P were a dollar amount less than $1,000,000, this attack would work; the cryptanalyst tries all million possible dollar amounts. (Probabilistic encryption solves the problem; see Section 23.15.) Even if P is not as well-defined, this attack can be very effective. Simply knowing that a ciphertext does not correspond to a particular plaintext can be useful information. Symmetric cryptosystems are not vulnerable to this attack because a cryptanalyst cannot perform trial encryptions with an unknown key.

In most practical implementations public-key cryptography is used to secure and distribute session keys; those session keys are used with symmetric algorithms to secure message traffic [879]. This is sometimes called a hybrid cryptosystem.

(1)  Bob sends Alice his public key.

(2)  Alice generates a random session key, K, encrypts it using Bob’s public key, and sends it to Bob.

E_B(K)

(3)  Bob decrypts Alice’s message using his private key to recover the session key.

D_B(E_B(K)) = K

(4)  Both of them encrypt their communications using the same session key.

Using public-key cryptography for key distribution solves a very important key-management problem. With symmetric cryptography, the data encryption key sits around until it is used. If Eve ever gets her hands on it, she can decrypt messages encrypted with it. With the previous protocol, the session key is created when it is needed to encrypt communications and destroyed when it is no longer needed. This drastically reduces the risk of compromising the session key. Of course, the private key is vulnerable to compromise, but it is at less risk because it is only used once per communication to encrypt a session key. This is further discussed in Section 3.1.

Merkle’s Puzzles

Ralph Merkle invented the first construction of public-key cryptography. In 1974 he registered for a course in computer security at the University of California, Berkeley, taught by Lance Hoffman. His term paper topic, submitted early in the term, addressed the problem of “Secure Communication over Insecure Channels” [1064]. Hoffman could not understand Merkle’s proposal and eventually Merkle dropped the course. He continued to work on the problem, despite continuing failure to make his results understood.

Merkle’s technique was based on “puzzles” that were easier to solve for the sender and receiver than for an eavesdropper. Here’s how Alice sends an encrypted message to Bob without first having to exchange a key with him.

(1)  Bob generates 2²⁰, or about a million, messages of the form: “This is puzzle number x. This is the secret key number y,” where x is a random number and y is a random secret key. Both x and y are different for each message. Using a symmetric algorithm, he encrypts each message with a different 20-bit key and sends them all to Alice.

(2)  Alice chooses one message at random and performs a brute-force attack to recover the plaintext. This is a large, but not impossible, amount of work.

(3)  Alice encrypts her secret message with the key she recovered and some symmetric algorithm, and sends it to Bob along with x.

(4)  Bob knows which secret key y he encrypts in message x, so he can decrypt the message.

Eve can break this system, but she has to do far more work than either Alice or Bob. To recover the message in step (3), she has to perform a brute-force attack against each of Bob’s 2²⁰ messages in step (1); this attack has a complexity of 2⁴⁰. The x values won’t help Eve either; they were assigned randomly in step (1). In general, Eve has to expend approximately the square of the effort that Alice expends.

This n to n² advantage is small by cryptographic standards, but in some circumstances it may be enough. If Alice and Bob can try ten thousand keys per second, it will take them a minute each to perform their steps and another minute to communicate the puzzles from Bob to Alice on a 1.544 MB link. If Eve had comparable computing facilities, it would take her about a year to break the system. Other algorithms are even harder to break.

2.6 Digital Signatures

Handwritten signatures have long been used as proof of authorship of, or at least agreement with, the contents of a document. What is it about a signature that is so compelling [1392]?

1.  The signature is authentic. The signature convinces the document’s recipient that the signer deliberately signed the document.

2.  The signature is unforgeable. The signature is proof that the signer, and no one else, deliberately signed the document.

3.  The signature is not reusable. The signature is part of the document; an unscrupulous person cannot move the signature to a different document.

4.  The signed document is unalterable. After the document is signed, it cannot be altered.

5.  The signature cannot be repudiated. The signature and the document are physical things. The signer cannot later claim that he or she didn’t sign it.

In reality, none of these statements about signatures is completely true. Signatures can be forged, signatures can be lifted from one piece of paper and moved to another, and documents can be altered after signing. However, we are willing to live with these problems because of the difficulty in cheating and the risk of detection.

We would like to do this sort of thing on computers, but there are problems. First, computer files are trivial to copy. Even if a person’s signature were difficult to forge (a graphical image of a written signature, for example), it would be easy to cut and paste a valid signature from one document to another document. The mere presence of such a signature means nothing. Second, computer files are easy to modify after they are signed, without leaving any evidence of modification.