基于纠错码的数据分片传输方案

刘 冰 马 壮 陈宜栋

(北京电子科技学院密码科学与技术系 北京 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 结 语

考虑到数据在传输过程中的安全性和容错性问题，本文提出一种基于纠错码的数据隐私传输方案。通过二次切片重组技术、双重加密方式较为高效地提升了数据的安全性和鲁棒性，实现数据安全传输的同时又保证了数据恢复的能力；本文也对传输效率和鲁棒性之间的关系进行了研究，两者存在着一定取舍关系，需根据应用需求确定相关参数。最后，通过对算法进行的实现与分析，验证本文方案的正确性和有效性。接下来会对算法与数据汇聚相结合方面进行深入研究。