海綿函數

在密碼學，海綿函數（sponge function）或者海綿建構（sponge construction）是一種演算法。它使用有限的狀態，接收任何長度的輸入位元流，然後可以滿足任何長度的輸出。海綿函數可以在理論上面或者實做上面應用，用來架構或者實做密碼學的原始函數，像是加密雜湊函式（cryptographic hash，參考雜湊函數）等等。

海綿函數是由三個部份組成：^[1]

• 一個內存狀態${\displaystyle S}$，包含${\displaystyle b}$個位元
• 一個能置換或者轉換內存狀態，固定大小的轉換函式${\displaystyle f}$
• 一個填充函式（padding function）${\displaystyle P}$

內存狀態會分成兩個區塊，${\displaystyle R}$（大小為${\displaystyle r}$位元）與${\displaystyle C}$（大小為${\displaystyle b-r}$位元）。這裡的參數${\displaystyle r}$又叫做轉換率（bitrate），而${\displaystyle c}$叫做容量（capacity）。

填充函式會在輸入裡面增加足夠的長度，讓輸入的位元流長度變成${\displaystyle r}$的整數倍。因此填充過後的輸入可以被切成長度為${\displaystyle r}$的數個分段。

然後，海綿函數運作如下：

• ${\displaystyle S}$先初始化為零
• 輸入經過填充函式處理
• 填充後輸入的前面${\displaystyle r}$個位元會與R進行XOR運算
• ${\displaystyle S}$經過函式${\displaystyle f}$轉換成${\displaystyle f(S)}$
• 如果填充後輸入還有剩餘，下一${\displaystyle r}$位元的分段與${\displaystyle R}$進行XOR運算
• ${\displaystyle }$S轉換成${\displaystyle f(S)}$
• …

這過程一直重複到所有的輸入都用完為止（在海棉的譬喻裡面，被函數「吸收」了）。

現在海綿函數可以依照如下的過程輸出（「擠出」內容）：

• 此時${\displaystyle R}$裡面的資料是輸出的前面${\displaystyle r}$個位元
• 如果需要更多輸出，先把${\displaystyle S}$轉換成${\displaystyle f(S)}$
• 此時R裡面的資料是輸出的下面${\displaystyle r}$個位元
• …

這過程會重複到滿足輸出所需要的長度為止。

這裡值得注意的地方是，輸入絕對不會與${\displaystyle C}$這部份的記憶體作XOR運算，而且${\displaystyle C}$這一部份記憶體也不會直接被輸出。${\displaystyle C}$這一部份的記憶體僅僅只和轉換函式${\displaystyle f}$相關。在雜湊裡面，防止撞擊攻擊（Collision attack）或者原像攻擊（preimage attack）是依靠${\displaystyle C}$這段記憶體作到的。一般實做上${\displaystyle C}$的大小會是所希望防止等級的兩倍。

海綿函數可以在理論上面或者實做上面應用。在密碼分析理論上，隨機海綿函數（random sponge function）是一個轉換函式f為隨機置換的海綿函數。隨機海綿函數比起經常使用的隨機預言（有關預言的部份請參考預言機）滿足更多加密基元（cryptographic primitives）的限制，像是有限大小的內存狀態。^[2]

海綿函數也可以用來建造實際的加密基元。例如，Keccak雜湊函數就是以海綿函數的方式建立的。Keccak雜湊函數使用1600位元大的版本被國家標準技術研究所（NIST）在SHA-3競賽之中選為贏家。Keccak演算法的特點在於作者所開發複雜、多次的置換函數。^[3]