Rotors of M-209 cipher machine.

Cultural Applications of Cryptography

Cryptography and Culture

Cryptography makes appearances in popular music and literature. There is an entire subgenre of rap or hip-hop based on cryptography. Also, stories by Edgar Allan Poe, Arthur C. Clarke, and Jorge Luis Borges have used cryptographic premises.

MC++ in front of the fountain on Purdue University's Engineering Mall.

MC Plus+ busting a cryptographic rhyme on the Purdue University campus.

Cryptographic Nerdcore Rap

Really. It exists. Nerdcore rap, or geeksta rap. See the mad cryptographic rhymes of MC Plus+ and others.

Literary Combinatorics by Poe, Clarke, and Borges

Edgar Allan Poe's short story "The Gold Bug" is probably the most readable explanation of how to break monoalphabetic substitution ciphers. It addresses the combinatoric issues and the statistics of single symbols and symbol sequences, and it is a much better and more complete explanation of elementary cryptanalysis than Arthur Conan Doyle's "The Dancing Men"

But what about other literary discussions of combinatorics?

"The Nine Billion Names of God" (1953) by Arthur C. Clarke has the premise of a Tibetan monastery with the goal of writing down (or, more to the point of the story, printing out) all the possible names of God using an undescribed special-purpose alphabet. Strings of up to nine symbols, avoiding combinations in which a symbol appears more than three times in succession. From that story, where the head lama is discussing the project with an engineer:

"This is a project on which we have been working for the last three centuries — since the lamasery was founded, in fact. It is somewhat alien to your way of thought, so I hope you will listen with an open mind while I explain it."

"Naturally."

It is really quite simple. We have been compiling a list which shall contain all the possible names of God."

"I beg your pardon?"

"We have reason to believe," continued the lama imperturbably, "that all such names can be written with not more than nine letters in an alphabet we have devised."

"And you have been doing this for three centuries?"

"Yes: we expected it would take us about fifteen thousand years to complete the task."

"Oh," Dr. Wagner looked a little dazed. "Now I see why you wanted to hire one of our machines. But exactly what is the purpose of this project?"

The lama hesitated for a fraction of a second, and Wagner wondered if he had offended him. If so, there was no trace of annoyance in the reply.

"Call it ritual, if you like, but it's a fundamental part of our belief. All the many names of the Supreme Being — God, Jehovah, Allah, and so on — they are only man-made labels. There is a philosophical problem of some difficulty here, which I do not propose to discuss, but somewhere among all the possible combinations of letters that can occur are what one may call the real names of God. By systematic permutation of letters, we have been trying to list them all."

"I see. You've been starting at AAAAAAA ... and working up to ZZZZZZZZ...."

"Exactly — though we use a special alphabet of our own. Modifying the electromatic typewriters to deal with this is, of course, trivial. A rather more interesting problem is that of devising suitable circuits to eliminate ridiculous combinations. For example, no letter must occur more than three times in succession."

"Three? Surely you mean two."

"Three is correct: I am afraid it would take too long to explain why, even if you understood our language."

There seem to be two ways to interpret "all such names can be written with not more than nine letters in an alphabet we has devised." The first is that the list would contain all possible strings using a set of nine symbols. That cannot be correct as it allows arbitrarily long strings and the list would be infinite. The monastery is hiring computer services and no one is worried about the halting problem being unsolvable in general (Alan Turing and Alonzo Church published closely related proofs in 1936, and Clarke wrote his story in 1953). Clearly the lama's problem is solvable.

The second interpretation is that the list contains sequences of one through nine symbols drawn from a set whose size is not specified here.

The lama says, "somewhere among all the possible combinations of letters that can occur are what one may call the real names of God." Eliminating strings with four or more repeated symbols just filters out the more obvious entries known to not be real names. The complete list will contain both real names and other irrelevant strings.

Ignoring the repeated-symbol limit, they have devised an alphabet of N symbols where:

N + N2 + N3 + N4 + N5 + N6 + N7 + N8 + N9 ≥ 9,000,000,000

Just 13 symbols would produce 11,488,207,653 combinations of 1 through 9 symbols, so their alphabet must have at least 13 symbols.

Assuming that the Unicode chart of Tibetan characters is authoritative, Tibetan has 43 consonants and 13 vowels. Those 56 symbols could form
56 + 562 + 563 + 564 + 565 + 566 + 567 + 568 + 569 = 5,514,645,256,292,984
strings. If nine billion of those are real names, then on average a real name appears once every 612,738 entries.

However, given the limitations of 1953 computer printing technology and manual binding, the "alphabet we have devised" must be a smaller special-purpose symbol set, perhaps based on Tibetan but not nearly as large.

"The Library of Babel" (1941) by Jorge Luis Borges describes a library built of an apparently endless expanse of hexagonal rooms, each of which has four walls of bookshelves. Each of the four walls has five shelves, each of those holding thirty-five books of 410 pages each, and so each room holds 700 books. Each page has forty lines of eighty characters, and so each book contains 1,312,000 characters. The character set contains 25 characters — 22 letters plus period, comma, and space.

The inhabitants of the library believe that the set of books contain all possible symbol sequences, and so while the majority are gibberish, the library must contain every book that was ever written or will ever be written, along with every possible translation into other languages (assuming a coding scheme for other character sets) and every possible alternative or erroneous version. Shorter works appear padded with spaces after (and before) the expected content. Works longer than 1,312,000 characters appear as (widely scattered) multi-volume sets.

Since the library contains all possible books, the number of books in the library is:

25(410 x 40 x 80) = 251,312,000 = 1.956 x 101,834,097

A further analysis shows that just one "authentic" or accurate version of an actual book along with the set of variations containing just a few misprinted characters would occupy more space than our known universe given the rapid growth of the number of slight variations:

Misprinted
Characters
Number of Versions
0 1
1 31,488,000
2 495,746,694,144,000
3 5,203,349,369,788,317,696,000
4 40,960,672,578,684,980,713,193,472,000

Let's say that the books weigh one kilogram each. According to the CRC Handbook of Chemistry and Physics, the masses of our Sun and the Earth are about 1.991x1030 kg and 5.979x1024 kg, respectively.

The collection of just the 4-misprint variants of one original book would have a mass over 6850 times that of the Earth and about 2% that of the Sun.

Dan Brown seems to be fascinated with the concept of cryptography, but after several books he still has no clue. Digital Fortress is probably his most extreme example of randomly inserted cryptography buzzwords used in meaningless ways.

Cryptographic Haikus

Cryptographic haikus exist. Not that they should, mind you.

A better .sig slogan

$ echo 'only outlaws will have privacy.' | \
                openssl enc -aes-256-cbc -k 'rot13' | \
                hexdump -C
00000000  53 61 6c 74 65 64 5f 5f  1b b8 4f 86 b9 3f f7 fb  |Salted__..O..?..|
00000010  69 a8 7b 4a 93 2d ab 75  27 40 b0 f7 e5 ef 75 14  |i.{J.-.u'@....u.|
00000020  7e 26 59 e4 38 21 4e af  fc a8 a4 3f 50 e5 d2 d3  |~&Y.8!N....?P...|
00000030  4d 60 b6 32 41 22 fe 90  bb 31 12 92 69 5c 74 8d  |M`.2A"...1..i\t.|
00000040
When cryptography is outlawed,
5361 6c74 6564 5f5f 712b 6f83 ab01 176c
ea33 cc00 6571 bcd6 bd8e 08af 743b abb4
7f75 5b1d 4487 bf2f 6e06 4359 fc22 d32e
81a1 0a88 6afe 0325 31d1 c694 8f28 3be1

Next — Further Reading