Can frequency attack be successful on Vigenère cipher? 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?
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)