线性反馈移位寄存器分析

Question

线性反馈移位寄存器的密码分析。从这个站点我发现lfsr可以被Berlekamp-Massey算法打破。该算法的具体进展是什么？如果有别的办法

Answer 1

首先，LFSR's单独使用时是不安全的。它们具有很好的统计特性，可以在给定反馈多项式的情况下计算出它们的周期。LFSR是最大长度当且仅当相应的反馈多项式是本原的.在这种情况下，如果它以非零状态开始，它将访问所有州，除非是零状态。

要找到LFSR的龙头和内部，您可以通过两种方式进行；

1. 给出内部和抽头点的变量名，然后生成系统的线性方程，然后用高斯消去法求解。
2. 使用Berlekamp-Massey算法，这是比高斯消除更快，只需要两倍的LFSR的大小。也就是说，长度为L的LFSR可以用2L顺序输出来构造，而不考虑抽头的数目。它是一种根据当前给定的输出位更新抽头的交互式算法。

实际上，Berlakamp-Massey算法产生最短的LFSR，其抽头会产生给定的序列。该算法在使用所有2L位之前可能会到达结果，但是攻击者需要使用所有2L位才能确定。如果LFSR的确定多项式不是原语，则可能有多个LFSR产生不同长度的序列。然而，Berlakamp-Massey算法总是能找到最短的LFSR。

基于LFSR的古流密码是；

• 新型西格纳攻击破坏线性组合器与LFSRs的结合
• 不规则时钟作为交流步进发生器
• 如果水龙头是已知的，收缩发生器就会中断；al，2009年一种新的收缩发生器攻击策略如果不知道，那么这些攻击也不比蛮力强。
• 滤除LFSR
• 自收缩发生器(SSG)。对SSG；的攻击
  • 2001年Zenner et.自收缩发生器的改进密码分析只需要不到70%的蛮力，例如，对于120位，攻击需要\mathcal{O}(2^{83})-time。
  • 2011年Amparo和Sabater；自收缩序列发生器的密码分析攻击需要\mathcal{O}(2^{L/2})作为时间复杂度，\mathcal{O}(2^{L/4})用于截获序列的数量和\mathcal{O}(L^2)。注意:此工作可能不正确，请参阅评论
  • 2006年张和方；对自收缩生成器的新的猜测和判断攻击。取决于L的长度，它们的攻击具有；
    • L \geq 100，\mathcal{O}(2^{0.556L})-time复杂性，\mathcal{O}(2^L)-memory复杂性，\mathcal{O}(2^{0.161L})-bit密钥流
    • L < 100，\mathcal{O}(2^{0.571L})-time复杂性，\mathcal{O}(2^L)-memory复杂性，\mathcal{O}(2^{0.184L})-bit密钥流

所有这些都被打破了，至少在理论上是这样的。

此外，一些众所周知的原因是GSM和蓝牙。

• A5/1和A5/2用于GSM手机，E0用于蓝牙。他们被打破了，看到链接。根据这个来源，国家安全局可以打破A5/1。