Running Key Cipher

Introduction §

The Running Key cipher has the same internal workings as the Vigenere cipher. The difference lies in how the key is chosen; the Vigenere cipher uses a short key that repeats, whereas the running key cipher uses a long key such as an excerpt from a book. This means the key does not repeat, making cryptanalysis more difficult. The cipher can still be broken though, as there are statistical patterns in both the key and the plaintext which can be exploited.

If the key for the running key cipher comes from a statistically random source, then it becomes a 'one time pad' cipher. One time pads are theoretically unbreakable ciphers, because every possible decryption is equally likely.

The Algorithm §

The 'key' for a running key cipher is a long piece of text, e.g. an excerpt from a book. The running key cipher uses the following tableau (the 'tabula recta') to encipher the plaintext:

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

To encipher a message, write the key stream above the plaintext, in this case our key is from a Terry Pratchett book: 'How does the duck know that? said Victor'. If we needed to encipher a longer plaintext, we could just continue reading from the book.

HOWDOESTHEDUCKKNOWTHATSAIDVI
DEFENDTHEEASTWALLOFTHECASTLE

Now we take the letter we will be encoding, 'D', and find it on the first column on the tableau. Then, we move along the 'D' row of the tableau until we come to the column with the 'H' at the top (The 'H' is the keyword letter for the first 'D'), the intersection is our ciphertext character, 'K'.

So, the ciphertext for the above plaintext is:

HOWDOESTHEDUCKKNOWTHATSAIDVI
DEFENDTHEEASTWALLOFTHECASTLE
KSBHBHLALIDMVGKYZKYAHXUAAWGM

Javascript Example §

Plaintext
Key Stream

Ciphertext

Cryptanalysis §

Vigenere-like ciphers were regarded by many as practically unbreakable for 300 years. The running key cipher is in general more difficult to break than the Vigenere or Autokey ciphers. Because the key does not repeat, finding repeating blocks is less useful. The easiest way to crack this cipher is to guess or obtain somehow a piece of the plaintext, this allows you to determine the key. With some of the key known, you should try and identify the source of the key text.

When trying to crack this cipher automatically, high order language models are required. The 4-grams used to break Vigenere ciphers are not good enough for breaking running key ciphers. This page (coming soon) describes the use of a second order word level model used to break running key ciphers. In essence, the key and plaintext are built simultaneously from sequences of words such that the key sequence and the plaintext sequence create the ciphertext. The restrictions that english words place on allowable characters can be enough to determine the key. If the key contains very rare words, though, the algorithm may find something that scores higher but consists of more common words.