骆正平， 陈中育， 林郁峰， 吴星同

(浙江师范大学数理与信息工程学院，浙江金华 321004)

基于MD5加密的Tornado码复制算法改进*

骆正平， 陈中育， 林郁峰， 吴星同

(浙江师范大学数理与信息工程学院，浙江金华 321004)

基于Tornado码的复制算法具有编解码速度比较快、部分数据丢失时亦能被恢复的优点，但将该算法应用于分布式存储系统时，存在数据易被窃取、篡改的风险.为此，对基于Tornado码的复制算法提出了改进: 1)引入加密机制，使数据即使被窃取时也不用担心泄密;2)对原始数据使用MD5算法产生数字指纹，当从分布式存储系统取回数据时，计算数字指纹并与本地的数字指纹对比，就可以判断数据是否被篡改.

纠删码;Tornado码;分布式存储;数字指纹;消息摘要算法

0 引言

当前，信息技术快速发展，已经从以计算设备为核心的时代进入到以存储设备为核心的时代，数据海量化成为一种趋势.分布式存储以其廉价和高扩展性等特点适用于数据的海量存储，得到越来越广泛的应用［1］.但由于分布式存储使用户数据的所有权和控制权分离，用户数据就会面临安全威胁.信息的冗余是信息安全的保障，现阶段主要采用复制技术、纠删码技术等数据冗余手段来提高数据的安全性、可靠性［2］.

复制技术是提高分布式存储系统数据可用性的有效方法，传统复制算法可以直接复制存储节约计算时间.但随着系统规模的增加，为保持系统的可用性和持久性，副本数目也会急剧增加.大量的副本严重消耗了网络资源和存储资源，也危害了数据的安全性.相比复制技术，基于Tornado码的存储冗余算法用较少的增量数据实现数据冗余，可以有效减少网络的通信压力和存储空间，同时提高数据的可用性、安全性.Tornado编码是基于稀疏矩阵的纠删码，它在不规则的级联二分图上构造码字，且编码和解码的算法中只有异或操作，因此编码解码的时间复杂度为(ε为编码过程中的无效率)［3］.它同样拥有其他纠删码的优点，在缺失较多数据节点时，能够精确地恢复原始数据［2］.但使用Tornado码编码的数据还存在着数据保密性差的问题，在分布式存储中面临着被篡改、窃取的风险.

本文针对分布式存储系统中使用Tornado码编码的数据存在的这些问题，提出了在使用Tornado码编码的过程中引入加密环节和数字指纹技术，这些技术可以有效保障分布式存储中用户数据的安全.

1 纠删码及其纠删原理

纠删码一般应用在通信系统中，一个(n，k)纠删码是把k个原数据编码为n(n＞k)个数据，使得用这n个数据中任意k个编码数据均可重构出原来的k个原数据［4－5］，如图1所示.线性纠删码(n，k)可以表示成y=xGk×n.其中:x=(x1，x2，…，xk)是原数据向量;y=(y1，y2，…，yn)是编码后的数据向量;Gk×n为k×n阶矩阵.称Gk×n为此线性纠删码的生成矩阵.若Gk×n的任意k列组成的子矩阵G'k×k均可逆，则有如下定理:

定理1［4－5］设G为(n，k)线性纠删码的生成矩阵.若G的任意k列组成的子矩阵G'均可逆，则利用接收到的任意k个数据均可重构原来的k个原数据.

证明 证明见文献［6］.

图1 编译码过程［6］

2 基于Tornado码的复制算法

基于Tornado码的复制算法可以分为以下几步:

步骤1 数据分块:将数据S分成m个大小为b的数据块，即S={s1，s2，…，sm}.

步骤2 数据编码:对上一步产生的m个数据块进行Tornado编码，得到n个数据块，将这n个数据块分别存储在Internet的不同结点上.

步骤3 数据解码:选取任意的k个结点，从中可以获取k个数据块，对所有取得的数据块进行解码还原为m个数据块.

步骤4 数据恢复:对得到的m个数据块合并为原数据S.

该算法的核心步骤是数据编码和数据解码.

二分图B显示了信息块和校验块之间的对应关系，每个校验块都可以由几个信息块进行异或运算得出(如图2(a)所示).由图2可知，对数据块s1，s2，…，sm进行编码可以得到m个信息块和βm个校验块.如果有一个信息块或者校验块丢失，就可以通过计算其他的信息块和校验块之间的异或后得到丢失的数据(如图2(b)所示).但是，某些校验块的丢失可能会造成部分数据的缺失.为此，可以利用级联二分图加强信息的冗余，保证部分数据的丢失不会影响到最后还原的数据.级联二分图(如图3所示)由k+2个二分图构成，分别为B0，B1，B2，…，Bk，Bk+1.Bk和Bk+1的左边结点相同.二分图B0使m个信息块产生βm (β＜1)个校验块，这βm个校验块成为下一个二分图B1的信息块，二分图B1做相同的操作，又产生β2m个校验块，依此类推，二分图Bk可以由βkm个信息块产生βk+1m个校验块;二分图Bk+1与二分图Bk产生同样多的校验块.因此，利用编码C(B0，B1，…，Bk，Bk+1)产生的校验块的数目为［7］:

图2 二分图B［7］

图3 级联二分图［7］

解码由二分图Bk和Bk+1开始，根据二分图Bk和Bk+1的校验块求出信息块，该信息块即为Bk－1的校验块，使用同样的方法依次往前求出Bk－2，…，B1，B0的信息块.如果事先已知Bi(0≤i≤k)的校验块，也可以从Bi开始进行解码.

基于B0，B1，…，Bk，Bk+1的编码和解码的计算开销与二分图中的边数成正比，基于Tornado码的复制算法的编码和解码的计算复杂度均为O(mb)［7］.

3 基于Tornado码的EMDC算法

在分布式存储系统中应用基于Tornado码的复制算法虽然提高了数据的可用性，但数据还存在着安全风险.为了增强数据在分布式存储中的安全性，可以将数据加密技术和数字指纹技术引入复制算法.

3.1 加密

一个加密系统W可以用数学符号描述为W={P，C，K，E，D}.其中:P为明文空间，表示全体可能出现的明文集合;C为密文空间，表示全体可能出现的密文空间;K为密钥空间，密钥是加密算法的可变参数;E为加密算法，由一些公式、法则或程序构成;D为解密算法，是加密算法E的逆运算.

加密操作:C=E(P，KE)表示将明文P和加密密钥KE作为参数，通过加密算法把明文变为密文.

解密操作:P=D(C，KD)表示将密文C和解密密钥KD作为参数，通过解密算法把密文变为明文.

可以看出，解密操作是加密操作的逆运算.

3.2 MD5

MD5的全称是Message Digest Algorithm 5(信息摘要算法)，用于保证信息的完整性和一致性.如果输入一段任意长度的数据，MD5算法都将输出一个长度为128位的二进制数.MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由4个32位分组组成，将这4个32位分组级联后将生成一个128位散列值［8］.通过MD5算法处理的信息都会有一个独一无二的数字指纹与信息对应.一旦信息发生细微的改动，对应于信息的数字指纹就会发生显著的变化.因此，MD5算法常被用来验证数据的完整性、一致性.

攻击MD5算法常见的方法有穷举法和生日攻击法.穷举法是通过穷举所有的可能输入，使用相同的MD5算法以期望得到一个相同的数字指纹，即使H(m')=H(m)(H为hash函数).但运算时间较长，即使使用一台每秒运算达10亿次的计算机也要花费1.07×1022a，因此是不可行的［8］.生日攻击［9］起源于生日悖论，即随着元素的增多，出现重复数据的概率会迅速增长.生日攻击尝试找到一对不同的输入，使其经过MD5算法后产生相同的输出，再通过比较输入和输出来破解MD5算法.给定n个输入和k个可能的输出，这样共有C(n，2)个输入对.一对不同输入产生相同输出的概率为1/k.若输入对数目不少于k/2，则得到一对匹配对的概率就会大于1/2.这样，在时将会以较大的概率得到输入匹配对.对MD5使用生日攻击法需要尝试264次，即使用每秒运算达10亿次的计算机也得花费58 a［8］.因此，生日攻击法也是不可行的.综上所述，MD5算法十分安全.

3.3 算法改进

本文对基于Tornado码的复制算法进行了改进，提出了EMDC(Encryption and MD5 Copy Algorithm)算法，该算法主要包括以下步骤:

步骤1 数据分割:将数据D分割为m个大小为b的数据块，即D=［d1，d2，…，dm］.

步骤2 数字指纹:计算m个数据块的数字指纹并存于本地.

步骤3 加密:对m个数据块进行加密，产生m个加密数据块.

步骤4 编码:对m个加密数据块进行编码，产生p个校验块.

步骤5 冗余:把p个校验块复制成kp个校验块.

步骤6 存储:将m个加密数据块和kp个校验块分散存储在Internet的多个结点上，如图4所示.

图4 数据加密、编码

数据恢复算法为该算法的逆过程，具体步骤为:

步骤1 解码:从当前可用的结点上获取r个数据块，对它们进行解码，得到原来的m个加密数据块.

步骤2 解密:对m个加密数据块进行解密，得到原m个未加密的数据.

步骤3 验证:将解密出的数据计算数字指纹，与存于本地的数字指纹进行对比，若数字指纹相同，则数据没有被篡改.

步骤4 恢复数据:由解密得到的m个数据块恢复数据D.如图5所示.

图5 数据解码、解密

4 算法分析

基于Tornado码的复制算法对分割后的数据块进行编码，使数据块之间存在一定的数据冗余.与传统复制算法相比，基于Tornado码的复制算法能够提供更高的可用性、持久性和安全性，有效降低系统的开销.基于Tornado码的EMDC算法先对数据进行加密操作和生成数字指纹，再使用Tornado码处理数据，对用户数据提供存储安全的同时，保护了用户的隐私不会被泄露.3种算法对比如表1所示.

表1 算法比较

5 应用实例

手机通信录中包含用户姓名、电话号码、家庭地址、电子邮箱、生日及与用户有关的社会关系等用户隐私信息.由于诸多原因，存于手机中的通信录面临着丢失的风险.因此，需要将通信录备份到云存储［10］中.如果直接将通信录上传到云存储中，不仅使通信录面临着被篡改、窃取的风险，而且用户的隐私信息也可能被泄露.为了保护云存储中用户通信录的安全，可以应用本文提出的算法对用户通信录进行操作，再将处理完的数据上传到云端.

存于云存储中的手机通信录信息如果有部分丢失，也可以通过Tornado算法恢复，并且存储于云端的数据是经过加密的，这样就不用担心用户隐私信息的泄露.并且只要将取回的数据使用MD5算法计算数字指纹，并与本地存储的数字指纹进行对比，就能知道数据是否被篡改.因此，经过本文算法处理后的数据有很好的安全性和鲁棒性.手机通信录处理过程如图6所示.

6 结语

与传统的复制算法相比，基于Tornado码的复制算法能够提供更高的可用性、持久性和安全性，有效降低系统开销.Tornado码采用级联二分图对分割后的数据块进行编码，虽然可以较快地编码，但经过编码后的数据存储到网络时，还是面临着数据被窃取、篡改的危险.提出了基于Tornado码的EMDC算法，有效解决了在网络存储中数据的安全性和鲁棒性问题，并且应用本算法在云端存储手机通信录时也取得了很好的效果.

图6 EMDC算法在云存储中的应用

［1］赵浩天.基于网络编码的分布式存储容错及扩容问题研究［D］.合肥:中国科学技术大学计算机科学与技术学院，2013.

［2］孙伟平，汤毅凡.基于Tornado码的存储冗余算法研究［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］慕建君，路成业，王新梅.关于纠删码的研究与进展［J］.电子与信息学报，2002，24(9):1276－1281.

［7］王意洁，卢锡城.基于Tornado码的复制算法［J］.国防科技大学学报，2004，26(3):39－42.

［8］张裔智，赵毅，汤小斌.MD5算法研究［J］.计算机科学，2008，35(7):295－297.

［9］杨波.现代密码学［M］.北京:清华大学出版社，2003:146－147.

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

(责任编辑 陶立方)

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

国家自然科学基金资助项目(61272007);浙江省自然科学基金资助项目(LY12F02009)

骆正平(1986－)，男，浙江义乌人，硕士研究生.研究方向:云存储安全.

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

10.16218/j.issn.1001－5051.2015.01.013