線性回饋移位寄存器分析
線性回饋移位寄存器的密碼分析。從這個站點我發現 lfsr 可以被 Berlekamp-Massey 算法打破。這個算法的具體進展是什麼？如果還有其他方法可以做到這一點
首先，LFSR單獨使用時並不安全。它們具有良好的統計特性，並且可以根據回饋多項式計算它們的周期。當且僅當相應的回饋多項式是原始的時，LFSR 才是最大長度的。在這種情況下，如果它以非零狀態開始，它將訪問除全零狀態之外的所有狀態。
要查找 LFSR 的抽頭和內部，您可以通過兩種方式進行；
- 為內部和抽頭點提供變數名稱，然後您可以生成系統的線性方程，然後用高斯消元法求解。
- 使用Berlekamp-Massey 算法，這比高斯消元法更快，並且只需要 LFSR 大小的兩倍。即一個有長度的LFSR $ L $ 可以用 $ 2L $ 無論抽頭的數量如何，順序輸出。它是一種互動式算法，根據目前給定的輸出位更新抽頭。
實際上，Berlakamp-Massey 算法產生最短的 LFSR，其抽頭產生給定的序列。該算法可能在消耗所有之前達到結果 $ 2L $ 位，然而，攻擊者需要使用所有 $ 2L $ 位可以肯定。如果 LFSR 的確定多項式不是原語，則可以有不止一個 LFSR 產生不同長度的序列。然而，Berlakamp-Massey 算法總是會找出最短的 LFSR。
基於 LFSR 的古老流密碼是：
將 LFSR 與被Siegenthaler的新穎攻擊破壞的非線性組合器相結合
不規則時鐘作為交替步進發生器
如果抽頭已知，則收縮生成器會損壞；吉爾等。al，2009 年收縮生成器的新攻擊策略， 如果不知道，那麼攻擊並不比蠻力更好。
過濾 LFSR
自收縮發生器（SSG）。對 SSG 的攻擊；
2001 澤納等。人; 自收縮生成器的改進密碼分析需要不到 70% 的蠻力，例如對於 120 位攻擊需要 $ \mathcal{O}(2^{83}) $ -時間。
2011 安帕羅和薩巴特；對自收縮序列生成器的密碼分析攻擊需要 $ \mathcal{O}(2^{L/2}) $ 對於時間複雜度， $ \mathcal{O}(2^{L/4}) $ 對於截獲序列的數量和 $ \mathcal{O}(L^2) $ . 注意這項工作可能不正確，請參閱評論
2006張和方；對自收縮生成器的新猜測和確定攻擊。取決於 $ L $ 他們攻擊的 LFSR 長度；
- $ L \geq 100 $ 然後 $ \mathcal{O}(2^{0.556L}) $ -時間複雜度， $ \mathcal{O}(2^L) $ - 記憶複雜度，和 $ \mathcal{O}(2^{0.161L}) $ -位密鑰流
- $ L < 100 $ 然後 $ \mathcal{O}(2^{0.571L}) $ -時間複雜度， $ \mathcal{O}(2^L) $ - 記憶複雜度，和 $ \mathcal{O}(2^{0.184L}) $ -位密鑰流
至少在理論上，以上所有內容都被打破了。
此外，由於 GSM 和藍牙，一些眾所周知的。