SHA-3

SHA-3（第三代安全雜湊演算法，），之前名為Keccak（或)）演算法，設計者宣稱在 Intel Core 2 的CPU上面，此演算法的效能是12.6时钟周期每位元組（cycles per byte）Keccak is second only to Luffa, which did not advance to the final round.。

SHA-3 在2015年8月5日由 NIST 通过 FIPS 202 正式发表。

 历史 
 Keccak 是一個加密雜湊演算法，由 Guido Bertoni，Joan Daemen，Michaël Peeters，以及Gilles Van Assche在RadioGatún上设计。
 2012年10月2日，Keccak 被選為NIST雜湊函式競賽的勝利者。SHA-2目前沒有出現明顯的弱點。由於對MD5、SHA-0和SHA-1出現成功的破解，NIST感覺需要一個與之前演算法不同的，可替換的加密雜湊演算法，也就是現在的 SHA-3。
 2014年，NIST 发布了 FIPS 202 的草案 "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions"。
 2015年8月5日，FIPS 202 最终被 NIST 批准。

 设计 
Keccak 使用海綿函數，此函數會將資料與初始的內部狀態做XOR運算，這是無可避免可置換的（inevitably permuted）。在最大的版本，演算法使用的內存狀態是使用一個5×5的二維陣列，資料型態是64位元的字節，總計1600位元 。縮版的演算法使用比較小的，以2為冪次的字節大小w為1位元，總計使用25位元。除了使用較小的版本來研究加密分析攻擊，比較適中的大小（例如從w=4使用100位元，到w=32使用800位元）則提供了比較實際且輕量的替代方案。

 Keccak 的置換 

置換方法是先定義字的長度為二的某次方，w = 2ℓ位元。SHA-3的主要應用使用64位元的字長，ℓ = 6。

內存狀態可以被視為5×5×w的三維陣列。令a[i][j][k]代表內存狀態的第(i×5 + j)×w + k個位元（使用小端序，little-endian，參見位元組序）。

置換函數是五個子段落（sub-round）作12+2ℓ次的迴圈，每一個子段落都相當簡單：

 修改 
在整個 NIST 雜湊函數比賽裡面，參賽者允許稍微修改演算法解決已經出現的問題。Keccak 的修改有：
 迴圈的數目從12+ℓ變成12+2ℓ，以增加安全度。
 填充函式使用比起上述10*1的方式更加複雜的作法。
 吸收比率r增加到安全限制，而非向下捨入到最接近某個2的冪次。

 SHA-3 範例 
 空字串的雜湊值：

 SHA3-224("")
 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
 SHA3-256("")
 a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
 SHA3-384("")
 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
 SHA3-512("")
 a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26
 SHAKE128("", 256)
 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26
 SHAKE256("", 512)
 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be

 由於雪崩效应，即使一個很小的改變都會產出幾乎完全不同的雜湊值。舉例來說，把 dog 改成 dof：

 SHAKE128("The quick brown fox jumps over the lazy dog", 256)
 f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e
 SHAKE128("The quick brown fox jumps over the lazy dof", 256)
 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

 SHA 家族函数的比较 
在下面的表格中，“内部状态”指的是传递到下一个块的位数。

+ SHA 家族函数的比较 算法及其变体 输出长度<br/ >(位) 内部状态大小<br/ >(位) 块大小<br/ >(位) 最大消息长度<br/ >(位) 循环 操作 安全性<br/ >(位) 示例的性能<br/ >(MiB/s) MD5(作为参考)  128  128(4 × 32)  512  264 − 1  64  按位与, 按位异或, 循环移位, 填充(求模 232), 按位或    335 SHA-0  160  160(5 × 32)  512  264 − 1 80  按位与, 按位异或, 循环移位, 填充(求模 232),按位或     - SHA-1  160  160(5 × 32)  512  264 − 1  80  )  192 SHA-2  SHA-224  SHA-256  224256  256(8 × 32)  512  264 − 1  64  按位与, 按位异或, 循环移位, 填充(求模 232), 按位或, 移位  112/128  139 SHA-384  SHA-512  SHA-512/224  SHA-512/256   384  512  224  256  512(8 × 64)  1024  2128 − 1  80  按位与, 按位异或, 循环移位, 填充(求模 264), 按位或, 移位  192/256/112/128  154 SHA-3  SHA3-224  SHA3-256  SHA3-384  SHA3-512  224  256  384  512  1600(5 × 5 × 64)  1152  1088  832  576  无限制  24  按位与, 按位异或, 循环移位, 取反  112/128/192/256  - SHAKE128  SHAKE256  d (可变长)  d (可变长)  1344  1088  min (d/2, 128)min (d/2, 256)  -

 參考資料 

 外部連結 
 Keccak網站(英文)
 Keccak官方C语言代码包
 Keccak官方C++语言工具集
 A Java implementation of Keccak
 A Cryptol implementation of Keccak
 A VHDL source codes developed in the Cryptographic Engineering Research Group (CERG) at George Mason University

Category:密码散列函数
Category:密碼學理論
Category:带有源代码的公共领域软件
Category:NIST散列函数竞赛