Playfair加密算法改進

張景龍,黃靜,王愛松,張春生,趙琳娜,寶力高

（內(nèi)蒙古民族大學(xué),內(nèi)蒙古通遼028000）

Playfair加密算法改進

張景龍,黃靜,王愛松,張春生,趙琳娜,寶力高

（內(nèi)蒙古民族大學(xué),內(nèi)蒙古通遼028000）

Playfair密碼是對稱加密中多表加密的一種,針對其原始算法存在的3個缺點提出了相應(yīng)的改進方案,并對改進方案的可行性進行了論證,最后給出了改進后的算法.對比表明：改進后的加密算法比原算法更具安全性.

Playfair；加密；算法

Playfair密碼是多表代換加密方式中最著名的一種,屬于經(jīng)典對稱加密方式,1854年由英國科學(xué)家ChaelesW發(fā)明.在第一次世界大戰(zhàn)中,英軍就使用它作為陸軍的戰(zhàn)時加密體制,在第二次世界大戰(zhàn)中,美軍及其他盟國軍隊都曾大量使用.曾經(jīng)在相當(dāng)長的一段時期內(nèi),Playfair密碼被認(rèn)為是一種牢不可破的加密方法[1-4].在網(wǎng)絡(luò)安全、數(shù)據(jù)加密等方面,其加密思想被廣泛應(yīng)用.Playfair密碼是把明文中的雙字母音節(jié)作為一個單元并將其轉(zhuǎn)換為密文的一種加密算法,原算法可用的字母對有26×26個,雖然比明文有著稍為平坦的頻率分布曲線,但密文中仍透露了大量的信息給密碼分析者[1].本文對Playfair加密進行了3個方面的改進,使得可用的密碼對多達25!×26!個,使得密文的字母有著更為平坦的頻率分布曲線,增加了破解的難度.

1 Playfair加密算法

Playfair加密算法是把明文中的雙字母作為一個單元,將其轉(zhuǎn)換為密文的雙字母,轉(zhuǎn)換依據(jù)由密鑰所構(gòu)成的5×5字母矩陣[4-5].

1.1 轉(zhuǎn)換矩陣的構(gòu)成

先將密鑰去掉重復(fù)字母（字母i和j視為同一個字母）,然后從左向右、從上至下填寫在矩陣格子中,假如密鑰為successful,去除重復(fù)字母后為的有效密鑰為sucefl,如圖1所示.將剩下的英文字母（i和j視為同一個字母）按從左到右、從上而下的順序填寫在剩余空白的格子中,如圖2所示.

圖1 填入密鑰后的5×5矩陣Fig.1 5×5matrix after filling key

圖2 完整的5×5字母矩陣Fig.2 Complete5×5matrix

1.2 加密算法

加密時,每次從明文中提出2個字母,具體的加密算法如圖3所示.

圖3 傳統(tǒng)Playfair加密算法流程Fig.3 The flow chartoforiginalPlayfairencryption algorithm

依據(jù)傳統(tǒng)Playfair加密算法,如果明文為“thank you verymuch”,密鑰為successful,則對應(yīng)的密文為“ongimxpsysyeiesk”.

1.3 Playfair算法的缺點

盡管Playfair密碼被認(rèn)為是比較安全的,但它仍是可以被破解的,因為它的密文中完好地保留了明文語言的大部分結(jié)構(gòu)特征,有幾百個字母的密文就可以分析出某些規(guī)律,從而為進一步破解提供線索[5-8].使用Playfair算法加密,之所以密文中保留了明文語言中的結(jié)構(gòu)特征,基于多方面的原因,其中有3方面主要因素導(dǎo)致密文完好地保留了明文語言的大部分結(jié)構(gòu)特征：

（1）明文的讀取是按序讀取,所以生成的密文與明文基本上是保持一一對應(yīng)關(guān)系,這種一一對應(yīng)關(guān)系直接暴露了明文的結(jié)構(gòu)特征.

（2）由密鑰構(gòu)造5×5字母矩陣時,密鑰寫在前面,剩下的字母按序填寫在后面,這樣后面的字母基本保留了英文字母的順序,使得破解者可以借助密文中的字母出現(xiàn)的頻率來構(gòu)造字母矩陣.一旦字母矩陣被構(gòu)造出一部分,那么再結(jié)合字母對出現(xiàn)頻率的統(tǒng)計,進一步從密文中挖掘出其他特征,密鑰就很有可能被猜到[9].

（3）i和j字符認(rèn)為是相同的字母,由于i在英文中出現(xiàn)的概率原本就很高,兩字母被視為同一個字母后,通過密文中的字母,能夠分析出哪些字母與i/j同行或同列,從而為構(gòu)造5×5字母矩陣提供了線索.

2 Playfair加密算法改進

2.1 改進思路

基于上文指出的Playfair加密算法的缺點,提出以下3種改進措施：

（1）在讀取明文的字符對時,不按明文的順序讀取,采用某種方案間隔著讀取明文.如：從首尾依次讀取字符,構(gòu)成字符對,或按某種算法間隔讀取明文字符構(gòu)成字符對.這樣相當(dāng)于加密前讀出的明文就打亂了明文字母的順序,原理上相當(dāng)于進行了一次換位加密,再對置換后的明文用某種函數(shù)作用,使得密文與原始明文不再有直接的位置對應(yīng)關(guān)系,從而可以隱藏明文中的結(jié)構(gòu)特征和語法特征.在此基礎(chǔ)上再進一步使用替換加密,增加破解的難度.打亂明文讀取順序的方法是可行的,只要在讀取明文時不出現(xiàn)對字符的重復(fù)讀取和遺漏,就可以保證密文與明文在加密和解密過程中是可逆的.擴散密碼系統(tǒng)的基本構(gòu)件之一就是,改變明文字符的讀取順序后,再通過矩陣變換產(chǎn)生的密文,比不改變明文順序直接變換產(chǎn)生的密文更加擴散.

（2）由密鑰構(gòu)造5×5字母矩陣時,密鑰寫在矩陣前面,剩下的字母打亂順序,使得構(gòu)造出的字母矩陣盡可能的“混亂”,盡量少地保留原來字母的順序.這種改進雖然看似簡單,但與改進前相比,卻最能有效地打亂密文中字符之間的順序關(guān)系,從而增加破解者構(gòu)造字母矩陣的難度.

（3）按某種方案,動態(tài)地而不是固定地將某兩個字母作為相同字母,并盡可能地在明文中選擇出現(xiàn)概率較少的兩個字母作為相同字母,從而降低某些字母出現(xiàn)的概率,使得密文中出現(xiàn)的字母或字母對越平均越好.這種方法增加了算法的復(fù)雜度,使得密文中的字母和字母對出現(xiàn)的概率更加平均,密文盡可能少地提供與明文相關(guān)的結(jié)構(gòu)規(guī)則和語法規(guī)則.由于相同字母的約定是動態(tài)的,即生成的5×5字母矩陣也是不同的,這樣,生成的密文更加符合密碼系統(tǒng)的另一個構(gòu)件——混淆,從而使得通過統(tǒng)計字母或字母對出現(xiàn)頻率來破解的方法失效.

2.2 改進后的算法

改進后的加密流程如圖4所示.

圖4 改進后的Playfair加密流程Fig.4 The flow chartof improved Playfairencryption algorithm

圖4中“運用傳統(tǒng)Playfair算法加密”的過程相當(dāng)于整個圖3的整個流程.構(gòu)造加密矩陣時,由于剩余字母排列組合方案數(shù)（26-K）!的所有方案數(shù)過大,可以根據(jù)需要適當(dāng)選擇一部分.

2.3 改進前后安全性的對比

采用改進后的Playfair加密與原始的Playfair加密,對同一原文進行加密然后進行對比.為對比方便,現(xiàn)對改進后的算法具體規(guī)定如下：

（1）以句為單位,每句選擇不同的兩個字母視為相同字母,第1句選擇除密鑰之外的第1個字母和第2個字母為相同的字母,第2句選擇除密鑰之個的第1個字母和第3個字母,依此類推,當(dāng)把除密鑰之外的第1個字母和最后一個字母視為相同字母之后,下一句則選擇除密鑰之外的第2個字母和第3個字母視為相同字母,再下一句則選擇除密鑰之外的第2個字母和第4個字母視為相同字母,依此類推.

（2）打亂除密鑰部分之外的剩余字母的順序方法為：除密鑰外,其余字母形成一個封閉的“字母環(huán)”,如密鑰為successful,則剩余字母“abdghijkmnopqrtvwxyz”,填充第1句話的字母矩陣時順序為“abdghijkmnopqrtvwxyz”,填充第2句話的字母矩陣時順序為“bdghijkmnopqrtvwxyza”,依此類推.

（3）讀取明文時,選擇從明文的中間和最后位置開始倒序讀起,構(gòu)成相應(yīng)的字母對.需加密的明文為

Thank you verymuch,thanksverymuch.

利用原始Playfair加密方法得到的密文為

ongimxpsysyeieskongihcysyeiesk

利用改進后的Playfair加密方法得到密文為

faqswemnmzgpgfoztiueqbonwzgtzh

加密結(jié)果的安全性對比見表1.

表1 原始Playfair加密與改進后的Playfair加密結(jié)果對比Tab.1 The resultsoforiginalPlayfairencryption and improved Playfairencryption

由表1可知,用原始的加密算法產(chǎn)生的密文原樣地保留了明文的結(jié)構(gòu)特征,并且兩句中的絕大部分密文相同.而改進后的加密算法生成的密文不保留明文的結(jié)構(gòu)特征,且兩句密文中不存在相同的字母對.明文只是做了微小的改動,密文就產(chǎn)生很大的變化,所以改進后的加密算法具有很好的擴散性、混淆性和雪崩效應(yīng).更重要的是改進前的Playfair算法的密碼字母對只有25×25個,獲取幾百個密文字母對就可能破解密文.改進后的Playfair加密算法理論上具有25!×26!個字母對,遠遠超過原始加密算法的數(shù)量,這樣企圖通過密碼對破解密文的想法沒有實際意義.改進后的加密方案中,每句話的加密矩陣都不同,所以產(chǎn)生的密文中相同字母對并不對應(yīng)相同原文,使得通過字母出現(xiàn)的頻率來解密的方法無效.改進后的加密方法比原始的加密更具安全性,極大程度地增加破解的難度[6-7].

3 小結(jié)

本文對傳統(tǒng)的Playfair加密算法進行了研究,并進行了3方面的改進.利用改進后的加密算法得到的密文,其字母分布曲線更加平坦,具有擴散性、混淆性以及雪崩效應(yīng),極大地增加了破解難度.

[1]William S.密碼編碼學(xué)與網(wǎng)絡(luò)安全：原理與實踐[M].北京：電子工業(yè)出版社,2008.

[2]范九倫.密碼學(xué)基礎(chǔ)[M].西安：西安電子科技大學(xué)出版社,2008.

[3]李暉,李麗香,邵帥.對稱密碼學(xué)及其應(yīng)用[M].北京：北京郵電大學(xué)出版社,2009.

[4]盧開澄.計算機密碼學(xué)[M].北京：清華大學(xué)出版社,2003.

[5]康曉鳳.Playfair加密算法的研究與設(shè)計[J].福建電腦,2006（5）：116-131.

[6]張猛,楊可新,鞠九濱.改進加密算法實現(xiàn)的性能[J].軟件學(xué)報,2001,12（6）：878-883.

[7]康曉鳳.Playfair算法及其C語言模擬實現(xiàn)[J].徐州工程學(xué)院學(xué)報,2006,21（12）：28-30.

[8]馬玉磊,杜川.數(shù)據(jù)加密技術(shù)的分析[J].大眾科技,2010（4）：21,37.

[9]馮登國.密碼分析學(xué)[M].北京：清華大學(xué)出版社,2000.

（責(zé)任編輯：盧奇）

Im proved Playfair cipher

Zhang Jinglong,Huang Jing,Wang Aisong,Zhang Chunsheng,Zhao Linna,Bao ligao
（InnerMongolia University forNationalities,Tongliao028000,China）

Playfair cipher is a symmetric encryption.According to the original algorithm,three improvement scheme and the improved scheme feasibility are given.The improved algorithm is supplied.By contrast,the improved algorithm hasmore security than the original algorithm.

Playfair cipher；encryption；algorithm

TN918

A

1008-7516（2013）04-0038-05

10.3969/j.issn.1008-7516.2013.04.010

2013-05-20

內(nèi)蒙古民族大學(xué)科學(xué)研究基金資助項目（NMD1230）

張景龍（1976-）,男,漢族,內(nèi)蒙古赤峰市人,實驗師.主要從事計算機實驗教學(xué)及網(wǎng)絡(luò)安全研究.