◆楊振 楊帆 夏山 高釧淏 萬(wàn)賀

一種基于卡西斯基試驗(yàn)的密鑰破譯算法分析

◆楊振 楊帆 夏山 高釧淏 萬(wàn)賀

（成都信息工程大學(xué)網(wǎng)絡(luò)空間安全學(xué)院 四川 610200）

卡西斯基試驗(yàn)（Kasiski examination）是弗里德里?！たㄎ魉够?863年提出的針對(duì)維吉尼亞密碼的破譯方法，它通過(guò)在密文中搜索長(zhǎng)度大于3的相同密文序列并計(jì)算幾者之間相隔的字母?jìng)€(gè)數(shù)來(lái)推測(cè)密鑰的長(zhǎng)度。且維吉尼亞算法對(duì)密鑰的簡(jiǎn)單填充處理使得它易于破解，對(duì)后世提出“完善保密性”也產(chǎn)生了一定影響。本文的算法基于卡西斯基試驗(yàn)，通過(guò)循環(huán)移位法確定密鑰長(zhǎng)度。隨機(jī)模擬實(shí)驗(yàn)表明，它可以簡(jiǎn)單、高效、準(zhǔn)確地提取對(duì)密鑰進(jìn)行了錯(cuò)誤填充的流密碼的密鑰長(zhǎng)度。

維吉尼亞密碼；異或；密鑰長(zhǎng)度

維吉尼亞密碼算法曾多次被發(fā)明，以其簡(jiǎn)單易用而著稱。弗里德里?！たㄎ魉够?863年提出，在未知維吉尼亞密碼密鑰長(zhǎng)度的情況下可以用卡西斯基試驗(yàn)法猜測(cè)密鑰長(zhǎng)度。一旦確定了密鑰長(zhǎng)度，密文就可以用矩陣形式排列，對(duì)于每一列便可以使用頻率分析攻擊推測(cè)出對(duì)應(yīng)的明文和密鑰，由此來(lái)實(shí)現(xiàn)對(duì)維吉尼亞密碼的破解[1-2]。本文主要分析一種基于卡西斯基試驗(yàn)的更為簡(jiǎn)單高效的算法，通過(guò)對(duì)維吉尼亞加密和異或流密碼加密的測(cè)試發(fā)現(xiàn)，該算法對(duì)于確定多表替換密碼密鑰長(zhǎng)度的效果良好。

1 簡(jiǎn)介

1.1 維吉尼亞加密算法

維吉尼亞算法的明文空間、密鑰空間、密文空間均為26個(gè)英文字母。

算法首先將明文和密鑰中的字母依據(jù)其在字母表中的順序?qū)⒆帜负蛿?shù)字做一個(gè)映射，比如a對(duì)應(yīng)0、b對(duì)應(yīng)1......

然后將密鑰重復(fù)復(fù)制，填充到和明文一樣的位數(shù)，再對(duì)明文進(jìn)行逐位加密。加密和解密的算法可以用以下的同余式表示[3]：

加密：

解密：

1.2 流密碼

流密碼是一種對(duì)稱加密算法。它要求加密者和解密者使用同樣的數(shù)據(jù)流作為密鑰，明文數(shù)據(jù)流和密鑰數(shù)據(jù)流順次對(duì)應(yīng)加密，得到密文數(shù)據(jù)流。

OTP（one-time pad，一次性密碼本）密碼是一種流加密算法，加密和解密算法可以描述為：

加密：

解密：

其中密鑰和明文的長(zhǎng)度相同，是真正隨機(jī)產(chǎn)生的且只使用一次。

雖然OTP密碼的加解密處理只是做了一個(gè)簡(jiǎn)單的異或運(yùn)算，但在理論上，克勞德·艾爾伍德·香農(nóng)已經(jīng)證明該算法是絕對(duì)安全的[4]。3.1節(jié)將進(jìn)一步討論OTP密碼。

1.3 卡希斯基試驗(yàn)

舉一個(gè)簡(jiǎn)單的維吉尼亞加密的例子，明文為say to me that you love me forever tomorrow morning，密鑰為sky，則：

明文：saytomethatyoulovemeforevertomorrowmorning

密鑰：skyskyskyskyskyskyskyskyskyskyskyskyskysky

密文：kkwlykwdfsdwgejgfceodgbcnoplykgbpggkgblaxe

可以看到密文中有用粗體標(biāo)記的重復(fù)kgb序列，這是因?yàn)樵诿魑闹杏衜or的重復(fù)序列，并且他們間隔的字母?jìng)€(gè)數(shù)恰好是密鑰長(zhǎng)度的倍數(shù)，即6。因此我們可以在密文中尋找一定長(zhǎng)度的重復(fù)序列，并且計(jì)算他們之間間隔的字母?jìng)€(gè)數(shù)，經(jīng)過(guò)多次計(jì)算后取這些字母?jìng)€(gè)數(shù)的最大公因數(shù)，就能基本推測(cè)出密鑰長(zhǎng)度了。

比如，我們還能在密文中發(fā)現(xiàn)重復(fù)的lyk序列，這兩個(gè)重復(fù)序列的間隔數(shù)是24，kgb重復(fù)序列的間隔數(shù)是6，則可以假設(shè)密鑰長(zhǎng)度為gcd（24，6）=6，雖然結(jié)果是實(shí)際密鑰長(zhǎng)度的2倍，但其對(duì)后續(xù)密文的破解操作影響不大。

值得注意的是，密文中其實(shí)還有一個(gè)重復(fù)的kw序列，但他們間隔的位數(shù)是4，如果以kw序列和kgb序列作為數(shù)據(jù)計(jì)算的話，則會(huì)得到密鑰長(zhǎng)度為gcd（4，24）=4的錯(cuò)誤結(jié)論，所以這種方法有一定概率會(huì)產(chǎn)生差錯(cuò)。

本文主要討論的簡(jiǎn)易算法對(duì)本小結(jié)的例子的處理將在2.1中進(jìn)一步討論。

2 簡(jiǎn)易算法

2.1 算法描述

卡西斯基試驗(yàn)法效率較高，但并不易行，本文中主要討論以下算法：

以1.3中的例子來(lái)說(shuō)，如果將的前三位去掉后則得到：

明文：tomethatyoulovemeforevertomorrowmorning

密鑰：skyskyskyskyskyskyskyskyskyskyskyskysky

密文：lykwdfsdwgejgfceodgbcnoplykgbpggkgblaxe

明文：saytomethatyoulovemeforevertomorrowmorn

密鑰：skyskyskyskyskyskyskyskyskyskyskyskysky

密文：kkwlykwdfsdwgejgfceodgbcnoplykgbpggkgbl

而如果將的前兩位去掉則可以得到：

明文：ytomethatyoulovemeforevertomorrowmorning

密鑰：yskyskyskyskyskyskyskyskyskyskyskyskysky

密文：wlykwdfsdwgejgfceodgbcnoplykgbpggkgblaxe

明文：saytomethatyoulovemeforevertomorrowmorni

密鑰：skyskyskyskyskyskyskyskyskyskyskyskyskys

密文：kkwlykwdfsdwgejgfceodgbcnoplykgbpggkgbla

2.2 算法分析

2.3 概率計(jì)算

假設(shè)對(duì)于明文序列中的每一位，26個(gè)字母均等概率出現(xiàn)，即每個(gè)字母出現(xiàn)的概率為1/26，則：

這一結(jié)果也將再下面的2.5中被實(shí)驗(yàn)證實(shí)。本節(jié)的假設(shè)將在3.2節(jié)中被引用。

2.4 字母頻率

然而，在一篇有語(yǔ)義的英文文章中，26個(gè)字母并不是等概率出現(xiàn)在每一個(gè)明文位上的。

在英語(yǔ)中，各字母出現(xiàn)的概率如表1所示[5]。

表1 英文字母頻率

其中，出現(xiàn)頻率最高的字母是e，其次是t。

通過(guò)計(jì)算，可以得到

2.5 實(shí)驗(yàn)驗(yàn)證

圖1為其中一次計(jì)算的結(jié)果：

從條形圖中也可以反映出來(lái)，我們無(wú)法有效的確定密鑰長(zhǎng)度。

對(duì)于等式（11），作者選擇了一篇較長(zhǎng)的英文文章，并剔除了標(biāo)點(diǎn)符號(hào)，提取出了里面的2600個(gè)字母進(jìn)行測(cè)試，同樣選擇隨機(jī)的7位密鑰，重復(fù)計(jì)算了100次數(shù)，結(jié)果為：

他們兩者的比值為1.746

其中一次的結(jié)果如圖2：

圖2 明文有語(yǔ)義的維吉尼亞實(shí)驗(yàn)結(jié)果

3 對(duì)流密碼的破解

相較于維吉尼亞密碼來(lái)說(shuō)，該算法對(duì)于錯(cuò)誤使用了OTP密碼加密的破解效果更好。

3.1 錯(cuò)誤的OTP加密

由于異或運(yùn)算的對(duì)稱性，流密碼在加密和解密的時(shí)候使用同一個(gè)密鑰。和維吉尼亞不同的是，流密碼異或?qū)τ谧帜傅綌?shù)字的映射是使用的字符的ASCII，由于密鑰流通常達(dá)不到明文的長(zhǎng)度，所以往往是由一個(gè)較短的密鑰通過(guò)一些偽隨機(jī)生成算法來(lái)生成足夠長(zhǎng)的密鑰序列，比如著名的RC4算法[7][8]。而如果拓展密鑰的時(shí)候是像維吉尼亞密鑰那樣拓展的話，就會(huì)使得該密碼算法很容易被破解。

“錯(cuò)誤”即對(duì)密鑰進(jìn)行了錯(cuò)誤的填充。對(duì)OTP密碼的描述已在1.2節(jié)中闡述，倘若加密方拓展密鑰長(zhǎng)度時(shí)，只是將一個(gè)較短的密鑰進(jìn)行簡(jiǎn)單的復(fù)制填充以達(dá)到和明文長(zhǎng)度一樣的目的，那么便可以用本算法很輕易的得到密鑰長(zhǎng)度。即如果明文為say to me that you love me forever tomorrow morning，密鑰為sky，則加密結(jié)果為：

明文：

say to me that you love me forever tomorrow morning

密鑰：

skyskyskyskyskyskyskyskyskyskyskyskyskyskyskyskysky

密文：

0x000a00531f1653061c531f11121f590a040c530716050e591e0e5915040b161d1c014b0d1c0616011916044b141c19171a051e

可以發(fā)現(xiàn)，密文中會(huì)出現(xiàn)很多不可見(jiàn)的ASCII字符。

3.2 計(jì)算

異或流密碼和維吉尼亞密碼其中一處不同即在于異或流密碼的明文空間和密鑰空間應(yīng)該是ascii可打印字符，而密文空間則可以是所有的ascii字符。

在查閱文獻(xiàn)后作者僅找到了英文字母和空格在英文中的出現(xiàn)頻率[6]如表2：

表2 英文中字母和空格的頻率

則基于此數(shù)據(jù)展開(kāi)討論，引用2.2和2.3節(jié)的假設(shè)，再增設(shè)set為26個(gè)字母和空格的集合。

則若在明文和密鑰中27個(gè)字符等概率出現(xiàn)：

那么假設(shè)在明文中27個(gè)字母出現(xiàn)的概率為上圖中的概率，進(jìn)一步討論有：

通過(guò)計(jì)算，可以得到：

可以發(fā)現(xiàn)，等式（18）的比值是明顯要比等式（11）的大的。

3.3 實(shí)例分析

對(duì)于等式（18），作者同樣選擇了一篇較長(zhǎng)的英文文章，并剔除了標(biāo)點(diǎn)符號(hào)，僅留下26個(gè)字母和空格作為明文進(jìn)行測(cè)試，同樣生成隨機(jī)的7位密鑰，重復(fù)計(jì)算了100次數(shù)，得到：

它們兩者的比值為4.067

其中一次的結(jié)果如圖3：

圖3 明文有語(yǔ)義的異或加密實(shí)驗(yàn)結(jié)果

從圖3中可以十分明顯的看出密鑰長(zhǎng)度為7。

4 總結(jié)

盡管維吉尼亞密碼在現(xiàn)代密碼體系中已經(jīng)用的不是很多了，但本算法對(duì)于重復(fù)使用了密鑰的流密碼來(lái)說(shuō)，效果十分明顯，可以從3.3中繪制的Ni條形圖快速準(zhǔn)確的得到密鑰的長(zhǎng)度。也從側(cè)面反映出了香農(nóng)提出的“完善保密性”的正確性，即密鑰空間等于或者大于明文空間時(shí)，即使攻擊者擁有無(wú)窮的計(jì)算時(shí)間和存儲(chǔ)空間，密文仍不可能被破解。

[1]Klaus Pommerening. Kasiski's Test：Couldn't the Repetitions be by Accident?[J]. Cryptologia，2006，30（4）.

[2]Seongmin Park，Juneyeun Kim，Kookrae Cho，Dae Hyun Yum. Finding the key length of a Vigenère cipher：How to improve the twist algorithm[J]. Cryptologia，2020，44（3）.

[3]葛藍(lán).淺談維吉尼亞加密算法的原理與實(shí)現(xiàn)[J].電腦與電信，2017（04）：64-65+86.

[4]Shannon C E. A Mathematical Theory of Communication[J]. The Bell System Technical Journal，1948，27.

[5]James Wiegold. CIPHER SYSTEMS：The Protection of Communications[J]. Bulletin of the London Mathematical Society，1983，15.

[6]Statistical Distributions of English Text [EB/OL].[2000-08-19].https://web.archive.org/web/20170918020907/http://www.data-compression.com/english.html.

[7]劉聰. 基于密鑰流的RC4算法安全性分析與改進(jìn)[D].湖南大學(xué)，2016.

[8]苑超，徐蜜雪，斯雪明.對(duì)不同種子密鑰長(zhǎng)度的RC4算法的明文恢復(fù)攻擊[J].計(jì)算機(jī)應(yīng)用，2018，38（02）：370-373.