基于分类搜索与快速变换的流密码攻击算法

作者：陆正福; 杨慧慧; 周宪法

来源：实验室研究与探索, 2019, 38(04): 90-114.

• 线性反馈移位寄存器
• 最大似然译码
• 快速相关攻击
• 映射结构

提出了基于分类搜索、快速变换和最大似然译码(MLD)的快速相关攻击算法FCA-MLD-CS-FWT。在寻找校验方程时首次引入分类搜索策略;对校验方程引用快速Walsh变换;在译码阶段对线性反馈移位寄存器(LFSR)的状态分割,并采用MLD进行LFSR初态的破译。实验表明:该算法可在单核计算平台上将原始密钥长度为60的流密码破译时间缩短在1 h左右;通过静态字典的建立可实现不同参数校验方程的快速搜索;译码阶段时间复杂度由O(2Bm)降低为O(2BB+m)。