Cryptonomicon

hour the jet of hot gas is joined by a rivulet of incandescent fluid that sinks to the bottom of the stream as soon as it emerges, clothed in a fuzz of wildly boiling water. For a long time there is really nothing to be seen except steam; but after Golgotha's been burning for an hour or two, it becomes possible to see that underneath the shallow water, spreading down the valley floor, indeed right around the isolated boulder where Randy's perched, is a bright, thick river of gold.

APPENDIX: THE SOLITAIRE ENCRYPTION ALGORITHM

by Bruce Schneier

Author, Applied Cryptography

President, Counterpane Systems

http://www.counterpane.com

In Neal Stephenson's novel Cryptonomicon,The character Enoch Root describes a cryptosystem code-named 'Pontifex' to another character named Randy Waterhouse, and later reveals that the steps of the algorithm are intended to be carried out using a deck of playing cards. These two characters go on to exchange several encrypted messages using this system. The system is called 'Solitaire' (in the novel, 'Pontifex' is a code name intended to temporarily conceal the fact that it employs a deck of cards) and I designed it to allow field agents to communicate securely without having to rely on electronics or having to carry incriminating tools. An agent might be in a situation where he just does not have access to a computer, or may be prosecuted if he has tools for secret communication. But a deck of cards . . . what harm is that?

Solitaire gets its security from the inherent randomness in a shuffled deck of cards. By manipulating this deck, a communicant can create a string of 'random' letters that he then combines with his message. Of course Solitaire can be simulated on a computer, but it is designed to be implemented by hand.

Solitaire may be low-tech, but its security is intended to be high-tech. I designed Solitaire to be secure even against the most well-funded military adversaries with the biggest computers and the smartest cryptanalysts. Of course there is no guarantee that someone won't find a clever attack against Solitaire (watch my web page for updates), but the algorithm is certainly better than any other pencil and paper cipher I've ever seen.

It's not fast, though. It can take an evening to encrypt or decrypt a reasonably long message. In David Kahn's book Kahn on Codes,he describes a real pencil-and-paper cipher used by a Soviet spy. Both the Soviet algorithm and Solitaire take about the same amount of time to encrypt a message.

ENCRYPTING WITH SOLITAIRE

Solitaire is an output-feedback mode stream cipher. Sometimes this is called a key-generator (KG in U.S. military speak). The basic idea is that Solitaire generates a stream, often called a 'keystream,' of numbers between 1 and 26. To encrypt, generate the same number of keystream letters as plaintext letters. Then add them modulo 26 to plaintext letters, one at a time, to create the ciphertext. To decrypt, generate the same keystream and subtract modulo 26 from the ciphertext to recover the plaintext.

For example, to encrypt the first Solitaire message mentioned in Stephenson's novel, 'DO NOT USE PC':

1. Split the plaintext message into five character groups. (There is nothing magical about five-character groups; it's just tradition.) Use X's to fill in the last group. So if the message is 'DO NOT USE PC' then the plaintext is:

DONOT USEPC

2. Use Solitaire to generate ten keystream letters. (Details are below.) Assume they are:

KDWUP ONOWT

3. Convert the plaintext message from letters into numbers: A = 1, B = 2, etc:

4 15 14 15 20 21 19 5 16 3

4. Convert the keystream letters similarly:

11 4 23 21 16 15 14 15 23 20

5. Add the plaintext number stream to the keystream numbers, modulo 26. (All this means is, if the sum is more than 26, subtract 26 from the result.) For example, 1 + 1 = 2, 26 + 1 = 27, and 27 — 26 = 1, so 26 + 1 = 1.

15 19 11 10 10 10 7 20 13 23

6. Convert the numbers back to letters.

OSKJJ JGTMW

If you are really good at this, you can learn to add letters in your head, and just add the letters from steps (1) and (2). It just takes practice. It's easy to remember that A + A = B; remembering that T + Q = K is harder.

DECRYPTING WITH SOLITAIRE

The basic idea is that the receiver generates the same keystream, and then subtracts the keystream letters from the ciphertext letters.

1. Take the ciphertext message and put it in five character groups. (It should already be in this form.)

OSKJJ JGTMW

2. Use Solitaire to generate ten keystream letters. If the receiver uses the same key as the sender, the keystream letters will be the same:

KDWUP ONOWT

3. Convert the ciphertext message from letters into numbers:

15 19 11 10 10 10 7 20 13 23

4. Convert the keystream letters similarly:

11 4 23 21 16 15 14 15 23 20

5. Subtract the keystream numbers from the ciphertext numbers, modulo 26. For example, 22 — 1 = 20, 1 — 22 = 5. (It's easy. If the first number is less than the second number, add 26 to the first number before subtracting. So 1 — 22 = ? becomes 27 — 22 = 5.)

4 15 14 15 20 21 19 5 16 3

6. Convert the numbers back to letters.

DONOT USEPC

Decryption is the same as encryption, except that you subtract the keystream from the ciphertext message.