海綿函數

维基百科,自由的百科全书
跳转至: 导航搜索
Illustration of the sponge construction
雜湊函數的海綿建構。這裡pi是輸入的分段,zi則是輸出的分段

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

結構[编辑]

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

  • 一個內存狀態S,包含b個位元
  • 一個能置換或者轉換內存狀態,固定大小的轉換函式f
  • 一個填充函式(padding function)P

內存狀態會分成兩個區塊,R(大小為r位元)與C(大小為b - r位元)。這裡的參數r又叫做轉換率(bitrate),而c叫做容量(capacity)。

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

然後,海綿函數運作如下:

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

這過程一直重複到所有的輸入都用完為止(在海棉的譬喻裡面,被函數"吸收"了)。

現在海綿函數可以依照如下的過程輸出("擠出"內容):

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

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

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

應用[编辑]

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

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

參考資料[编辑]

  1. ^ Sponge Functions. Ecrypt Hash Workshop 2007.  |coauthors= requires |author= (帮助)
  2. ^ On the Indifferentiability of the Sponge Construction. EuroCrypt 2008.  |coauthors= requires |author= (帮助)
  3. ^ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. [2012-10-04].