| 摘要: |
| 差分分析是分析分组密码安全性的最有效的方法之一，本文从一个新的角度研究了轮函数为双射的密钥交替的迭代型分组密码的差分性质。S盒的差分分布表在研究迭代型分组密码的差分分析中起到了重要作用。类比S盒的差分分布表，我们研究轮函数的差分概率分布表（DPT），我们发现DPT矩阵是一个马尔科夫矩阵，并通过研究DPT矩阵的性质来研究分组密码的差分性质。一方面，我们通过分析矩阵的性质给出了一些有关迭代型分组密码的差分性质的证明，并且研究了当轮函数是对合轮函数时其最大差分概率的性质。我们证明了若迭代型分组密码的DPT矩阵有两个值为1的特征值，那么经过足够高的轮数后，该分组密码一定没有高概率差分;而当值为1的特征值个数多于两个时，其可能存在任意轮的高概率差分。另一方面，由于对实际的迭代型分组密码来说，轮函数的差分概率分布表所对应的矩阵维数过高，实现这样规模的矩阵的存储与计算并不可行。为了解决该问题，我们分析其字节级截断差分概率，构造其字节级截断差分概率分布表，通过研究其对应的矩阵来研究字节级截断差分性质。对于状态被分成16个字节或半字节的 轮分组密码来说，构造该表的空间复杂度是c1*2^(32)，时间复杂度是c1*2^(37.92) ，其中c1,c2=O(log r)。现阶段，可以借助高性能计算机在可接受的时间内得到整个分组密码的全部字节级截断差分信息。 |
| 关键词: 分组密码 差分分析 截断差分分析 差分分布表 对合轮函数 |
| DOI：10.19363/J.cnki.cn10-1380/tn.2023.06.05 |
| 投稿时间：2020-10-31修订日期：2021-02-20 |
| 基金项目:国家自然科学基金项目（面上项目，重点项目，重大项目） |
|
| Research on Differential Analysis using Differential Probability Distribution Table |
|
liuhui, yangli
|
| (Institute of Information Engineering,Chinese Academy of Sciences) |
| Abstract: |
| Differential cryptanalysis is one of the most effective methods of block cipher cryptanalysis. In this paper we study the differential properties of key-alternating iterated block cipher with bijective round function from a new sight. Differential Distribution Table(DDT) plays an important role in the differential cryptanalysis of iterated block ci-pher. By analogy with DDT, we study the Differential Probability Distribution Table(DPT) of round function, and we find the DPT matrix is a Markov matrix. Then we study the differential properties of block cipher by analyzing the properties of DPT matrix. On one hand, we provide some proofs concerning the differential properties of block ci-pher and we focus on the special case when the round function is involutory. We proved that if the DPT matrix of a block cipher’s round function has only two eigenvalues with value 1, then the block cipher must have no high-probability differential after sufficiently many rounds. However, when the number of DPT matrix’s eigenvalue with value 1 exceeds 2, the block cipher may have a high probability difference for any round. On the other hand, for a practical block cipher, the dimension of its round function’s DPT matrix is so high that storing and computing such matrix is infeasible. To settle this problem, we analyze the byte-oriented truncated differential probability and construct Byte-oriented Truncated Differential Probability Distribution Table(TPT) of iterated block cipher to study the byte-oriented truncated differential properties. For a r-round block cipher the block of which can be divided into 16 bytes or nibbles, it costs c1*2^(32) in memory and takes c1*2^(37.92) in time to construct TPT, where c1,c2=O(log r). We can get all the byte-oriented truncated differential information of the whole block cipher with high-performance computer in acceptable time at the present stage. |
| Key words: block cipher differential cryptanalysis truncated differential cryptanalysis differential distribution table involu-tory round function |
