海綿函式，在密碼學中是一種算法。它使用有限的狀態，接收任何長度的輸入位元流，然後可以滿足任何長度的輸出。海綿函式可以在理論上面或者實做上面套用，用來架構或者實做密碼學的原始函式，像是加密雜湊函式(cryptographic hash，參考雜湊函式)等等。
基本介紹
- 中文名：海綿函式
- 外文名：sponge function
- 別稱：海綿建構
操作,結構,套用,
操作
海綿功能操作如下：
1、狀態S初始化為零
2、填充輸入字元串。這意味著使用填充函式P將輸入轉換為r位塊。
3、對於填充輸入的每個r位塊B：
a.R被R XOR B替換（使用按位異或）
b.S被f（S）取代
這個過程“吸收”（在海綿比喻中）填充輸入字元串的所有塊。
海綿功能輸出可以生成（“擠出”），如下所示：
1、輸出狀態存儲器的R部分。
2、重複直到輸出足夠的位：
a.S被f（S）取代。
b.輸出狀態存儲器的R部分
如果剩餘少於r位要輸出，則R將被截斷（僅輸出R的一部分）。
另一個比喻將狀態記憶描述為“熵池”，輸入“湧入”池中，轉換函式稱為“攪動熵池”。
注意，輸入位永遠不會異或進入狀態存儲器的C部分，也不會直接輸出任何C位。輸入改變C的程度完全取決於變換函式f。在哈希套用中，對碰撞或前像攻擊的抵抗力取決於C，並且其大小（“容量”c）通常是所需阻力水平的兩倍。
結構
海綿函式是由三個部份組成：
1.一個記憶體狀態S，包含b個位元
2.一個能置換或者轉換記憶體狀態，固定大小的轉換函式f
3.一個填充函式(padding function)P
記憶體狀態會分成兩個區塊，R（大小為r位元）與C（大小為b - r位元）。這裡的參數r又叫做轉換率（bitrate），而c叫做容量（capacity）。
填充函式會在輸入裡面增加足夠的長度，讓輸入的位元流長度變成r的整數倍。因此填充過後的輸入可以被切成長度為r的數個分段。
然後，海綿函式運作如下：
1.S先初始化為零
2.輸入經過填充函式處理
3.填充後輸入的前面r個位元會與R進行XOR運算
4.S經過函式f轉換成f(S)
5.如果填充後輸入還有剩餘，下一r位元的分段與R進行XOR運算
6.S轉換成f(S)
…
這過程一直重複到所有的輸入都用完為止（在海棉的譬喻裡面，被函式"吸收"了）。
海綿函式可以依照如下的過程輸出（"擠出"內容）：
1.此時R裡面的資料是輸出的前面r個位元
2.如果需要更多輸出，先把S轉換成f(S)
3.此時R裡面的資料是輸出的下面r個位元
…
這過程會重複到滿足輸出所需要的長度為止。
這裡值得注意的地方是，輸入絕對不會與C這部份的記憶體作XOR運算，而且C這一部份記憶體也不會直接被輸出。C這一部份的記憶體僅僅只和轉換函式f相關。在雜湊裡面，防止撞擊攻擊(Collision attack)或者原像攻擊(preimage attack)是依靠C這段記憶體作到的。一般實做上C的大小會是所希望防止等級的兩倍。
套用
海綿函式可以在理論上面或者實做上面套用。在密碼分析理論上，隨機海綿函式(random sponge function)是一個轉換函式f為隨機置換的海綿函式。隨機海綿函式比起經常使用的隨機預言（有關預言的部份請參考預言機）滿足更多加密基元(cryptographic primitives)的限制，像是有限大小的記憶體狀態。
海綿函式也可以用來建造實際的加密基元。例如，Keccak雜湊函式就是以海綿函式的方式建立的。Keccak雜湊函式使用1600位元大的版本被國家標準技術研究所(NIST)在SHA-3競賽之中選為贏家。Keccak算法的特點在於作者所開發複雜、多次的置換函式。
