SHA-3

维基百科,自由的百科全书
跳转至: 导航搜索

SHA-3,之前名為Keccak(唸作[kɛtʃak],像l“ketchak”)演算法,[1]是一個加密雜湊演算法,由 Guido BertoniJoan DaemenMichaël Peeters,以及Gilles Van Assche設計在RadioGatún上面。2012年10月2號,Keccak被選為NIST雜湊函式競賽的勝利者。[2] SHA-3並不是要取代SHA-2,因為SHA-2目前並沒有出現明顯的弱點。由於對MD5出現成功的破解,以及對SHA-0SHA-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 + jw + 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

參考資料[编辑]

  1. ^ The Keccak sponge function family: Specifications summary. [2011-05-11]. 
  2. ^ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. [2012-10-02]. 
  3. ^ Keccak implementation overview Version 3.2 http://keccak.noekeon.org/Keccak-implementation-3.2.pdf
  4. ^ 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.
  5. ^ Sponge Functions. Ecrypt Hash Workshop 2007. 
  6. ^ On the Indifferentiability of the Sponge Construction. EuroCrypt 2008. 

外部連接[编辑]