密碼學I：流密碼基礎 - 定義及其應用（續）

08-09

來自專欄你好，密碼學！5 人贊了文章

在知乎閱讀體驗極差（三級標題都沒有...）
強烈建議前往作者博客或超理論壇閱讀！！
強烈建議前往作者博客或超理論壇閱讀！！！

強烈建議前往作者博客或超理論壇閱讀！！！！

流密碼基礎：定義及其應用（續）

現代流密碼：Salsa20

在討論了一個不好的PRG（線性反饋移位寄存器，LFSR）和一個不好的密碼（內容擾亂系統，CSS）之後，接下來我們再簡要討論一個設計良好的現代流密碼系統：Salsa20。

順帶一提，Salsa20是由eSTREAM項目發布的。

構造

Salsa20的PRG並不太符合我們先前介紹的PRG的結構。類似LFSR的PRG要輸入一個密鑰，隨後輸出偽隨機序列；而類似Salsa20的PRG則要輸入一個密鑰和一個新鮮值（Nonce），輸出偽隨機序列。這個新鮮值將參與偽隨機序列的生成，用於保證即使密鑰相同，輸出的偽隨機序列依然不同。關於這個新鮮值我們之後還會講到。

Salsa20輸入128位或256位密鑰和一個64位的新鮮值，每輪產生64位元組（512位）的輸出。

實際上，Salsa20每輪的計算還與一個輪計數器有關。該計數器以0為初始值，逐輪遞增。由於Salsa20每輪使用輪計數器的值不同，因而最終可以輸出極長的偽隨機序列。

操作

Salsa20的運算由若干輪組成，每輪執行一些運算，產生64位元組的輸出，最後將這若干輪個64位元組拼接得到最終的輸出。

每輪

接下來我們來看看Salsa20每輪的基本操作：

初始化。Salsa20初始狀態長64位元組，每輪也輸出64位元組。這64位元組如此初始化：

圖中的B表示「位元組」，以下均同

其中的 $au_0$ 、 $au_1$ 、 $au_2$ 和 $au_3$ 分別表示三個不同的固定常數，它們的值由Salsa20規範給定。

2. 重複施加函數。 對上述初始狀態施加一可逆的循環移位函數 $h$ ，重複約12輪。

PPT製圖大法好！

其中函數 $h$ 為一個高效、可逆的函數以保證Salsa20符合一致性方程。關於函數的詳細信息可參見：Salsa20 - Design, Specification, Security and Speed

3. 逐字加。最後，將64位元組的初始狀態（上圖橙框）與施加了位移函數的數據（上圖紅框）進行4位元組一次的加法，得到該輪的輸出。（這就不用上圖了吧Orz）

事實上，如果沒有最後一步逐字加，Salsa20將沒有任何的偽隨機性；因為：

我們已知輸出和輸入的結構
函數$h$完全可逆
故而，在沒有逐字加這一步的情況下，還原原始輸入，進而得到密鑰$k$會很容易。

總操作

以下給出Salsa20的總計算式：

$mathtt{Salsa20(}k;;rmathtt)::=:H(:k,;(r,:0):)quad||quad H(:k,;(r,:0):) quad || quad ...$

其中：

每個由拼接符號 $||$ 分隔的即為每輪的輸出，裡邊的數字代表的正是輪計數器。
函數 $H(...)$ 表示「輪」，具體操作步驟在上邊有給出。

可以發現，每輪的輸出依賴於每輪的初始狀態，而每輪的初始狀態依賴於輪計數器，這意味著只要輪計數器不同，在執行了若干次循環位移函數後，每輪的輸出將會相當不同。

而根據定義可知，輪計數器是逐輪遞增的，顯然每輪都不同，因而每輪的輸出也不會相同了。故而將每輪的輸出拼接後得到的總輸出具有相當的偽隨機性。

「當你的輪計數器遞增，0，1，2，3 ...；它會給你一個偽隨機序列，要多長有多長。」

分析

需要指出，Salsa20有很多不同的版本（Salsa20/5、Salsa20/6、Salsa20/12等），它們唯一的不同僅在於每輪重複施加函數$h$的次數不同。如Salsa20/5每輪重複施加函數$h$5次，Salsa20/12每輪重複施加函數$h$12次，以此類推。

最後，我們再來看看Salsa20的安全性、性能及其影響。

安全性

作為流密碼，Salsa20似乎是無法預測的。根據cr.yp.to - Stream-cipher attacks中的描述，256密鑰版本、每輪重複施加12次函數的Salsa20/12目前仍未被攻破且被認為具有256位的安全性（256-bit security）。其它一些重複施加較少次函數的版本（Salsa20/5、Salsa20/6）則已被攻破。

各不同版本的Salsa20的安全情況見下表：