為什麼基於線性回饋移位寄存器的流密碼如此流行？

我正在研究流密碼，而 LFSR 是我研究的一個子課題，我想知道為什麼 LFSR 如此受歡迎？

從前有流行；

1. 它們很容易在硬體中實現。想想你只需要閂鎖和 $ \oplus $ . 對於組合功能一些 $ \wedge $ 手術。
2. 它們的周期性質，最小多項式和特徵多項式等都得到了很好的研究。您可以在所羅門·哥倫布的經典著作中看到一瞥。
3. 正如弗格里厄在評論中所說，他們沒有安全感。單個 LFSR 可以被Berlekamp-Massay 算法破解。你只需要 $ 2L $ 密鑰流，如果 LFSR 的長度是 $ L $ . 有趣的是，這個算法是為解碼 BCH 碼而發明的。
4. 許多人嘗試使用 LFSR 來生成安全的流密碼。要查看對他們的攻擊，請查看連結。

• 將 LFSR 與被Siegenthaler的新穎攻擊破壞的非線性組合器相結合
• 不規則時鐘作為交替步進發生器
• 收縮發電機
• 過濾 LFSR

5. 一些最近（可追溯到 1999 年）基於 LFSR 的算法

• A5/1和A5/2用於 GSM 手機，E0用於藍牙。如果您仔細查看它們的用法，您會發現該密碼還有第二個設計因素。那是; 使用更小的硬體。並且，這降低了功耗。

---

**注0：**定義：

• 移位寄存器：級聯觸發器，每個輸出連接到下一個輸入。在每個時鐘週期，數據移位一個。如’C’程式碼 x << 1
• 線性回饋移位寄存器，LFSR是一個移位寄存器，其輸入是先前狀態的線性組合。
• 非線性回饋移位寄存器 NLFSR是一個移位寄存器，其輸入是先前狀態的非線性組合。

注 1：eSream 項目中的以下內容正在使用 LFSR 或 NLFSR 或兩者：

1. Trivium使用 3 個 NLFSR。
2. Sosemanuk 使用具有最大周期的 LFSR $ 2^{230}-1 $
3. Grain同時使用 LFSR 和 NLFSR
4. MICKEY同時使用 LFSR 和 NLFSR

**注 2：**正如@bmmo6 在評論中所說，他們還有其他應用程序。

**注 3：**我幾乎不記得 Cryptologia 中的產品廣告。他們聲稱他們結合了 5 個 LFSR 來生成安全密碼。

@kelalaka 出色答案的補充。

這裡有一些基於 LFSR（以及 Trivium 的 NLFSR）的流密碼，它們尚未被破解。

1. 瑣事
2. 自收縮發電機。

此外，一些具有更現代結構的流密碼也鮮為人知。

引用自：https://crypto.stackexchange.com/questions/66698