Playfair加密算法改进

张景龙,黄静,王爱松,张春生,赵琳娜,宝力高

（内蒙古民族大学,内蒙古通辽028000）

Playfair加密算法改进

张景龙,黄静,王爱松,张春生,赵琳娜,宝力高

（内蒙古民族大学,内蒙古通辽028000）

Playfair密码是对称加密中多表加密的一种,针对其原始算法存在的3个缺点提出了相应的改进方案,并对改进方案的可行性进行了论证,最后给出了改进后的算法.对比表明：改进后的加密算法比原算法更具安全性.

Playfair；加密；算法

Playfair密码是多表代换加密方式中最著名的一种,属于经典对称加密方式,1854年由英国科学家ChaelesW发明.在第一次世界大战中,英军就使用它作为陆军的战时加密体制,在第二次世界大战中,美军及其他盟国军队都曾大量使用.曾经在相当长的一段时期内,Playfair密码被认为是一种牢不可破的加密方法[1-4].在网络安全、数据加密等方面,其加密思想被广泛应用.Playfair密码是把明文中的双字母音节作为一个单元并将其转换为密文的一种加密算法,原算法可用的字母对有26×26个,虽然比明文有着稍为平坦的频率分布曲线,但密文中仍透露了大量的信息给密码分析者[1].本文对Playfair加密进行了3个方面的改进,使得可用的密码对多达25!×26!个,使得密文的字母有着更为平坦的频率分布曲线,增加了破解的难度.

1 Playfair加密算法

Playfair加密算法是把明文中的双字母作为一个单元,将其转换为密文的双字母,转换依据由密钥所构成的5×5字母矩阵[4-5].

1.1 转换矩阵的构成

先将密钥去掉重复字母（字母i和j视为同一个字母）,然后从左向右、从上至下填写在矩阵格子中,假如密钥为successful,去除重复字母后为的有效密钥为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 传统Playfair加密算法流程Fig.3 The flow chartoforiginalPlayfairencryption algorithm

依据传统Playfair加密算法,如果明文为“thank you verymuch”,密钥为successful,则对应的密文为“ongimxpsysyeiesk”.

1.3 Playfair算法的缺点

尽管Playfair密码被认为是比较安全的,但它仍是可以被破解的,因为它的密文中完好地保留了明文语言的大部分结构特征,有几百个字母的密文就可以分析出某些规律,从而为进一步破解提供线索[5-8].使用Playfair算法加密,之所以密文中保留了明文语言中的结构特征,基于多方面的原因,其中有3方面主要因素导致密文完好地保留了明文语言的大部分结构特征：

（1）明文的读取是按序读取,所以生成的密文与明文基本上是保持一一对应关系,这种一一对应关系直接暴露了明文的结构特征.

（2）由密钥构造5×5字母矩阵时,密钥写在前面,剩下的字母按序填写在后面,这样后面的字母基本保留了英文字母的顺序,使得破解者可以借助密文中的字母出现的频率来构造字母矩阵.一旦字母矩阵被构造出一部分,那么再结合字母对出现频率的统计,进一步从密文中挖掘出其他特征,密钥就很有可能被猜到[9].

（3）i和j字符认为是相同的字母,由于i在英文中出现的概率原本就很高,两字母被视为同一个字母后,通过密文中的字母,能够分析出哪些字母与i/j同行或同列,从而为构造5×5字母矩阵提供了线索.

2 Playfair加密算法改进

2.1 改进思路

基于上文指出的Playfair加密算法的缺点,提出以下3种改进措施：

（1）在读取明文的字符对时,不按明文的顺序读取,采用某种方案间隔着读取明文.如：从首尾依次读取字符,构成字符对,或按某种算法间隔读取明文字符构成字符对.这样相当于加密前读出的明文就打乱了明文字母的顺序,原理上相当于进行了一次换位加密,再对置换后的明文用某种函数作用,使得密文与原始明文不再有直接的位置对应关系,从而可以隐藏明文中的结构特征和语法特征.在此基础上再进一步使用替换加密,增加破解的难度.打乱明文读取顺序的方法是可行的,只要在读取明文时不出现对字符的重复读取和遗漏,就可以保证密文与明文在加密和解密过程中是可逆的.扩散密码系统的基本构件之一就是,改变明文字符的读取顺序后,再通过矩阵变换产生的密文,比不改变明文顺序直接变换产生的密文更加扩散.

（2）由密钥构造5×5字母矩阵时,密钥写在矩阵前面,剩下的字母打乱顺序,使得构造出的字母矩阵尽可能的“混乱”,尽量少地保留原来字母的顺序.这种改进虽然看似简单,但与改进前相比,却最能有效地打乱密文中字符之间的顺序关系,从而增加破解者构造字母矩阵的难度.

（3）按某种方案,动态地而不是固定地将某两个字母作为相同字母,并尽可能地在明文中选择出现概率较少的两个字母作为相同字母,从而降低某些字母出现的概率,使得密文中出现的字母或字母对越平均越好.这种方法增加了算法的复杂度,使得密文中的字母和字母对出现的概率更加平均,密文尽可能少地提供与明文相关的结构规则和语法规则.由于相同字母的约定是动态的,即生成的5×5字母矩阵也是不同的,这样,生成的密文更加符合密码系统的另一个构件——混淆,从而使得通过统计字母或字母对出现频率来破解的方法失效.

2.2 改进后的算法

改进后的加密流程如图4所示.

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

图4中“运用传统Playfair算法加密”的过程相当于整个图3的整个流程.构造加密矩阵时,由于剩余字母排列组合方案数（26-K）!的所有方案数过大,可以根据需要适当选择一部分.

2.3 改进前后安全性的对比

采用改进后的Playfair加密与原始的Playfair加密,对同一原文进行加密然后进行对比.为对比方便,现对改进后的算法具体规定如下：

（1）以句为单位,每句选择不同的两个字母视为相同字母,第1句选择除密钥之外的第1个字母和第2个字母为相同的字母,第2句选择除密钥之个的第1个字母和第3个字母,依此类推,当把除密钥之外的第1个字母和最后一个字母视为相同字母之后,下一句则选择除密钥之外的第2个字母和第3个字母视为相同字母,再下一句则选择除密钥之外的第2个字母和第4个字母视为相同字母,依此类推.

（2）打乱除密钥部分之外的剩余字母的顺序方法为：除密钥外,其余字母形成一个封闭的“字母环”,如密钥为successful,则剩余字母“abdghijkmnopqrtvwxyz”,填充第1句话的字母矩阵时顺序为“abdghijkmnopqrtvwxyz”,填充第2句话的字母矩阵时顺序为“bdghijkmnopqrtvwxyza”,依此类推.

（3）读取明文时,选择从明文的中间和最后位置开始倒序读起,构成相应的字母对.需加密的明文为

Thank you verymuch,thanksverymuch.

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

ongimxpsysyeieskongihcysyeiesk

利用改进后的Playfair加密方法得到密文为

faqswemnmzgpgfoztiueqbonwzgtzh

加密结果的安全性对比见表1.

表1 原始Playfair加密与改进后的Playfair加密结果对比Tab.1 The resultsoforiginalPlayfairencryption and improved Playfairencryption

由表1可知,用原始的加密算法产生的密文原样地保留了明文的结构特征,并且两句中的绝大部分密文相同.而改进后的加密算法生成的密文不保留明文的结构特征,且两句密文中不存在相同的字母对.明文只是做了微小的改动,密文就产生很大的变化,所以改进后的加密算法具有很好的扩散性、混淆性和雪崩效应.更重要的是改进前的Playfair算法的密码字母对只有25×25个,获取几百个密文字母对就可能破解密文.改进后的Playfair加密算法理论上具有25!×26!个字母对,远远超过原始加密算法的数量,这样企图通过密码对破解密文的想法没有实际意义.改进后的加密方案中,每句话的加密矩阵都不同,所以产生的密文中相同字母对并不对应相同原文,使得通过字母出现的频率来解密的方法无效.改进后的加密方法比原始的加密更具安全性,极大程度地增加破解的难度[6-7].

3 小结

本文对传统的Playfair加密算法进行了研究,并进行了3方面的改进.利用改进后的加密算法得到的密文,其字母分布曲线更加平坦,具有扩散性、混淆性以及雪崩效应,极大地增加了破解难度.

[1]William S.密码编码学与网络安全：原理与实践[M].北京：电子工业出版社,2008.

[2]范九伦.密码学基础[M].西安：西安电子科技大学出版社,2008.

[3]李晖,李丽香,邵帅.对称密码学及其应用[M].北京：北京邮电大学出版社,2009.

[4]卢开澄.计算机密码学[M].北京：清华大学出版社,2003.

[5]康晓凤.Playfair加密算法的研究与设计[J].福建电脑,2006（5）：116-131.

[6]张猛,杨可新,鞠九滨.改进加密算法实现的性能[J].软件学报,2001,12（6）：878-883.

[7]康晓凤.Playfair算法及其C语言模拟实现[J].徐州工程学院学报,2006,21（12）：28-30.

[8]马玉磊,杜川.数据加密技术的分析[J].大众科技,2010（4）：21,37.

[9]冯登国.密码分析学[M].北京：清华大学出版社,2000.

（责任编辑：卢奇）

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

内蒙古民族大学科学研究基金资助项目（NMD1230）

张景龙（1976-）,男,汉族,内蒙古赤峰市人,实验师.主要从事计算机实验教学及网络安全研究.