Finding a keylength in a repeating key XOR cipher

Question

In an old cryptography FAQ, I found the following step described for determining a the length of the key a cipher was repeatedly XORed against:

1. Discover the length of the key by counting coincidences. (See Gaines [GAI44], Sinkov [SIN66].) Trying each displacement of the ciphertext against itself, count those bytes which are equal. If the two ciphertext portions have used the same key, something over 6% of the bytes will be equal. If they have used different keys, then less than 0.4% will be equal (assuming random 8-bit bytes of key covering normal ASCII text). The smallest displacement which indicates an equal key is the length of the repeated key.

The wording of the bolded text is the part I'm confused with. Given that my plaintext equals the string "This is a secret message", would I be comparing the first n number of bytes with a second set of n number of bytes that is offset from the first (e.g. the xor'd version of "Th" with "is", if I was comparing 2-byte chunks of the cipher against itself)?

If not, what's the correct way to interpret this passage? Thank you.

Answer 1

This looks like a sliding window approach to calculating the index of coincidence. So you would have something like:

ABCDE FGHIJ KLMNO
OACBD EFGHI JKLMN

Given enough cyphertext, you'll discover a length at which the IC is high; this is a candidate keylength for the cyphertext, because you've shifted the two texts by one keylength. Multiples of this size will also return high ICs.

---

Another way to brute force the key length of a Vigenère cypher by iterating through keysizes of different lengths, computing the Hamming distance of adjacent cyphertext blocks of that length, normalizing the distance to the keylength, and taking the smallest value as your keylength. In this case, given cyphertext:

CYPHERCYPHERCYPHERCYPHER

for a guess of keysize 4 you'd split the text into

CYPH
ERCY
PHER
CYPH
ERCY
PHER

and get the Hamming distances that way. You'd keep going for a few more keysizes and should eventually 'settle' on 6 (in this highly contrived example, at least).

Answer 2

You'd be trying each possible displacement (offset).

Suppose the ciphertext is CXEKCWCOZKUCAYZEKW. Here's displacement 1:

CXEKCWCOZKUCAYZEKW
 CXEKCWCOZKUCAYZEKW

At displacement 1, there are no matches (nothing where the a letter in the top line is equal to the letter immediately below it).

Here's displacement 2:

CXEKCWCOZKUCAYZEKW
  CXEKCWCOZKUCAYZEKW
      ^

You can see that, at displacement 2, there is one match.

Here's displacement 3:

CXEKCWCOZKUCAYZEKW
   CXEKCWCOZKUCAYZEKW

At displacement 3, there are no matches.

In this way, you can count the number of matches at each displacement.

The idea is that, if you line up the ciphertext with itself displaced by $k$, where $k$ is the period of the keystream (i.e., the length of the key), then you get a match in the ciphertext (offset by $k$ places) if and only if there is a match in the plaintext (offset by $k$ places). Now it's a property of English language that the frequency distribution of English letters is not uniform: some are more likely than others. If you pick two positions at random from an English text, there's about a 6% chance (say) that those two positions have the same letter. Consequently, when you've guessed $k$ correctly, there's about a 6% chance that any particular ciphertext letter matches the one $k$ positions later.

In contrast, when you line up the ciphertext with itself displaced by something displacement that does not match the key length, the chances of a match at any particular position are much smaller (1/256, if ciphertexts are bytes; 1/26, if ciphertexts are letters).