為流密碼組合 LFSR：為什麼我們需要高非線性？
線性回饋移位寄存器 ( LFSR ) 可以是出色的（高效、快速且具有良好統計特性）的偽隨機發生器。許多流密碼都是基於 LFSR的，這種流密碼的一種可能設計是結合 $ m $ LFSR 作為布爾函式的輸入 $ f:GF(2)^m\rightarrow GF(2) $ . 最後一個功能必須仔細選擇。
我的問題是一個相當基本的問題。我知道使用一個LFSR 來生成密鑰流是不合適的，因為可以通過知道其中的一小部分來創建整個密鑰流：如果一個長度的抽頭位置 $ n $ LFSR是已知的，一個需要 $ n $ 位來確定整個密鑰流序列，如果它們不知道，則需要 $ 2n $ 位（通過使用Berlekamp-Massey算法找出抽頭位置）。但是，為什麼我們需要LFSR的非線性組合（以及各種其他要求）？獲得多個具有適當長度和抽頭位置的 LFSR 並將它們的輸出進行異或以生成密鑰流會有什麼問題？
如果沒有非線性，那麼密鑰流輸出的每一位都將是未知密鑰位的（已知）線性函式。因此，在已知明文攻擊場景中，已知密鑰流輸出的每一位都允許我們在未知密鑰位上編寫線性方程。如果我們有一個 128 位的密鑰，則有 128 個布爾未知數（變數），所以一旦我們有 128 位的已知密鑰流，我們就有 128 個未知數中的 128 個線性方程。此時，使用求解線性方程組的標準方法（例如，高斯消元法）求解原始密鑰位變得容易。因此，攻擊者可以從流密碼的 128 位已知輸出中恢復密鑰，這完全破壞了流密碼。
防止這種攻擊的唯一方法是確保密碼包含非線性元素。為了防止其他相關但更高級的攻擊（例如，線性密碼分析），還需要在流密碼中具有足夠的非線性。
澄清：為簡單起見，我上面的回答假設 LFSR 的回饋多項式是已知的。該攻擊確實可以推廣到回饋多項式未知的情況（您需要兩倍的已知密鑰流輸出）；在這種情況下，攻擊變得有點複雜，但基本思想仍然適用。我試圖保持簡單，以幫助您理解直覺，而不會陷入數學困境，但是如果您想查看有關回饋多項式未知的情況的更多詳細資訊，Dilip Sarwate 有一個很好的答案，可以更徹底地解釋這種情況.