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
Top comments (0)