SHA-3

维基百科,自由的百科全书
跳转至: 导航搜索
SHA-3(Keccak)
第三代安全散列算法
作者 Guido Bertoni
Joan Daemen
Michaël Peeters
Gilles Van Assche
摘要尺寸 任意
速度 当 r = 1024, c = 576 时
Intel Core 2 上为
12.5 cpb(每位元組周期數)
结构 海绵函数
NIST推荐的组合 SHA3-224
SHA3-256
SHA3-384
SHA3-512
SHAKE128
SHAKE256
摘要长度() 224(SHA3-224)
256(SHA3-256)
384(SHA3-384)
512(SHA3-512)
可变长(SHAKE128/SHAKE256)
内部状态 使用一个5×5字节长度为64位的二维矩阵共1600位
块长度(位) 1152
1088
832
576
最大摘要信息长度 不存在
重复回数 24
所需位操作 按位与按位异或取反循环移位
碰撞 未发现

SHA-3,之前名為Keccak(唸作[kɛtʃak],像l“ketchak”)演算法,[2]是一個加密雜湊演算法,由 Guido BertoniJoan DaemenMichaël Peeters,以及Gilles Van Assche設計在RadioGatún上面。2012年10月2號,Keccak被選為NIST雜湊函式競賽的勝利者。[3] SHA-3並不是要取代SHA-2,因為SHA-2目前並沒有出現明顯的弱點。由於對MD5出現成功的破解,以及對SHA-0SHA-1出現理論上破解的方法,NIST感覺需要一個與之前演算法不同的,可替換的加密雜湊演算法,也就是現在的SHA-3。設計者宣稱在Intel Core 2的CPU上面,此演算法的效能是12.5cpb(每位元組周期數,cycles per byte)。[4]不過,在硬體實做上面,這個演算法比起其他演算法明顯的快上很多。[5]

Keccak使用海綿函數[6][7],此函數會將資料與初始的內部狀態做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 範例[编辑]

赢得NIST公开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

2014年4月 FIPS 202 草案的算法[编辑]

  • 空字串的雜湊值:
SHA3-224("")
0x 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
SHA3-256("")
0x a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
SHA3-384("")
0x 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
SHA3-512("")
0x a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26
SHAKE128("")
0x 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef263cb1eea988004b93103cfb0aeefd2a686e01fa4a58e8a3639ca8a1e3f9ae57e2
35b8cc873c23dc62b8d260169afa2f75ab916a58d974918835d25e6a435085b2badfd6dfaac359a5efbb7bcc4b59d538df9a04302e10c8bc1cbf1a0b3a5120ea
17cda7cfad765f5623474d368ccca8af0007cd9f5e4c849f167a580b14aabdefaee7eef47cb0fca9767be1fda69419dfb927e9df07348b196691abaeb580b32d
ef58538b8d23f87732ea63b02b4fa0f4873360e2841928cd60dd4cee8cc0d4c922a96188d032675c8ac850933c7aff1533b94c834adbb69c6115bad4692d8619
f90b0cdf8a7b9c264029ac185b70b83f2801f2f4b3f70c593ea3aeeb613a7f1b1de33fd75081f592305f2e4526edc09631b10958f464d889f31ba010250fda7f
1368ec2967fc84ef2ae9aff268e0b1700affc6820b523a3d917135f2dff2ee06bfe72b3124721d4a26c04e53a75e30e73a7a9c4a95d91c55d495e9f51dd0b5e9
d83c6d5e8ce803aa62b8d654db53d09b8dcff273cdfeb573fad8bcd45578bec2e770d01efde86e721a3f7c6cce275dabe6e2143f1af18da7efddc4c7b70b5e34
5db93cc936bea323491ccb38a388f546a9ff00dd4e1300b9b2153d2041d205b443e41b45a653f2a5c4492c1add544512dda2529833462b71a41a45be97290b6f
SHAKE256("") 0x 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be
141e96616fb13957692cc7edd0b45ae3dc07223c8e92937bef84bc0eab862853349ec75546f58fb7c2775c38462c5010d846c185c15111e595522a6bcd16cf86
f3d122109e3b1fdd943b6aec468a2d621a7c06c6a957c62b54dafc3be87567d677231395f6147293b68ceab7a9e0c58d864e8efde4e1b9a46cbe854713672f5c
aaae314ed9083dab4b099f8e300f01b8650f1f4b1d8fcf3f3cb53fb8e9eb2ea203bdc970f50ae55428a91f7f53ac266b28419c3778a15fd248d339ede785fb7f
5a1aaa96d313eacc890936c173cdcd0fab882c45755feb3aed96d477ff96390bf9a66d1368b208e21f7c10d04a3dbd4e360633e5db4b602601c14cea737db3dc
f722632cc77851cbdde2aaf0a33a07b373445df490cc8fc1e4160ff118378f11f0477de055a81a9eda57a4a2cfb0c83929d310912f729ec6cfa36c6ac6a75837

參考資料[编辑]

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

外部連接[编辑]