# Obtaining the key length from the ciphertext of an auto-encipher

I'm revising for a cryptography exam at the moment and I'm having some problems with a question.

The question looks for the key length of a cipher given that the word "earthquake" appears in the plaintext.

Ciphertext: aaatr ksams itahb netrs weurs rheti aadne ttrht eakgt snqid s

I was wondering how I use the fact that the word "earthquake" appears in the plaintext to make it easier to obtain the key length?

At the moment, I'm just using the method of looking for repeated letters in the ciphertext to obtain a possible key length.

EDIT: Here's the actual question:

Consider the following ciphertext, [12 marks]

aaatr ksams itahb netrs weurs rheti aadne ttrht eakgt snqid s

i) Provide some evidence to suggest that this is not a substitution cipher.
ii) Determine the keylength of this cipher given that the word earthquake appears in the plaintext.
iii) Hence or otherwise decrypt this message to recover the plaintext.
iv) Historically a variant of this cipher had a very important application. Briefly describe the variant and the application.

-
Could you describe the cipher you're trying to analyze? I assume it's some variant of the autokey cipher, but it would help to know the details. – Ilmari Karonen Jan 1 '12 at 19:55
I've updated the question with the actual question from the paper. As you can see, all I know is it's not a substitution cipher. The fact that the keylength is being looked for leads me to think that it's either a Vigenere cipher or auto-encipher(auto-key). – cian1500ww Jan 5 '12 at 16:52

Both the Vigenère and autokey ciphers are classified as polyalphabetic substitution ciphers, so the cipher in your exam is not likely to be either of those. Rather, the phrasing of the question suggests that it belongs to the other branch of classical ciphers, transposition ciphers.

Indeed, looking at the letter frequencies of the ciphertext strongly suggests that, being similar to the frequency distribution of plain English text:

A (8) ########
T (8) ########
S (6) ######
E (5) #####
R (5) #####
H (3) ###
I (3) ###
N (3) ###
D (2) ##
K (2) ##
B (1) #
G (1) #
M (1) #
Q (1) #
U (1) #
W (1) #


The question also implies that this cipher has a key, so we're looking at a keyed transposition cipher. The simplest one of those is probably a columnar transposition. These come in two varieties: regular and irregular. If this were the regular kind, the length of the ciphertext (51 letters) would be a multiple of the key length; but since the only factors of 51 are 3 and 17, neither of which seems likely for a key length, we can guess that we're dealing with the irregular type.

Now, the obvious way to try to guess the key length (even without knowing anything about the plaintext) would be to note that the ciphertext contains exactly one Q and one U. Those letters very often follow one another in English, as in the word "earthQUake", so we can assume that they're probably adjacent in the plaintext. So we should try to divide the ciphertext into n groups (where n is, say, between 4 and 10) of approximately equal length (since this is an irregular columnar transposition, some of the groups will be one letter longer than the others) such that the Q and the U end up at the same position within their groups. Also, since we know the surrounding letters of the QU pair, we should check that those (particularly the Ks, of which there are only two) also end up in suitable positions.

If we try that for various values of n, we might find that dividing the ciphertext into six groups of eight and nine letters each looks promising:

aaatrksam sitahbne trsweursr hetiaadn ettrhtea kgtsnqids

Notice how the Q, U and K all line up in the fifth position of their groups. We can now try to write these groups one per line and try rearrange them to form "earthquake" vertically:

6 kgtsnqids
3 trsweursr
1 aaatrksam
5 ettrhtea
2 sitahbne

This is looking very promising: we almost have the word "earthquake", and the surrounding letters start to form meaningful-looking words. However, there are a few problems left: the fifth group doesn't quite line up with the rest, and the longest groups are not all at the top as they should be. Let's try to fix the first issue by shifting group 5 right by one letter:

6 gtsnqids
3 trsweursr
1 aaatrksam
5 ttrhteak
2 sitahbne

Now group 6 looks misplaced, but the fix is obvious — it clearly belongs at the bottom, not at the top:

3 trsweursr
1 aaatrksam
5 ttrhteak
2 sitahbne
6 gtsnqids

And now we can read the plaintext from top down:

thats great it starts with an earthquake birds and snakes rem

(Ps. If you don't recognize the reference, listen to this.)

I do have to admit, however, that if there's some simple shortcut to reliably determine the key length without (mostly) solving the cipher, I'm not aware of it.

Edit: I did think of one shortcut: if the keylength were less than 6, the sixth letter of "earthquake", Q, would have to line up with one of the earlier letters of the same word, and thus follow it in the ciphertext. Since the only Q in the ciphertext follows an N, which is not found in "earthquake", the keylength must be at least 6. We can also see that keylength 6 does look plausible (the pairs EU, AA, RK and TE are all found int the ciphertext), while 7, 8 and 9 are impossible (neither RE, EK nor EE are found in the ciphertext). Alas, this method doesn't let us conclusively rule out keylengths of 10 or more, even if they do seem a priori unlikely.

-