How the World’s Most Famous Code Was Cracked
Uncovering the CIA’s Kryptos puzzle took three parts math and one part sleuthing
The Kryptos sculpture sits in front of the CIA headquarters in Virginia.
The 35-year-old saga of Kryptos, an enigmatic sculpture containing four encrypted messages outside the CIA headquarters, just took a bizarre twist. Though cryptographers broke the first three passages in the 1990s, just a few years after artist Jim Sanborn erected the copper monolith, the fourth, known as K4, remained a 97-character fortress—that is, until September 2, when journalists Jarett Kobek and Richard Byrne discovered the answer in the Smithsonian archives.
How does one crack the world’s most famous code? The breakthroughs on Kryptos provide a guided tour through the cat and mouse game between code makers and code breakers that has defined information security for millennia.
The core challenge of cryptography is to send a secret message securely in the presence of eavesdroppers. The strategy always involves the same ingredients: The message, called the plaintext, gets distorted (the encryption) so that anybody who intercepts it sees only garbled gibberish (the ciphertext). Ideally only those with a secret key can decrypt it. If you share your secret key with the intended recipient and nobody else, then you can, in theory, communicate with them in code. Cryptography underlies everyday financial transactions and online communication, not just spy messages.
If you’re enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
To understand Kryptos, we’ll need to dig into early cryptosystems and why they failed. One of the simplest and oldest encryption methods dates back to a historical secret keeper: Julius Caesar. The Caesar cipher obscures messages by shifting every letter of the alphabet by some fixed amount. Here the key is a number between 1 and 25. Say we pick 5. The encryption of “hello” would be “mjqqt” because M is five letters after H, J is five letters after E, and so on. (If you reach the end of the alphabet, then wrap back around to the beginning.) For a more entertaining example, astute fans of 2001: A Space Odyssey have noticed that the name of the rogue AI called HAL spells “IBM” with a Caesar cipher shift of one letter backward. (Director Stanley Kubrick insisted that this was a coincidence.) Although Caesar trusted this method for his confidential correspondence, it’s a lousy way to protect state secrets. If an adversary learns that you encrypt messages with a Caesar cipher, they only need to try 25 different keys to recover the original text.
A general substitution cipher offers the most natural upgrade. Instead of merely shifting the alphabet, you scramble it. The letter A might become Q, B might become X, C might become D, and so on, in no particular order. This seems far more secure. A Caesar cipher has only 25 possible keys, but a full substitution cipher has 403,291,461,126,605,635,584,000,000. (There are 26 factorial ways to mix up the alphabet, or 26 × 25 × 24 × 23 … 3 × 2 × 1.) A brute-force search of checking every key isn’t feasible, yet substitution ciphers are still woefully insecure by today’s standards. If you don’t already know why, ask yourself how you would go about decoding a page of text encrypted with a substitution cipher.
The flaw in a substitution cipher is that it leaves patterns in language intact. English has a distinct fingerprint. E accounts for more than 12 percent of all letters in English text, whereas the letter Z crops up less than 0.1 percent of the time. If you intercept a page of gibberish encrypted with a substitution cipher and the letter J appears more often than any other letter, it’s a good bet that J stands for E. The second-most-common letter is probably a T. Furthermore, single-letter words almost certainly stand for A or I (the only frequently used one-letter English words), and common two- and three-letter words can give code breakers a foot in the door as well. Called frequency analysis, this method is the subject of popular newspaper puzzles called cryptograms; it also played a critical role in deciphering the first three Kryptos passages.
Sanborn encrypted the first two Kryptos messages, called K1 and K2, and which contain 63 and 372 characters, respectively, using the next level up: the Vigenère cipher. Invented in the 16th century and named after the cryptographer Blaise de Vigenère, it stood unbroken for 300 years, earning it the nickname “le chiffre indéchiffrable” (the indecipherable cipher). It works by applying several different Caesar ciphers to a single plaintext. For example, maybe we shift the first letter of the message forward by 19, the second letter forward by 16, the third letter forward by 25 and then repeat. (The fourth letter shifts by 19, the fifth by 16, the sixth by 25, and so on.) These shift amounts constitute the key, which is typically represented by a word corresponding to those locations in the alphabet. In this case, the key is SPY because S, P and Y are the 19th, 16th and 25th letters.
The Vigenère cipher ingeniously defeats straightforward frequency analysis because not all E’s, for example, will get mapped to the same letter. Imagine that the first two letters of a message are both E. The first gets shifted by 19 to become an X and the second by 16 to become a U. But clever cryptanalysts can still break through. If you can guess the length of the key (for example, three for SPY), you can break the problem apart. You take the first, fourth, seventh and 10th letters, and so on, of the ciphertext and put them in a pile. All of these were shifted according to the same key letter: S. Now you can conduct frequency analysis on just that pile. You do the same for the second, fifth and eighth letters, all shifted according to P, and so on. The “unbreakable” cipher becomes three simple Caesar ciphers. Not sure of the length of the key? Careful scrutiny of the ciphertext can sometimes provide clues, but if all else fails, try all possible lengths. Too time-consuming? A computer program can help with the search.
Sanborn encrypted K1 and K2 with the keys “PALIMPSEST” and “ABSCISSA,” respectively. The former, a poetic choice, refers to a piece of writing that has been erased and written over multiple times. Abscissa is the x coordinate of an (x, y) coordinate pair. As is common practice in Vigenère ciphers, Sanborn also used a modified alphabet for the shifting: in this case, KRYPTOSABCDEFGHIJLMNQUVWXZ, which he etched into the sculpture.
Sanborn switched methods for K3, a 337-character ciphertext. Here he opted for a transposition cipher in which he simply jumbled all of the letters in the message as though it were a massive anagram. The jumble in this type of cipher typically follows certain rules so that an intended recipient with a key can easily restore the letters to their rightful order. Cryptographers readily suspected that K3 used this cipher. How? You guessed it—frequency analysis. The letter distribution in the ciphertext matched what would be expected in typical English text, suggesting that letters had not been substituted, merely shuffled.
K4 had resisted all attempts for 35 years. Perhaps Sanborn intentionally cranked up its complexity to reflect the strides made in cryptographic science since the days of Vigenère. Breaking full-fledged modern cryptography wouldn’t merely amount to a cleverer deployment of frequency analysis but a revolution in our understanding of math itself. That’s because cutting-edge encryption shrouds information behind mathematical problems (such as factoring enormous numbers) that are conjectured to be unsolvable in any practical amount of time. To break the encryption would mean finding a fast solution to these supposedly infeasible problems, an act that would overturn a foundational assumption of modern math.
This fall Sanborn was planning to auction off the solution to K4—an encrypted message that starts with “OBKR”—to relieve himself of the role of sole steward to its secrets. The auction announcement referenced original “coding charts” at the Smithsonian. Rather than actually deciphering K4, journalists Kobek and Byrne requested access to the documents and found scraps of paper containing K4’s plaintext. On September 3 the duo e-mailed Sanborn with the solution.
This doesn’t seem to be the artist’s perspective: Sanborn asked the journalists to sign NDAs. (They refused.) Those still longing for a puzzle are in luck because the public doesn’t know what K4 says or how it was encrypted. Nobody fully understands the enigmatic messages that K1 through K3 revealed. Sanborn also confirmed the existence of a K5 in an open letter published this past August. Code breakers have plenty to look forward to in the next era of Kryptos.
Jack Murtagh is a freelance math writer and puzzle creator. He writes a column on mathematical curiosities for Scientific American and creates daily puzzles for the Morning Brew newsletter. He holds a Ph.D. in theoretical computer science from Harvard University. Follow him on X @JackPMurtagh
If you enjoyed this article, I’d like to ask for your support. Scientific American has served as an advocate for science and industry for 180 years, and right now may be the most critical moment in that two-century history.
I’ve been a Scientific American subscriber since I was 12 years old, and it helped shape the way I look at the world. SciAm always educates and delights me, and inspires a sense of awe for our vast, beautiful universe. I hope it does that for you, too.
If you , you help ensure that our coverage is centered on meaningful research and discovery; that we have the resources to report on the decisions that threaten labs across the U.S.; and that we support both budding and working scientists at a time when the value of science itself too often goes unrecognized.
In return, you get essential news, captivating podcasts, brilliant infographics, , must-watch videos, challenging games, and the science world’s best writing and reporting. You can even gift someone a subscription.
There has never been a more important time for us to stand up and show why science matters. I hope you’ll support us in that mission.
Thank you,
David M. Ewalt, Editor in Chief, Scientific American
Source: www.scientificamerican.com