查看“︁海綿函數”︁的源代码

{{noteTA
|G1=IT
}}
[[File:SpongeConstruction.svg|lang=zh|thumb|upright=1.35|right|alt=Illustration of the sponge construction |雜湊函數的海綿建構。這裡p<sub>i</sub>是輸入的分段，z<sub>i</sub>則是輸出的分段]]

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

==結構==
海綿函數是由三個部份組成：<ref>{{Cite web |url=http://sponge.noekeon.org/ |title=Sponge Functions |publisher=Ecrypt Hash Workshop 2007 |author1=Guido Bertoni |author2=Joan Daemen |author3=Michaël Peeters |author4=Gilles Van Assche |accessdate=2012-10-09 |archive-date=2016-10-23 |archive-url=https://web.archive.org/web/20161023195714/http://sponge.noekeon.org/ |dead-url=yes }}</ref>

* 一個內存狀態<math>S</math>，包含<math>b</math>個位元 
* 一個能置換或者轉換內存狀態，固定大小的轉換函式<math>f</math>
* 一個填充函式（padding function）<math>P</math>

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

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

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

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

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

現在海綿函數可以依照如下的過程輸出（「擠出」內容）：
*此時<math>R</math>裡面的資料是輸出的前面<math>r</math>個位元
*如果需要更多輸出，先把<math>S</math>轉換成<math>f(S)</math>
*此時R裡面的資料是輸出的下面<math>r</math>個位元
*…

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

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

==應用==
海綿函數可以在理論上面或者實做上面應用。在密碼分析理論上，'''隨機海綿函數'''（random sponge function）是一個轉換函式''f''為隨機置換的海綿函數。隨機海綿函數比起經常使用的[[隨機預言]]（有關預言的部份請參考[[預言機]]）滿足更多加密基元（cryptographic primitives）的限制，像是有限大小的內存狀態。<ref>{{Cite web |url=http://sponge.noekeon.org/ |title=On the Indifferentiability of the Sponge Construction |publisher=EuroCrypt 2008 |author1=Guido Bertoni |author2=Joan Daemen |author3=Michaël Peeters |author4=Gilles Van Assche |accessdate=2012-10-09 |archive-date=2016-10-23 |archive-url=https://web.archive.org/web/20161023195714/http://sponge.noekeon.org/ |dead-url=yes }}</ref>   

海綿函數也可以用來建造實際的加密基元。例如，[[Keccak]]雜湊函數就是以海綿函數的方式建立的。Keccak雜湊函數使用1600位元大的版本被[[國家標準技術研究所]]（NIST）在[[SHA-3|SHA-3競賽]]之中選為贏家。Keccak演算法的特點在於作者所開發複雜、多次的置換函數。<ref>{{Cite web|url=http://www.nist.gov/itl/csd/sha-100212.cfm|title=NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition|date=2012-10-02|publisher=[[NIST]]|accessdate=2012-10-04|archive-date=2012-10-05|archive-url=https://web.archive.org/web/20121005031201/http://www.nist.gov/itl/csd/sha-100212.cfm|dead-url=no}}</ref>

==參考資料==
{{reflist}}

[[Category:密码散列函数]]
[[Category:密码学理论]]