基于糾錯碼的數據分片傳輸方案

劉 冰 馬 壯 陳宜棟

(北京電子科技學院密碼科學與技術系 北京 100070)

0 引 言

林海峰等[2]提出了一種無線傳感器網絡的數據包編碼加密的算法，分別利用非線性隨機異或操作的網絡編碼方式對無線傳感器網絡中傳遞的數據包進行加密，明顯降低無線傳感器網絡的能量消耗，提高無線網絡的生命周期。魏煜等[3]為了減少數據傳輸量并更為精確地由源端傳感器向匯聚節點傳輸數據，抑制丟包對數據精簡的影響，提出LRPH算法來抑制丟包帶來的影響，并且及時監測傳感器是否故障，同時提出LRSH算法來優化LRPH，減少冗余信息。

Wei等[4]提出了一種在分級無線網絡中(與分簇結構無實質性的區別)使用可更新哈希鏈的高效安全數據匯聚方案。該方案基于端到端的加密機制，包括可更新哈希鏈的生成方法和數據認證方法。通過可更新的哈希鏈生成并用于數據驗證和密鑰更新；在數據認證方面，分別對簇內、簇間、簇頭與基站之間進行認證。采用實際設置的無線傳感器網絡進行實驗，得出結果后分析其在數據機密性、完整性、可認證性上較其他方案的優勢。

由于以切片的方式進行數據傳輸增加了數據包的數量和沖突的概率，使得切片在傳輸過程中，尤其是在無線傳感器網絡、物聯網等無中心且信道質量較差的網絡中，發生丟失、損壞的概率增大，從而使得合法用戶(基站)無法正常接收、恢復出完整數據，進而影響數據傳輸的效果。同樣，在通信過程中，當部分信息位出現問題時，糾錯碼通過其自身的糾錯能力便可將錯誤碼糾正過來，實現信息的完整通信。在實現部分數據恢復完整數據方面已有不少相關成熟的技術，如秘密共享[5]等。在保證數據傳輸隱私性的基礎上，本文利用糾錯碼技術解決網絡中數據傳輸過程中出現部分數據丟失、損壞造成傳輸匯聚效率較低的問題。同時，針對不同的應用場景采取不同的譯碼方式：當因碰撞導致丟包或有附加認證手段時，此時能夠判斷單切片正確與否，可使用接收的正確切片恢復出完整數據；當由于傳輸錯誤或主動攻擊造成無法判斷數據包的正確性時，可直接調用譯碼函數恢復出完整數據。

1 基礎介紹

1.1 RS碼

Reed-Solomon 碼(RS碼)是BCH 碼(循環糾錯碼)的一個重要子類，是一種極大最小距離可分碼(MDS 碼)，具有較強的糾錯能力，特別是在較短和中等碼長下，其性能幾乎接近于理論值，同時其構造簡便，編譯碼容易，且具有相當嚴格的代數結構，故而RS碼在編碼理論方面起著巨大作用[6]。

RS碼的定義為：設q≥3，碼長為q-1，設計距離為δ的q元BCH碼，稱為q元Reed-Solomon碼。當q=2m(m>1)，其碼元符號取自于有限域GF(2m)的RS碼最常用。RS碼的重要性質為：真正的最小距離與設計距離總是相等的[7]。

設計一個能糾t個符號錯誤的RS碼需要的參數如表1所示。

表1 RS碼構建所需參數表

對于糾t個錯誤符號的RS碼生成多項式為：

(1)

式中：a是GF(2m)上的本原元。顯而易見,g(x)的根為a,a2,a3,…，a2t。由g(x)生成的(n,n-2t)循環碼，它由所有能被g(x)除盡、系數是GF(2m)上的元素且次數不大于n-1的多項式組成。RS碼編碼方式與一般循環碼編碼方式完全相同。用信息碼多項式m(x)=mk-1xk-1+mk-2xk-2+mk-3xk-3+…+m0上升xn-k位后加上監督多項式r(x)就是RS碼,監督多項式r(x)是由信息碼多項式上升xn-k位后除以生成多項式g(x)得到的。故若設輸入信息碼為m(x)，編碼后的碼組為c(x)，則有：

c(x)=xn-km(x)+xn-km(x) modg(x)

(2)

1.2 哈希鏈

哈希鏈(又稱為散列鏈)的思想最初由美國數學家Lamport提出[8]，用于一次性口令機制。哈希鏈是指密碼學中重復使用同一哈希函數對該函數生成的哈希值作哈希運算，最終會產生出一系列的哈希值。在網絡安全方面，可以將單個密鑰或密碼通過哈希鏈生成多個不同的一次性密鑰或密碼。用公式表示為：

hn=hn-1(hn-2(hn-3…(h(x))))

(3)

哈希鏈應用廣泛，尤其是在密碼保護和數據認證方面頗受青睞。從理論上講，一個提供身份驗證的存儲器在密碼存儲傳輸方面，改直接存儲純文本密碼為存儲哈希字符串更能防止密碼在存儲傳輸過程中被攻破。然而，具有有限長度的哈希鏈大大限制哈希鏈各方面的應用，于是有研究者采取了一些方法來解決這一問題，如重新初始化哈希鏈、無限哈希鏈等，但這些方法是低效且不平滑的。故Zhang等[9]提出一種自更新哈希鏈(SUHC)機制。這是一種全新的哈希鏈，它自身能進行重新初始化和更新，其更新過程是平滑的、安全的、高效的，且不需要任何外加的協議或獨立的重新初始化過程。該機制可以無限期地產生無限長度的哈希鏈。哈希鏈的生成如圖1所示。

圖1 哈希鏈生成圖

采用自更新哈希鏈(SUHC)機制生成密鑰的具體過程：1) 節點隨機選擇鏈的秘密種子，其值為s，然后通過迭代地應用散列函數h導出所有的哈希值，其鏈尾值為hi(s)，同時隨機選擇另一秘密種子s′，構造另一哈希鏈，其鏈尾值為hi(s′)，安全存儲在節點中；2) 分別用hi(s),hi-1(s),hi-2(s),…,h(s)作為加解密的密鑰；3) 當以秘密種子s為初始值生成的哈希鏈消耗完時，節點自動用hi(s′)替換hi(s)，用s′替換s″，同時產生下一條哈希鏈包括s″和hi(s″)。這樣執行下去就可以實現哈希鏈的無限使用。

2 基于糾錯碼技術的數據切片

2.1 基本思想

本文針對網絡數據傳輸過程中的部分數據丟失、損壞的情況或存在主動攻擊者進行數據篡改時，采用糾錯碼技術來實現數據穩定性傳輸。在數據傳輸過程中，主要采用二次切分重組技術與RS碼編譯碼技術的有機結合，同時采用雙重加密方式。雙重加密是使用可更新哈希鏈生成的密鑰通過簡單的置換加密來打亂切片原有的順序，進而實現第一層加密操作；接著使用輕量級的加密算法對整個切片(包括編號和切片數據)進行第二層加密操作。通過二次切分重組技術和以可更新哈希鏈為主的雙重加密來實現數據的隱私保護，增加數據的安全性；利用RS碼編譯碼技術對數據進行編譯可以提升整個網絡的魯棒性，增強了數據的可靠性，擴大了合法用戶恢復數據的能力。

2.2 算法步驟

算法示意圖如圖2所示。

圖2 算法示意圖

2.2.1數據拆分

將普通節點采集的信息數據按k×q×m塊排列，其中：k為后續采用RS碼信息位長度；q代表切片長度(q是變量，根據應用需要確定)；m為RS碼元的二進制長度。將數據排布成k×q的矩陣形式，矩陣元素為GF(2m)上的元素。

2.2.2RS編碼

對q行采用RS碼進行編碼，得到(n,k)RS碼。即每塊數據拆分塊的信息碼長為n，實際信息段為k，則監督位為r=n-k。由于RS碼為MDS碼，其最小碼距為dmin=n-k+1。由于每個原始數據大小的不同，故每個原始數據被拆分后的拆分塊大小也不同，也就是說，n、k、r的值均為變量。針對不同大小的拆分塊，將采用不同的RS碼進行針對性的編碼。經過本輪操作后，原矩陣變為n×q的規模。

2.2.3分塊切片

在編碼操作的基礎上，對矩陣進行縱向切片，并對每一切片標注相應的序號(H1,H2,…,Hn)。編號的長度為log2n，為方便起見，將其取為m，相當于給數據矩陣增加一行序號行。編號的目的是為了在數據恢復階段，更準確地保證數據拆分塊按順序重組，從而保證譯碼率及數據傳輸的安全性。因為只有當匯聚節點按順序對切片數據進行排列后才能進一步譯碼恢復完整數據，即便有任何的順序差錯也無法恢復完整數據。

2.2.4加 密

本文對切片數據的加密分層次進行：通過對切片的順序打亂來實現，使用哈希鏈生成的每一哈希值(隨機序列)作為置換密鑰來實現每組切片數據編號的置換加密。

具體操作為：1) 普通節點和匯聚節點通過秘密種子s，應用自更新哈希鏈方式分別生成加密密鑰h(s),h2(s),…,hi(s)。2) 進行加密，即直接依次使用每個哈希值hi(s),hi-1(s),…,h(s)分別對每組切片數據編號(H1,H2,…,Hn)進行置換，打亂每組完整切片數據的正確順序。當i=n時，普通節點和匯聚節點再次通過隨機選擇另一秘密種子s′，構造另一哈希鏈，如此往復。3) 以切片為單位，采用輕量級的加密算法對每個切片數據進行加密。

2.2.5數據恢復

當匯聚節點接收到來自普通節點的加密數據后，操作如下。(1) 利用輕量級的解密算法對每個切片數據進行解密。(2) 將解密的切片數據的編號進行置換解密，使其恢復出正確的順序，并按其編號進行重新組合并橫向排布。(3) 進行譯碼操作，恢復出原始數據的拆分塊{N11,N12,…,N1q}，根據應用需求采用不同的譯碼方法：當因沖突造成丟包或附加認證技術能夠確認接收包正確性時，可通過k個正確片一一對應恢復出完整數據；如果存在主動攻擊無法判斷單片正確性的情況，可直接調用譯碼函數恢復出完整數據。(4) 對所有拆分塊進行數據匯聚，并將匯聚結果傳輸至基站。

3 算法分析與實現

3.1 安全性

安全性是無線網絡安全數據匯聚算法首要考慮的性能，主要從抗被動攻擊和抗主動攻擊兩個方面來說明。

3.1.1抗被動攻擊

當無線傳輸信道上只有監聽者，而沒有篡改者時，稱為被動攻擊。防御被動攻擊的主要手段為加密。針對數據傳輸過程中的泄露問題，本文方案存在兩個層次的加密處理：一是以切片為單位進行的對稱加密，利用輕量級對稱加密算法進行加解密；二是采取了基于哈希鏈方式生成密鑰，并使用生成的哈希值作為密鑰對切片編號進行置換加密運算，進而對編號重新排序，打亂正常順序。采用自更新哈希鏈方式生成的密鑰進行數據加密；采用每個哈希值作為一個數據的密鑰，實現了一次一密，安全性更有保障；采用哈希鏈的哈希值逆用，利用哈希函數的單向性保證安全性，即使攻擊者獲得了前一個哈希值也無法推出后一個哈希值密鑰[10]。

另外，本文采取的二次切片重組方式更加有利于數據安全性的保護。首先橫向拆分，即使部分拆分塊被破解也無法恢復出完整數據；其次在進行RS碼編碼后，對拆分塊再次縱向切片，再次增加數據恢復的難度，提升其隱私保護性能?？傊@種橫向拆分與縱向切片的交叉切片組合對數據傳輸匯聚過程中的隱私保護起到了很大的作用。

3.1.2抗主動攻擊

當無線傳輸信道上的攻擊者不僅可以監聽信道，而且可以進行篡改等主動操作時，稱為主動攻擊。傳統針對主動攻擊的手段包括認證等[11]。而本文方案中未采取認證手段，即使當傳輸過程中，存在攻擊者的故意攻擊，對切片數據進行篡改時，(n,k)RS碼能在誤比特數e≤[(n-k+1)/2]時恢復出完整數據，從而能夠在一定程度上抵抗主動攻擊。

3.2 魯棒性

切片技術的采用造成網絡中數據包的數量增大，從而使數據沖突和傳輸錯誤的概率都增大。魯棒性是指當數據切片在傳輸過程中有部分丟失或出現錯誤，對完整數據的最終恢復無任何影響。RS碼不僅可以實現部分數據丟失的糾錯，還可以實現大段數據丟失糾錯，其糾錯能力幾乎是所有糾錯碼中最強的一種。因此本文采用RS碼對數據進行編碼來實現數據傳輸匯聚過程中的冗余，提升整個過程的魯棒性。

本文將在兩種不同的情況下對魯棒性能進行分析。

1) 無線通信信道為理想信道且無故意攻擊，僅僅是數據切片由于沖突或通過通信協議能夠發現錯誤從而丟失部分數據包。根據MDS碼的最優特性，當(n,k)RS碼獲得的至少k個正確切片數據，即當錯誤切片在e1≤n-k時，就能恢復出正確的完整數據；當(n,k)RS碼獲得少于k個正確切片數據，即當錯誤切片在e1>n-k時，能恢復出正確的完整數據概率為1/2k-(n-e1)。

2) 在傳輸過程中存在未發現的傳輸錯誤或3.1節所說的攻擊者的故意攻擊，當錯誤切片在e2≤[(n-k+1)/2]時也能恢復出完整數據。

3.3 魯棒性與傳輸效率的關系

采用RS碼進行編碼時，需要進行相應的數據擴展，即將數據切片從k×q×m變為n×(q+1)×m，此時的效率為kq/n(q+1)，當q比較大時基本等同于RS碼的傳輸效率，與利用秘密共享等手段來實現數據安全匯聚相比具有較大優勢。

魯棒性可表示為:

L1=e1/ne1=n-k

(4)

L2=e2/ne2=[(n-k+1)/2]

(5)

傳輸效率可表示為:

T=k/n

(6)

因此，由式(4)-式(6)可得魯棒性與傳輸效率間的關系式為：

L1=1-T0

(7)

L2=(1-T)/2 0

(8)

3.4 算法實現

針對僅僅是數據切片由于沖突或通過通信協議能夠發現錯誤從而丟失部分數據包的情況，隨機取幾組數據對算法進行驗證并說明算法的正確性，結果見表2。

表2 魯棒性隨機驗證表(情況一)

針對在傳輸過程中存在未發現的傳輸錯誤或攻擊者的故意攻擊的情況，隨機取幾組數據對算法進行驗證并說明算法的正確性，結果見表3。

表3 魯棒性隨機驗證表(情況二)

續表3

根據表2和表3，可以清晰地得到兩種不同情況下數據的驗證結果，由此可以證明所提算法是正確的。根據以上30組驗證數據，可以形成圖3中的兩條正確數據恢復的上界，經過與由式(7)、式(8)生成的魯棒性能與傳輸效率關系圖相對比，發現基本吻合，從而進一步說明了本文算法的正確性。

圖3 魯棒性與傳輸效率關系圖

由圖3可以很清晰地得到，本文算法的魯棒性與傳輸效率成線性反比例關系。當傳輸效率越大時，魯棒性相應降低；反之，當傳輸效率越小時，魯棒性相應上升。還可知當傳輸錯誤的切片e1≤n-k時，魯棒性與傳輸效率之間的反比關系較大；當傳輸錯誤的切片e2≤[(n-k+1)/2]時，魯棒性與傳輸效率之間的反比關系較小。

將表2、表3的驗證數據在圖3中體現。由表2可知當傳輸錯誤的切片e1≤n-k時，在圖3所示斜線“正確恢復上限(一)”下方的切片數據是完全可以正確恢復出完整數據的；在其上方的切片數據部分無法恢復出完整數據，而部分是可以恢復出完整數據的。因為當接收的正確切片數據不足k片但很接近時，可以對丟失切片的值進行推測來完成整個數據的恢復。例如，當(n=30,k=12,e1=19)時，此時接收的正確切片為11(30-19=11)，而實際需要接收k=12個正確切片才可恢復出完整數據，那么就可以以1/2k-(n-e1)的概率推測出所缺切片的正確值，進而完成整個數據的恢復。由表3可知，當傳輸錯誤的切片e2≤[(n-k+1)/2]時，在圖3中斜線“正確恢復上限(二)”下方的切片數據是完全可以正確恢復出完整數據的，而在其上方的切片數據則無法恢復出完整數據。

4 結 語

考慮到數據在傳輸過程中的安全性和容錯性問題，本文提出一種基于糾錯碼的數據隱私傳輸方案。通過二次切片重組技術、雙重加密方式較為高效地提升了數據的安全性和魯棒性，實現數據安全傳輸的同時又保證了數據恢復的能力；本文也對傳輸效率和魯棒性之間的關系進行了研究，兩者存在著一定取舍關系，需根據應用需求確定相關參數。最后，通過對算法進行的實現與分析，驗證本文方案的正確性和有效性。接下來會對算法與數據匯聚相結合方面進行深入研究。