關於重合指數的問題？

01-28

如圖m=1、m=2……m=5的重合指數分別是如何求出的？

請題主下次發圖片時注意方向，脖子都快扭斷了。。。

重合指數法（index of coincidence，又稱一致檢索法）是Wolfe Friendman於1920年提出的方法。

它可以進一步地檢驗多表代換密碼的密鑰長度。正如圖中所述，首先利用Kasiski測試法猜測出密鑰的長度，然後利用重合指數法進行驗證我們的猜測對不對。

根據基本測試和計算，26個字母構成的一段有意義文字中，任取兩個元素剛好相同的概率約為0.065（有說0.068，反正個人寫作習慣不同，這個概率是有偏差的），所以如果一段明文是用同一個字母做密鑰加密的話，這個概率是不變的。如果你對數學比較感興趣，其計算方法如下：

如果英文的26個字母在有意義文本中出現的概率分別為： $p_{0} ,p_{1},...,p_{25}$ ，那麼文本中兩個元素相同的概率為

$I_capprox sum_{i=0}^{25}{p_i^2} =0.065$ 。

但是如果是用不同的字母，這個概率是會發生變化的，這時相當於在一個隨機的字母串（而不是一段有意義的文字）中抽取兩個字母相等，其概率很容易計算是0.038。

$I_capprox sum_{i=0}^{25}{(frac{1}{26} )^2} =0.038$ 。

以上是基礎數學知識，下面來說怎麼算。

首先根據Kasiski測試法得到了一個猜測出來的密鑰長度m=5。我們可以直奔主題驗證m=5時的概率，但是也可以謹慎地從m=1開始驗起。

驗證m=1的情況方法如下：

首先將密文（按順序）排成一列，兩兩選取字母（取遍所有可能情況），計算其相同的概率。當然像圖中所述例子，用手算顯然不是我們想要的，我們如果自己想算的話可以利用計算機程序。我們用「字母相同的次數」除以「總抽取次數」即可得這一概率。最後計算出來的結果是0.045，很顯然它更接近0.038，而不是0.065。

驗證m=2的情況方法如下：

將密文按順序

1 2

3 4

5 6

...

排成兩列，對每一列用類似m=1的方法去做，則每一列可以得到一個概率，也就是說我們到手了兩個概率0.046，0.041，顯然它們也是離0.038更近，離0.065更遠。

m=3，m=4的情況類似可做。

見證奇蹟的時刻到了，我們終於等到驗證m=5的情況了。

首先將密文按順序

1 2 3 4 5

6 7 8 9 10

...

排成5列，對每列計算「任取兩個字母剛好相同」的概率，分別為0.063，0.068，0.069，0.061，0.072，好了，數字完全不一樣了，完全是我們希望的節奏了。它們和0.065非常滴接近。

這時，我們可以驕傲地宣布：我們的猜想是正確地，m=5。

不用多久，我就會升職加薪，當上總經理，出任CEO，迎娶白富美，走上人生巔峰。想想還有點小激動呢，嘿嘿~~

等等，我只是猜到了密鑰的長度，還沒有確定密鑰到底是什麼呢！

×%%#@×……

我猜中了開頭，卻猜不到這結局……

3月22日的更新：

有知乎上的朋友想我詢問算維吉尼亞密碼的源程序，我就貼出來吧，幾個月前寫的程序，當時解出了後面的1.21練習(b)道題，現在有些記不清楚了，只能解釋到這裡了：

一共用到了2個程序，第一個程序，首先確定長度m,，這裡假設m=6:

#include &

main()

{

char data[]="KCCPKBGUFDPHQTYAVINRRTMVGRKDNBVFDETDGILTXRGUDDKOTFMBPVGEGLTGCKQRACQCWDNAWCRXIZAKFTLEWRPTYCQKYVXCHKFTPONCQQRHJVAJUWETMCMSPKQDYHJVDAHCTRLSVSKCGCZQQDZXGSFRLSWCWSJTBHAFSIASPRJAHKJRJUMVGKMITZHFPDISPZLVLGWTFPLKKEBDPGCEBSHCTJRWXBAFSPEZQNRWXCVYCGAONWDDKACKAWBBIKFTIOVKCGGHJVLNHIFFSQESVYCLACNVRWBBIREPBBVFEXOSCDYGZWPFDTKFQIYCWHJVLNHIQIBTKHJVNPIST";

char alpha[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

char crypt_data[200];

int count = 0;

int i,j;

int Efi2=0,n2=0,n=0;

int m=6;

double Icx;

memset(crypt_data,0,sizeof(crypt_data));

for (i = 0; i &< sizeof(data)-1; )

{

crypt_data[i/m]=data[i+5];

i=i+m;

}

printf("crypt_data:
%s
", crypt_data);

n=strlen(crypt_data);

n2=n*(n-1);

printf("length of crypt_data :%d
",n);

for (i = 0; i &< sizeof(alpha)-1; )

{

for(j = 0; j &< strlen(crypt_data); j++)

{

if(crypt_data[j] == alpha[i]) count++;

}

// printf("Alpha[%d] %c:%d
",i, alpha[i],count);

printf(" %c:%d", alpha[i],count);

Efi2 = Efi2+count*(count-1);

count=0;

i++;

}

printf("
Efi2:%d
",Efi2);

printf("n2:%d
",n2);

Icx=(double)Efi2/n2;

printf("Icx: %f
",Icx);

}

第二個程序decrypt.c，解出明文：

#include &

main()

{

char crypt_data[]="KCCPKBGUFDPHQTYAVINRRTMVGRKDNBVFDETDGILTXRGUDDKOTFMBPVGEGLTGCKQRACQCWDNAWCRXIZAKFTLEWRPTYCQKYVXCHKFTPONCQQRHJVAJUWETMCMSPKQDYHJVDAHCTRLSVSKCGCZQQDZXGSFRLSWCWSJTBHAFSIASPRJAHKJRJUMVGKMITZHFPDISPZLVLGWTFPLKKEBDPGCEBSHCTJRWXBAFSPEZQNRWXCVYCGAONWDDKACKAWBBIKFTIOVKCGGHJVLNHIFFSQESVYCLACNVRWBBIREPBBVFEXOSCDYGZWPFDTKFQIYCWHJVLNHIQIBTKHJVNPIST";

//char crypt_data[]="KCCPKBGUFDPHQTYAVINRRTM";

int key[]={2,17,24,15,19,14};

char data[200];

int count = 0;

int i,j;

int Efi2=0,n2=0,n=0;

int m=6;

double Icx;

memset(data,0,sizeof(data));

for (i = 0; i &< strlen(crypt_data)-1; i++)

{

data[i]=crypt_data[i]-key[i%m];

if (data[i]&<65) data[i]=data[i]+26;

printf("%d %d
", crypt_data[i], data[i]);

}

printf("data:
%s
", data);

}

10月15日更新：

繼算出m=5之後，下面就是算key了，趁著熱乎勁就算算吧，書上沒有說的太細，但給了公式，不知大家算出來沒有，我姑且就把算的程序貼出來吧，供大家參考。

char alpha[]="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

float probab[26]={0.082,0.015,0.028,0.043,0.127,0.022,0.020,0.061,0.07,0.002,0.008,0.04,0.024,

0.067,0.075,0.019,0.001,0.06,0.063,0.091,0.028,0.01,0.023,0.001,0.02,0.001};

memset(crypt_data,0,sizeof(crypt_data));

//strcpy(crypt_data,"CVABWEBQBUAWWQRWWXANTBDPXXRDWBFAXCWMNJJFAIACNRNCATBWKDMCDCQQXWK");

//strcpy(crypt_data,"HOEITESEWOOEGMFTIFUDSTNSNVTNDPASNHESBGSEGEMRDRSHEAIEORTHNHOANOE");

//strcpy(crypt_data,"RARANOBQRASAJNVRAPTCXUGRJRUQTHLVGRLJHNGYNQRRGINRYQPVEEBRVRHIRIE");

//strcpy(crypt_data,"EHAXXPQEVKXHMKGZKSEMMIMEEVLWYXJBLZEIWMLPRJVELMRQEEEKWMJTRCPIMI");

strcpy(crypt_data,"EMTXBHMRXXXBMGXXLKMGXAGLLPHTGTHFLBKKRGXHBTLMXGWHVBEAAXJKZLWWGF");

n1=strlen(crypt_data);

printf("n :%d
",n1);

for (k=0;k&<26;k++)

{

for (i = 0; i &< sizeof(alpha)-1; )

{

for(j = 0; j &< strlen(crypt_data); j++)

{

if(crypt_data[j] == alpha[i]) count++;

}

// printf("Alpha[%d] %c:%d
",i, alpha[i],count);

//printf(" %c:%d %03f", alpha[i],count,(float)count/n1);

mg = mg + probab[(i-k+26)%26]*(float)count/(n1);

count=0;

i++;

}

printf("
Mg(%d):%03f
",k,mg);

mg=0;

}

結果與書上表1.4 $M_{G}$ 的值相差無幾

至此，採用重合指數法Index Of Coincidence 破解維吉尼亞密碼Vigenere Cipher 圓滿完成。

解後感：真難以想像Friedman當時是怎麼想到破解思路的，我光讀和理解都要費很大的勁，人家可是憑空想出來的，可能無法簡單用「佩服」來表達，難道是上帝派來的光明使者？

=====================================================================

***************************************************************************************************************

10月13日回答：

這一段也把我卡住了，經過一整天的思考和計算，發現答案就在公式 $I_{c}(x)=frac{sum_{i=0}^{25}{f_{i} (f_{i} -1)} }{n(n-1)}$ 中。為了計算 $f_{i}$ ，需要先構造出 $y_{1}, y_{2},y_{3}...y_{m},$ 的矩陣出來，就以書中的維吉尼亞加密數據為例，

CHREEVOAHMAERATBIAXXWTNXBEEOPHBSBQMQEQERBW

RVXUOAKXAOSXXWEAHBWGJMMQMNKGRFVGXWTRZXWIAK

LXFPSKAUTEMNDCMGTSXMXBTUIADNGMGPSRELXNJELX

VRVPRTULHDNQWTWDTYGBPHXTFALJHASVBFXNGLLCHR

ZBWELEKMSJIKNBHWRJGNMGJSGLXFEYPHAGNRBIEQJT

AMRVLCRREMNDGLXRRIMGNSNRWCHRQHAEYEVTAQEBBI

PEEWEVKAKOEWADREMXMTBJJCHRTKDNVRZCHRCLQOHP

WQAIIWXNRMGWOIIFKEE

當M=1時，一行對應一個字母，形成1列313行矩陣，計算各字母的出現頻率：

A:19 B:15 C:8 D:7 E:26 F:6 G:15 H:15 I:11 J:9 K:10 L:12 M:17 N:15 O:7 P:8 Q:10

R:24 S:9 T:14 U:4 V:10 W:16 X:20 Y:3 Z:3

$sum_{i=0}^{25}{f_{i}(f_{i}-1) }$ =19*(19-1)+15*(15-1)+8*(8-1)…=4364

n*(n-1)=313(313-1)=97656

$I_{c}(x)$ =4364/97656=0.045

當M=2時，一行對應2個字母，形成2列，156行矩陣(第157行只有一個字元，忽略)，第一列的所有行：

crypt_data: CREOHARTIXWNBEPBBMEEBRXOKASXEHWJMMKRVXTZWALFSATMDMTXXTIDGGSEXJLVVRUHNWWTGPXFLHSBXGLHZWLKSINHRGMJGXEPANBEJARLRENGXRMNNWHQAYVAEBPEEKKEARMMBJHTDVZHCQHWAIXRGOIKE

計算各字母的出現頻率：

A:10 B:8 C:2 D:3 E:14 F:2 G:8 H:10 I:5 J:5 K:6 L:6 M:9 N:7 O:3 P:4 Q:2 R:11 S:5

T:7 U:1 V:5 W:8 X:12 Y:1 Z:3

$sum_{i=0}^{25}{f_{i}(f_{i}-1) }$ =10*(10-1)+8*(8-1)...=1104

n(n-1)=156*(156-1)=24180

$I_{c}(x)$ =1104/24180=0.046

第二列的所有行:

HEVAMEABAXTXEOHSQQQRWVUAXOXWABGMQNGFGWRXIKXPKUENCGSMBUANMPRLNEXRPTLDQTDYBHTAJAVFNLCRBEEMJKBWJNGSLFYHGRIQTMVCRMDLRIGSRCRHEETQBIEWVAOWDEXTJCRKNRCRLOPQIWNMWIFE

同樣按照上述的計算：

$I_{c}(x)$ =0.041

當m=5時，一行包括5個字母，形成5列，62行矩陣，第一列的所有行：

CVABWEBQBUAWWQRWWXANTBDPXXRDWBFAXCWMNJJFAIACNRNCATBWKDMCDCQQXWK

A:7 B:6 C:6 D:4 E:1 F:2 G:0 H:0 I:1 J:2 K:2 L:0 M:2 N:4 O:0 P:1 Q:4 R:3 S:0 T:2

U:1 V:1 W:9 X:5 Y:0 Z:0

$I_{c}(x)$ =246/3782=0.065

第2列的所有行：

HOEITESEWOOEGMFTIFUDSTNSNVTNDPASNHESBGSEGEMRDRSHEAIEORTHNHOANOE

以此類推，你可以試試看算算得到多少。

我的計算結果大部分與書中的相符，少數差個0.001什麼的，感覺上計算方法應該是正確的。

我是憑興趣看這本書的，這一塊是我遇到的第一個非常困難的地方，不知道後面是不是有更難的。忘了在哪兒看到的，大概意思是說：如果加密是智慧的代表，那麼解密就是才華橫溢的體現。

我只是百度了重合指數法就來到了這個問題，和題主在一模一樣的位置卡住了！

--------------------------------------------------------------------------------------------------------------------

兩小時後的更新

作業里要求用重合指數法實現密碼分析，以代碼實現，如下，也許能幫助理解。

a是一個char類型的數組。

---------------------------------------------------------------------------------------------------------------------

string output = "";

for (int i = 0; i &< m; i++)

{

int count = 0;

for(int j = i; j &< a.Length -m; j += m)

{

for(int k = j + m; k &< a.Length; k += m)

{

if(a[j] == a[k])

{

count++;

}

double likelihood = (count * 2.0) / (a.Length/m)/(a.Length/m -1);

output += likelihood ;

output +=
;

-----------------------------------------------------------------------------------------------------------------

附圖證明結果是對的，和書上的結果略有一點差異，應該是可以忽略的。

----------------------------------------------------------------------------------------------------------------------------------------

我又查了一下likelihood好像不是概率的意思，懶得再改了。。