On the estimation of the second largest eigenvalue of Markov ciphers
On the estimation of the second largest eigenvalue of Markov ciphers
复制标题
马尔可夫密码第二大特征值的估计
DOI：
10.1002/sec.1465
复制
发表时间：
2016-09
影响因子：
--
通讯作者：
Lai, Xuejia
中科院分区：
文献类型：
--
作者：
Lin, Tingting;Shun, Xin;Xue, Fenglei;Lai, Xuejia
差分密码分析是现代密码分析中的一种有效工具。马尔可夫密码的差分链形成马尔可夫链，转移矩阵的第二大特征值SLE确定迭代次数，使得马尔可夫密码能够抵抗差分密码分析。由于转移矩阵的规模很大，计算SLE是不可行的。因此，估计方法是可取的。我们发现了两种利用文献中的行随机矩阵的元素来估计SLE的方法。它们的优势是并行计算，不需要生成完整的矩阵。我们将这两种方法应用到国际数据加密算法8的转移矩阵中，并考察了这种估计的准确性。由于国际数据加密算法是一种原始的马尔可夫密码，其转移矩阵将收敛到一个均匀分布。我们使用初始转移矩阵的功率来估计不同轮数下的SLE，并对结果进行比较。当转移矩阵中零元素较少且分布更均匀时，经过几轮后估计的误差将是可以接受的。此外，我们还给出了马尔可夫密码针对差分密码分析所需的迭代次数与SLE之间的简单关系，并给出了矩阵分解方法的必要条件。版权所有©2016 John Wiley&Sons，Ltd.
Differential cryptanalysis is an effective tool in modern cryptanalysis. The differential chain of a Markov cipher forms a Markov chain, and the second largest eigenvalue SLE of the transition matrix determines the number of iterations such that the Markov cipher can resist differential cryptanalysis. Owing to the huge scale of the transition matrix, it is infeasible to compute the SLE. Thus, an estimation method would be desirable. We find two methods to estimate the SLE by using the elements of the row-stochastic matrix in the literature. Their advantage is parallel computing, without generating the complete matrix. We apply these two methods to the transition matrix of International Data Encryption Algorithm8 and investigate the accuracy of such estimation. Because the International Data Encryption Algorithm is a primitive Markov cipher, its transition matrix will converge to a uniform distribution. We use the power of the initial transition matrix to estimate the SLE for different number of rounds and compare the results. The errors of the estimation will be acceptable after several rounds when there are less zero elements in the transition matrix and the distribution is more uniform. Moreover, we present a simple relation between the SLE and the number of iterations that the Markov cipher requires against differential cryptanalysis and show the necessary condition of the matrix decomposition method. Copyright © 2016 John Wiley & Sons, Ltd.
登录
查看更多内容
DOI：
--
发表时间：
2003
期刊：
--
影响因子：
--
作者：
Taher H. Haveliwala;S. Kamvar
通讯作者：
Taher H. Haveliwala;S. Kamvar
DOI：
10.3929/ethz-a-000646711
发表时间：
1992
期刊：
--
影响因子：
--
作者：
Xuejia Lai
通讯作者：
Xuejia Lai
DOI：
10.1007/978-3-540-74462-7_1
发表时间：
2006-08
期刊：
--
影响因子：
--
作者：
E. S. Ayaz;A. Selçuk
通讯作者：
E. S. Ayaz;A. Selçuk
影响因子：
3
作者：
E. Biham;O. Dunkelman;Nathan Keller;A. Shamir
通讯作者：
E. Biham;O. Dunkelman;Nathan Keller;A. Shamir
DOI：
10.1007/3-540-48519-8_10
发表时间：
1999-03
期刊：
--
影响因子：
--
作者：
E. Biham;A. Biryukov;A. Shamir
通讯作者：
E. Biham;A. Biryukov;A. Shamir