Solving the CIA Kryptos Code (Part 2)

You can find all the code for this series on GitHub.

In the previous post we solved Kryptos 1 and 2. Kryptos 3 is going to be a bit tougher. It doesn't use our trusty Vigenere cipher. And it doesn't use just one cipher, either; it uses two. We'll learn them separately in this post, then use them together in the next one.

Keyed columnar transposition

We need to learn a transposition cipher, which is where the letters in a message are rearranged but not changed. There are many kinds of transposition ciphers, but for starters, we'll do a keyed columnar transposition cipher. Again, you need a message and a key. Let's use "ILOVEWATER" and "HYDRATE" again.

To start, you put the key in alphabetical order and note the position of each letter. "A" is the earliest alphabetical letter in HYDRATE, so it's 0. "D" is the next alphabetical letter, so it's 1. And so on:

Column #	0	1	2	3	4	5	6
Alphabetized key	A	D	E	H	R	T	Y
Original key	H	Y	D	R	A	T	E
Position numbers	3	6	1	4	0	5	2

Our numeric key is 3614052. Since the key, HYDRATE, is 7 characters long, let's write out our message in rows of 7 characters:

Position numbers	3	6	1	4	0	5	2
Message line 1	I	L	O	V	E	W	A
Message line 2	T	E	R

Now all we have to do is order the columns by their position number and write out the encrypted message:

Position numbers	0	1	2	3	4	5	6
Message line 1	E	O	A	I	V	W	L
Message line 2		R		T			E

The encrypted message, which you read out a column at a time, is "EORAITVWLE".

To decrypt it, first we look at the length of the message: 10 characters. The key, HYDRATE, is 7 characters. We have to multiply 7 by 2 to get enough space for 10 characters, so we know there will be 2 rows, and since 14 minus 10 is 4, there will be 4 blank cells at the end of the message.

Let's write out the key and the position numbers, with two blank lines for our message, and block out the last four cells.

Key	H	Y	D	R	A	T	E
Position numbers	3	6	1	4	0	5	2
Message line 1
Message line 2				X	X	X	X

Now we can take our encrypted message, "EORAITVWLE", and start writing it out in order of the "Position numbers" row. The first letter "E" goes under 0, and then that column is full. The second letter "O" goes under 1, and since there's a space for another letter, the third letter "R" goes in that column as well. Then we move onto the 2 column, and so on.

Key	H	Y	D	R	A	T	E
Position numbers	3	6	1	4	0	5	2
Message line 1	I	L	O	V	E	W	A
Message line 2	T	E	R	X	X	X	X

And we've decrypted our original message, "ILOVEWATER".

Here's how we'd do this in TypeScript:

// Breaks an array into sub-arrays of size `chunkSize`
function chunk<T>(array: T[], chunkSize: number): T[][] {
  const result: T[][] = [];
  for (let i = 0; i < array.length; i += chunkSize) {
      const chunk = array.slice(i, i + chunkSize);
      result.push(chunk);
  }
  return result;
}

function columnarEncrypt(message: string, key: string): string {
  // First, sort the key and get the alphabetical position number of each character
  const keyChars = key.split('');
  const sortedKey = keyChars.toSorted();
  const positionNumbers = keyChars.map(char => sortedKey.indexOf(char));

  // Then break the message into rows the same length as the key
  const messageChars = message.split('');
  const messageRows = chunk(messageChars, keyChars.length);

  // Create a two-dimensional array with the same number of rows
  //  as the message and the same number of columns as the key
  const encryptedRows: (string | null)[][] = Array(messageRows.length)
    .fill(null)
    .map(_ => Array(key.length).fill(null).map(_ => null));

  // For each column of the to-be-encrypted message...
  for (const orderedColumnIx in keyChars) {
    // Find out what column its characters are currently in
    const messageColumnIx = positionNumbers.indexOf(Number(orderedColumnIx));

    // And put them in order
    for (const rowIx in messageRows) {
      encryptedRows[rowIx][orderedColumnIx] = messageRows[rowIx][messageColumnIx] ?? null;
    }
  }

  // Finally, read out the encrypted message a column at a time
  let encrypted = '';
  for (let ix = 0; ix < key.length; ix++) {
    for (const row of encryptedRows) {
      if (row[ix] === null) {
        continue;
      }

      encrypted += row[ix];
    }
  }
  return encrypted;
}

function columnarDecrypt(encrypted: string, key: string): string {
  // Again, sort the key and get position numbers
  const keyChars = key.split('');
  const sortedKey = keyChars.toSorted();
  const positionNumbers = keyChars.map(char => sortedKey.indexOf(char));

  // Figure out how many rows are needed
  const numberOfRows = Math.ceil(encrypted.length / key.length);

  // And how many empty cells there will be
  const numberOfEmpties = (numberOfRows * key.length) % encrypted.length;

  // Create a two-dimensional array with the correct number of rows
  //  and the same number of columns as the key
  const messageRows = Array(numberOfRows)
    .fill(null)
    .map(row => Array(key.length).fill(null));

  // Work backwards to fill in the number of empty cells on the last row
  const lastRow = messageRows[messageRows.length - 1];
  for (let emptyIx = 1; emptyIx <= numberOfEmpties; emptyIx++) {
    lastRow[lastRow.length - emptyIx] = '';
  }

  // Then, starting with column 0...
  let orderedColumnIx = 0;
  // For each character in the encrypted message...
  for (const encryptedChar of encrypted) {
    // Find out the position number of the current column
    const messageColumnIx = positionNumbers.indexOf(orderedColumnIx);

    // Put the current character in the first available row of that column
    const availableRowIx = messageRows.findIndex(row => row[messageColumnIx] === null);
    const availableRow = messageRows[availableRowIx];
    availableRow[messageColumnIx] = encryptedChar;

    // If all rows are full, increment the column
    if (messageRows.every(row => row[messageColumnIx] !== null)) {
      orderedColumnIx++;
    }
  }

  // Finally, flatten and join the decrypted message
  return messageRows.flat().join('');
}

const key = 'HAMLET';
const message = 'OMYOFFENCEISRANKITSMELLSTOHEAVEN';

const encrypted = columnarEncrypt(message, key);
console.log(encrypted); // > MNAMONFIILAOERSTEOEKLEYCNEHFSTSV

const decrypted = columnarDecrypt(encrypted, key);
console.log(decrypted); // > OMYOFFENCEISRANKITSMELLSTOHEAVEN

This is already quite a bit more complex than the Vigenere cypher. But we're not ready to solve Kryptos 3 yet. Not even close!

Route transposition

Another type of transposition is called route transposition. The kind we'll do right now involves wrapping the text at a certain line length, chunking each line, stacking the chunks, and reading out one vertical line at a time.

Instead of a cipher key, this algorithm uses two numbers: a rectangle size and a block size. Let's say our rectangle size is 15 and our block size is 4. To encode the message "THE FITNESSGRAM PACER TEST IS A MULTI STAGE AEROBIC CAPACITY TEST", first we'll write it out in lines of 15 characters:

THEFITNESSGRAMP
ACERTESTISAMULT
ISTAGEAEROBICCA
PACITYTEST

Then we divide each line into blocks of 4 characters:

THEF ITNE SSGR AMP
ACER TEST ISAM ULT
ISTA GEAE ROBI CCA
PACI TYTE ST

For reasons that will be clear later, we only want to have two sizes of blocks. Right now we have too many: most blocks are 4 characters, but the ones at the end of the first three lines are 3 characters and the very last one is 2. The easiest way to fix that is to add a "padding character" (a character that isn't part of the message) to the last line. We'll use Q, since it's an uncommon letter and unlikely to confuse the message.

THEF ITNE SSGR AMP
ACER TEST ISAM ULT
ISTA GEAE ROBI CCA
PACI TYTE STQ

Much better. You can see how we have four vertical columns of blocks. Let's stack those columns up:

THEF
ACER
ISTA
PACI

ITNE
TEST
GEAE
TYTE

SSGR
ISAM
ROBI
STQ

AMP
ULT
CCA

Finally, we read out the characters from top to bottom, starting with the first letter of each row (TAIPI etc.), then the second letter of each row (HCSAT etc.), and so on.

TAIP ITGT SIRS AUC HCSA TEEY SSOT MLC EETC NSAT GABQ PTA FRAI ETEE RMI

Remove the spaces, and we have the encrypted message TAIPITGTSIRSAUCHCSATEEYSSOTMLCEETCNSATGABQPTAFRAIETEERMI.

To decrypt this message, we can start by laying it out the same way we did the original message:

TAIP ITGT SIRS AUC
HCSA TEEY SSOT MLC
EETC NSAT GABQ PTA
FRAI ETEE RMI

We'll throw this away in a moment, but it shows the "shape" of the final decryption step. More importantly, if you stack the columns up like we did before, you'll see the leftmost three lines from top to bottom have 15 characters in them and the fourth only has 11. (Note that this isn't necessarily the same as counting the number of characters in each row above—it's just a coincidence they're the same for this message!)

We could also obtain this information mathematically:

There are 56 characters in the message. 56 divided by 15 is 3 remainder 11, so there are four rows, with 15 characters in the first three rows and 11 characters in the fourth.
15 divided by 4 is 3 remainder 3, so in each of the first three rows there will be three blocks of 4 and one block of 3.
11 divided by 4 is 2 remainder 3, so in the fourth row there will be two blocks of 4 and one block of 3.
In total, there are 15 blocks: 11 blocks of 4 characters and 4 blocks of 3 characters.
4 minus 3 is 1, so there are 3 long (vertical) lines and 1 short line. The long lines will have 15 characters–the same as the total number of blocks—and the short line will have 11 characters, the same as the number of blocks with the larger number of characters.

Now we can throw away the layout above and start over. We'll write the encrypted message in four vertical lines (three lines of 15 and one line of 11).

THEF
ACER
ISTA
PACI

ITNE
TEST
GEAE
TYTE

SSGR
ISAM
ROBI
STQ

AMP
ULT
CCA

Now we'll place the columns next to each other:

THEF ITNE SSGR AMP
ACER TEST ISAM ULT
ISTA GEAE ROBI CCA
PACI TYTE STQ

And if we remove the spaces, we get the original message: THEFITNESSGRAMPACERTESTISAMULTISTAGEAEROBICCAPACITYTEST.

Here's some TypeScript to manage all this:

// Breaks an array into sub-arrays of size `chunkSize`
function chunk<T>(array: T[], chunkSize: number): T[][] {
  const result: T[][] = [];
  for (let i = 0; i < array.length; i += chunkSize) {
      const chunk = array.slice(i, i + chunkSize);
      result.push(chunk);
  }
  return result;
}

function routeEncrypt(message: string, rectangleSize: number, blockSize: number): string {
  const messageChars = message.split('');

  // Lay out the message in lines of length `rectangleSize`
  const messageLines = chunk(messageChars, rectangleSize);

  // Then break each line into chunks of length `blockSize`
  const chunkedLines = messageLines.map(line => chunk(line, blockSize));

  // Check to see if padding characters are needed at the end
  const allChunks = chunkedLines.flat();
  const finalChunk = allChunks.pop();
  const mainChunkSizes = allChunks.map(chunk => chunk.length);
  const oddChunkSize = mainChunkSizes.find(chunkSize => chunkSize !== blockSize);

  // Only add padding if the "odd chunks" (chunks at the ends of lines)
  //  are shorter than regular chunks, the final chunk isn't the same size
  //  as the odd chunks, and the final chunk isn't the same size as a
  //  regular chunk
  if (
    typeof oddChunkSize === 'number' &&
    Array.isArray(finalChunk) &&
    finalChunk.length !== oddChunkSize &&
    finalChunk.length !== blockSize
  ) {
    if (finalChunk.length < oddChunkSize) {
      finalChunk.push(...'Q'.repeat(oddChunkSize - finalChunk.length));
    } else {
      finalChunk.push(...'Q'.repeat(blockSize - finalChunk.length));
    }
  }

  // We could skip the intermediate step of "stacking" the chunks—that's just
  //  a convenience to help visualize the process—but we'll need it intact
  //  for Part 3.
  const stackedLines: string[][] = [];

  // For each block column...
  const blocksPerLine = Math.ceil(rectangleSize / blockSize);
  for (let blockIx = 0; blockIx < blocksPerLine; blockIx++) {
    // For each row...
    const numberOfRows = chunkedLines.length;
    for (let rowIx = 0; rowIx < numberOfRows; rowIx++) {
      // We'll have numberOfRows rows for each block column
      const encryptedRowIx = rowIx + (blockIx * numberOfRows);
      stackedLines[encryptedRowIx] = chunkedLines[rowIx][blockIx];
    }
  }

  // Now we read out from top to bottom, starting at the left
  const encryptedChars: string[] = [];
  for (let charIx = 0; charIx < blockSize; charIx++) {
    for (let rowIx = 0; rowIx < stackedLines.length; rowIx++) {
      if (!Array.isArray(stackedLines[rowIx])) {
        continue;
      }

      const char = stackedLines[rowIx][charIx];
      if (typeof char === 'string') {
        encryptedChars.push(char);
      }
    }
  }

  // Join and return the encrypted message
  return encryptedChars.join('');
}

function routeDecrypt(encrypted: string, rectangleSize: number, blockSize: number): string {
  // Do the math to determine the total number of chunks
  const numberOfRows = Math.ceil(encrypted.length / rectangleSize);
  const chunksPerRow = Math.ceil(rectangleSize / blockSize);
  const lastRowLength = encrypted.length % rectangleSize;
  const lastRowChunks = Math.ceil(lastRowLength / blockSize);
  const totalChunks = (chunksPerRow * (numberOfRows - 1)) + lastRowChunks;

  // If there are chunk(s) of a different size, either the
  //  "odd chunks" or the final chunk, find them so we know
  //  how many long/short vertical lines there are
  const lastChunkSize = (lastRowLength % blockSize) || blockSize;
  const oddChunkSize = rectangleSize % blockSize;

  let numberOfShortVLines: number;
  if (oddChunkSize !== blockSize) {
    numberOfShortVLines = blockSize - oddChunkSize;
  } else if (lastChunkSize !== blockSize) {
    numberOfShortVLines = blockSize - lastChunkSize;
  } else {
    numberOfShortVLines = 0;
  }

  const numberOfLongVLines = blockSize - numberOfShortVLines;

  // Determine the length of the short and long lines
  const longVLineLength = totalChunks;
  const shortVLineLength = totalChunks -
    ((oddChunkSize !== blockSize ? numberOfRows - 1 : 0) +
     (lastChunkSize !== blockSize ? 1 : 0));

  const stackedLines: string[][] = [];
  let encryptedIx = 0;

  // For each vertical line...
  for (let vLineIx = 0; vLineIx < blockSize; vLineIx++) {
    // The long lines come first, then the short lines
    const currentVLineLength = vLineIx < numberOfLongVLines ?
      longVLineLength :
      shortVLineLength;

    // For each row in the current vertical line length...
    for (let rowIx = 0; rowIx < currentVLineLength; rowIx++) {
      stackedLines[rowIx] ??= [];

      // Place the next character from the encrypted message
      stackedLines[rowIx][vLineIx] = encrypted[encryptedIx++];
    }
  }

  // Now we'll place the blocks next to each other.
  // First, we need to figure out how many blocks are in each row
  const blocksPerRow = Math.ceil(rectangleSize / blockSize);
  const lastRowBlocks = Math.ceil(lastRowLength / blockSize);

  const messageLines: string[][] = [];
  let stackedLineIx = 0;

  // For each column of blocks...
  for (let columnIx = 0; columnIx < blocksPerRow; columnIx++) {
    const rowsInBlock = columnIx < lastRowBlocks ? numberOfRows : numberOfRows - 1;

    // For each row in the column...
    for (let rowIx = 0; rowIx < rowsInBlock; rowIx++) {
      messageLines[rowIx] ??= [];

      // Grab the next line from the stack and place it
      messageLines[rowIx].push(stackedLines[stackedLineIx++].join(''));
    }
  }

  return messageLines.flat().join('');
}

const rectangleSize = 15;
const blockSize = 4

const encrypted = routeEncrypt(
  'THEFITNESSGRAMPACERTESTISAMULTISTAGEAEROBICCAPACITYTEST',
  rectangleSize,
  blockSize
);
console.log(encrypted);
// > TAIPITGTSIRSAUCHCSATEEYSSOTMLCEETCNSATGABQPTAFRAIETEERMI

const decrypted = routeDecrypt(encrypted, rectangleSize, blockSize);
console.log(decrypted);
// > THEFITNESSGRAMPACERTESTISAMULTISTAGEAEROBICCAPACITYTESTQ

Solved! Now you know all the operations you need to decode Kryptos 3, which we'll do in the next post.

Acknowledgments

Thanks to the following, who made this series possible:

The NSA: The CIA Kryptos Sculpture (Declassified)
UC San Diego: The Kryptos Sculpture Solutions
Wikipedia: Kryptos, Transposition cipher

Blog

Solving the CIA Kryptos Code (Part 2)

Isaac Lyman

Keyed columnar transposition

Route transposition

Acknowledgments

Join Our Newsletter. No Spam, Only the good stuff.

Related