3
$\begingroup$

Here is my question when learning Vigenère cipher, can we perform frequency analysis attack toward this cipher?

My first impression is no, because each column of its matrix has exactly 26 English letters. But I also know that this cipher is not secure. So, my question is, whether and how we can perform frequency attack towards this cipher?

$\endgroup$
  • 2
    $\begingroup$ Hint: you're reusing a key, and there is no information taken into account from previous encryption operations to randomize the results. $\endgroup$ – Maarten Bodewes Sep 4 at 15:13
2
$\begingroup$

Yes, Vigenère cipher is vulnerable to frequency analysis.

BUT! It requires some pre-processing first.

I propose to walk us through a small example of how frequency analysis can help decrypting Vigenère cipher in order to get a better idea of the process.

Firstly, it is important to notice that if you were to choose a key length of 1, then Vigenère cipher becomes Caesar cipher, which is one of the best examples of ciphers sensitive to frequency analysis!

Let us consider the following ciphertext encrypted using Vigenère:

Vyc qxgv gpdzfcdq pks yigimsp jm iaov tmbiivzlv foeygcxg erl exfhfpb mvgd ojbqmcw pgr uf rwth jlkpg pgzlvl qce scwstjrpgr vycb vzgrpar. O rimvkoodcg bg kucpeza rl tlgcpghm kjf udkyu ngia htrbxmwqeya tsukftmwe rls ewvvppkm hfpbl ou ncae ou dyiasorrxvon tmcvsrkq, ih qqdkjgwerrt mvg nyn mvck yc tzifpxmvo nmgdg ceb ih qqetxgqg r pttrgi rwth vyc gxgwcrh pwnc zt vcticrm.

If we were to perform a simple frequency analysis on it, we do not get really insightful information:

letter  occurrences  %  
G           25      8.2%
R           21      6.89%
C           20      6.56%
V           19      6.23%
P           17      5.57%
T           16      5.25%
M           16      5.25%
I           13      4.26%
E           12      3.93%
O           11      3.61%
K           11      3.61%
Q           11      3.61%
W           10      3.28%
Y           10      3.28%
L           9       2.95%
F           9       2.95%
H           9       2.95%
D           8       2.62%
B           8       2.62%
X           8       2.62%
S           8       2.62%
Z           7       2.3%
A           7       2.3%
U           7       2.3%
N           7       2.3%
J           6       1.97%

On a total of 305 characters (not counting punctuation marks), we can see the raw frequency analysis is not helping on first sight, as it's far from matching English's frequency.

But, if we study the n-grams appearing in that ciphertext, we can notably see the following occurrences:

n-gram    occur.  positions
RWTH        2       74,278
HFPB        2       54,186
IHQQ        2       219,261
VYC         3       0,102,282
MV          5       58,116,232,238,250

Now, the positions of these repetitions is important, let us take a look at the distance between any two of them:

n-gram    positions     distances
RWTH        74,278      278-74= 204
HFPB        54,186          132
IHQQ        219,261         42
VYC         0,102,282       102, 180
MV    58,116,232,238,250    58, 16, 6, 12

Now, if we are to look at each of these distances, we can see that among all the common divisors there are between any two distances, the most common one is 6: $\gcd(12, 42, 102, 132, 180, 204) = 6$

This allows us to infer the size of the key could probably be 6.

From there, we just need to split it into 6 columns (I mean in Python it would be [trimmed[i::6] for i in range(6)]) and consider each column as a single string encrypted using Caesar cipher! We thus get:

Vvcypvveehgmujgctvgrokacjutquevhuuonrqegciocqggvwnt
ygdijtzyrfdcflzejyridurpfnrekrvfndrtkdrnkfneeriycci
cpqgmmlglpowrklsrcpmcclgugbyflppcyrmqkryypmbtprcrzc
qdpiibvcebjpwpvcpbavgpthdixatspbaixcijtncxgixtwghtr
xzkmaifxxmbgtglwgvrkbelmkamtmekleavvhgmmtmdhgttxpvm
gfssoiogfvqrhpqsrzOogzgkyhwswwmoososqwvvzvgqqrhgwc

And now we can again perform a frequency analysis like we would for any Caesar cipher, but this time on each string independently: Vvcypvveehgmujgctvgrokacjutquevhuuonrqegciocqggvwnt gives:

let.   occ.  % 
V       7   13.73%
G       6   11.76%
U       5   9.8%

And we know that in English the frequency table goes as follows:

let.  % 
E   12.02
T   9.10
A   8.12
O   7.68

Which means that since the most common letters in the English alphabet are E, T A and O, we can assume they are very likely represented by the most common letters in the cipher too. (Sadly, this won't work here for all 6 Caesar ciphertexts we got, and some require a better frequency analysis using more advanced tools such as cross-entropy or chi-squared tests...)

So, let us find in Vigenère matrix which column is using V for E or for T, G for T (or for E), and U,C or E for A! We find that if V is used for E, we would be in the case where key would be R and then G would match P, and U would be the matches for D, which doesn't really fit our frequency table for English... But if V is used for T, then we would be in the case where the key is C, and then the cleartext for G would effectively be E! Now this latter case seems way more plausible, so we have probably found the first letter of the key: C. Notice that in practice, instead of performing such deduction, we would typically use the graphs of the frequency of each letter under every 26 possible keys to find which one is the closest to the English distribution. (Well, in fact we would probably be computing the cross entropy between the English frequency and the frequency we obtain from our ciphertext when it is decrypted as a Caesar cipher for each letter of the alphabet and we would retain the letter that has the smallest entropy as our best candidate.)

If we do the same for ygdijtzyrfdcflzejyridurpfnrekrvfndrtkdrnkfneeriycci, we can find that the most probable shift would be for index 17, that is the letter R. But here it is not trivially done by hand anymore and I've relied on the cpqgmmlglpowrklsrcpmcclgugbyflppcyrmqkryypmbtprcrzc gives Y when analysed in turn by frequency like Caesar cipher.
qdpiibvcebjpwpvcpbavgpthdixatspbaixcijtncxgixtwghtr gives in turn P.
xzkmaifxxmbgtglwgvrkbelmkamtmekleavvhgmmtmdhgttxpvm gives T (with I also a possibility).
Finally gfssoiogfvqrhpqsrzOogzgkyhwswwmoososqwvvzvgqqrhgwc will be a bit more of a problem: frequency analysis tells us it could probably be S, E, N, D, C or O ... What a pain! (However, notice cross-entropy is the lowest for O)

However, since we've greatly reduced the number of candidates, we can simply try all of them until our ciphertext decrypts using Vigenere decryption to an English text.

And this finally works here with the CRYPTO keyword and gives the following plaintext:

The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct.

(A quote by D.Knuth)

$\endgroup$
  • 1
    $\begingroup$ In the end, once you know the key length, the hardest part is to solve multiple Caesar ciphers in a row. :) BTW, there are many resources on the internet actually! Here is an example of how you could construct a "Match Score" between the English frequency and the letter frequencies you get after Caesar decryption to perform the Caesar attack you need to do at the end: inventwithpython.com/hacking/chapter20.html and here is a cross-entropy calculator in JS that allows you to solve the last part easily: nayuki.io/page/automatic-caesar-cipher-breaker-javascript $\endgroup$ – Lery Sep 4 at 23:03
1
$\begingroup$

It's actually rather easy to break the Vigenère cipher.

The first published method to decrypt Vigenère without having knowledge of the key (breaking the cipher) was done in 1863 and this could be done by hand.

Since the keyword is always repeating you would find a lot of repetitions in a ciphertext.

For example as described in Wikipedia:

If the ciphertext has lots of A's in it you can assume that most of these A's are indeed an E in plaintext, because E is the most common letter in the English language (assuming that the plaintext is English of course).

But that fact alone is not enough to break Vigenère. The actual attack angle lies in the repetition of the key.

If you correctly guess the key length you can just treat it as a Caesar cipher.

There are a possibility of $26^n$ keys, where $n$ is the key length. I.e. if the known key length is $4$ there would be a total of $26^4 = 456976$ possible keys.

Once the key length is known it's easy to decipher any text (again see Wikipedia for the exact procedure).

$\endgroup$
  • $\begingroup$ The total number of possible keys doesn't matter at all, tbh. It is rather misleading. The important bit for the key is: You can solve it step-by-step, like they break passwords in movies. So the difficulty of the attack would be more like $26$ times $26$ (not really true, because frequency analysis scales linear with the length of the ciphertext). Of course, such a divide-and-conquer doesn't work for modern encryption. $\endgroup$ – tylo Sep 4 at 20:04

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.