Keccak演算法簡介美國國家標準與技術研究院(National Institute of Standards and Technology，NIST)於2007年公開徵集SHA-3，要求：能夠直接替代SHA-2，這要求SHA--3必須也能夠產生224，256，384，512位元的雜湊值。保持SHA-2的線上處理能力，這要求SHA-33必須能處理小的資料塊(如512或1024位元)。安全性：能夠抵抗原像和碰撞攻擊的能力，能夠抵抗已有的或潛在的對於SHA-2的攻擊。效率：可在各種硬體平臺上的實現，且是高效的和儲存節省的。靈活性：可設定可選引數以提供安全性與效率折中的選擇，便於平行計算等。2008年10月，有64個演算法正式向NIST提交了方案，經過初步評價，共有51個演算法進入第一輪評估，主要對演算法的安全性、消耗、和實現特點等進行分析。2009年7月24日宣佈，其中14個演算法透過第一輪評審進入第二輪；2010年12月9日宣佈，其中5個演算法(JH、Grstl、Blake、Keccak和Skein)透過第二輪評審進入第三輪。2012年10月2日NIST公佈了最終的優勝者，它就是由意法半導體公司的Guido Bertoai Bertoai、Jean Daemen Daemen、Gilles Van Assche Assche與恩智半導體公司的Micha Michaëël Peeters 聯合設計的Keccak演算法。SHA-3成為NIST的新雜湊函式標準演算法(FIPS PUB 180--5)，Keccak演算法的分析與實現詳見：https://keccak.team/index.htmlSHA-3的結構仍屬於Merkle提出的迭代型雜湊函式結。最大的創新點是採用了一種被稱為海綿結構的新的迭代結構.。海綿結構又稱為海綿函式。在海綿函式中，輸入資料被分為固定長度的資料分組。每個分組逐次作為迭代的輸入，同時上輪迭代的輸出也反饋至下輪的迭代中，最終產生輸出雜湊值。海綿函式允許輸入長度和輸出長度都可變，具有靈活的性，能夠用於設計雜湊函式(固定輸出長度)、偽隨機數發生器，以及其他密碼函式。Keccak演算法描述其輸入資料沒有長度限制，輸出雜湊值的位元長度分為：224，256，384，512。符號與函式Keccak演算法使用以下符號與函式：符號r：位元率(位元 rate)，其值為每個輸入塊的長度c：容量(capacity)，其長度為輸出長度的兩倍b：向量的長度，b=r+c，而b的值依賴於指數I，即b=25×2I
· 函式
Keccak演算法用到了以下5個函式：θ(theta)、ρ(rho)、π(pi)、χ(chi)、ι(iota)
演算法描述
Keccak演算法對資料進行填充，然後迭代壓縮生成雜湊值。
· 填充
對資料填充的目的是使填充後的資料長度為r的整數倍.因為迭代壓縮是對r位資料塊進行的，如果資料的長度不是r的整數倍，最後一塊資料將是短塊，這將無法處理。
設訊息m長度為l位元。首先將位元“1”新增到m的末尾，再新增k個“0”，其中，k是滿足下式的最小非負整數：l+1+k=r-1modr；
然後再新增位元“1”新增到末尾. 填充後的訊息m的位元長度一定為r的倍數。
以演算法Keccak-256，資訊“abc”為例顯示補位的過程. a, b, c對應的ASCII碼分別是97, 98, 99；於是原始資訊的二進位制編碼為：01100001 01100010 01100011。此時r = 1088。
① 補一個“1” ：0110000101100010 01100011 1
② 補1062個“0”：
01100001 01100010 01100011 10000000 00000000 … 00000000
③ 補一個“1” ，得到1088位元的資料：
· 整體描述
Keccak演算法採用海綿結構(Sponge Construction)，在預處理(padding並分成大小相同的塊)後，海綿結構主要分成兩部分：
吸入階段(Absorbing Phase)：將塊xi傳入演算法並處理。
擠出階段(Squeezing Phase)：產生一個固定長度的輸出。
Keccak演算法的整體結構如下圖：
· 吸入與擠出階段
· 壓縮函式
安全性與效能
安全性
可以抵禦對雜湊函式的所有現有攻擊。
到目前為止，沒有發現它有嚴重的安全弱點。
靈活性
可選引數配置，能夠適應雜湊函式的各種應用。
高效性
設計簡單，軟硬體實現方便.在效率方面，它是高效的。
尚未廣泛應用，需要經過實踐檢驗。
常用的Keccak演算法就講到這裡啦，下節課我們將學習常用雜湊函式SM3演算法，敬請期待！
