（计算机应用技术专业论文）基于erasure+code的p2p存储系统安全方案.pdf

摘要 摘要 近年来，p 2 p 技术随互联网技术的发展而兴起，成为网络技术研究的热点。 而基于p 2 p 网络构建的存储系统，相比传统存储系统具有如下优势：不依赖中 心节点、高容错、高扩展、高效率、低成本，因而被认为是极富前景的p 2 p 应 用技术。在p 2 p 存储系统中主要面对的是两个基本和关键的问题：存储数据可 用性和存储数据安全性，这两个问题直接制约了p 2 p 存储技术的发展，因此成 为p 2 p 网络技术研究的重点。 目前p 2 p 存储系统的数据可用性问题主要利用数据冗余方案来解决，而目 前所使用的冗余方案主要包括副本和e r a s u r ec o d e 两类。比较而言，e r a s u r ec o d e 的方式更适合p 2 p 存储系统。文中将基于e r a s u r ec o d e 研究p 2 p 存储系统的数 据安全性问题。在研究目前已有的基于e r a s u r ec o d e 的r s 码安全加密方案s e c 后，提出了多项式时间内利用部分已知明文破解s e c 方案的方法，论证得出s e c 方案是不安全的。针对这一问题，文中提出了一种新的基于e r a s u r ec o d e 的r s 码安全加密方案e r s ，该方案通过文件分块算法使得原文件数据分块具备安 全性，其与秘密柯西矩阵加密的r s 码结合更整体提升了e r s 的安全性能。安 全分析显示e r s 能抵抗穷举和已知明文攻击。文中基于c 语言实现了r s 码和 e r s 方案的基本程序，运行结果表明，e r s 相比r s 码并没有增加过多的运算负 担，但却提高了安全性能，因此完全可以替代r s 码，从而应用于p 2 p 存储系统。 关键词：p 2 p 存储系统；e r a s u r ec o d e ；r s 码；安全方案 a b s t r a c t a b s t r a c t i i lr e c e n ty e a r s ，p 2 pt e c h n o l o g ys p r i n g su pw i t ht h ed e v e l o p m e n to fi n t e m e ta n d b e c o m e so n eo ft h eh o t t e s tr e s e a r c h s y s t e m s ，t h es t o r a g es y s t e m sb a s e do n i s s u e s c o m p a r e dt ot h et r a d i t i o n a ls t o r a g e p 2 pn e t w o r kh a v et h ef o l l o w i n ga d v a n t a g e s ： d e c e n t r a l i z e d ，f a u l t - t o l e r a n t ，s c a l a b l e ，e f f i c i e n ta n dl o w - c o s t t h e r e f o r e ，p 2 ps t o r a g e s y s t e mi sc o n s i d e r e da so n eo ft h em o s tp r o m i s i n ga p p l i c a t i o n so fp 2 pt e c h n o l o g y p 2 ps t o r a g es y s t e mh a st od e a lw i t ht w ob a s i cb u tk e yi s s u e s ：d a t aa v a i l a b i l i t ya n d d a t as e c u r i t y , w h i c hc o n s t r a i nt h ed e v e l o p m e n to fp 2 p s t o r a g et e c h n o l o g y t h e r e f o r e ， t h e s et w oi s s u e sb e c o m et h er e s e a r c hf o c u s e so ft h ep 2 pt e c h n o l o g y t od e a lw i t ht h ei s s u eo fd a t aa v a i l a b i f i t y , c u r r e n tp 2 ps t o r a g es y s t e m sm a i n l y r e l yo nt h ed a t ar e d u n d a n c ys c h e m e ，w h i c hc a nb ec l a s s i f i e di n t ot w ot y p e s ：t h e d u p l i c a t i o ns c h e m ea n dt h ee r a s u r ec o d i n gs c h e m e b yc o m p a r i s o n ，e r a s u r ec o d i n g s c h e m ei sm o r es u i t a b l ef o rp 2 ps t o r a g es y s t e m s t h i sp a p e rd i s c u s s e st h ed a t a s e c u r i t yi s s u ei np 2 ps t o r a g es y s t e ma n di tf o c u s e so nt h ee r a s u r ec o d i n gs c h e m et o r e a l i z et h ed a t as e c u r i t y b ya n a l y z i n gt h es e c u r i t ye n c r y p t i o nr sc o d es c h e m eb a s e d o nr se r a s u r ec o d e s e c ，w ef i n dak n o w n p l a i n t e x ta t t a c km e t h o dw h i c hc a ng e t t h ep l a i n t e x ti np o l y n o m i a lt i m e ，a n dp r o v et h a ts e cs c h e m ei su n s a f e t od e a lw i t h t h i sp r o b l e m ，t h i sp a p e rp r o p o s e san e we r a s u r ec o d i n ge n c r y p t i o ns c h e m eb a s e do n r sc o d e e r s b yt h ef i l ef r a g m e n t i n ga l g o r i t h m ，t h es c h e m ee n s u r e st h es e c u r i t yo f t h eo r i g i n a lf i l ed a t af r a g m e n t s f u r t h e r m o r e ，t h ec o m b i n a t i o no ft h ea l g o r i t h ma n d t h es e c r e tc a u c h ym a t r i xo fr sc o d ea r ea b l et oi m p r o v et h eo v e r a l ls e c u r i t y p e r f o r m a n c eo fe r s t h ea n a l y s i ss h o w st h a te r s c a nr e s i s tk n o w n p l a i n t e x ta t t a c k a n de x h a u s t i v ea t t a c k b yu s i n gt h ecl a n g u a g e ，t h i sp a p e rr e a l i z e st h er ss c h e m e a n dt h ee r ss c h e m e t h es i m u l a t i o nr e s u l t ss h o wt h a tc o m p a r e dt ot h er ss c h e m e ， e r ss c h e m ei m p r o v e st h es e c u r i t yp e r f o r m a n c ew i t h o u ti n c r e a s i n gt h ec o m p u t a t i o n a l b u r d e n t h e r e f o r e ，e r ss c h e m ei sm o r ee f f e c t i v ea n di sm o r es u i t a b l ef o rp 2 ps t o r a g e s y s t e m s k e yw o r d s ：p 2 ps t o r a g es y s t e m ；e r a s u r ec o d e ；r sc o d e ；s e c u r i t ys c h e m e ； i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：商葆竿 二矽口7 年6 月弓日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：薛葆华 2 0 0 7 年占月3 e t f 南开大学学位论文电子版授权使用协议 论文基于e r a s u r ec o d e 的p 2 p 存储系统安全方案系本人在南开大学工作和 学习期间创作完成的作品，并已通过论文答辩。 本人系本作品的唯一作者( 第一作者) ，即著作权人。现本人同意将本作品收 录于“南开大学博硕士学位论文全文数据库”。本人承诺：已提交的学位论文电子 版与印刷版论文的内容一致，如因不同而引起学术声誉上的损失由本人自负。 本人完全了解南开大学图书馆关于保存、使用学位论文的管理办法。同意 南开大学图书馆在下述范围内免费使用本人作品的电子版： 本作品呈交当年，在校园网上提供论文目录检索、文摘浏览以及论文全文部分 浏览服务( 论文前1 6 页) 。公开级学位论文全文电子版于提交1 年后，在校园网上 允许读者浏览并下载全文。 注：本协议书对于“非公开学位论文在保密期限过后同样适用。 日月 ： 年 t 、 称： 名名 所签：系者号期院作学日 第一章引言 第一章引言 第一节研究背景 i n t e r n e t 发展近3 0 年来，已经渗透到社会生活的各个领域，给人类生活带来 了极大的变化。而近年来，p e e r - t o p e e r ( 亦称对等网络，简称p 2 p ) 技术迅速发 展，它打破了传统的客户服务器( c l i e n t s e r v e r ) 模式，网络中的每个结点的地位 都是对等的，每个结点既充当服务器，为其它结点提供服务，同时也享用其它 结点提供的服务，在即时通讯、文件共享及流媒体传输等应用领域均显示出了 极大的优势，成为构建新型大规模互联网应用的主要结构和技术之一。 自“9 1 1 事件之后，数据存储日益受到重视，金融、保险、电信等多个 对数据敏感的行业相继开始建立和完善数据灾难恢复机制，数据的可用性、可 生存性、完整性和安全性也已成为人们关注的焦点。基于p 2 p 技术的迅速发展， 人们希望有安全可靠的p 2 p 数据存储系统的出现，它能够将信息分散在整个p 2 p 网络的多个存储节点上，使得合法用户能在持续有效且高度可靠的方式下访问 信息，即使系统在节点失效，网络断开，或受到恶意攻击的情况下，依然能有 效地提供数据存储服务。由于巨大的技术挑战，基于p 2 p 的存储应用并没有获 得相应的商业成功，然而p 2 p 存储系统却一直被p 2 p 技术领域研究者认为是极 富前景的一种应用，并一直是学术界研究的热点。 1 1 1p 2 p 存储系统简介 p 2 p 存储系统，是指应用于p 2 p 网络上的信息数据存储服务系统，系统中的 节点以功能对等的方式组成开放式存储网络，与传统的客户n 务器的集中控制 模式相对应。p 2 p 存储系统的节点即可以是服务器节点，也可以是用户桌面机等 各种节点，所以p 2 p 存储系统可用来组织专业的大型存储服务，亦可用来组织 闲散的用户计算机资源形成互助存储网络。下面将给出几个知名的p 2 p 存储系 统实例的简单介绍。 ( 1 ) o c e a n s t o r e 的全球数据存储 o c e a n s t o r e 1 】是加州大学伯克利分校在2 0 0 0 年提出的一个遍布全球的数据 存储网络，是第一个基于p 2 p 架构存储系统的构想，对于文件查找、数据分块、 第一章引言 数据一致性都给出了相应的解决方案。 o c e a n s t o r e 底层采用b e r k e l e y 提出的t a p e s t r y f 3 6 1 路由算法，通过对i d 的后 缀路由提供o ( 1 0 9 n ) 的消息路由效率。在冗余策略上，o c e a n s t o r e 同时使用e r a s u r e c o d e ( 也称纠删码) 和副本冗余的方式。使用e r a s u r ec o d e 存储归档的数据可 以降低存储空间和带宽消耗，使用完整副本则用来提高数据访问的效率。由于 o c e a n s t o r e 系统主要部署在稳定节点集合上，节点的暂时性错误不是非常严重的 问题，故o c e a n s t o r e 对于数据可用性的讨论不多，只有对数据可靠性的讨论。 ( 2 ) m i t 的c f s ( c o o p e r a t i v ef i l es y s t e m ) c f s c 2 1 是一个只读的文件系统，底层采用c h o r d 【3 刀算法，利用副本方式冗余， 直接d h t 方式分发冗余数据，通过底层的覆盖网络来检测邻居节点的失效，数 据修复上采用积极修复的策略。c f s 认为在p 2 p 网络中存储空间不是稀缺资源， 因此没有采用e r a s u r ec o d e 技术，但e r a s u r ec o d e 技术却是节约系统维护带宽的 重要手段。 ( 3 ) 微软研究院的b i t v a u l t b i t v a u l t 3 】也是一个面向网络较少更新的存储系统，主要由较为稳定的机房 内部存储节点构成。b i t v a u l t 底层使用微软亚洲研究院提出的x r i n g 3 8 】覆盖网络， 在高动态性的环境下，其路由表的大小保证o ( 1 0 9 n ) 的路由效率；在动态性小的 环境中，x r i n g 不断扩充节点路由表，最终达到o ( 1 ) 的路由效率。在数据冗余 策略方面，b i t v a u l t 系统也只采用了副本方式。 ( 4 ) u c s d 的t o t a lr e c a l l 对等存储系统t o t a lr e c a l l 4 j 的设计目标是自动配置系统所需要的各种参数， 包括冗余策略、冗余度和修复时间等，以避免繁琐且困难的人工设置。t o t a lr e c a l l 底层采用c h o r d 3 7 】路由算法。冗余策略上，t o t a lr e c a l l 针对不同类型数据分别使 用副本或e r a s u r ec o d e 方式或混合的方式。在数据修复策略上，系统对小文件采 用积极修复策略，对大文件采用消极修复策略。 1 1 2p 2 p 存储系统的优势和面临的问题 p 2 p 存储系统对比传统的存储系统有如下优点： ( 1 ) 不依赖中央控制，网络中的资源和服务分散在所有结点上，信息的传输 和服务的实现都直接在结点之间进行，从而可以充分利用网络中的带宽资源， 避免了可能的瓶颈。 2 第一章引言 ( 2 ) 各个节点功能对等，使得整个系统在缺失部分节点后仍能正常工作，即 有高容错性；每个节点的加入都能使得系统整体的资源和服务能力在同步地扩 充，即有高扩展性。这两个特点使得利用廉价机群搭建大规模高性能存储服务 成为可能。 ( 3 ) 个人计算机能力的不断增长，使得采用p 2 p 架构可以更加有效地利用互 联网中的大量普通结点，将存储任务分布到所有结点上，利用其闲置存储空间， 达到海量存储的目的。而网络中大量空闲资源的充分利用，同时带来的是更低 的成本提供更高的存储能力。 ( 4 ) p 2 p 网络中，信息的传输分散在各节点之间进行，无需经过某个集中环 节，用户的隐私信息被窃听和泄漏的可能性大大缩小，匿名通讯的实现变得更 加灵活和可靠，能够为用户提供更好的隐私保护。 在p 2 p 存储系统研究中面临的两个基础和关键的问题是存储数据的可用性 和安全性研究，详细分析如下： ( 1 ) 存储数据可用性：可用性对于任何一个存储系统来说都是最为重要的系 统属性，如果存储在系统中的数据不能保证很高概率的可被访问，则存储系统 本身是没有意义的。p 2 p 存储系统中的每个节点均负责存储数据，而其运行环境 中任何节点都可能随时会暂时或永久的离开系统，存在其上的数据就将暂时不 可访问甚至造成存储数据的丢失。而经典的存储系统一般仅考虑永久错误的情 况，即节点永久离开网络的情况。这些特点都使得存储数据可用性研究面临新 的问题和挑战，需要研究更新的适用于高动态系统的方案。事实上，目前还没 有大规模真正实用的p 2 p 存储系统，这在很大程度上是由数据可用性问题所制 约的。 ( 2 ) 存储数据安全性：假如p 2 p 存储系统可以保证高可用的数据存储，用户 也会对p 2 p 存储系统的数据安全性产生怀疑。这是因为，组成p 2 p 存储网络的 节点都是来自不同域的节点，它们的安全性没有任何机构来保障。当用户使用 经典的分组加密方案( 如a e s 1 1 1 等) 加密数据，发现其隐私受到威胁时( 如加 密算法弱点被公布) ，其存储在网络中别的节点中加密后的敏感数据就可能被破 解，从而对用户的数据安全造成极大的威胁。 3 第一章引言 第二节p 2 p 存储数据研究现状 p 2 p 存储系统中数据操作的基本对象是数据文件，其存储数据的可用性和安 全性研究也是基于数据文件来进行研究的。p 2 p 存储系统数据的可用性研究主要 集中于数据文件冗余策略的应用上，而存储数据的安全性研究则集中于数据的 加密和恢复策略的研究。现在将就这两个方面展开讨论。 1 2 1p 2 p 存储系统中存储数据可用性 在第一节的p 2 p 存储系统实例中可以看到，目前的p 2 p 存储系统主要采用 的冗余策略有两种基本方式：副本冗余方式以及e r a s u r ec o d e 方式。针对这两种 冗余方式，不少研究人员作了很多研究比较工作，主要有： ( 1 ) 2 0 0 2 年，o c e a n s t o r e 项目的研究者w e a t h e r s p o o n 等人【5 】用量化的方法分 析了e r a s u r ec o d e 和副本方式冗余对系统可靠性的影响。此分析工作以 o c e a n s t o r e 的较为稳定的运行环境为参考，考察不同冗余方式对系统可靠性的影 响，采用随机过程的方法进行建模和分析。研究者假设系统每隔一定时间间隔 做一次全面的数据修复，系统中每个存储节点都独立且等概率的失效。在以上 假设下，通过对比发现：在分布式系统中使用e r a s u r ec o d e 冗余，可以在与副本 冗余得到相同可靠性的条件下极大的节约系统中的存储空间和维护带宽；若使 用相同的存储空间和维护带宽，e r a s u r ec o d e 方式也能够极大的提高系统的可靠 性。因此研究表明，e r a s u r ec o d e 有利于提高系统的可靠性。 ( 2 ) t o t a lr e c a l l 的作者b h a g w a n 等人【6 】在2 0 0 2 年针对系统中数据的可用性， 也比较了副本和e r a s u r ec o d e 两种冗余方式。作者认为，在p 2 p 系统中以整个 文件的形式复制和处理大文件是耗时和麻烦的，因此要考虑将文件切分为小块。 通过实验，作者对比了整个文件副本、对文件碎片做副本和e r a s u r ec o d e 三种冗 余方法对数据可用性的影响。实验结果也显示，e r a s u r ec o d e 方式在提高数据可 用性方面有明显优势。 ( 3 ) 2 0 0 5 年，m i t 的学者r o d r i g u e s 等人 】主要从系统可行性的角度分析了 两种冗余方式对可靠性和可用性的影响，指出了e r a s u r ec o d e 方式优势的局限 性。研究者建立了系统在稳态情况下维护带宽的模型，根据模型，作者推导出 维护系统数据的冗余度所需要的带宽资源。作者使用o v e r n e t 8 1 、f a r s i t e 9 】和 p l a l l e t l a b o 】三个系统的动态性测量结果，分析它们所需要的维护带宽，结论如 下： 4 第一章引言 在p l a n e t l a b 这种稳定节点组成的系统中，副本方式已经能够在低的维护带 宽情况下提供很好的可靠性和可用性。 在f a r s i t e 这种中等动态的系统中，e r a s u r ec o d e 方式比副本方式并没有很明 显的优势，但却会带来设计和实现上的复杂度，因此没有必要使用e r a s u r ec o d e 。 e r a s u r ec o d e 能为o v e r n e t 这种高动态的系统节约存储空间和维护带宽，但 是其维护带宽仍然是每个节点不可接受的，因此系统本身就不可行。 总结上述结论，尽管r o d r i g u e s 等人对e r a s u r ec o d e 持批评意见，但是可以 看到，p 2 p 存储系统使用的副本和e r a s u r ec o d e 这两种数据冗余方式相比较而言， e r a s u r ec o d e 方式能够节约存储空间，降低维护带宽，提高数据可用性和系统的 可靠性。事实上，对p 2 p 网络这种节点可以随意加入和暂时离开甚至永久离开 的网络中，副本冗余的方式所能保障的数据可用性已不能满足要求；p 2 p 网络中 存在的大量不可信节点对副本冗余方式的数据安全性亦造成了巨大的威胁。 e r a s u r ec o d e 方式较为适合p 2 p 存储系统，这是由e r a s u r ec o d e 的编制特点所决 定的。 1 2 2p 2 p 存储系统中的数据安全性 p 2 p 数据安全方案中，不同的p 2 p 存储系统关注的方向并不相同，一些注重 对存储数据的加密研究，有些侧重的是数据文件的修复策略。实际上目前p 2 p 存储系统数据安全的研究也主要集中在存储数据的加密和数据修复这两个方 面。 ( 1 ) p s t o r e 对数据安全性的研究 p s t o r e 1 2 】侧重研究的是p 2 p 存储系统中的备份系统，它使用c h o r d 3 刀来组织 p 2 p 网络，其文件查找效率达到o ( 1 0 9 n ) 。数据的可用性p s t o r e 使用数据块( d a t a c h u n k s ) 的额p f p 丑i 本方式作为冗余策略来提高数据可用性。在数据安全性方面， 主要采用了是分组密码体制加密文件副本，其数据安全部分描述如下： p s t o r e 使用的数据结构包括文件分块( f i l eb l o c k s ，f b ) 、文件分块列表( f i l e b l o c kl i s t s ，f b l ) 以及数据块( d a t ac h u n k s ) 。 f b 每个文件分块f b 都包含了原始文件的部分信息，是p s t o r e 的最基 本存储单位。 f b i 是保存着文件分块f b 的标识等方面信息的表单，每个文件分块f b 在f b l 中包括如下四项： 第章引言 1 ) f b 的唯一标识 2 ) f b 文件内容在未经分组加密之前的h a s h 值 3 ) f b 文件的长度 4 ) f b 文件在原始数据文件的偏移量 d a t ac h 】k s - - p s t o r e 文件处理的基本结构，无论是f b 还是f b l ，p s t o r e 都当成是数据块( d a t ac h u n k s ) 来处理。d a t ac h u n k s 可以用表达式c ( i ，p ，s ，d ) 来 标识，参数( i p ，s ，d ) 的设置视处理f b 或f b l 有所不同，其具体设置已经超出本 文的范围，有兴趣读者可以参考文献，这里不再赘述。 p s t o r e 主要是使用公开的加密算法对d a t ac h u n k s 这一基本数据结构进行保 护。d a t ac h u n k s 的参数s 的生成使用的加密算法是公钥密码体制r s a 算法，而 表示活动文件的d 则采用a e s 加密，也就是说对f b 和f b l 采用a e s 加密。 d a t ac h u n k s 中还使用了单向h a s h 函数s h a 1 用于生成密钥或标识等等。 因此，p s t o r e 的数据安全性主要基于这些密码体制算法的安全性。此外p s t o r e 还设置了数据访问控制机制，用户不能直接访问其贡献给系统的存储空间，以 此来保护其它用户保存的私有数据文件。p s t o r e 还拥有文件删除机制，使得用户 可以删除其存储在p 2 p 网络中其它节点里的文件。 从数据安全性设置来看，p s t o r e 的数据安全性很高，但是由于其系统较为复 杂，实现困难且代价比较高，因此没有得到广泛应用。 2 、s s s 1 3 】：秘密共享方案( s e c r e ts h a r i n gs c h e m e ) 与e r a s u r ec o d e 的结合 在参考文献【l3 】中给出了一个p 2 p 存储系统的模型，该p 2 p 存储系统基于 d h t ( d i s t r i b u t e dh a s ht a b l e ，分布式哈希表) 组织p 2 p 网络，使用s s s ( s h o r ts e c r e t s h a r i n g ) 来提供数据的高可用性和安全性。文中还设计了三个基于版本号的协议 c o v n 、d o v n 和d u v n 分别用于数据的同步更新、部分更新和受损数据的恢 复，实际上是一种应用于积极的文件修复策略的协议。 数据的安全部分：文中提及为保证关键性数据的机密性，使用( n ，k ) s s s 数据 分块算法将数据文件对象分割为n 个数据分块并将其分发到n 个存储节点。s s s 数据分块算法使用e r a s u r ec o d e 将加密后的数据对象分割成n 个数据分块，并使 用秘密共享方案保存用于加密的密钥。因此，文中认为s s s 同时具有e r a s u r ec o d e 和秘密共享方案的优点。实际上，文中数据的安全部分侧重点在于文件的修复 策略，c o v n 、d o v n 和d u v n 这三个协议的设计也是为数据的修复策略服务 的。这三个协议的具体描述由于不是本文重点，且过于复杂，本文将不再展开 6 第一章引言 叙述。 但s s s 考虑的是在一个较为理想的网络环境：加入网络的节点需通过一定 的过滤规则；网络中节点互相信任；节点较为稳定，只会暂时离开网络且在一 段时间内会返回网络。因此，文中关于数据安全性的讨论也基于这种理想的网 络环境，从而使得其安全策略并不具有较强的通用性。 在以上所介绍的两个具体p 2 p 数据安全方案中，p s t o r e 主要注重对存储数据 的加密研究，而s s s 侧重的是数据文件的修复策略。实际上目前p 2 p 存储系统 数据安全性的研究也主要集中在存储数据的加密和数据修复这两个方面。 第三节本文研究内容一r s 码的安全方案设计 在本文的设计中，笔者将主要基于e r a s u r ec o d e 对p 2 p 存储系统数据安全 进行研究。e r a s u r ec o d e 被应用于p 2 p 存储技术后，由于其具有很强的容错能力 和纠错能力，因此成为存储技术领域的热门研究问题，而且其所具有的特点和 优势，使得研究人员可以基于e r a s u r ec o d e 设计和实现加密存储系统，从而将加 密和编码有效地结合起来( 基于e r a s u r ec o d e 设计和实现的密码体制，如m 公 钥体制【1 4 】和r a o - n a m 私钥体制【15 】在后文中介绍) 。本文中研究的是属于e r a s u r e c o d e 的r s ( r e e d s o l o m o n ) 1 6 码，所设计的数据安全方案基于r s 码实现。应用 于存储系统的r s 码的具体原理将在第二章中详细说明。 本文中，笔者首先对已有的基于r s 码的p 2 p 存储系统安全方案s e c 【1 。7 】 进行了研究，s e c 方案属于秘密密钥体制，密钥由用户给定，密钥丢失将会导 致s e c 方案的失效。s e c 方案作者对r s 码的编码函数e ( d ) = g d 中的生成矩 阵g 做了设计，将g 设计为一个由密钥生成的秘密矩阵g 。另外，s e c 方案将 所生成数据分块的文件名使用h a s h 函数生成，从而将数据分块之间的联系隐藏。 但是，对s e c 中秘密生成矩阵g 的安全性方案作者仅考虑了在暴力破解情 况下穷举量很大，从而认为这个秘密生成矩阵g 是安全的。事实上，笔者通过 已知明文攻击，可以使得在获取部分原文件和1 t 1 个数据分块的情况下，获取解 码矩阵，而运算代价只是求解m 个定义于有限域上的一次线性方程组，且每个 方程组含有m 个未知量。解码矩阵的破译使得获取了m 个数据分块后，就能够 完全还原原数据文件，从而论证了s e c 方案是不安全的。具体的分析破译方法 将在第三章中介绍。 7 第一章引言 笔者经分析后认为，s e c 方案的不足在于其加密所用的r s 码是线性码，其 线性性导致了s e c 方案产生的明文和密文之间存在着线性对应关系，对手利用 这种线性关系，通过已知明文攻击，可以达到破译的目的。但是s e c 方案的可 取之处在于： 1 ) 生成的数据分块由于都是冗余数据分块，与原数据文件的分块相比较， 相当大程度隐藏了原数据文件的信息，从而使得对手不得不必须从破译生成矩 阵入手才能达到破译目的； 2 ) 假使对手并没有获得相应的明密文对，那么当数据分块数量够多时，用 穷举的方法破解秘密生成矩阵几乎不可能。 3 ) 使用h a s h 函数生成文件名，从而完全隐藏了s e c 数据分块文件之间的 联系，使得对手在收集足够多用于破译的密文时有很大的困难。这一点，极大 提高了已知明文攻击的难度，降低了己知明文攻击发生的概率。 因此，本文中针对s e c 方案存在的问题，设计了一种基于r s 码的安全方 案设计_ e r s ( e n c 帅t e dr s ) 。e r s 同样基于密钥保密，属于秘密密钥体制。 e r s 的设计包括： 1 ) 对文件分块算法进行了全新的设计，通过使同一文件在不同的密钥下能 生成不同的数据文件分块，提高了已知明文攻击的难度，提升了系统的安全性 能。 2 ) 对秘密矩阵的生成算法做了改进，通过自动生成的密钥，生成秘密柯西 矩阵。 3 ) e r s 所产生的数据分块其文件名采用h a s h 函数设计。 4 ) e r s 的所有密钥都是由系统自动生成，而不是基于用户给定，从而降低 了用户设置弱密钥口令而产生的对系统安全的威胁。 对e r s 进行安全分析，结果显示，e r s 具有很高的安全性，能抵抗穷举和 已知明文攻击。 第四节论文结构 本文在结构上分为六个组成部分： 第一章介绍了p 2 p 存储系统的发展现状和需面对的主要问题，并着重分析 了p 2 p 存储系统中对数据安全问题的研究现状，由此提出了从冗余策略e r a s u r e 8 第一章引言 c o d e 出发而设计的安全方案e r s 。 第二章详细介绍了e r a s u r ec o d e 的基本理论和r e e d s o l o m o n 码的基本实现。 第三章对现有的r e e d s o l o m o n 码安全方案s e c 中加密部分进行了详细 的介绍，并提出了对其已知明文攻击的方法，证明了其不安全性。 第四章详细介绍了笔者所设计的基于e r a s u r ec o d e 的安全方案e r s ，对其 设计方法进行了细致的说明，并就一些细节问题给出了建议。 第五章主要介绍了e r s 的程序实现，并与r e e d s o l o m o n 码的基本实现进行 了对比。 第六章主要总结论文工作，并就论文未来的工作提出了展望。 9 第二章e r a s u r ec o d e 理论与基本实现 第二章e r a s u r ec o d e 理论与基本实现 第一节e r a s u r ec o d e 理论发展 1 9 4 8 年，c l a u d es h a n n o n ( 克劳德香农) 在他的经典论文“am a t h e m a t i c a l t h e o r yo f c o m m u n i c a t i o n ”( 通信中的数学理论) 的引言部分中写道： “通信中的基本问题就是在某一点精确或近似的再生另一点选择的信息。” 从解决这一问题出发他提出了应用数学的一个全新分支信息理论和编 码理论。在香农编码定理的指导下，信道编码理论与编码技术的研究至今已有 近6 0 年，逐步发展走向成熟。2 0 世纪5 0 年代初，汉明( r w h a m m i n g ) 提出 了重要的线性分组码一汉明码后，代数方法被引入到纠错码的研究，从而形成 了代数编码理论。1 9 5 7 年普兰奇( p r a n g e ) 提出了循环码，循环码是线性分组 码中最重要的一种子类，具有许多特殊的代数性质，这些性质有助于按照所要 求的纠错能力系统地构造这类码，并且简化译码算法，目前发现的大部分线性 码与循环码有密切关系。循环码还有易于实现的特点，很容易用带反馈的移位 寄存器实现其硬件。正是由于循环码具有代数结构清晰、性能较好、编译码简 单和易于实现的特点，因此目前的计算机纠错系统中所使用的线性分组码几乎 都是循环码，这些循环码不仅可以用于纠正独立的随机错误，而且也可以用于 纠正突发错误。随后的十多年里，纠错码理论研究主要是围绕着循环码进行， 取得了许多重要成果。1 9 5 9 年由霍昆格姆( h o c q u e n g h e m ) 、1 9 6 0 年由博斯( b o s e ) 和查德胡里( c h a u d h a r i ) 各自分别提出了b c h 码，b c h 码是循环码的一个重 要子类，是一种可纠正多个突发随机错误的码。b c h 码的代数理论严密，它的 生成多项式与最小码距之间有密切的关系，人们可以根据所要求的纠错能力很 容易构造出b c h 码，它们的译码器也容易实现，是线性分组码中应用最普遍的 一类码。1 9 6 0 年i s r e e d 和g s o l o m o n d 提出r s 码，r s 码是一类纠错能力很 强的多进制b c h 码。它不但可以纠正随机错误、突发错误以及二者的组合，而 且可以用来构造其它码类。因此，r s 码在卫星通信、数字电视传输以及磁记录 系统等许多领域得到广泛应用。 e r a s u r ec o d e 是无线通信中有噪信道编码的一种，后来由k a r n i n 提出的密钥 共享【1 8 】( s e c r e ts h a r i n g ) 以及m o r a b i n 提出i d a 1 9 】( i n f o r m a t i o nd i s p e r s a l l o 第二章e r a s u r ec o d e 理论与基本实现 a l g o r i t h m ) 算法，将其引入到计算机应用中，发展到现在，已有数十种编码， 主要包括r e e d s o l o m o n ( r s ) c o d e 和t o r n a d oc o d e 2 0 】【2 1 1 2 2 等，最常用的是r s c o d e ，它适合于m ，n 较小的情况下( 如m + n 2 5 6 ) 。e r a s u r e c o d e 是由一个四元 组( m ，n ，b ，r ) 来确定的编码。设其编码函数为e ，解码函数为d ，对于消息 m = ( m ，m 2 ，m 。) ，其中m ，( f 1 ，m ) 由原始消息m 分割为大小为bb i t s 的消息包( 不足部分补o ) ，编码后的消息( m ) = ( m 。，m 。：，m 。) ，其中m ， ( f l ，n ) 大小仍为bb i t s 。设e ( m ) 为e ( m ) 中任意r ( r m ) 个消息包组成的 子消息，则d ( e ( m ) ) = m ，即对e ( m ) 中任意r 个消息包进行解码就可以得到 原始消息，而获得少于m 个消息包会导致原文件无法获取，于是系统将可以容 忍多达n m 个节点的失效。在这里，m n 即为e r a s u r ec o d e 的编码率。 e r a s u r ec o d e 具有很强的容错能力和纠错能力，使得其广泛应用于计算机存 储领域和安全应用。实际上，前文提到的几个典型的p 2 p 存储系统都是注重于 数据的可用性，对数据安全性的解决主要侧重于数据的修复和维护。而e r a s u r e c o d e 完全可以应用于密码系统和构建加密算法，因此也能用于提高p 2 p 存储系 统的安全性。 第二节e r a s u r ec o d e 相关密码学研究 e r a s u r ec o d e 应用于公钥密码体制的代表是m ee l i e c e 公钥密码体制【1 4 1 ( 简称 m 公钥密码体制) 。1 9 7 8 年，由于b e r l e k a m p 等证明了一般线性码译码是n p c 难题，因而m ce l i e c e 根据这一事实并利用g o p p a 码的特点，于1 9 7 8 年首次 提出用纠错码构造出m 公钥密码体制，从而开创了纠错码在公钥密码学中的应 用。 m 公钥密码体制简介： 设g 是二元( n ，k ，d ) g o p p a 码的生成矩阵，这里n = 2 m ，d = 2 t + l ，k - - - n m t 。 密钥的产生：随机选取有限域g f ( 2 ) 上一个k k 的可逆矩阵s 和n x n 的置换矩 阵p ，令g + = s g p ，将s 、g 、p - 1 作为私钥，g + 和t 作为公钥。这里的置换矩阵 是指矩阵的每行每列都仅有一个“1 ”，其他全为“0 ”，它的作用是任一组数据 与之相乘，仅改变原数据中各元素的顺序。 加密过程：对于任意明文m e g f 。( 2 ) ( g f k ( 2 ) 表示g f ( 2 ) 上的k 维向量) ，将其 加密成密文：c - - - m g + e ，这里e 是g f ( 2 ) 上重量为j ( t ) 的随机向量。 第二章e r a s u r ec o d e 理论与基本实现 解密过程：收方收到密文c 后，计算c p j - - m s g p p 。+ e p 。1 = m s g + e ，因为p 是置换矩阵，所以w ( e ) - - w ( e ) t 。然后利用g o p p a 码的快速译码算法将其译成 m - - m s ，计算m s1 - - m s s = r n ，即得到密文c 对应的明文。 1 9 9 1 年，王新梅发表纠错码数字签名、加密纠错公钥体制 2 3 】，文中构 造了一类基于m 公钥密码体制，既能对消息签名又能对消息加密的公钥体制 e c p s 2 和e c p s 3 ，它们的签名和验签，及加解密运算都非常简单，还能提供不 同的纠错和检错能力。但是，1 9 9 2 年，a l a b b a d i 和w i c k e r 针对此方案提出对其 选择明文攻击方法的工作因子仅为o ( n 3 ) 矧，该体制被破解；1 9 9 3 年隆永红发表 ( ( e c p s 2 和e c p s 3 中的加密也是不安全的 2 5 】，指出公钥体制e c p s 2 和e c p s 3 可以在o ( n 3 ) w t n 内由体制的公开密钥信息找到一个置