Encryption
對 LFSR 密鑰流生成器的攻擊
好吧，這是我在我的一本書中發現的一個問題：
給定的是一個流密碼，它使用單個 LFSR 作為密鑰流生成器。LFSR 的度數為 256。
- 發起一次成功的攻擊需要多少個明文/密文位對？
- 詳細描述攻擊的所有步驟，並製定需要解決的公式。
我不明白的是作者是如何得出答案的。
首先，似乎需要 512 對連續的明文/密文來發起攻擊，這包括創建一個由 256 個線性方程組成的系統並求解它們，我明白這一點。
我的問題是：如果我們要建構一個只有 256 個方程的系統，為什麼我們需要 512 個連續的明文/密文對？不應該是256對嗎？
連續明文-密文對的數量 $ (x_i,y_i) $ 如果我們提前知道 LFSR 抽頭（等效於：歸約多項式），則必要的比特數是 256，原因在問題中解釋。512 是我們不這樣做的時候，因為它會產生更多的未知數：除了初始狀態之外，多項式的係數。
如果我們知道 LFSR 抽頭，那麼初始狀態就是所有未知的，並且直接由前 256 個值的向量給出 $ x_i\oplus y_i $ 對於斐波那契形式的 LFSR （在反射中，取決於符號）。在伽羅瓦形式中，找到初始狀態的一種選擇是求解方程組。
如果 LFSR 抽頭未知，標準算法是Berlekamp-Massey，它重建最短 LFSR 狀態和回饋多項式匹配給定序列 $ x_i\oplus y_i $ （不以學位為輸入）。
PS：我在網上找到了解決方案，並調整了我的符號。假設回饋多項式最初是未知的（或等效的密鑰的一部分），因此有 512 對。根據 Berlekamp-Massey，該決議沒有明確規定。相當
- 使用斐波那契形式的 LFSR，前 256 $ x_i\oplus y_i $ 給出初始的內部狀態。唯一剩下的未知數是 256 個係數 $ p_i $ 的回饋多項式。
- 這 256 個剩餘的未知數是通過求解具有 256 個未知數的 256 個方程的系統來找到的，該系統使用 512 $ x_i\oplus y_i $ . 該系統指出內部狀態是從前 256 $ x_i\oplus y_i $ 到下一個 256 $ x_i\oplus y_i $ 經過 256 步後，由 $ p_i $ .