混沌分组密码抗差分密码攻击的分析

郑晓丽， 姜迪刚

（①军事体育进修学院，广东 广州 510500；②中山大学基础医学院，广东 广州 510080）

0 引言

随着互联网和计算机技术的迅猛发展，计算机和通信网络已经融入军事作战、军事侦查中，而保证军事通信信息的安全就成为亟待解决的问题。随着密码技术不断发展，密码学中的混沌理论与密码学的融合也日趋成熟，混沌密码学也成为密码学的一个重要分支[1-2]。目前主要采用的方法是，利用混沌映射构造出S盒[3-4]，再与分组密码进行结合。但是，对于混沌密码的安全性分析却非常少，有的也仅仅是对S盒的抗差分、线性分析，并没有对整个密码结构进行完整的安全性分析[5]。本文针对基于Feistel结构的动态混沌密码，对其密码算法进行了系统的安全性分析[6]。

1 基于Feistel结构的混沌分组密码

Feistel结构是 20世纪60年代末IBM 公司的Feistel和 Tuchman在设计Lucifer分组密码时提出的，后因 DES算法的广泛使用而流行[7-8]。它最大的特点是加解密相似，就是在设计轮函数时不管多么复杂也不用考虑解密时的结构，它已被证明具有很好的安全性[9]。基于 Feistel结构的混沌分组密码算法流程如图1示。

将128 bit的明文进行加密，加密过程中将f函数对应的 Logistic映射取两个不同的初值生成两个不同的S盒f1和f2，加密中奇数轮使用f1，偶数轮使用f2，经过整个扩展加解密结构后得到128 bit伪明文，将其输入初始逆变换中求逆，得到明文，这样便完成了整个加解密流程。

图1 算法流程

扩展Feistel结构的分组加密算法包括8轮，第i轮中(1≤i≤8)，Bi-1是输入，Bi是输出，B0是明文，B8是经过加密的密文，明文的长度是128 bit，加密产生的密文也是128 bit，每个分组Bi,j是8 bit。整个加解密过程首先对128 bit明文进行初始变换，让明文通过一个类似P盒的结构，对明文的比特位进行置乱，但是不改变明文中的0和1 bit数，然后对产生的序列进行分组，将其按照8 bit为一组分成16组输入扩展加解密结构，其中，f函数采用Logistic映射生成的S盒，混沌迭代的初值采用输入密钥。

每一轮的加密函数是：

对应的解密函数是：

加密轮结构中的f为使用Logistic映射构造的S盒，奇数轮用S1，偶数轮用S2。本算法使用动态S盒构造如下：

首先，初始S盒的生成，使用Logistic映射，K为二进制128位长的初始密钥；

其次，使用Baker映射对生成的S盒进行置乱，经过离散化后的Baker映射表示为个整数的和是N，N=256，即令，其中，整个的Baker映射置乱表达式是：

密钥选取Cubic映射来生成密钥，Cubic映射的迭代方程式为：

其中通常选取A=4，B=3，0

2 固定S盒情况下的不可能差分分析

假设上述算法的S盒是固定状态（即S1、S2为已知S盒）

2.1 S盒的第7轮是不可能差分

图2所示为算法的7轮不可能差分。

图2 七轮不可能差分

图2可看出第7轮差分：(a7,a6,a5,a4,a3,a2,a1,a0,0,0,0,0,0,0,0,0)→(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,h)不可能发生，其中( i = 0 ,1,2,3,4,5,6,7)和g表示任意字节。输入差分0,0,0,0,0)，0,14B∆与子密钥1,15K异或，经过S盒变换后，再与0,15B∆异或得到1,14B∆为一未知的非0字节7b。0,13B∆与子密钥1,14K异或，经过S盒变换后，再与0,14B∆异或得到1,13B∆为一未知的非0字节6b。以此类推，可以得出1,12B∆,1,11B∆,…,1,8B∆,1,7B∆的值分别为5b,4b,…,1b,0a。其余字节差分为 0，于是在第 1轮变换后的输出差分变为同理，第2轮，第3轮，……第 7轮变换后的输出差分分别为：，其中，其中8,9)≠0，0,0,0,0)，其中

2.2 对7轮不可能差分密码进行分析

将上述7轮不可能差分用于第1轮--第7轮。

第2步：对1272 个明文对。筛选出密文差分8B满足下面条件的数据对：，其中1h和h为任意非0字节，总共有个可能的密文对满足条件，因此概率大约为，经过过滤，大约剩余151272 (2= ×个数据对。

第3步：猜测最后一轮子密钥8K的前2个字节8,1K 、8,0K ，对于剩余的每一个数据对，计算并检验是否有如果等式成立，则说明相应的数据对满足7轮不可能差分，所建议的密钥猜测值就是错误的，这时删除相应的密钥猜测8,1K 、8,0K 。

攻击复杂度分析：分析了 215个密文对进行删除错误密钥之后，大约会剩余密钥猜测值。可以忽略第2步的时间复杂度。第3步需要大约231(=216×215)次1轮加密。因此，攻击的数据复杂度大约为264个选择明文，时间复杂度大约为228次8轮加密。

3 混沌动态S盒情况下的安全性分析

由以上分析可知，在S盒已知的情况下，不可能差分可以有效地攻击此算法。所谓动态S盒是指，每一次加、解密所用的S盒是变化的，这就要求加、解密双方所使用的S盒必须相同，否则接收方将无法正确获得明文。因此，双方共享的数据并不仅仅只有初始密钥K，同时还包括迭代次数 1n+。

通过以上分析可得出如下结论，在S盒未知的情况下，7轮不可能差分路径仍然可以通过上述方法构造，因为其中并没有涉及到具体数据；上述步骤1、2也可如法炮制，但在分析步骤3时，由于并不知道 S盒的具体内容，这一步骤完成后并不能得到正确的数值，而想要通过强力攻击来遍历S盒几乎是不可能的，因此，差分攻击对于这种动态S盒的分组密码并不能实施有效地攻击。

本文所分析的混沌分组密码能够更有效地抵抗差分密码分析。从分析过程中可以看出，这种基于Feistel结构的混沌分组密码的安全性主要体现在混沌动态 S盒的变化性和不可知性上。这为混沌分组密码的发展提供了良好的安全性保证。但从分析过程中也可以看出此算法每 1轮中的扩散度很少，8轮结构不足以使1比特扩散至其他所有比特中，适当增加轮数可以有效地解决这一问题；同时，由于此算法使用了混沌动态 S盒，虽然提高了加解密的安全性，但同时也增加了加解密的复杂度。

4 结语

本文对一种基于Feistel结构的混沌分组密码进行了差分密码分析，分析结果表明，由于混沌动态S盒的存在，使得此算法能够有效地抵抗差分密码分析。分析的同时也指出了一些此算法的不足，为混沌分组密码的研究提供了参考。

[1] 廖晓峰,肖迪,陈勇.混沌密码学的原理及应用[M].北京:科学出版社,2009:59-61.

[2] 郑晓丽.基于单向函数树的多播密钥安全性分析[J].信息安全与通信保密,2007(05):127-128.

[3] ZHAO Geng,CHEN Guanrong, FANG Jingqing,et al.Block Cipher Design: Generalized Single-use-Algorithm based on Chaos[J]. Journal of Tsinghua University,2011,16(02):194-206.

[4] KOCAREV L,JAKIMOSKI G.Logistic Map as a Block Enryption Algorithm[J].Physics Letters A,2001,289(4-5):199-206.

[5] JAKIMOSKI G,KOCAREV L.Differential and Linear Probabilities of a Block-encryption Cipher[J].IEEE Trans. Circuits and Systems-I,2003,50(01):121-123.

[6] 吴文玲,冯登国,张文涛.分组密码的设计与分析[M].第2版.北京:清华大学出版社,2009:1-2.

[7] 郑晓丽.基于无证书公钥密码体制的密钥管理[J].通信技术,2010,43(07):95-97.

[8] 郑晓丽.基于无证书公钥的IP注册的移动协议认证[J].通信技术,2011,44(08):127-129.

[9] 韩睿.一种基于 Feistel结构的混沌分组密码设计与分析[D].西安:西安电子科技大学通信工程学院,2011.