采样攻击的最短采样距分析

Analysis of the Minimum Decimation Distance of Decimation Attack

采样攻击是针对序列密码的一种攻击方法。该文对本原线性反馈移存器(LFSR)序列的采样攻击方法进行了研究,给出了采样距与被采序列和采出序列的线性复杂度之间的制约关系,给出了能使采出序列的线性复杂度小于被采序列的线性复杂度的最短采样距,给出了能成功实施采样攻击需要的最少已知明文量,并据此分析了对本原LFSR序列进行采样攻击的实际可行性,证明了只有当本原LFSR的级数很小时,该方法才可能有实用价值。

Decimation attack is one attack method of stream ciphers. In this paper, the decimation attack to prime Linear Feedback Shift Register（LFSR） sequences is investigated. The connection of decimation distance and the linear complexity of the original sequence and the decimate sequence is presented. The minimum decimate distance that makes the linear complexity of the decimate sequence less than that of the original sequence is obtained. The minimum known plaintext amount for decimation attack is given, and the practical feasibility of the decimation attack to prime LFSR＇s is analyzed. It is proved that the decimation attack to prime LFSR is useful possibly only in the case that the degree of LFSR is very small.