对称密码算法中两类线性表达式的概率优势

计算机科学与探索 ›› 2007, Vol. 1 ›› Issue (1): 39-46.

对称密码算法中两类线性表达式的概率优势

张海纳¹,王少辉¹,王小云²

1.山东大学数学与系统科学学院，济南 250100
2.清华大学高等研究中心，北京 100087

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-06-06 发布日期:2007-06-06
通讯作者: 张海纳

Probability advantages of two linear expressions in symmetric ciphers*

ZHANG Hai-na¹,WANG Shao-hui¹,WANG Xiao-yun²⁺

1.School of Mathematics and System Sciences，Shandong University，Ji’nan 250100，China
2.Center for Advanced Study，Tsinghua University，Beijing 100087，China

Received:1900-01-01 Revised:1900-01-01 Online:2007-06-06 Published:2007-06-06
Contact: ZHANG Hai-na

摘要/Abstract

摘要： 分析欧洲序列密码候选算法ABC的安全性，提炼出两类与安全性密切相关的具有概率优势的线性表达式。两个概率优势反映了模加法运算之间的两种线性相关性。利用每类表达式及其概率优势都可以推导出ABC算法的大量弱密钥。在弱密钥条件下，可以计算出算法的1 257 bit初始密钥，从而导致了算法的有效破解方法。第一类表达式反映了两个模加法方程普遍存在的一种线性相关性，第二类表达式反映了三个模加法方程的比特进位之间的线性相关性。其中，第二类中一个典型的表达式最初是由Wu和Preneel发现，并由此得到296个弱密钥，但他们只是通过测试试验数据得到了该表达式的概率优势估计值，并未给出严格证明。文中给出两类表达式的概率优势的严格证明。模加运算被广泛应用于对称密码的设计中，相信这两类线性表达式的概率优势不仅可以用来分析其它对称密码算法，而且对于设计安全的对称密码算法也是非常重要的。

关键词: 密码分析, 概率优势, 模加法运算, ABC序列密码

Abstract: The paper proves the probability advantages of two linear expressions which are summarized from the ABC stream cipher submitted to ECRPYT Estream Project.Two linear expressions with probability advantages reflect the linear correlations among Modular Addition equations.Corresponding to each linear expression and its advantage，a large amount of weak keys are derived under which all the ABC main keys can be retrieved successively.The first linear expression is a generic bit linear correlation between two Modular Addition equations.The second is a linear correlation of bit carries derived from three Modular Addition equations and the linearequation of LFSR in ABC.
It is remarked that the second is found by Wu and Preneel，and has been used to find 296 weak keys.In the cryptanalysis of ABC，Wu and Preneel only utilized its estimated probability advantage which is concluded by experimental data，and they did not give its strict proof.
Modular Addition and XOR operations are widely used in designing symmetric ciphers.It is believed that these types of linear expressions with probability advantages not only can be used to analyze some other symmetric ciphers，but also are important criteria in designing secure symmetric ciphers.

Key words: cryptanalysis, probability advantage, Modular Addition, ABC stream cipher

张海纳1,王少辉1,王小云2 . 对称密码算法中两类线性表达式的概率优势[J]. 计算机科学与探索, 2007, 1(1): 39-46.

ZHANG Hai-na¹,WANG Shao-hui¹,WANG Xiao-yun²⁺. Probability advantages of two linear expressions in symmetric ciphers*[J]. Journal of Frontiers of Computer Science and Technology, 2007, 1(1): 39-46.