比特搜索生成器的快速密钥恢复攻击

摘要

针对比特搜索生成器,利用Martin Hell关于自缩生成器的攻击思想,提出了一种基于多段密钥流的概率快速密钥恢复攻击.与目前已知的最好攻击结果相比,该攻击能够将计算复杂度人O(20.5LL3)降低到O(20.43LL3),特别地,当L为96时,计算复杂度可以达到O(20.39LL3),所需的数据复杂度为O(NL).实验结果表明,随着密钥段数的增多,算法的计算复杂度明显减少；密钥长度越长,该算法的攻击效果越好.%For the bit-search generator, a fast probabilistic key recovery attack based on multi segments of keystream bites is presented using the idea of Martin Hell's attack on the self-shrinking generator. Compared with the best known attack, the attack complexity can be significantly reduced from O(20.5lL3) to O(20.43LL3) if we have O(NL) of keystream bits. Here L is the length of the linear feedback shift register (LFSR); JV is the number of the segments of keystream bits. The experimental results show that: the complexity of this algorithm can be significantly degraded as the number of attacks increases; The longer the length of the key is, the more efficient our attack is.