Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know that Vigenère can broken using auto-correlation (as explained at cryptool-online.org). Now my question is: Why does this also work with autokey (tested it using crypttool)?

To prove that I have already put work into this, I have read Simon Singh: “The Code Book”, F.L.Bauer: “Decrypted Secrets”. Though the latter book said in does not work the same way in autokey than it does in Vigenère. Why is there still a maximum of coincidences when the text is shifted by the key length?

share|improve this question
up vote 1 down vote accepted

In a Vigenère cipher, the $i$-th ciphertext letter $c_i$ is calculated as $p_i + k_{i \bmod \ell}$, where $p_i$ is the $i$-th plaintext letter, $k_i$ is the $i$-th key letter, and $\ell$ is the length of the key. Thus, the difference between two ciphertext letters at positions $i$ and $j$ is $$c_i - c_j = p_i - p_j + c_{i \bmod \ell} - c_{j \bmod \ell}.$$

Normally, for this difference to be zero, the difference between the key letters would have to just happen to cancel out the difference between the plaintext letters. When $i \equiv j \pmod \ell$, however, the last two terms cancel out, leaving just $p_i - p_j$, which, since the plaintext typically has an uneven letter frequency distribution, is more likely to be zero than one would otherwise expect.

Now, consider the autokey cipher, where (beyond the first $\ell$ letters) $c_i = p_i + p_{i-\ell}$. Now the difference between two ciphertext letters is given by $$c_i - c_j = p_i - p_j + p_{i-\ell} - p_{j-\ell}.$$ This time, when $i - j = \ell$, it's the middle terms that cancel, leaving just $p_i - p_{j-\ell}$ $=$ $p_i - p_{i-2\ell}$.

Again, it's a lot more likely for a single pair of plaintext letters to be identical than it is for the differences of two pairs of letters to cancel out just by chance. Exactly how much more likely depends on details of the plaintext frequency distribution, but the qualitative behavior is quite robust and shows up for most naturally occurring letter frequencies.


Ps. Note that the conditions for this cancellation to occur are different. For the Vigenère cipher, cancellation occurs whenever $i - j$ is a multiple of the key length $\ell$, producing a characteristic comb-shaped autocorrelation plot. For an autokey cipher, however, cancellation only occurs when $i - j$ exactly equals the key length, resulting in just a single peak.

share|improve this answer

It works with autokey system because the key itself have a bias : in the key is much more E than other letters (this is a natural consequence of using a clear text as key).

share|improve this answer
    
How does that result in a maximum of correlations when shifting by the length of the key? – joz Nov 28 '15 at 16:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.