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

Fast Key Recovery Attack on the Bit-Search Generator

作　　者：贾艳艳[1] 胡予濮[1] 高军涛[1] 

机构地区：[1]西安电子科技大学计算机网络与信息安全教育部重点实验室西安710071

出　　处：《电子科技大学学报》2011年第5期783-786,共4页Journal of University of Electronic Science and Technology of China

基　　金：国家自然科学基金(6083300860803149);国家973计划(2007CB311201)

摘　　要：针对比特搜索生成器,利用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（2^0.5L L^3） to 0（2^0.43L L^3） if we have O（NL） of keystream bits. Here L is the length of the linear feedback shift register （LFSR）; N 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.

关 键 词：比特搜索生成器 密钥流生成器 密钥恢复攻击 缩减生成器 流密码 

分 类 号：TN918.1[电子电信—通信与信息系统]