密碼學I：流密碼基礎 - 定義及其應用
前往原文地址閱讀，體驗上五個台階......
回顧 & 導言
上節回顧
在上一節中，我們花很長篇幅討論了PRG——偽隨機數生成器，本節我們將看到作為流密碼核心的PRG如何發揮效用，以及幾個PRG的實現和由此構建的流密碼系統。
快速回顧
我們先來快速回顧一下前邊幾篇文章中講到的相關要點：
OTP
首先，我們定義了一次性密碼本（OTP）密碼：
若一個密碼完美安全，則其全體密鑰的數量的必須不少於全體明文的數量
因此，OTP密碼完美安全，因為其 ；但是它又不可實現，因為若存在一種能安全運輸和密文一樣長的密鑰的方法，那我為何不直接用這種方法安全運輸明文呢？
因此，像OTP密碼一樣要求密鑰和明文一樣長的密碼，是無法實現的。
PRG
偽隨機數生成器（PRG）是一個高效的、確定的、不可預測的函數 ，能將一個長度為
的二進位數字元串，擴充為一個長得多的、長度為
的二進位數字元串。
這個函數是否不可預測將直接決定它是否安全，也將決定以它作為核心的流密碼是否安全。
流密碼
為解決OTP不可實現的問題，流密碼引入了一個不可預測的PRG ，將輸入的密鑰
（又稱為「種子」，我們將在下文中交替使用這兩種稱法）送入$G$，從而得到一個和明文一樣長的偽隨機密鑰
，再使用這個偽隨機密鑰完成加密過程。即：
由此可見，正如我們反覆強調的那樣，一個流密碼的安全性將完全依賴於它使用的PRG的安全性，也即這個PRG的不可預測性。
關於上文我們反覆指出流密碼的安全性等同於其不可預測性，這裡作如下解釋：
Andrew C. Yao在其於1982年發表的論文《Theory and application of trapdoor functions》中證明了：
一個不可預測的PRG是安全的。事實上，上述定理的逆定理（一個安全的PRG必然不可預測）也很容易證明。在此就不給出證明過程。關於以上兩個定理的更多討論，請見： - StackExchange - An unpredictable PRG is secure (Theorem Yao82) - ResearchGate - Theory and application of trapdoor functions
線性反饋移位寄存器（LFSR）
在開始介紹流密碼之前，我們先介紹一種簡單的PRG：線性反饋移位寄存器（LFSR）。我們下面將要介紹的一些流密碼都使用這種PRG作為其演算法的核心。這種PRG理解、實現起來都很簡單，因而攻破起來也很簡單（嗯？）
操作
以下簡要介紹LFSR運行的基本操作：
- 初始化。首先，LFSR會以給定的種子（即密鑰）初始化寄存器，以位（比特）為單位：
2. 抽頭。隨後，LFSR從這些比特位中隨機選取一些（稱作「抽頭」），並計算這些抽頭的異或：
圖中綠色的即為抽頭。橙色的為將所有抽頭異或的結果。
3. 位移並附加。最後，LFSR將這些抽頭異或的結果附加到寄存器開頭，並使寄存器向右位移，最後一個比特位作為結果輸出：
用ProcessOn做這些插圖累死了... ...（′□｀川）
順便說下：上邊圖中看上去非常丑的「⊕ XOR」感覺是ProcessOn的bug...
很簡單吧？初始化寄存器後，每個時鐘周期LFSR將執行重複上邊這些步驟，選取一些抽頭，將它們異或，隨後寄存器右移輸出最右一位並將異或結果附加到寄存器開頭。
好處 壞處
使用LFSR的好處是顯然的：簡單還快！計算設備能以非常快的速度運算異或，再加上很短的運算步驟，LFSR生成偽隨機數序列的速度將會很快。同時我們可以看出，LFSR顯然是面向硬體設計的，這使得使用硬體實現高速運行的LFSR將會相當方便和簡單（見NEW WAVE Instruments - LFSR Reference#LFSR Generator Implementations）。
但是，「由於寄存器的狀態是有限的，它最終肯定會是一個重複的循環。」（摘自維基百科 - 線性反饋移位寄存器）因而，LFSR並不安全。使用LFSR構建的流密碼系統也不會安全。事實上，幾乎所有使用LFSR構建的流密碼系統（即使它使用了四個LFSR，見Wikipedia - E0 (cipher)#Cryptanalysis）都已被攻破。
關於LFSR安全性的討論我們暫時就到這裡。下邊我們還會在對一個使用了LFSR的流密碼進行分析的過程中再次探討LFSR的安全性。
內容擾亂系統（CSS）
接下來，我們將討論一個簡單的流密碼——用於加密DVD的內容擾亂系統（Content Scramble System，CSS）。這個系統使用了兩個LFSR，但即便如此，它也已被攻破。事實上，這個流密碼不僅不安全，在現代計算機上運行起來也比那些安全的流密碼慢上不少。這點我們之後還會講到。
構造
CSS使用5位元組（也就是40比特）長度的密鑰和兩個LFSR：一個長17比特的LFSR（即其寄存器長17比特）和一個長25比特的LFSR。每輪兩個LFSR運行幾輪，最後輸出一個位元組。
操作
我們先來看看CSS的基本操作：
- 初始化。CSS使用
接上5位元組種子的前兩個位元組初始化17比特的LFSR，再用
圖中 表示「拼接」。這個符號在之前的一些文章中也有出現。
2. 運行。CSS將每個LFSR都運行八輪。
3. 求和後求模，得到一個位元組。最後，CSS將兩個LFSR的輸出求和並對256求模，得到一個位元組。本輪結束。
總的來說，CSS初始化後每輪運行每個LFSR各8輪（產生八個輸出），隨後將這些輸出求和並模256，得到一個位元組。
CSS是一個相當簡單的密碼。易於硬體實現、速度快，在廉價設備上依能很好地工作。故在廉價設備上也能很好的破解。
攻破
下面我們將簡要討論對CSS的攻破。
以下討論基於一段密文、一段很短的已知的明文頭部（如MPEG-4要求以特定的「box」數據開頭，見MP4文件格式的解析，以及MP4文件的分割演算法），我們能通過最多 次嘗試還原出完整的明文。
操作
- 首先，我們將密文與已知的明文頭部異或，可以得到一段很短的CSS輸出頭部（圖中青色部分）：
為方便說明，下邊我們都假設已知的明文頭部為20位元組，得到的CSS輸出也為20位元組。
2. 隨後，我們猜測第一個17比特長度LFSR的初始狀態，運行它以輸出20位元組，再用先前得 到的CSS輸出頭部減去這個LFSR的輸出，根據CSS的定義，這時我們得到的這個字串（可能）是25比特長度LFSR的一個可能輸出。
3. 事實上，判斷一個20位元組的字串是否來自一個25比特長度的LFSR是簡單的。這裡將包含 一個循環判斷邏輯：
- 如果我們判斷上一步得到的字串確實是25比特長度LFSR的一個可能輸出，則說明我們對17比特長度LFSR的初始狀態猜測正確。
- 如果不是，則說明對17比特長度LFSR的初始狀態猜測錯誤，那我們就再猜一次。
4. 隨後我們再用上一步得到的25比特長度LFSR的一個可能輸出逆推出25比特長度LFSR的初始狀態。
這樣，通過最多 次嘗試，我們就能還原出所有LFSR的初始狀態，並運算出餘下的CSS輸出，最終完成解密。
在家用計算機上，使用類似上述操作的CSS破譯器（如DeCSS，見DeCSS Central - CSS and DeCSS）通常能在一天之內破譯任意一部使用CSS加密的影片。因而現在使用CSS加密DVD已經不流行了。
結語
先前我們已經提到，LFSR並不安全，從上邊「判斷一個20位元組的字串是否來自一個25比特長度的LFSR是簡單的」這句話也可看出。使用LFSR的CSS因LFSR的不安全而被攻破，其它使用LFSR的流密碼系統也是如此。
結語
本節中，我們討論了一個並不強健的PRG（LFSR）和基於這個PRG的同樣並不強健的流密碼系統（CSS），這些密碼系統均已被攻破。在下一節，《流密碼基礎：定義及其應用（續）》中，我們將討論一個現代的流密碼系統：Salsa20。
其實關於Salsa20的玩意已經寫的差不多了的...這裡不一起發出來主要是因為現在的內容已經很多了...而且...我有一點疑問...
<完>
這支付編輯器改版了還是特么超級難用啊.......................∑(O_O；)
推薦閱讀：