2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
0
$\begingroup$

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).

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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