对比特搜索生成器的猜测确定攻击

摘要

针对具有低重量反馈多项式的比特搜索生成器(BSG),利用猜测确定攻击的思想提出了一种快速密钥恢复攻击.该算法基于BSG序列的差分构造特点,首先由截获的密钥流恢复出候选差分序列,然后用反馈多项式对候选差分序列进行校验,以此减少需要求解的L维线性方程系统的数量,从而大大减少了算法所需的复杂度.理论分析和仿真结果表明,对于反馈多项式的重量小于10的BSG,该算法明显优于现有的攻击方法.特别地当反馈多项式的重量为3时,该算法能够将最好的攻击结果O(L320.5L)降低到O(L20.5L).