SHA-3
SHA-3，之前名為Keccak（唸作[kɛtʃak]，像l“ketchak”）演算法，[1]是一個加密雜湊演算法，由 Guido Bertoni，Joan Daemen，Michaël Peeters，以及Gilles Van Assche設計在RadioGatún上面。2012年10月2號，Keccak被選為NIST雜湊函式競賽的勝利者。[2] SHA-3並不是要取代SHA-2，因為SHA-2目前並沒有出現明顯的弱點。由於對MD5出現成功的破解，以及對SHA-0和SHA-1出現理論上破解的方法，NIST感覺需要一個與之前演算法不同的，可替換的加密雜湊演算法，也就是現在的SHA-3。設計者宣稱在Intel Core 2的CPU上面，此演算法的效能是12.5cpb(每位元組周期數，cycles per byte)。[3]不過，在硬體實做上面，這個演算法比起其他演算法明顯的快上很多。[4]
Keccak使用海綿函數[5][6]，此函數會將資料與初始的內部狀態做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("") 0x f71837502ba8e10837bdd8d365adb85591895602fc552b48b7390abd SHA3-256("") 0x c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470 SHA3-384("") 0x 2c23146a63a29acf99e73b88f8c24eaa7dc60aa771780ccc006afbfa8fe2479b2dd2b21362337441ac12b515911957ff SHA3-512("") 0x 0eab42de4c3ceb9235fc91acffe746b29c29a8c366b7c60e4e67c466f36a4304c00fa9caf9d87976ba469bcbe06713b435f091ef2769fb160cdab33d3670680e
由於雪崩效應，即使一個很小的改變都會產出幾乎完全不同的雜湊值。舉例來說，在句子後面加入句點：
SHA3-224("The quick brown fox jumps over the lazy dog") 0x 310aee6b30c47350576ac2873fa89fd190cdc488442f3ef654cf23fe SHA3-224("The quick brown fox jumps over the lazy dog.") 0x c59d4eaeac728671c635ff645014e2afa935bebffdb5fbd207ffdeab SHA3-256("The quick brown fox jumps over the lazy dog") 0x 4d741b6f1eb29cb2a9b9911c82f56fa8d73b04959d3d9d222895df6c0b28aa15 SHA3-256("The quick brown fox jumps over the lazy dog.") 0x 578951e24efd62a3d63a86f7cd19aaa53c898fe287d2552133220370240b572d SHA3-384("The quick brown fox jumps over the lazy dog") 0x 283990fa9d5fb731d786c5bbee94ea4db4910f18c62c03d173fc0a5e494422e8a0b3da7574dae7fa0baf005e504063b3 SHA3-384("The quick brown fox jumps over the lazy dog.") 0x 9ad8e17325408eddb6edee6147f13856ad819bb7532668b605a24a2d958f88bd5c169e56dc4b2f89ffd325f6006d820b SHA3-512("The quick brown fox jumps over the lazy dog") 0x d135bb84d0439dbac432247ee573a23ea7d3c9deb2a968eb31d47c4fb45f1ef4422d6c531b5b9bd6f449ebcc449ea94d0a8f05f62130fda612da53c79659f609 SHA3-512("The quick brown fox jumps over the lazy dog.") 0x ab7192d2b11f51c7dd744e7b3441febf397ca07bf812cceae122ca4ded6387889064f8db9230f173f6d1ab6e24b6e50f065b039f799f5592360a6558eb52d760
參考資料[编辑]
- ^ The Keccak sponge function family: Specifications summary. [2011-05-11].
- ^ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. [2012-10-02].
- ^ Keccak implementation overview Version 3.2 http://keccak.noekeon.org/Keccak-implementation-3.2.pdf
- ^ Guo, Xu; Huang, Sinan; Nazhandali, Leyla; Schaumont, Patrick, Fair and Comprehensive Performance Evaluation of 14 Second Round SHA-3 ASIC Implementations, NIST 2nd SHA-3 Candidate Conference. Aug. 2010: 12 [2011-02-18] Keccak is second only to Luffa, which did not advance to the final round.
- ^ Sponge Functions. Ecrypt Hash Workshop 2007.
- ^ On the Indifferentiability of the Sponge Construction. EuroCrypt 2008.
外部連接[编辑]
- Keccak網站(英文)
- 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
