The KRYPTOS Code — How to Break a Vigenère Code

“I genuinely enjoyed working on the Kryptos ciphers. Professional cryptographers almost certainly could have broken these codes much faster, and would have used superior methods. But I doubt that they would have derived as much satisfaction as I have. I didn’t use any computers to decrypt the Kryptos codes–just pencil and paper, some common sense, and a lot of perseverance. Using a computer would have cheated me out of the feeling of accomplishment that I obtained, because I have found that often in life the journey itself can be more gratifying than arriving at the final destination. Mountains are not climbed nor marathons run merely to reach a geographical location–there are much easier ways to accomplish these feats–but as personal and spiritual challenges to the participants.

When confronted with a puzzle or problem, we sometimes can lose sight of the fact that we have issued a challenge to ourselves–not to our tools. And before we automatically reach for our computers, we sometimes need to remember that we already possess the most essential and powerful problem solving tool within our own minds.”

David Stein — CIA Analyst (Directorate of Intelligence)

Kryptos is a sculpture by the American artist Jim Sanborn located on the grounds of the Central Intelligence Agency (CIA) in Langley, Virginia. Of the four parts of the message, the first three have been solved. The last part of the message remains as one of the most famous unsolved code in the world.

The ciphertext on the left-hand side of the sculpture (as seen from the courtyard) of the main sculpture contains 869 characters in total (865 letters and 4 question marks). The right-hand side of the sculpture comprises a keyed Vigenère encryption tableau, consisting of 867 letters. Today, we will learn how to break the so-called section II of this ciphertext. Follow us on Twitter: @INTEL_TODAY

RELATED POST: The KRYPTOS Sculpture — An Introduction

RELATED POST: THE BORIS PROJECT: HOW THE NSA FOOLED THE WORLD WITH THE HELP OF A SWEDISH GENIUS

RELATED POST: Key figures in UK Sigint: Conel Hugh O’Donel Alexander

RELATED POST: Alan Turing – Remembering the life of a genius [23 June 1912 – 7 June 1954]

Top parts of the sculpture

Bottom parts of the sculpture

Where do we start?

This post will discuss only some part — although a big one — of the message coded in the (LEFT) top panel. Many people have realized something ‘promising’ in the fourth line.

GGWHKK? DQM CPFQZ DQM MIAGPFXHQRLG

The sequence ‘DQM’ appears twice (separated by a length of eight characters). In English, a three letter word is very likely to be ‘THE’. We are going to start our journey by assuming that the entire text from DQM to the end of the first panel has been coded by a unique method (Vigenère table) using the same key and passphrase. Perhaps, Sanborn even gave us the correct key — KRYPTOS — in the right panels? First, we need to learn a few concepts.

The Vigenère Cipher

The Vigenère square or Vigenère table, also known as the tabula recta, can be used for encryption and decryption.

A table of alphabets, termed a tabula recta, Vigenère square, or Vigenère table can be used to encrypt a message. It consists of the alphabet written out 26 times in different rows, each alphabet shifted cyclically to the left compared to the previous alphabet, corresponding to the 26 possible Caesar ciphers. At different points in the encryption process, the cipher uses a different alphabet from one of the rows. The alphabet used at each point depends on a repeating passphrase. [Wikipedia]

For example, suppose that the plaintext to be encrypted is:

ATTACKATDAWN

The person sending the message chooses a passphrase and repeats it until it matches the length of the plaintext, for example, the passphrase “LEMON”:

Plaintext         ATTACKATDAWN

Passphrase     LEMONLEMONLE

Ciphertext       LXFOPVEFRHNR

The ‘Keyed’ Vigenère Cipher

The ‘Keyed’ Vigenère Cipher uses an alternate tableau. The “Alphabet Key” helps decide the alphabet to use to encrypt and decrypt the message. Instead of just using the alphabet from A to Z in order, the alphabet key puts a series of letters first, making the cipher even tougher to break. The “passphrase” is the code word/sentence used to select columns in the tableau.

For instance, in the right panels of his sculpture, Sanborn used the key “KRYPTOS” before the normal sequence of the alphabet: KRYPTOSABCDE…

The Index of Coincidence

The Index of Coincidence [IC] measures the probability that any two randomly chosen source-language letters are the same. This probability — also known as the \kappa index — is about 0.067 for monocase English while the probability of a coincidence for a uniform random selection from the alphabet is 1/26 = 0.0385.

\displaystyle \kappa =\frac{\sum_{i=1}^{c}n_i(n_i -1)}{N(N-1)}

where c is the size of the alphabet (26 for English), N is the length of the text, and n_1 through n_c are the observed ciphertext letter frequencies, as integers.

The IC for ‘Section II’ of KRYPTOS

Therefore, I have calculated the IC for each passphrase length from 1 to 16. It is clear that the passphrase is 8 characters long. The peaks above average at length 4, 12 and 16 are due to some mathematical consequences which I will not discuss here. For now, let us just say that it is highly likely — indeed, almost certain — that the passphrase is  8 characters long. The hard work has been done. The fun can begin.

Comment — Unlike David Stein, my calculations show no roughness/anomaly at length 13. Perhaps, one (or both) of us made a mistake. We both worked out the whole thing by hand. It is of course FUN, but not best for exactitude and reliability…]  Or perhaps, the ‘signal’ detected by Stein is a statistical ‘fluke’ resulting from a short number of letters and the fact that Stein and myself worked on different parts of the real section II. This issue MUST be investigated a bit further. I will make my calculations available to the readers. Obviously, a computer code will decide quickly on this issue. — End of Comment

The Cipher in 8 columns

So, I re-wrote the coded text in eight columns. I know that ALL letters in a given column have been encrypted with the same “Vigenère alphabet”.

Back to our early hunch…

At this point, a frequency analysis of the letters contained in each column will reveal which letters in the plaintext have been substituted in the coded text. But that is a bit mathematical and not nearly as much fun as following our early hunch!

I will now search for the ‘Vigenère alphabets’ [keyed with KRYPTOS] that transform ‘DQM’ into ‘THE’. Clearly, the passphrase characters for the first, second, and third column correspond to the letters: S, S and A.

K  R  Y  P  T  O  S  A B C D E F G H I J L M N Q U V W X Z

S  A B C D E F G H I J L M N Q U V W X Z K  R  Y  P  T  O

S  A B C D E F G H I J L M N Q U V W X Z K  R  Y  P  T  O

A B C D E F G H I J L M N Q U V W X Z K  R  Y  P  T  O  S

How does it look?

How to keep going?

At this point, it seems very likely that we are on the right path. Let us keep going. Anyone will go his own way. I simply noticed that the first three letters in row 41 are ‘WES’ which is likely to be followed by a ‘T’. This implies that the 4th letter in the passphrase is again a ‘A’.

Now, words begin to appear. For instance, GATH in row 7 is likely to be followed by a ‘E’. This implies that the 5th in the passphrase is a ‘B’.

We could go on…. But we can be smarter. We KNOW that the passphrase is eight characters long. And so far, we have identify SSAAB. Assuming that the passphrase is an english word — and this is why you should NEVER use english words in a passphrase — the word obviously must start with a ‘A’ as there are no English words with a double A. So we are looking for a word that looks like this: AB – – – SSA. You will find only one such word in English: ABSCISSA.

The TEXT at Last

And now?

Here is thus the plaintext message:

“They used the Earths magnetic field X The information was gathered and transmitted undergruund to an unknown location X Does Langley know about this? They should Its buried out there somewhere X Who knows the exact location? Only WW This was his last message X Thirty eight degrees fifty seven minutes six point five seconds north Seventy seven degrees eight minutes forty four seconds west ID by rows”

However, we are not done for several reasons. First,  Jim Sanborn has acknowledged that he made an error in the sculpture by omitting an “X” used to separate sentences, for aesthetic reasons. Therefore, the deciphered text that ends “…FOUR SECONDS WEST ID BY ROWS” is NOT correct. We will fix that.

Then, since our passphrase starts in the middle of a word ‘SSA’ from ‘ABSCISSA’, we can safely conclude that the coded text starts earlier than I had assumed. Clearly, it starts 5 + (8*N) characters earlier!

And indeed, with a bit of additional work, you will come to the conclusion that the 37 characters [5 + (8*4)] before the question mark

[VFPJUDEEHZWETZYVGWHKKQETGFQJNCEGGWHKK?]

have been encoded with the same key and passphrase. We will decode this too in a following post.

Finally, the puzzle is also — and perhaps most importantly — about solving the underlying riddle.  But, we are not ready for this yet. Tiny steps for tiny feet… Stay tuned!

REFERENCES

Kryptos — Wikipedia

Stein, David D. (1999). “The Puzzle at CIA Headquarters: Cracking the Courtyard Crypto” (pdf). Studies in Intelligence. 43 (1).

=

The KRYPTOS Code — How to Break a Vigenère Code

This entry was posted in KRYPTOS and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s