演化密码对抗多重线性密码分析能力的研究  

Evolutionary cryptography against multidimensional linear cryptanalysis

作　　者：张焕国[1,2] 李春雷[1,2] 唐明[1,2] 

机构地区：[1]武汉大学计算机学院,武汉430072 [2]空天信息安全与可信计算教育部重点实验室,武汉430072

出　　处：《中国科学：信息科学》2012年第5期603-616,共14页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:69973034;90104005;60373087;60673071;60970115;60970116;91018008;60970006;61003267)资助项目

摘　　要：演化密码是我国学者提出的一种新型密码.文中对演化密码对抗多重线性密码分析的能力进行研究,研究表明演化密码对抗多重线性攻击方面的能力高于普通固定算法密码.文中介绍了基于对数似然比(LLR)统计方法的两种多重线性密码分析方法,这两种方法利用多个线性逼近式分别扩展了Matsui最初提出的线性攻击算法1和算法2.在考察这两种算法的数据复杂度N、比特优势a,以及预期成功率PS三者关系的基础上,证明了在比特优势和预期成功率相同的条件下,攻击演化密码的数据复杂度大于攻击固定算法密码的数据复杂度,并论述了在数据复杂度N相同的情况下,攻击演化密码的时间复杂度和空间复杂度都明显高于攻击固定算法密码的情形.这表明演化密码在对抗多重线性攻击方面的安全性高于固定算法密码.The evolutionary cryptosystem is a new cryptosystem proposed by a Chinese researcher recently. This paper studies its security level resisting against multidimensional linear cryptanalysis in this paper. It is shown that the evolutionary cryptosystem possesses higher resistance than its initial fixed cryptosystem does for resisting against multidimensional linear cryptanalysis. Multidimensional generalizations of Matsui＇s Algorithm 1 and Algorithm 2 based on log-likelihood ratio （LLR） statistics are introduced. By the relationship among the data complexity N, the bit advantage a and the success rate Ps of these two multidimensional generalized algorithms, it is proven that more data is needed for attacking the evolutionary cryptosystem than that is needed for attacking its initial fixed cryptosystem when the bit advantage and success rate are identical. Moreover, it is shown that both time complexity and memory complexity for attacking the evolutionary cryptosystem are higher than that of attacking its initial fixed cryptosystem the evolutionary cryptosystem is more robust than linear cryptanalysis. with the same data complexity. The research indicates that its initial fixed cryptosystem against the multidimensional

关 键 词：信息安全 密码学 演化密码 密码分析 多重线性密码分析 

分 类 号：TN918.1[电子电信—通信与信息系统]