基于MD5加密的Tornado碼復(fù)制算法改進(jìn)*

駱正平， 陳中育， 林郁峰， 吳星同

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

基于MD5加密的Tornado碼復(fù)制算法改進(jìn)*

駱正平， 陳中育， 林郁峰， 吳星同

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院，浙江金華 321004)

基于Tornado碼的復(fù)制算法具有編解碼速度比較快、部分?jǐn)?shù)據(jù)丟失時(shí)亦能被恢復(fù)的優(yōu)點(diǎn)，但將該算法應(yīng)用于分布式存儲(chǔ)系統(tǒng)時(shí)，存在數(shù)據(jù)易被竊取、篡改的風(fēng)險(xiǎn).為此，對(duì)基于Tornado碼的復(fù)制算法提出了改進(jìn): 1)引入加密機(jī)制，使數(shù)據(jù)即使被竊取時(shí)也不用擔(dān)心泄密;2)對(duì)原始數(shù)據(jù)使用MD5算法產(chǎn)生數(shù)字指紋，當(dāng)從分布式存儲(chǔ)系統(tǒng)取回?cái)?shù)據(jù)時(shí)，計(jì)算數(shù)字指紋并與本地的數(shù)字指紋對(duì)比，就可以判斷數(shù)據(jù)是否被篡改.

糾刪碼;Tornado碼;分布式存儲(chǔ);數(shù)字指紋;消息摘要算法

0 引言

當(dāng)前，信息技術(shù)快速發(fā)展，已經(jīng)從以計(jì)算設(shè)備為核心的時(shí)代進(jìn)入到以存儲(chǔ)設(shè)備為核心的時(shí)代，數(shù)據(jù)海量化成為一種趨勢(shì).分布式存儲(chǔ)以其廉價(jià)和高擴(kuò)展性等特點(diǎn)適用于數(shù)據(jù)的海量存儲(chǔ)，得到越來(lái)越廣泛的應(yīng)用［1］.但由于分布式存儲(chǔ)使用戶(hù)數(shù)據(jù)的所有權(quán)和控制權(quán)分離，用戶(hù)數(shù)據(jù)就會(huì)面臨安全威脅.信息的冗余是信息安全的保障，現(xiàn)階段主要采用復(fù)制技術(shù)、糾刪碼技術(shù)等數(shù)據(jù)冗余手段來(lái)提高數(shù)據(jù)的安全性、可靠性［2］.

復(fù)制技術(shù)是提高分布式存儲(chǔ)系統(tǒng)數(shù)據(jù)可用性的有效方法，傳統(tǒng)復(fù)制算法可以直接復(fù)制存儲(chǔ)節(jié)約計(jì)算時(shí)間.但隨著系統(tǒng)規(guī)模的增加，為保持系統(tǒng)的可用性和持久性，副本數(shù)目也會(huì)急劇增加.大量的副本嚴(yán)重消耗了網(wǎng)絡(luò)資源和存儲(chǔ)資源，也危害了數(shù)據(jù)的安全性.相比復(fù)制技術(shù)，基于Tornado碼的存儲(chǔ)冗余算法用較少的增量數(shù)據(jù)實(shí)現(xiàn)數(shù)據(jù)冗余，可以有效減少網(wǎng)絡(luò)的通信壓力和存儲(chǔ)空間，同時(shí)提高數(shù)據(jù)的可用性、安全性.Tornado編碼是基于稀疏矩陣的糾刪碼，它在不規(guī)則的級(jí)聯(lián)二分圖上構(gòu)造碼字，且編碼和解碼的算法中只有異或操作，因此編碼解碼的時(shí)間復(fù)雜度為(ε為編碼過(guò)程中的無(wú)效率)［3］.它同樣擁有其他糾刪碼的優(yōu)點(diǎn)，在缺失較多數(shù)據(jù)節(jié)點(diǎn)時(shí)，能夠精確地恢復(fù)原始數(shù)據(jù)［2］.但使用Tornado碼編碼的數(shù)據(jù)還存在著數(shù)據(jù)保密性差的問(wèn)題，在分布式存儲(chǔ)中面臨著被篡改、竊取的風(fēng)險(xiǎn).

本文針對(duì)分布式存儲(chǔ)系統(tǒng)中使用Tornado碼編碼的數(shù)據(jù)存在的這些問(wèn)題，提出了在使用Tornado碼編碼的過(guò)程中引入加密環(huán)節(jié)和數(shù)字指紋技術(shù)，這些技術(shù)可以有效保障分布式存儲(chǔ)中用戶(hù)數(shù)據(jù)的安全.

1 糾刪碼及其糾刪原理

糾刪碼一般應(yīng)用在通信系統(tǒng)中，一個(gè)(n，k)糾刪碼是把k個(gè)原數(shù)據(jù)編碼為n(n＞k)個(gè)數(shù)據(jù)，使得用這n個(gè)數(shù)據(jù)中任意k個(gè)編碼數(shù)據(jù)均可重構(gòu)出原來(lái)的k個(gè)原數(shù)據(jù)［4－5］，如圖1所示.線(xiàn)性糾刪碼(n，k)可以表示成y=xGk×n.其中:x=(x1，x2，…，xk)是原數(shù)據(jù)向量;y=(y1，y2，…，yn)是編碼后的數(shù)據(jù)向量;Gk×n為k×n階矩陣.稱(chēng)Gk×n為此線(xiàn)性糾刪碼的生成矩陣.若Gk×n的任意k列組成的子矩陣G'k×k均可逆，則有如下定理:

定理1［4－5］設(shè)G為(n，k)線(xiàn)性糾刪碼的生成矩陣.若G的任意k列組成的子矩陣G'均可逆，則利用接收到的任意k個(gè)數(shù)據(jù)均可重構(gòu)原來(lái)的k個(gè)原數(shù)據(jù).

證明 證明見(jiàn)文獻(xiàn)［6］.

圖1 編譯碼過(guò)程［6］

2 基于Tornado碼的復(fù)制算法

基于Tornado碼的復(fù)制算法可以分為以下幾步:

步驟1 數(shù)據(jù)分塊:將數(shù)據(jù)S分成m個(gè)大小為b的數(shù)據(jù)塊，即S={s1，s2，…，sm}.

步驟2 數(shù)據(jù)編碼:對(duì)上一步產(chǎn)生的m個(gè)數(shù)據(jù)塊進(jìn)行Tornado編碼，得到n個(gè)數(shù)據(jù)塊，將這n個(gè)數(shù)據(jù)塊分別存儲(chǔ)在Internet的不同結(jié)點(diǎn)上.

步驟3 數(shù)據(jù)解碼:選取任意的k個(gè)結(jié)點(diǎn)，從中可以獲取k個(gè)數(shù)據(jù)塊，對(duì)所有取得的數(shù)據(jù)塊進(jìn)行解碼還原為m個(gè)數(shù)據(jù)塊.

步驟4 數(shù)據(jù)恢復(fù):對(duì)得到的m個(gè)數(shù)據(jù)塊合并為原數(shù)據(jù)S.

該算法的核心步驟是數(shù)據(jù)編碼和數(shù)據(jù)解碼.

二分圖B顯示了信息塊和校驗(yàn)塊之間的對(duì)應(yīng)關(guān)系，每個(gè)校驗(yàn)塊都可以由幾個(gè)信息塊進(jìn)行異或運(yùn)算得出(如圖2(a)所示).由圖2可知，對(duì)數(shù)據(jù)塊s1，s2，…，sm進(jìn)行編碼可以得到m個(gè)信息塊和βm個(gè)校驗(yàn)塊.如果有一個(gè)信息塊或者校驗(yàn)塊丟失，就可以通過(guò)計(jì)算其他的信息塊和校驗(yàn)塊之間的異或后得到丟失的數(shù)據(jù)(如圖2(b)所示).但是，某些校驗(yàn)塊的丟失可能會(huì)造成部分?jǐn)?shù)據(jù)的缺失.為此，可以利用級(jí)聯(lián)二分圖加強(qiáng)信息的冗余，保證部分?jǐn)?shù)據(jù)的丟失不會(huì)影響到最后還原的數(shù)據(jù).級(jí)聯(lián)二分圖(如圖3所示)由k+2個(gè)二分圖構(gòu)成，分別為B0，B1，B2，…，Bk，Bk+1.Bk和Bk+1的左邊結(jié)點(diǎn)相同.二分圖B0使m個(gè)信息塊產(chǎn)生βm (β＜1)個(gè)校驗(yàn)塊，這βm個(gè)校驗(yàn)塊成為下一個(gè)二分圖B1的信息塊，二分圖B1做相同的操作，又產(chǎn)生β2m個(gè)校驗(yàn)塊，依此類(lèi)推，二分圖Bk可以由βkm個(gè)信息塊產(chǎn)生βk+1m個(gè)校驗(yàn)塊;二分圖Bk+1與二分圖Bk產(chǎn)生同樣多的校驗(yàn)塊.因此，利用編碼C(B0，B1，…，Bk，Bk+1)產(chǎn)生的校驗(yàn)塊的數(shù)目為［7］:

圖2 二分圖B［7］

圖3 級(jí)聯(lián)二分圖［7］

解碼由二分圖Bk和Bk+1開(kāi)始，根據(jù)二分圖Bk和Bk+1的校驗(yàn)塊求出信息塊，該信息塊即為Bk－1的校驗(yàn)塊，使用同樣的方法依次往前求出Bk－2，…，B1，B0的信息塊.如果事先已知Bi(0≤i≤k)的校驗(yàn)塊，也可以從Bi開(kāi)始進(jìn)行解碼.

基于B0，B1，…，Bk，Bk+1的編碼和解碼的計(jì)算開(kāi)銷(xiāo)與二分圖中的邊數(shù)成正比，基于Tornado碼的復(fù)制算法的編碼和解碼的計(jì)算復(fù)雜度均為O(mb)［7］.

3 基于Tornado碼的EMDC算法

在分布式存儲(chǔ)系統(tǒng)中應(yīng)用基于Tornado碼的復(fù)制算法雖然提高了數(shù)據(jù)的可用性，但數(shù)據(jù)還存在著安全風(fēng)險(xiǎn).為了增強(qiáng)數(shù)據(jù)在分布式存儲(chǔ)中的安全性，可以將數(shù)據(jù)加密技術(shù)和數(shù)字指紋技術(shù)引入復(fù)制算法.

3.1 加密

一個(gè)加密系統(tǒng)W可以用數(shù)學(xué)符號(hào)描述為W={P，C，K，E，D}.其中:P為明文空間，表示全體可能出現(xiàn)的明文集合;C為密文空間，表示全體可能出現(xiàn)的密文空間;K為密鑰空間，密鑰是加密算法的可變參數(shù);E為加密算法，由一些公式、法則或程序構(gòu)成;D為解密算法，是加密算法E的逆運(yùn)算.

加密操作:C=E(P，KE)表示將明文P和加密密鑰KE作為參數(shù)，通過(guò)加密算法把明文變?yōu)槊芪?

解密操作:P=D(C，KD)表示將密文C和解密密鑰KD作為參數(shù)，通過(guò)解密算法把密文變?yōu)槊魑?

可以看出，解密操作是加密操作的逆運(yùn)算.

3.2 MD5

MD5的全稱(chēng)是Message Digest Algorithm 5(信息摘要算法)，用于保證信息的完整性和一致性.如果輸入一段任意長(zhǎng)度的數(shù)據(jù)，MD5算法都將輸出一個(gè)長(zhǎng)度為128位的二進(jìn)制數(shù).MD5以512位分組來(lái)處理輸入的信息，且每一分組又被劃分為16個(gè)32位子分組，經(jīng)過(guò)了一系列的處理后，算法的輸出由4個(gè)32位分組組成，將這4個(gè)32位分組級(jí)聯(lián)后將生成一個(gè)128位散列值［8］.通過(guò)MD5算法處理的信息都會(huì)有一個(gè)獨(dú)一無(wú)二的數(shù)字指紋與信息對(duì)應(yīng).一旦信息發(fā)生細(xì)微的改動(dòng)，對(duì)應(yīng)于信息的數(shù)字指紋就會(huì)發(fā)生顯著的變化.因此，MD5算法常被用來(lái)驗(yàn)證數(shù)據(jù)的完整性、一致性.

攻擊MD5算法常見(jiàn)的方法有窮舉法和生日攻擊法.窮舉法是通過(guò)窮舉所有的可能輸入，使用相同的MD5算法以期望得到一個(gè)相同的數(shù)字指紋，即使H(m')=H(m)(H為hash函數(shù)).但運(yùn)算時(shí)間較長(zhǎng)，即使使用一臺(tái)每秒運(yùn)算達(dá)10億次的計(jì)算機(jī)也要花費(fèi)1.07×1022a，因此是不可行的［8］.生日攻擊［9］起源于生日悖論，即隨著元素的增多，出現(xiàn)重復(fù)數(shù)據(jù)的概率會(huì)迅速增長(zhǎng).生日攻擊嘗試找到一對(duì)不同的輸入，使其經(jīng)過(guò)MD5算法后產(chǎn)生相同的輸出，再通過(guò)比較輸入和輸出來(lái)破解MD5算法.給定n個(gè)輸入和k個(gè)可能的輸出，這樣共有C(n，2)個(gè)輸入對(duì).一對(duì)不同輸入產(chǎn)生相同輸出的概率為1/k.若輸入對(duì)數(shù)目不少于k/2，則得到一對(duì)匹配對(duì)的概率就會(huì)大于1/2.這樣，在時(shí)將會(huì)以較大的概率得到輸入匹配對(duì).對(duì)MD5使用生日攻擊法需要嘗試264次，即使用每秒運(yùn)算達(dá)10億次的計(jì)算機(jī)也得花費(fèi)58 a［8］.因此，生日攻擊法也是不可行的.綜上所述，MD5算法十分安全.

3.3 算法改進(jìn)

本文對(duì)基于Tornado碼的復(fù)制算法進(jìn)行了改進(jìn)，提出了EMDC(Encryption and MD5 Copy Algorithm)算法，該算法主要包括以下步驟:

步驟1 數(shù)據(jù)分割:將數(shù)據(jù)D分割為m個(gè)大小為b的數(shù)據(jù)塊，即D=［d1，d2，…，dm］.

步驟2 數(shù)字指紋:計(jì)算m個(gè)數(shù)據(jù)塊的數(shù)字指紋并存于本地.

步驟3 加密:對(duì)m個(gè)數(shù)據(jù)塊進(jìn)行加密，產(chǎn)生m個(gè)加密數(shù)據(jù)塊.

步驟4 編碼:對(duì)m個(gè)加密數(shù)據(jù)塊進(jìn)行編碼，產(chǎn)生p個(gè)校驗(yàn)塊.

步驟5 冗余:把p個(gè)校驗(yàn)塊復(fù)制成kp個(gè)校驗(yàn)塊.

步驟6 存儲(chǔ):將m個(gè)加密數(shù)據(jù)塊和kp個(gè)校驗(yàn)塊分散存儲(chǔ)在Internet的多個(gè)結(jié)點(diǎn)上，如圖4所示.

圖4 數(shù)據(jù)加密、編碼

數(shù)據(jù)恢復(fù)算法為該算法的逆過(guò)程，具體步驟為:

步驟1 解碼:從當(dāng)前可用的結(jié)點(diǎn)上獲取r個(gè)數(shù)據(jù)塊，對(duì)它們進(jìn)行解碼，得到原來(lái)的m個(gè)加密數(shù)據(jù)塊.

步驟2 解密:對(duì)m個(gè)加密數(shù)據(jù)塊進(jìn)行解密，得到原m個(gè)未加密的數(shù)據(jù).

步驟3 驗(yàn)證:將解密出的數(shù)據(jù)計(jì)算數(shù)字指紋，與存于本地的數(shù)字指紋進(jìn)行對(duì)比，若數(shù)字指紋相同，則數(shù)據(jù)沒(méi)有被篡改.

步驟4 恢復(fù)數(shù)據(jù):由解密得到的m個(gè)數(shù)據(jù)塊恢復(fù)數(shù)據(jù)D.如圖5所示.

圖5 數(shù)據(jù)解碼、解密

4 算法分析

基于Tornado碼的復(fù)制算法對(duì)分割后的數(shù)據(jù)塊進(jìn)行編碼，使數(shù)據(jù)塊之間存在一定的數(shù)據(jù)冗余.與傳統(tǒng)復(fù)制算法相比，基于Tornado碼的復(fù)制算法能夠提供更高的可用性、持久性和安全性，有效降低系統(tǒng)的開(kāi)銷(xiāo).基于Tornado碼的EMDC算法先對(duì)數(shù)據(jù)進(jìn)行加密操作和生成數(shù)字指紋，再使用Tornado碼處理數(shù)據(jù)，對(duì)用戶(hù)數(shù)據(jù)提供存儲(chǔ)安全的同時(shí)，保護(hù)了用戶(hù)的隱私不會(huì)被泄露.3種算法對(duì)比如表1所示.

表1 算法比較

5 應(yīng)用實(shí)例

手機(jī)通信錄中包含用戶(hù)姓名、電話(huà)號(hào)碼、家庭地址、電子郵箱、生日及與用戶(hù)有關(guān)的社會(huì)關(guān)系等用戶(hù)隱私信息.由于諸多原因，存于手機(jī)中的通信錄面臨著丟失的風(fēng)險(xiǎn).因此，需要將通信錄備份到云存儲(chǔ)［10］中.如果直接將通信錄上傳到云存儲(chǔ)中，不僅使通信錄面臨著被篡改、竊取的風(fēng)險(xiǎn)，而且用戶(hù)的隱私信息也可能被泄露.為了保護(hù)云存儲(chǔ)中用戶(hù)通信錄的安全，可以應(yīng)用本文提出的算法對(duì)用戶(hù)通信錄進(jìn)行操作，再將處理完的數(shù)據(jù)上傳到云端.

存于云存儲(chǔ)中的手機(jī)通信錄信息如果有部分丟失，也可以通過(guò)Tornado算法恢復(fù)，并且存儲(chǔ)于云端的數(shù)據(jù)是經(jīng)過(guò)加密的，這樣就不用擔(dān)心用戶(hù)隱私信息的泄露.并且只要將取回的數(shù)據(jù)使用MD5算法計(jì)算數(shù)字指紋，并與本地存儲(chǔ)的數(shù)字指紋進(jìn)行對(duì)比，就能知道數(shù)據(jù)是否被篡改.因此，經(jīng)過(guò)本文算法處理后的數(shù)據(jù)有很好的安全性和魯棒性.手機(jī)通信錄處理過(guò)程如圖6所示.

6 結(jié)語(yǔ)

與傳統(tǒng)的復(fù)制算法相比，基于Tornado碼的復(fù)制算法能夠提供更高的可用性、持久性和安全性，有效降低系統(tǒng)開(kāi)銷(xiāo).Tornado碼采用級(jí)聯(lián)二分圖對(duì)分割后的數(shù)據(jù)塊進(jìn)行編碼，雖然可以較快地編碼，但經(jīng)過(guò)編碼后的數(shù)據(jù)存儲(chǔ)到網(wǎng)絡(luò)時(shí)，還是面臨著數(shù)據(jù)被竊取、篡改的危險(xiǎn).提出了基于Tornado碼的EMDC算法，有效解決了在網(wǎng)絡(luò)存儲(chǔ)中數(shù)據(jù)的安全性和魯棒性問(wèn)題，并且應(yīng)用本算法在云端存儲(chǔ)手機(jī)通信錄時(shí)也取得了很好的效果.

圖6 EMDC算法在云存儲(chǔ)中的應(yīng)用

［1］趙浩天.基于網(wǎng)絡(luò)編碼的分布式存儲(chǔ)容錯(cuò)及擴(kuò)容問(wèn)題研究［D］.合肥:中國(guó)科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，2013.

［2］孫偉平，湯毅凡.基于Tornado碼的存儲(chǔ)冗余算法研究［J］.微處理機(jī)，2008(2):71－74.

［3］Druschel P，Rowstron A.PAST:A Large－scale，persistent peer－to－peer storage utility［C］//Proceedings of the 8th Workshop on Hot Topics in Operating Systems.Scloss Elmau:Jason Flinn，2001.

［4］Rizzo L.Effective erasure codes for reliable computer communication protocols［J］.ACM SIGCOMM Computer Communication Review，1997，27(2):24－36.

［5］Rizzo L.On the feasibility of software FEC［EB/OL］.(1997－01－31)［2014－05－18］.http://www.iet.unipi.it/luigi/softfcc.ps.

［6］慕建君，路成業(yè)，王新梅.關(guān)于糾刪碼的研究與進(jìn)展［J］.電子與信息學(xué)報(bào)，2002，24(9):1276－1281.

［7］王意潔，盧錫城.基于Tornado碼的復(fù)制算法［J］.國(guó)防科技大學(xué)學(xué)報(bào)，2004，26(3):39－42.

［8］張裔智，趙毅，湯小斌.MD5算法研究［J］.計(jì)算機(jī)科學(xué)，2008，35(7):295－297.

［9］楊波.現(xiàn)代密碼學(xué)［M］.北京:清華大學(xué)出版社，2003:146－147.

［10］Wikipedia.Cloud storage［EB/OL］.(2012－05－10)［2014－05－18］.http://en.wikipedia.org/wiki/Cloud_storage.

(責(zé)任編輯 陶立方)

An improved algorithm based on MD5 encryption Tornado code

LUO Zhengping， CHEN Zhongyu， LIN Yufeng， WU Xingtong

(College of Mathematics Physics and Information Engineering，Zhejiang Normal University，Jinhua Zhejiang 321004，China)

Tornado code based replication algorithm had the advantages of faster encoding and decoding，and could also recover the original data when some data were missing，but when the algorithm was applied to a distributed storage system，the presence of data would be susceptible to theft，tampering risk.For this reason，several optimization strategies were proposed to improve the replication algorithm based on Tornado code:1) an encryption mechanism into replication algorithm was introduced in case of even some data were stolen there would be no worry about information leak.2)the raw data using the MD5 algorithm to generate digital fingerprints produced a digital fingerprint when retrieving data from a distributed storage system with local digital fingerprint comparison，it would be easy to determine whether the data had been tampered with.

erasure code;Tornado code;distributed storage;digital fingerprint;MD5

TP309.2

A

1001－5051(2015)01－0078－05

?:2014－04－19;

2014－09－02

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272007);浙江省自然科學(xué)基金資助項(xiàng)目(LY12F02009)

駱正平(1986－)，男，浙江義烏人，碩士研究生.研究方向:云存儲(chǔ)安全.

陳中育.E－mail:czy@zjnu.cn

10.16218/j.issn.1001－5051.2015.01.013