汪建　方洪鷹

摘要：安全哈希算法（Secure Hash Algorithm）誕生之初便作為優(yōu)秀的簽名算法得到安全界的重視，其中SHA-1更是因為其安全性和高效性被全球各個領(lǐng)域普遍采用。但是面對海量的待簽信息，傳統(tǒng)的算法將不再勝任。該文著力于基于大數(shù)據(jù)的SHA-1算法研究，通過改造散列計算步驟，提出分布式云計算模型，最終減少算法的空間復(fù)雜度提高計算效率。

關(guān)鍵詞：大數(shù)據(jù)；云計算；分布式計算；SHA-1

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1009-3044（2014）30-7032-04

安全散列算法（Secure Hash Algorithm，SHA） 是1993年美國國家安全局（NSA）設(shè)計，由美國國家標(biāo)準(zhǔn)與技術(shù)研究院（NIST） 發(fā)布的密碼散列算法，1995年升級發(fā)布了SHA-1[1]版本。SHA-1可以從一個最大[264]位的原始信息中產(chǎn)生一串 160位的摘要。其安全性體現(xiàn)在單向性和抗碰撞性兩個方面[2]：單向性指的是的其散列函數(shù)[y=fSHA-1x]理論上不存在逆函數(shù)[f'SHA-1]使得[x=f'SHA-1y]；抗碰撞性指的是要找到兩個不同的[x1]和[x2]，使得[fSHA-1x1=fSHA-1x2]，在有限計算上也是不可行的。

SHA-1正是因為其安全性和高效性被全球各個領(lǐng)域普遍采用。但自1995年誕生至今SHA-1已有20個年頭的，面對當(dāng)今海量的數(shù)據(jù)信息（G級文件比比皆是，T級文件也不罕見），其計算效率已不再具有優(yōu)勢。該文基于大數(shù)據(jù)需求對SHA-1算法進行研究，通過改造散列計算步驟，提出分布式云計算模型，利用分布式云計算，最終減少算法的空間復(fù)雜度提高計算效率。

1 傳統(tǒng)的SHA-1算法介紹

1.1 常量定義[3]

[H]集：SHA-1算法需要5個字長為32位的初始散列集合[H=h0，h1，h2，h3，h4]。其中：[h0=0x67452301]，[h1=0xEFCDAB89]，[h2=0x98BADCFE]，[h3=0x10325476]，[h4=0xC3D2E1F0]。

[K]集：散列計算時需要4個字長為32位的常量集合[K=k0，k1，k2，k3]。其中：[k0=0x5A827999]，[k1=0x6ED9EBA1]，[k2=0x8F1BBCDC]，[k3=0xCA62C1D6]。

[ml]（Message Length）：原始代簽名數(shù)據(jù)長度。采用64位二進制數(shù)據(jù)表示原始消息的長度。

1.2 算法聲明

考慮到算法的一致性，SHA-1算法用到的所有變量均為32位無符號整數(shù)，所有的常量，無論大小，數(shù)據(jù)均采用大端字節(jié)序（Big Endian）存放，即位元組由大到小，高位優(yōu)先。

1.3 原始信息預(yù)處理

假設(shè)原始消息為[M0]，其長度為[l]。

首先在原始消息末尾增加1個位（Bit），并將其值置為1，由此得來的消息塊命名為[M1]，其長度為[l+1]；

然后在[M1]之后添加[k0≤k<512]個0，使得[l+1+k mod 512=448]，由此得來的消息塊命名為[M2]，當(dāng)然其長度為[l+1+k]；

最后在[M2]之后添加64位的常量[ml]，由此得來的消息塊命名為[M]，其長度為[L=l+1+k]+64。

比如原始消息[M0]為“abc”，采用ASCII進行編碼，其長度[l=8×3=24]；[k=423]。

1.4 信息分割

原始信息經(jīng)過預(yù)處理之后，還必須進行分割。SHA-1將填充之后的信息[M]分割成長度為512位的塊（Chunk），并記為集合[C=ci|0≤i≤L/512]。

1.5 哈希值計算[4]

SHA-1的核心部分即是哈希值的迭代計算過程，其算法可以用如下偽代碼表示：

//定義臨時變量[a，b，c，d，e，f，tmp]

//定義變量[sha1]

for each [ci0≤i≤L/512]

{分解[ci]成為16個32位的字[wj]，記為[W=wj|0≤j≤15]；

[擴展[W]集，使[W=wj|0≤j≤79]；

for [j] from 16 to 79

[wj=wj-3⊕wj-8⊕wj-14⊕wj-16 leftrotate 1]；

[a=h0]； [b=h1]； [c=h2]； [d=h3]； [e=h4]；

for [j] from 0 to 79

{if （[0≤j≤19]）

{[f=b?c?∽b?d]；

[temp=a leftrotate 5+f+e+k0+wj]；

}

else if （[20≤j≤39]）

{[f=b⊕c⊕d]；

[temp=a leftrotate 5+f+e+k1+wj]；

}

else if （4[0≤j≤59]）

{[f=b∧c∨b∧d∨c∧d]；

[temp=a leftrotate 5+f+e+k2+wj]；

}

else if （6[0≤j≤79]）

{[f=b⊕c⊕d]；

[temp=a leftrotate 5+f+e+k3+wj]；

}

[e=d]； [d=c]； [c=b leftrotate 30]； [b=a]； [a=temp]；

} 公式1]

[h0=h0+a]；endprint

[h1=h1+b]；

[h2=h2+c]；

[h3=h3+d]；

[h4=h4+e]；

}

[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate 64∨h3 leftrotate 32∨h4]；

2 分布式SHA-1算法改進

2.1 傳統(tǒng)SHA-1遇到的挑戰(zhàn)

SHA-1具有兩個重要的特性：單向性和抗碰撞性，并且以其高效性著稱。但自從1995年SHA-1誕生以來經(jīng)歷了近20個年頭，面對當(dāng)今海量的數(shù)據(jù)信息（G級文件比比皆是，T級文件也不罕見），其計算效率已不再具有優(yōu)勢。

分布式云計算的出現(xiàn)給這個挑戰(zhàn)帶來了機遇，該文基于大數(shù)據(jù)[5]對SHA-1算法進行研究，通過改造散列計算步驟，提出分布式云計算模型，最終減少算法的空間復(fù)雜度提高計算效率。

2.2 分布式SHA-1算法架構(gòu)

分布式云計算[6]采用C/S架構(gòu)，系統(tǒng)包含一個服務(wù)器端的應(yīng)用程序和一個客戶端的應(yīng)用程序。算法框架結(jié)構(gòu)如圖1所示。

圖1 分布式云計算框架結(jié)構(gòu)

服務(wù)器根據(jù)Chunk Table調(diào)度表指示的狀態(tài)給客戶端分發(fā)任務(wù)，客戶端從服務(wù)器接收到Chunk塊信息后進行單個Chunk Hash計算任務(wù)，計算完畢后把結(jié)果上傳給服務(wù)器。兩者之間采用TCP作為通信協(xié)議。

Chunk Table調(diào)度表是整個分布式云計算平臺的中心，如表1所示，其中的控制信息是各個客戶端（云端）協(xié)調(diào)一致工作的基礎(chǔ)。

表1 Chunk Table結(jié)構(gòu)

[字段名稱＼&類型＼&說明＼&ChunkNO＼&bigint＼&分段信息序號＼&a＼&int＼&分段哈希值：a段＼&b＼&int＼&分段哈希值：b段＼&c＼&int＼&分段哈希值：c段＼&d＼&int＼&分段哈希值：d段＼&e＼&int＼&分段哈希值：e段＼&FinishFlag＼&char＼&段處理標(biāo)志＼&]

2.3 服務(wù)器端算法

1） 通信請求處理線程

原始信息預(yù)處理（同1.3節(jié)）

信息分割（同1.4節(jié)）

switch（通信請求.類型）

{case 取任務(wù)：

for each [ChunkTable.recordi0≤i≤L/512]

{if（[ChunkTable.recordi.FinishFlag==‘閑]）

{[ChunkTable.recordi.FinishFlag=‘忙]；

讀取取數(shù)據(jù)文件[ChunkTable.recordi.ChunkNO×512， ChunkTable.recordi.ChunkNO×512+511]區(qū)間（位）數(shù)據(jù)，并回復(fù)客戶端；

}}

break；

case 存結(jié)果：

for each [ChunkTable.recordi0≤i≤L/512]

{if（[ChunkTable.recordi.ChunkNO==通信請求.ChunkNO]）

{[ChunkTable.recordi.FinishFlag=‘完]；

[ChunkTable.recordi.a=通信請求.a]；

[ChunkTable.recordi.b=通信請求.b]；

[ChunkTable.recordi.c=通信請求.c]；

[ChunkTable.recordi.d=通信請求.d]；

[ChunkTable.recordi.e=通信請求.e]；

}}

break；

}

2） 合并結(jié)果

for each [ChunkTable.recordi0≤i≤L/512]

{[h0=h0+ChunkTable.recordi.a]；

[h1=h1+ChunkTable.recordi.b]；

[h2=h2+ChunkTable.recordi.c]；

[h3=h3+ChunkTable.recordi.d]；

[h4=h4+ChunkTable.recordi.e]；

}

[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate 64∨h3 leftrotate 32∨h4]；

2.4 客戶端（云端）算法

從服務(wù)器獲取計算任務(wù)和512位數(shù)據(jù)塊[c]；

分解[c]成為16個32位的字[wj]，記為[W=wj|0≤j≤15]；

公式1向服務(wù)器匯報運算結(jié)果：[a，b，c，d，e]；

3 基于大數(shù)據(jù)的實驗及結(jié)果分析

為了驗證將分布式云計算引入SHA-1算法的有效性，特地在局域網(wǎng)中搭建了小型的云計算環(huán)境，1臺服務(wù)器+10臺客戶機（云端），計算大小為500M和6T的文本文件的SHA-1簽名值，實驗得出傳統(tǒng)算法和不同規(guī)模的分布計算耗時數(shù)據(jù)表：

表2

[算法＼&500M＼&6T＼&傳統(tǒng)SHA-1＼&805s＼&9720s＼&分布式SHA-1（5云端）＼&121s＼&1904s＼&分布式SHA-1（10云端）＼&63s＼&952s＼&]

從表中數(shù)據(jù)可以看出：傳統(tǒng)SHA-1算法，單機承擔(dān)了巨大的計算量，效率隨計算規(guī)模增加而降低；而本文提出的改進算法優(yōu)勢明顯，具有很高的實時性和技術(shù)可行性。

5 結(jié)論

本文將全面剖析SHA-1摘要算法，研討了大數(shù)據(jù)模式下將云計算引入到傳統(tǒng)的SHA-1中的具體實現(xiàn)細(xì)節(jié)，提出基于分布式云計算的改進算法，并且通過試驗證明該算法的實用性和高效性，取得了令人滿意的結(jié)果。

參考文獻：

[1] 張松敏，陶榮，于國華.安全散列算法SHA-1的研究[J].計算機安全，2010（10）.

[2] 孫楠楠，韓銀河，許都.一種基于循環(huán)展開結(jié)構(gòu)的SHA-1算法實現(xiàn)[J].信息技術(shù)，2007（3）：29.

[3] 朱雷鈞.哈希函數(shù)加密算法的高速實現(xiàn)[D].上海：上海交通大學(xué)，2007.

[4] 高銘達.基于SHA-1安全認(rèn)證的題庫管理系統(tǒng)[D].廈門：廈門大學(xué)，2009.

[5] 萬澤春.大數(shù)據(jù)的應(yīng)用與解決方案淺析[J].電腦知識與技術(shù)，2013（27）.

[6] 周祥峰.智能電網(wǎng)中虛擬化云計算安全的研究[J].計算機安全，2013（5）.

[h1=h1+b]；

[h2=h2+c]；

[h3=h3+d]；

[h4=h4+e]；

}

[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate 64∨h3 leftrotate 32∨h4]；

2 分布式SHA-1算法改進

2.1 傳統(tǒng)SHA-1遇到的挑戰(zhàn)

SHA-1具有兩個重要的特性：單向性和抗碰撞性，并且以其高效性著稱。但自從1995年SHA-1誕生以來經(jīng)歷了近20個年頭，面對當(dāng)今海量的數(shù)據(jù)信息（G級文件比比皆是，T級文件也不罕見），其計算效率已不再具有優(yōu)勢。

分布式云計算的出現(xiàn)給這個挑戰(zhàn)帶來了機遇，該文基于大數(shù)據(jù)[5]對SHA-1算法進行研究，通過改造散列計算步驟，提出分布式云計算模型，最終減少算法的空間復(fù)雜度提高計算效率。

2.2 分布式SHA-1算法架構(gòu)

分布式云計算[6]采用C/S架構(gòu)，系統(tǒng)包含一個服務(wù)器端的應(yīng)用程序和一個客戶端的應(yīng)用程序。算法框架結(jié)構(gòu)如圖1所示。

圖1 分布式云計算框架結(jié)構(gòu)

服務(wù)器根據(jù)Chunk Table調(diào)度表指示的狀態(tài)給客戶端分發(fā)任務(wù)，客戶端從服務(wù)器接收到Chunk塊信息后進行單個Chunk Hash計算任務(wù)，計算完畢后把結(jié)果上傳給服務(wù)器。兩者之間采用TCP作為通信協(xié)議。

Chunk Table調(diào)度表是整個分布式云計算平臺的中心，如表1所示，其中的控制信息是各個客戶端（云端）協(xié)調(diào)一致工作的基礎(chǔ)。

表1 Chunk Table結(jié)構(gòu)

[字段名稱＼&類型＼&說明＼&ChunkNO＼&bigint＼&分段信息序號＼&a＼&int＼&分段哈希值：a段＼&b＼&int＼&分段哈希值：b段＼&c＼&int＼&分段哈希值：c段＼&d＼&int＼&分段哈希值：d段＼&e＼&int＼&分段哈希值：e段＼&FinishFlag＼&char＼&段處理標(biāo)志＼&]

2.3 服務(wù)器端算法

1） 通信請求處理線程

原始信息預(yù)處理（同1.3節(jié)）

信息分割（同1.4節(jié)）

switch（通信請求.類型）

{case 取任務(wù)：

for each [ChunkTable.recordi0≤i≤L/512]

{if（[ChunkTable.recordi.FinishFlag==‘閑]）

{[ChunkTable.recordi.FinishFlag=‘忙]；

讀取取數(shù)據(jù)文件[ChunkTable.recordi.ChunkNO×512， ChunkTable.recordi.ChunkNO×512+511]區(qū)間（位）數(shù)據(jù)，并回復(fù)客戶端；

}}

break；

case 存結(jié)果：

for each [ChunkTable.recordi0≤i≤L/512]

{if（[ChunkTable.recordi.ChunkNO==通信請求.ChunkNO]）

{[ChunkTable.recordi.FinishFlag=‘完]；

[ChunkTable.recordi.a=通信請求.a]；

[ChunkTable.recordi.b=通信請求.b]；

[ChunkTable.recordi.c=通信請求.c]；

[ChunkTable.recordi.d=通信請求.d]；

[ChunkTable.recordi.e=通信請求.e]；

}}

break；

}

2） 合并結(jié)果

for each [ChunkTable.recordi0≤i≤L/512]

{[h0=h0+ChunkTable.recordi.a]；

[h1=h1+ChunkTable.recordi.b]；

[h2=h2+ChunkTable.recordi.c]；

[h3=h3+ChunkTable.recordi.d]；

[h4=h4+ChunkTable.recordi.e]；

}

[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate 64∨h3 leftrotate 32∨h4]；

2.4 客戶端（云端）算法

從服務(wù)器獲取計算任務(wù)和512位數(shù)據(jù)塊[c]；

分解[c]成為16個32位的字[wj]，記為[W=wj|0≤j≤15]；

公式1向服務(wù)器匯報運算結(jié)果：[a，b，c，d，e]；

3 基于大數(shù)據(jù)的實驗及結(jié)果分析

為了驗證將分布式云計算引入SHA-1算法的有效性，特地在局域網(wǎng)中搭建了小型的云計算環(huán)境，1臺服務(wù)器+10臺客戶機（云端），計算大小為500M和6T的文本文件的SHA-1簽名值，實驗得出傳統(tǒng)算法和不同規(guī)模的分布計算耗時數(shù)據(jù)表：

表2

[算法＼&500M＼&6T＼&傳統(tǒng)SHA-1＼&805s＼&9720s＼&分布式SHA-1（5云端）＼&121s＼&1904s＼&分布式SHA-1（10云端）＼&63s＼&952s＼&]

從表中數(shù)據(jù)可以看出：傳統(tǒng)SHA-1算法，單機承擔(dān)了巨大的計算量，效率隨計算規(guī)模增加而降低；而本文提出的改進算法優(yōu)勢明顯，具有很高的實時性和技術(shù)可行性。

5 結(jié)論

本文將全面剖析SHA-1摘要算法，研討了大數(shù)據(jù)模式下將云計算引入到傳統(tǒng)的SHA-1中的具體實現(xiàn)細(xì)節(jié)，提出基于分布式云計算的改進算法，并且通過試驗證明該算法的實用性和高效性，取得了令人滿意的結(jié)果。

參考文獻：

[1] 張松敏，陶榮，于國華.安全散列算法SHA-1的研究[J].計算機安全，2010（10）.

[2] 孫楠楠，韓銀河，許都.一種基于循環(huán)展開結(jié)構(gòu)的SHA-1算法實現(xiàn)[J].信息技術(shù)，2007（3）：29.

[3] 朱雷鈞.哈希函數(shù)加密算法的高速實現(xiàn)[D].上海：上海交通大學(xué)，2007.

[4] 高銘達.基于SHA-1安全認(rèn)證的題庫管理系統(tǒng)[D].廈門：廈門大學(xué)，2009.

[5] 萬澤春.大數(shù)據(jù)的應(yīng)用與解決方案淺析[J].電腦知識與技術(shù)，2013（27）.

[6] 周祥峰.智能電網(wǎng)中虛擬化云計算安全的研究[J].計算機安全，2013（5）.

[h1=h1+b]；

[h2=h2+c]；

[h3=h3+d]；

[h4=h4+e]；

}

[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate 64∨h3 leftrotate 32∨h4]；

2 分布式SHA-1算法改進

2.1 傳統(tǒng)SHA-1遇到的挑戰(zhàn)

SHA-1具有兩個重要的特性：單向性和抗碰撞性，并且以其高效性著稱。但自從1995年SHA-1誕生以來經(jīng)歷了近20個年頭，面對當(dāng)今海量的數(shù)據(jù)信息（G級文件比比皆是，T級文件也不罕見），其計算效率已不再具有優(yōu)勢。

分布式云計算的出現(xiàn)給這個挑戰(zhàn)帶來了機遇，該文基于大數(shù)據(jù)[5]對SHA-1算法進行研究，通過改造散列計算步驟，提出分布式云計算模型，最終減少算法的空間復(fù)雜度提高計算效率。

2.2 分布式SHA-1算法架構(gòu)

分布式云計算[6]采用C/S架構(gòu)，系統(tǒng)包含一個服務(wù)器端的應(yīng)用程序和一個客戶端的應(yīng)用程序。算法框架結(jié)構(gòu)如圖1所示。

圖1 分布式云計算框架結(jié)構(gòu)

服務(wù)器根據(jù)Chunk Table調(diào)度表指示的狀態(tài)給客戶端分發(fā)任務(wù)，客戶端從服務(wù)器接收到Chunk塊信息后進行單個Chunk Hash計算任務(wù)，計算完畢后把結(jié)果上傳給服務(wù)器。兩者之間采用TCP作為通信協(xié)議。

Chunk Table調(diào)度表是整個分布式云計算平臺的中心，如表1所示，其中的控制信息是各個客戶端（云端）協(xié)調(diào)一致工作的基礎(chǔ)。

表1 Chunk Table結(jié)構(gòu)

[字段名稱＼&類型＼&說明＼&ChunkNO＼&bigint＼&分段信息序號＼&a＼&int＼&分段哈希值：a段＼&b＼&int＼&分段哈希值：b段＼&c＼&int＼&分段哈希值：c段＼&d＼&int＼&分段哈希值：d段＼&e＼&int＼&分段哈希值：e段＼&FinishFlag＼&char＼&段處理標(biāo)志＼&]

2.3 服務(wù)器端算法

1） 通信請求處理線程

原始信息預(yù)處理（同1.3節(jié)）

信息分割（同1.4節(jié)）

switch（通信請求.類型）

{case 取任務(wù)：

for each [ChunkTable.recordi0≤i≤L/512]

{if（[ChunkTable.recordi.FinishFlag==‘閑]）

{[ChunkTable.recordi.FinishFlag=‘忙]；

讀取取數(shù)據(jù)文件[ChunkTable.recordi.ChunkNO×512， ChunkTable.recordi.ChunkNO×512+511]區(qū)間（位）數(shù)據(jù)，并回復(fù)客戶端；

}}

break；

case 存結(jié)果：

for each [ChunkTable.recordi0≤i≤L/512]

{if（[ChunkTable.recordi.ChunkNO==通信請求.ChunkNO]）

{[ChunkTable.recordi.FinishFlag=‘完]；

[ChunkTable.recordi.a=通信請求.a]；

[ChunkTable.recordi.b=通信請求.b]；

[ChunkTable.recordi.c=通信請求.c]；

[ChunkTable.recordi.d=通信請求.d]；

[ChunkTable.recordi.e=通信請求.e]；

}}

break；

}

2） 合并結(jié)果

for each [ChunkTable.recordi0≤i≤L/512]

{[h0=h0+ChunkTable.recordi.a]；

[h1=h1+ChunkTable.recordi.b]；

[h2=h2+ChunkTable.recordi.c]；

[h3=h3+ChunkTable.recordi.d]；

[h4=h4+ChunkTable.recordi.e]；

}

[sha1=h0 leftrotate 128∨h1 leftrotate 96∨h2 leftrotate 64∨h3 leftrotate 32∨h4]；

2.4 客戶端（云端）算法

從服務(wù)器獲取計算任務(wù)和512位數(shù)據(jù)塊[c]；

分解[c]成為16個32位的字[wj]，記為[W=wj|0≤j≤15]；

公式1向服務(wù)器匯報運算結(jié)果：[a，b，c，d，e]；

3 基于大數(shù)據(jù)的實驗及結(jié)果分析

為了驗證將分布式云計算引入SHA-1算法的有效性，特地在局域網(wǎng)中搭建了小型的云計算環(huán)境，1臺服務(wù)器+10臺客戶機（云端），計算大小為500M和6T的文本文件的SHA-1簽名值，實驗得出傳統(tǒng)算法和不同規(guī)模的分布計算耗時數(shù)據(jù)表：

表2

[算法＼&500M＼&6T＼&傳統(tǒng)SHA-1＼&805s＼&9720s＼&分布式SHA-1（5云端）＼&121s＼&1904s＼&分布式SHA-1（10云端）＼&63s＼&952s＼&]

從表中數(shù)據(jù)可以看出：傳統(tǒng)SHA-1算法，單機承擔(dān)了巨大的計算量，效率隨計算規(guī)模增加而降低；而本文提出的改進算法優(yōu)勢明顯，具有很高的實時性和技術(shù)可行性。

5 結(jié)論

本文將全面剖析SHA-1摘要算法，研討了大數(shù)據(jù)模式下將云計算引入到傳統(tǒng)的SHA-1中的具體實現(xiàn)細(xì)節(jié)，提出基于分布式云計算的改進算法，并且通過試驗證明該算法的實用性和高效性，取得了令人滿意的結(jié)果。

參考文獻：

[1] 張松敏，陶榮，于國華.安全散列算法SHA-1的研究[J].計算機安全，2010（10）.

[2] 孫楠楠，韓銀河，許都.一種基于循環(huán)展開結(jié)構(gòu)的SHA-1算法實現(xiàn)[J].信息技術(shù)，2007（3）：29.

[3] 朱雷鈞.哈希函數(shù)加密算法的高速實現(xiàn)[D].上海：上海交通大學(xué)，2007.

[4] 高銘達.基于SHA-1安全認(rèn)證的題庫管理系統(tǒng)[D].廈門：廈門大學(xué)，2009.

[5] 萬澤春.大數(shù)據(jù)的應(yīng)用與解決方案淺析[J].電腦知識與技術(shù)，2013（27）.

[6] 周祥峰.智能電網(wǎng)中虛擬化云計算安全的研究[J].計算機安全，2013（5）.