消息认证之SHA散列算法族
消息認證——安全散列算法SHA(Secure Hash Algorithm)
一. 消息認證
對要傳遞的消息進行加密有兩個目的，其一是防止消息被消息發(fā)送者和消息接收者之外的第三者竊聽（被動攻擊），在之前文章中列舉了一系列的對稱加密算法（DES、AES、RC4等）都已經(jīng)滿足這一點目標；而加密的另一個目的就是防止消息被偽造（主動攻擊）。
偽造消息的意思是指第三者已經(jīng)獲取到消息傳遞的規(guī)則，并假裝自己是消息發(fā)送者，向消息接收者發(fā)送經(jīng)過篡改或捏造的假消息，而消息接收者在不知情的情況下誤以為這些假消息是來自合法的發(fā)送者。為了防止消息被偽造，我們就需要對被發(fā)送的消息進行“簽名”認證。這種對消息的簽名在密碼學上稱之為消息認證碼MAC(Message Authentication Code)。
消息認證需要滿足以下三點目標：
二. 散列函數(shù)
2.1 散列函數(shù)介紹
散列函數(shù)的目的是為文件、消息或其他數(shù)據(jù)塊產生“指紋”，為滿足在消息認證中的應用，散列函數(shù)H必須具有下列性質：
前三個性質是使用散列函數(shù)進行消息認證的實際可行要求。第四個性質，抗原像攻擊（單向性），使得給定消息容易產生它的散列碼，但給定散列碼幾乎不可能恢復出消息。如果認證技術中使用了消息+密鑰作為輸入，那么單向性就變得非常重要了。假如散列函數(shù)不是單向的，而攻擊者能夠獲得消息M以及對消息M+密鑰K的散列碼 C=H(M+K) C = H ( M + K ) ，攻擊者對散列函數(shù)取逆得到 M+K=H?1(C) M + K = H ? 1 ( C ) ,這時攻擊者同時擁有消息M和消息+密鑰（M+K），所以他可以輕而易舉地恢復密鑰K。
第五個性質，抗弱碰撞性，保證了對于給定的消息，不可能找到具有相同散列值的可替換消息，利用加密的散列碼可防止消息被偽造。如果散列函數(shù)不具有該特性，那么接活消息及加密的消息散列碼的攻擊者，可以根據(jù)消息產生沒被加密的散列碼，然后生成具有相同散列碼的偽造消息來替換原消息。
滿足上述五個性質的散列函數(shù)稱為弱散列函數(shù)，散列碼長度為 n 的散列函數(shù)強度為 2n 2 n 。如果還滿足第六個性質則稱為強散列函數(shù)。第六個性質可以防止像生日攻擊這種類型的復雜攻擊。這種攻擊把散列碼長度為 n 的散列函數(shù)強度降為 2n/2 2 n / 2 。
| 抗原像 | 2n 2 n |
| 抗弱碰撞 | 2n 2 n |
| 抗強碰撞 | 2n/2 2 n / 2 |
表 2.1 散列值長度為n的散列函數(shù)強度
2.2 簡單散列函數(shù)
所有散列函數(shù)都按照這種普通原理操作：將輸入（消息、文件等）看成長度為n比特的數(shù)據(jù)塊序列，對輸入用迭代方式每次處理一塊，最終生成n比特長度的散列碼。
一種最簡單的散列函數(shù)就是將輸入的每一個數(shù)據(jù)塊都按比特異或。表達式如下：
其中i為最終散列碼的第i比特，1…m表示第幾個數(shù)據(jù)塊。
這種操作為輸入的每一比特位置產生簡單的奇偶校驗，這種校驗對于隨機數(shù)據(jù)相當有效，數(shù)據(jù)查錯卻不改變散列值的幾率為 2?n 2 ? n 。但如果數(shù)據(jù)是可預測格式化的，那么校驗有效性將變差。比如普通的文本中，每個字節(jié)（8比特）的最高階總是0，因此如果采用128比特的散列值，該散列值的校驗有效概率變?yōu)?span id="ze8trgl8bvbq" class="MathJax_Preview" style="color: inherit; display: none;"> 2?112 2 ? 112 ，而不是 2?128 2 ? 128 。
對上面的方案進行改進的一種簡單方法是在每個數(shù)據(jù)塊處理后，對散列循環(huán)移位或旋轉固定比特位數(shù)，來消除輸入數(shù)據(jù)的可預測格式。
雖然上述方案提供了一個數(shù)據(jù)完整性方法，但別忘了，這種簡單的異或操作完全不具有上一節(jié)所述的散列函數(shù)第五個特性——抗弱碰撞性。對于一個消息x的異或散列值， Hxor(x) H x o r ( x ) ，總是能輕而易舉地找到一個在原消息上追加、混淆、甚至與原消息毫無相干的偽造消息y，來使得 Hxor(y)=Hxor(x) H x o r ( y ) = H x o r ( x ) 。那么這樣產生的散列值，對于消息的簽名認證就毫無意義。
三. 安全散列函數(shù)SHA算法族
3.1 SHA介紹
近些年，應用最為廣泛的散列函數(shù)是安全散列算法（SHA）。有意思的是，由于其他每一種被廣泛應用的散列函數(shù)都已被證實存在著密碼分析學上的缺陷，截止到目前，SHA或許是最后僅存的標準散列算法。
SHA由美國國家標準與技術研究所（NIST）開發(fā)，生成160比特長度的散列值，并于1993年公布成為美國聯(lián)邦信息處理標準。2002年，NIST公布了三種新版本的SHA：SHA-256、SHA-384、SHA-512，散列長度分別為256、384和512，三者并稱SHA-2。
2005年，NIST宣布計劃到2010年不再認可SHA-1，轉為信任SHA-2。此后不久，有研究團隊描述了一種攻擊方法，該方法可以只用 269 2 69 次操作找到產生相同的SHA-1散列值的兩條獨立消息，遠少于SHA-1碰撞理論所需的 280 2 80 次。之后，我國的王小云教授等人又提出一種新的攻擊，是的碰撞復雜度再次降到 263 2 63 ，這些結果迫使NIST在2006年宣布2010年后不再推薦使用SHA-1。而Google于2017年公布并開源了在當前計算能力下對SHA-1的碰撞攻擊算法，并在自家實驗室完成了真實世界中的第一次碰撞攻擊，他們通過GPU加速碰撞，創(chuàng)造了兩個SHA-1完全相同的PDF文件，徹底將SHA-1逼入死胡同，當然，這些都是題外話。
| 消息摘要大小 | 160 | 256 | 384 | 512 |
| 消息大小 | <264 < 2 64 <script type="math/tex" id="MathJax-Element-158"><2^{64}</script> | <264 < 2 64 <script type="math/tex" id="MathJax-Element-159"><2^{64}</script> | <2128 < 2 128 <script type="math/tex" id="MathJax-Element-160"><2^{128}</script> | <2128 < 2 128 <script type="math/tex" id="MathJax-Element-161"><2^{128}</script> |
| 消息塊大小 | 512 | 512 | 1024 | 1024 |
| 字大小 | 32 | 32 | 64 | 64 |
| 步驟數(shù) | 80 | 64 | 80 | 80 |
| 安全強度(理論值) | 280 2 80 | 2128 2 128 | 2192 2 192 | 2256 2 256 |
表 3.1 SHA各算法參數(shù)比較
3.2 SHA-512
這一節(jié)將對SHA-512進行詳細介紹，該算法以最大長度不超過 2128 2 128 位的消息作為輸入，將輸入以1024位的數(shù)據(jù)塊進行處理，生成512位的消息摘要散列值。處理過程包括以下步驟。
3.2.1 SHA-512 算法步驟
第1步：追加填充比特。填充消息使其長度模1024余896 [ 896≡len%1024 896 ≡ l e n % 1024 ]。即使消息已經(jīng)是期望的長度，也總是要填充，因此填充比特的范圍是1~1024，填充部分是由單個比特1后接所需個數(shù)的比特0構成。
第2步：追加長度。將128比特的含有原始消息長度信息的無符號整數(shù)追加在消息后面。這一步后，消息長度為1024比特的整數(shù)倍。
第3步：初始化散列緩沖區(qū)。用512比特的緩沖區(qū)保存散列函數(shù)中間和最終結果。緩沖區(qū)可以是8個64比特的寄存器（a、b、c、d、e、f、g、h），這些寄存器初始化為64比特的整數(shù)，這些值取自前8個質數(shù)的平方根小數(shù)部分的前64比特。
圖 3.1 緩沖區(qū)寄存器初始值
第4步： 處理1024比特的數(shù)據(jù)塊消息。算法的核心是80輪迭代構成的模塊。每一輪都以512比特的換沖區(qū)值 abcdefgh 作為輸入，并且更新緩沖區(qū)內容。處理第 i 個消息塊 Mi M i 時，初始輪的輸入端，緩存中間散列值為 Hi?1 H i ? 1 ，任意第 t 輪，從1024比特的消息塊 Mi M i 中獲取64比特的輪子消息 Wt W t ，每一輪嗨使用外加常數(shù) Kt K t ，這些常數(shù)來自于前80個質數(shù)立方根小數(shù)部分的前64比特，用來隨機化消息，消除輸入數(shù)據(jù)中的任何規(guī)則性。第80輪輸出加到初始輪輸入 Hi?1 H i ? 1 上，生成 Hi H i 。
第5步：輸出。當所有N個1024比特數(shù)據(jù)塊都處理完畢后，最終緩沖區(qū)寄存器中的值便是512比特的消息摘要散列值。
整個過程的步驟如圖3.2 所示，其中最核心的第4步對單個數(shù)據(jù)塊的輪處理步驟在圖中標記為F。
圖 3.2 SHA-512 生成消息摘要過程圖
3.2.2 SHA-512 數(shù)據(jù)塊處理步驟詳解
第4步對數(shù)據(jù)塊的輪處理過程較為復雜，這一小節(jié)再單獨詳細描述一下。對于每個待處理的消息數(shù)據(jù)塊 Mi M i ，執(zhí)行以下處理步驟。
- 用1024比特的數(shù)據(jù)塊生成每輪處理所需的64比特的輪子數(shù)據(jù)分組，一共80個（ [W0,W1,...,W79] [ W 0 , W 1 , . . . , W 79 ] ）。前16個數(shù)據(jù)分組 W0 W 0 ~ W15 W 15 直接取自數(shù)據(jù)塊（1024=64*16），剩余分組使用以下方式產生：
Wt=δ5121(Wt?2)+Wt?7+δ5120(Wt?15)+Wt?16 W t = δ 1 512 ( W t ? 2 ) + W t ? 7 + δ 0 512 ( W t ? 15 ) + W t ? 16
δ5121(x)=ROTR1(x)⊕ROTR8(x)⊕SHR7(x) δ 1 512 ( x ) = R O T R 1 ( x ) ⊕ R O T R 8 ( x ) ⊕ S H R 7 ( x )
δ5120(x)=ROTR19(x)⊕ROTR61(x)⊕SHR6(x) δ 0 512 ( x ) = R O T R 1 9 ( x ) ⊕ R O T R 6 1 ( x ) ⊕ S H R 6 ( x )
其中 ROTRn(x) R O T R n ( x ) 為對64比特變量 x 做循環(huán)右移 n 位的操作，+ 為模 264 2 64 位加。
圖 3.3 數(shù)據(jù)塊輪處理分組的產生過程
獲取每輪處理所需的64比特外加常數(shù)，一共80個（ [K0,K1,...,K79] [ K 0 , K 1 , . . . , K 79 ] ）,由上節(jié)所述方式獲取，取自前80個質數(shù)的立方根小數(shù)部分的前64比特。
單輪處理，具體輪處理過程如圖3.4所示。
圖 3.4 基本的SHA-512單輪處理過程
從圖中可以看出，輪函數(shù)輸出的8個字中，有6個是通過簡單的輪置換獲得的（圖中陰影部分的 abcefg→bcdfgh a b c e f g → b c d f g h ），剩余的兩個字 a 和 e 則通過替換操作產生。
字 e 是將輸入變量 (d,e,f,g,h) ( d , e , f , g , h ) 以及輪常數(shù) Kt K t 和輪分組 Wt W t 作為輸入的函數(shù)輸出。字 a 則是將除 d 之外的輸入變量以及輪常數(shù) Kt K t 和輪分組 Wt W t 作為輸入的函數(shù)輸出。這兩個字的產生方法解釋如下：
T2=(∑5120a)+Maj(a,b,c)(3.2) (3.2) T 2 = ( ∑ 0 512 a ) + M a j ( a , b , c )
e=d+T1(3.3) (3.3) e = d + T 1
a=T1+T2(3.4) (3.4) a = T 1 + T 2
Ch(e,f,g)=(eANDf)⊕(NOTeANDg)(3.5) (3.5) C h ( e , f , g ) = ( e A N D f ) ⊕ ( N O T e A N D g )
Maj(a,b,c)=(aANDb)⊕(aANDc)⊕(bANDc)(3.6) (3.6) M a j ( a , b , c ) = ( a A N D b ) ⊕ ( a A N D c ) ⊕ ( b A N D c )
(∑5120a)=ROTR28(a)⊕ROTR34(a)⊕ROTR39(a)(3.7) (3.7) ( ∑ 0 512 a ) = R O T R 28 ( a ) ⊕ R O T R 34 ( a ) ⊕ R O T R 39 ( a )
(∑5121e)=ROTR14(e)⊕ROTR18(e)⊕ROTR41(e)(3.8) (3.8) ( ∑ 1 512 e ) = R O T R 14 ( e ) ⊕ R O T R 18 ( e ) ⊕ R O T R 41 ( e )
其中，式3.5中的條件位運算函數(shù)意義為如果e，則f，否則g；式2、6中的條件位運算函數(shù)意義為當且僅當變量的多數(shù)（2個或者3個）為真時函數(shù)為真；+ 運算與上節(jié)一樣，為模 264 2 64 位加。
- 循環(huán)單輪處理80次，最后的輸出與初始輪輸入做加運算即為本數(shù)據(jù)塊處理后的輸出。
3.2.4 SHA-512算法總結
SHA-512算法使得散列碼的任意比特都受到輸入端每1比特的影響，基本函數(shù)F的復雜迭代產生了非常好的混淆效果，即隨機選取兩組即使很相似的規(guī)則性消息也不可能產生相同的散列碼。除非SHA-512中存在目前未公開的隱藏缺陷，找到兩個具有相同摘要的消息的復雜度需要 2256 2 256 次操作，給定摘要尋找消息的復雜度需要 2512 2 512 次操作。這在當前軟硬件計算能力水平，理論上是不可攻破的。
總結
以上是生活随笔為你收集整理的消息认证之SHA散列算法族的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Android +kotlin Bann
- 下一篇： 微信小程序之获取接口数据展示