海綿函式
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![Illustration of the sponge construction](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/7/70/SpongeConstruction.svg/langzh-300px-SpongeConstruction.svg.png)
在密碼學,海綿函式(sponge function)或者海綿建構(sponge construction)是一種演算法。它使用有限的狀態,接收任何長度的輸入位元流,然後可以滿足任何長度的輸出。海綿函式可以在理論上面或者實做上面應用,用來架構或者實做密碼學的原始函式,像是加密雜湊函式(cryptographic hash,參考雜湊函式)等等。
結構
海綿函式是由三個部份組成:[1]
- 一個主記憶體狀態,包含個位元
- 一個能置換或者轉換主記憶體狀態,固定大小的轉換函式
- 一個填充函式(padding function)
主記憶體狀態會分成兩個區塊,(大小為位元)與(大小為位元)。這裡的參數又叫做轉換率(bitrate),而叫做容量(capacity)。
填充函式會在輸入裡面增加足夠的長度,讓輸入的位元流長度變成的整數倍。因此填充過後的輸入可以被切成長度為的數個分段。
然後,海綿函式運作如下:
- 先初始化為零
- 輸入經過填充函式處理
- 填充後輸入的前面個位元會與R進行XOR運算
- 經過函式轉換成
- 如果填充後輸入還有剩餘,下一位元的分段與進行XOR運算
- S轉換成
- …
這過程一直重複到所有的輸入都用完為止(在海棉的譬喻裡面,被函式「吸收」了)。
現在海綿函式可以依照如下的過程輸出(「擠出」內容):
- 此時裡面的資料是輸出的前面個位元
- 如果需要更多輸出,先把轉換成
- 此時R裡面的資料是輸出的下面個位元
- …
這過程會重複到滿足輸出所需要的長度為止。
這裡值得注意的地方是,輸入絕對不會與這部份的記憶體作XOR運算,而且這一部份記憶體也不會直接被輸出。這一部份的記憶體僅僅只和轉換函式相關。在雜湊裡面,防止撞擊攻擊(Collision attack)或者原像攻擊(preimage attack)是依靠這段記憶體作到的。一般實做上的大小會是所希望防止等級的兩倍。
應用
海綿函式可以在理論上面或者實做上面應用。在密碼分析理論上,隨機海綿函式(random sponge function)是一個轉換函式f為隨機置換的海綿函式。隨機海綿函式比起經常使用的隨機預言(有關預言的部份請參考預言機)滿足更多加密基元(cryptographic primitives)的限制,像是有限大小的主記憶體狀態。[2]
海綿函式也可以用來建造實際的加密基元。例如,Keccak雜湊函式就是以海綿函式的方式建立的。Keccak雜湊函式使用1600位元大的版本被國家標準技術研究所(NIST)在SHA-3競賽之中選為贏家。Keccak演算法的特點在於作者所開發複雜、多次的置換函式。[3]
參考資料
- ^ Guido Bertoni; Joan Daemen; Michaël Peeters; Gilles Van Assche. Sponge Functions. Ecrypt Hash Workshop 2007. [2012-10-09]. (原始內容存檔於2016-10-23).
- ^ Guido Bertoni; Joan Daemen; Michaël Peeters; Gilles Van Assche. On the Indifferentiability of the Sponge Construction. EuroCrypt 2008. [2012-10-09]. (原始內容存檔於2016-10-23).
- ^ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. 2012-10-02 [2012-10-04]. (原始內容存檔於2012-10-05).