[硕士论文精品]网络编码签名算法

摘要大量研究证明，网络编码能广泛应用于无线传感器网络，传统计算机网络，P2P及P4P网络中，并能提供各方面好处，例如增加网络带宽利用率，减少网络拥塞，增强网络健壮性，降低能量消耗等。然而，网络编码极易遭受污染攻击的破坏。近年来，国内外众多学者针对网络编码中的污染攻击提出了许多防御方法，其中基于密码学的签名算法在抵御污染攻击方面具有更高的安全性，能抵御任意数量攻击者的污染攻击，因此拥有更为广泛的应用前景。本文在大量研究网络编码现有签名算法的前提下，针对现有签名算法中的某些缺陷，提出了三种网络编码签名算法，每种算法都有不同的特点与优势，可以为不同性质的网络传输系统提供性能更优越的签名算法的选择。同时，本文分别利用分析的方法和随机预言模型的方法对所提出的算法进行了安全性的证明一一次一密网络编码签名算法现有的许多基于密码学的网络编码签名算法在传输一个新的文件时需要重新选择私钥，并更换公钥，这极大增大了网络传输负载。本算法针对这种缺陷，采用一次一密的无条件签名方法，在不改变公钥的情况下，对每一代新消息都使用不同私钥进行签名，这样既增强了签名安全性，同时也降低了网络传输负载；一快速网络编码签名算法当前，网络编码签名算法都基于复杂的计算操作，这使中间结点在验证消息是产生大量时延，特别是在许多无线传感器网络中，由于结点计算能力低下，使用这种复杂的验证算法会极大降低网络传输效率。本算法通过采用基于线性计算的同态哈希函数为消息计算哈希值，可以极大提高结点的验证速度。实验表明，本算法验证过程的时间复杂度远小于其它已发表的文献；一多源网络编码短签名算法几乎所有现有网络编码签名算法都只能用于单源网络编码，而对于拥有广泛应用的多源网络编码则无法适用，这极大的缩小了网络编码的应用领域。本算法设计了一种新的同态签名函数，可以对基于线性编码的多源网络编码的消息的完整性进行全面的安全保护，并且具有较短的尺寸和高安全性。关键字网络编码，同态哈希函数，签名函数，污染攻击，重放攻击姓名测试打分HTTP/WWWXINGMINGCESHIORGABSTRACTITHASBEENPROVENTHATNETWORKCODINGCANBEWIDELYAPPLIEDINWIRELESSSENSORNETWORKS，TRADITIONALNETWORKS，PEERTOPEERANDPEERFORPEERSYSTEMS，ANDPROVIDESIGNIFICANTBENEFITSTONETWORKS，SUCHASIMPROVEDTHROUGHPUT，REDUCEDCONGESTION，INCREASEDRELIABILITY，REDUCEDPOWERCONSUMPTION，ANDSOONHOWEVER，NETWORKCODINGISVERYVULNERABLETOPOLLUTIONATTACKSINRECENTYEARS,MANYAUTHENTICATIONSCHEMESHAVEBEENPROPOSEDTODEFENDAGAINSTTHISKINDOFATTACKS，THOSESCHEMESBASEDONCRYPTOGRAPHICAPPROACHESHAVEHIGHERSECURITY，ANDCANDEFENDAGAINSTATTACKSFROMANYAMOUNTOFADVERSARIES，THEREFORE，THISKINDOFSCHEMESHAVEMOREPROMISINGFUTURETHISPAPERPROPOSEDTHREESIGNATURESCHEMESFORNETWORKCODINGAIMSATKINDSOFDISADVANTAGESINPUBLISHEDSIGNATURESCHEMES，WHICHWILLMAKENETWORKCODINGBEUSEDINVARIOUSNETWORKSYSTEMSWHATSMORE，WEHAVEPROVEDTHESECURITYOFTHETHREESIGNATURESCHEMESBYUSINGANALYSISANDRANDOMORACLEMODELONETIMESIGNATURESCHEMEFORNETWORKCODINGSOMESIGNATURESCHEMESREQUIRETOUPDATETHEPUBLICKEYSWHENTRANSMITTINGANEWFILE，WHICHWILLGREATLYINCREASETHEOVERLOADINTHENETWORKTHISPROPOSEDSIGNATURESCHEMEUSESONETIMESECRETEKEYBASEDONHOMOMORPHICPUBLICCRYPTOGRAPGYTOSIGNTHEMESSAGES，ANDUPDATINGTHESECRETEKEYWHENTRANSMITANEWFILEWITHOUTCHANGINGTHEPUBLICKEY，ITWILLNOTONLYREDUCETHEOVERLOADINNETWORK,BUTALSOENHANCETHESECURITYOFTHESCHEME；FASTSIGNATURESCHEMEFORNETWORKCODINGMOSTOFTHESEPRBLISHEDSCHEMESAREBASEDONEXPENSIVECOMPUTATIONS，THESESCHEMES剐CINEFFICIENTFORVERIFYINGMESSAGES，ANDARENOTSUITABLEFORSCENARIOSWITHLOWCOMPUTINGCAPABILITY，SUCHASMOBILEADHOENETWORKSANDWIRELESSSENSORNETWORKSTHISSCHEMEPROPOSEDANOVELSIGNATURESCHEMEFORNETWORKCODINGBASEDONALINEARHOMOMORPHICPUBLICCRYPTOGRAPHY，ANDUSINGFASTCOMPUTATIONWHICHGREATLYIMPROVEDTHEEFFICIENCYOFAUTHENTICATIONWHENCOUNTERACTINGIPOLLUTIONATTACKFORNETWORKCODINGEXPERIMENTSHOWSTHATTHETIMECOMPLEXITYOFVERIFICATIONINTHISSIGNATURESCHEMEISMUCHLESSTHANTHOSEINTHEEXISTINGALGORITHMS一SHORTSIGNATURESFO，MULTISOURCENETWORKCODINGALLOFTHESEPUBLISHEDSCHEMESCANNOTBEUSEDINMULTISOURCENETWORKCODING,WHICHHASABROADERAPPLICATIONBACKGROUNDTHANSINGLESOURCENETWORKCODINGINTHISSIGNATUROSCHEM，WEPROPOSEDANOVELHOMOMORPHICSIGNATURESCHEMEBASEDONBILINEARPAIRINGSTOSTANDAGAINSTPOLLUTIONATTACKSFORMULTISOUICENE铆ORKCODINGTHESIGNATURESINTHISSCHEMEALEPUBLICLYVERIFIABLEANDTHEPUBLICKEYSAREINDEPENDENTOFTHEFILESSOTHATTHISSCHEMECANBEUSEDTOAUTHENTICATEMULTIPLEFILESWITHOUTHAVINGTOUPDATEPUBLICKEYSTHESIGNATURELENGTHINTHISSCHEMEIS弱SHORTASTHESHORTESTSIGNATURESOFASINGLESOURCENETWORK，ANDTHEVERIFICATIONSPEEDISFASTERTHANTHOSESIGNATURESCHEMESBASEDONELLIPTICCURVESINTHESINGLESOURCENETWORKKEYWORDSNETWORKCODING,HOMOMORPHICHASHFUNCTION，SIGNATUREFILNCTION，POLLUTIONATTACKS，REPLAYINGATTACKSIII姓名测试打分HTTP/WWWXINGMINGCESHIORG独创性声明本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。研究生签名学位论文使用授权书本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段保存或汇编本学位论文。同时授权经武汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论文，并向社会公众提供信息服务。保密的论文在解密后应遵守此规定研究生签名导师签名超生芝日期塑F们武汉理工大学硕士学位论文第1章引言11研究背景及课题来源当前，网络技术日新月异，无线网络也蓬勃发展，人类对各种信息网络的依赖性越来越高，网络，特别是无线网络为人类提供的服务充斥了人类工作和生活的每个方面和每个角落。随着人们对网络依赖性的提高，人们对网络各方面的要求也越来越高，特别是在追求时间和效率的今天，人们对信息传输的效率提出了更高的要求，但更多的时候，网络资源却并没有被充分利用，这种高要求和低效率之间的矛盾，催生了一种新的网络技术的诞生网络编码。传统的网络传输认为，中间结点对其传输的数据进行处理的过程并不会为网络传输带来任何好处，只是在对信息传输有特殊要求如保证信息的安全传输，信息交换等时才会要求中间结点对信息进行相应的处理，因此，绝大多数情况下，无论是互联网中的报文，还是电话网络中的信号，只要他们来自不同的源，他们就会以相同的方式独立的在网络中进行传输，即不同的数据流彼此相互独立，网络的中间结点只是对信息进行简单的存储和转发。直到2000年李硕彦等人T41仓D造性的提出了网络编码的思想，才使人们从另外一个角度来研究网络中信息流的传输方式。网络编码允许中间结点对相互独立的信息进行特定算法的编码组合，并发送组合后的信息，目的结点接收到足够的信息后，可以根据特定的解码算法来恢复原始信息。显然，经过这样的组合过程，网络中的传输链路流量不变，但其所承载的信息量却成倍增加。除了提高网络传输效率外，网络编码还可以为网络提供多方面的好处，例如，它可以减少网络传输的次数，延长无线网络中结点的电池适用时间，减少网络拥塞，提高网络健壮性等。同时，由于网络编码对传输消息的编码组合，使得网络编码与生俱来拥有对信息的隐藏功能，防止网络中恶意结点的窃听行为。网络编码的这些突出的优点无疑将使其在各种计算机网络中得到广泛应用。然而，伴随着这种新技术的产生与应用，也出现了许多新的困难问题，其中最为显著的就是污染攻击151。污染攻击的产生主要是由于网络编码允许中间结点姓名测试打分HTTP/WWWXINGMINGCESHIORG武汉理工大学硕士学位论文对消息进行编码，事实上，这种编码显然是对消息的一种篡改行为。并不是网络中的每个结点都会忠实的按照编码原则来对消息进行组合，一旦网络中的某个信息被某蓄意结点恶意篡改，或在传输过程中由于外界原因发生变异，该污染信息将在整个网络中迅速繁殖，使目的结点无法恢复源信息，导致网络传输的失败。这种失败并不是针对单个信息，而是所有的参与编码的信息。针对网络编码的污染攻击，近年来，国内外已有许多学者对此进行了深入研究。主要的防御方法可分为两大类基于信息论的方法【67，8】和基于密码学的方法【9，10，11,12,13,14,151。基于信息论的方法计算快，但只能对网络中的某个或某部分恶意结点的攻击进行预防和抵御，其在实际应用中有许多限制条件。基于密码学的方法可以完全抵抗网络中任意数量的污染攻击，保证消息传输的可靠性，但由于这些方法多基于离散对数或椭圆曲线【16J等算法，其计算较为复杂。另外，现存的网络编码签名算法几乎都是针对单源网络的，对应用更加广泛的多源网络编码则鲜有提及目前为止除了罗蛟的117J以外，多源网络编码签名算法的空缺，似乎成为了阻碍网络编码得到更广泛应用的瓶颈之一课题来源国家自然科学基金资助项目项目编号60672137。12研究意义对于传统计算机网络，无线自主网络【LJ，P2P2L及P4P13】网络系统，采用网络编码可以极大的提高网络资源的利用率，特别是对于无线网络，其在提高效率的同时，还能有效的降低结点能耗118】，提高网络健壮性【19】以及提高信息在传输过程中的安全性圆J。网络编码几乎可以在各种网络传输中发挥巨大作用。然而，作为一种有广泛应用前景的新技术，网络编码的发展不得不面对污染攻击的存在，而污染攻击又会极大降低网络编码的传输效率，使网络编码的优点仅停留在理想状态。因此，设计一种可以抵御网络编码污染攻击的算法对于网络编码的发展显得尤为重要。而在抵御网络编码污染攻击方面，基于密码学的验证算法比基于信息论的方法更为彻底可靠，其研究成果也相对更丰富一些。然而，纵观整个网络编码签名算法的发展，本文认为其主要存在以下几点缺点，这些缺点或多或少的出现在现存的网络编码签名算法中1在网络编码签名算法的一些初期成果中【12131，虽然能防止蓄意结点伪2武汉理工大学硕士学位论文造消息来进行污染攻击，但却忽略了在多代消息传输时的代间污染攻击2现存的网络编码签名算法在更换私钥时，需要相应的更新公钥，增大了网络传输负载，降低了传输效率；3在许多网络系统中特别是无线网络中，结点的计算能力有限，对于复杂的计算将会消耗过多的时间和能量，而现存的网络编码签名算法都是基于一些复杂的运算来构造验证算法，不适合这些网络系统的使用4目前几乎所有的基于密码学的网络编码验证算法都只能用于单源网络中罗蛟【171等人的虽可以用于多源，但其复杂的计算以及冗长的签名影响了其在实际网络中的实施，对于应用更加广泛的多源网络则没有一个很好的算法来保证其信息的完整性，这极大的影响了网络编码在更广泛领域中的应用；综上所述，现有网络编码签名算法中出现的多种问题都极大的影响了网络编码在实际网络中的广泛应用，因此，针对上述缺点设计新的网络编码签名算法对促进网络编码的应用有重要意义。13本文主要工作针对网络编码中污染攻击的存在，在分析现存的防止网络编码污染攻击研究成果的基础上，分别从三个方面提出了三种基于密码学的网络编码签名算法，因此，本文具体包括以下三个工作1分析了当前基于密码学的网络编码验证算法，针对公钥需要随私钥更新的缺点，提出了一种一次一密的网络编码签名算法，可以有效的防止攻击者在窃取私钥的情况下对网络编码系统进行污染攻击。同时，采用分析的方法对该算法的安全性进行了全面的证明；2根据目前某些网络传输，特别是无线网络传输中结点计算能力低的实际情况，在分析了当前众多基于密码学的网络编码验证算法的前提下，指出了其计算过于复杂的缺点，并针对此缺点设计了一种新的网络编码签名算法，实验结果显示该算法在验证速度方面远大于其他基于密码学的3姓名测试打分HTTP/WWWXINGMINGCESHIORG武汉理工大学硕士学位论文算法。同时，本文采用分析的方法详细的证明了该算法的安全性；3详细分析了目前网络编码验证算法的适应范围仅适应于单源网络编码，针对多源网络编码，提出了一种新的同态签名函数，为多源网络编码提供的更好的安全性，同时利用随机预言模型证明了该算法的安全性。14本文结构本文共分为6个章节，其中第3至5章为本人主要工作。第1章主要对本文的研究背景以及研究意义进行了整体上的介绍，并对本文将要进行的主要工作进行了简单阐述。第2章主要介绍了现有的基于密码学的网络编码验证算法，并简单分析了这些算法中所存在的一些缺点；最后对一些签名算法中经常用到的一些数学运算及数学计算难题进行了简单说明。第3章为本文工作之一，主要针对现存网络编码验证算法中过分依赖于私钥的缺点，提出了一种基于同态公钥密码学的一次一密网络编码算法。第4章借鉴BRECSON加密函数的同态性，设计了一种新的基于线性运算的同态哈希函数，并用于网络编码签名算法，极大提高了中间结点对于消息的验证速度，减少了网络传输时延。第5章创造性的提出了一种可用于多源网络编码的同态签名算法，该算法在保证消息安全性的同时，使签名长度缩小到只有约160比特。第6章对本文进行了总结，并对本文的研究内容可能的发展方向进行了展望。4武汉理工大学硕士学位论文21离散对数第2章背景知识介绍离散对数是许多公钥密码算法的基础，在公钥密码学中有广泛应用。本节将对离散对数作简要介绍，文献【21,22】中有更详细介绍。欧拉定型231指出，对于任意的A和撑，若GCAA，刀1，则有D妒“鲁1MODN。若将该定理一般化，可以有如下描述若GCA口，1，则至少存在一个整数M，使得口辨1MOD1显然，至少有M驴门满足以上一般形式，称满足上式的最小M为A在模R下的阶。定理21若A在模以下的阶为册，则DLMOD，L的充要条件是MK。证明若DLMOD刀，由于朋为A的阶，所以KM，令KQMR，OG2满足如下性质1双线性对于任意的GL，92EGL及QBEZ，有PLL6国1J舰严；2非退化性若G为G1的生成元，则P慨G为G2的生成元，即P如姘1；3可计算性对于任意VEGL，存在一个有效算法来计算EU，叻。数学计算难题以下介绍的这些数学计算难题是密码学中许多签名及加密算法的基础。离散对数问题DLPDISCRETELOGARITHMPROBLEM由给定的元素蜀GAG1计算口乙。DIFFIEHELLMALL计算难题CDHPCOMPUTERDIFFERHELLMALLPROBLEMEH给定的元素蜀H，旷GL计算HAEGL。16武汉理工大学硕士学位论文31引言第3章一次一密网络编码签名算法本文在23节中已经讨论了网络编码面临的主要的挑战以及近年来出现的针对污染攻击的主要研究成果，但同时，我们可以发现现存的基于密码学的网络编码签名算法大多利用私钥对待发送的消息进行同态签名，当传输一个新的文件时，这些方案需要更改私钥，并更新相应的公钥，这将极大的增加网络传输负载。因此，有必要设计一种算法来预防此类情况的发生。本人在论文【371中已针对上述缺点提出了初步的解决放法，本节将对该算法进行改进和扩充。本节提出了一种基于同态哈希函数的签名算法，其中利用一次一密的方法，在不改变公钥的同时使签名私钥随报文的改变而更新，使得网络无需为反复的传输公钥而浪费网络资源，攻击者也无法获得准确即时的私钥信息。此外，本算法还引入的代的概念，在对每个代进行编号后，将代的编号引入算法中，用来抵抗代间的重放攻击。32算法模型321算法模型本节所需用到的随机线性网络编码及其所依赖的网络的模型可参见224节中描述的模型。此外，本中算法将引入消息叶”的概念，我们将每代消息以数字耐来编号，中间节点只对处在同一代的消息进行编码组合。在后面所进行的讨论中，如果没有特殊的说明，可认为算法中所讨论的消息都来自同一个代耐。322算法定义为了能够实现在不更换公钥的情况下进行多代消息的传输，在本算法中，无论是对签名的计算、验证，以及消息和签名的组合与验证，都需要引入相应的消17姓名测试打分HTTP/WWWXINGMINGCESHIORG武汉理工大学硕士学位论文息代的代号，因此，本文对网络编码同态签名算法进行如下定义定义31网络编码同态签名算法一个网络编码同态签名算法为一个PPTPROBABILISTIC，POLYNOMIALTIME算法四元组初始化GEN，签名SIGN，组合COMBINE及验证VERIFY，这四部分分别定义为如下GEN给定一个安全参数1A，消息的维数N以及子空间的维数M，输出公钥私钥对OJK,SKGEN1，研，力；SIGN给定私钥SK，向量VE譬”以及消息代序号IDO，1幸，输出签名ASIGNSK,V，曲；COMBINE给定公钥PK，一个随机向量CL，C2，C，爿，一组消息向量W1，W2，咋譬棚及其对应的签名口1，O2，田，输出消息VA，QWF及其签名盯；VERIFY给定公钥肼，消息代序号ID，向量VEF”及签名盯，输出VERIFYID,PK,，回L接受或跆，钡磁PK,1，力0拒绝。同时，该算法组必须满足下列条件1对于每组公私钥对P毛SKGEN1A，M，刀以及消息代碹若ARSIGNSK,1，奶，则必有VERIFY斌PK,V，力L。2对于I1，2，M，若殆，钡ID,PK,，F，力1，则必有VE，痧伽，ID，MBINPPK，D，兀，印A1根据定义31，若源结点对其消息进行签名，并通过验证，那么中间结点则可以在不知道私钥的情况下为由源消息组合而来的消息进行签名，且该签名能通过验证，这是网络编码同态签名算法关键思想所在。下面，本文将根据该定义，详细描述本算法。33算法描述3J1算法实现本方案的主要工作是构造签名毋。源结点首先计算与X正交的向量Z，然后将Z分解成R一RL90009，卅一和U；甜。”，“棚。两部分，其中，签名仍为R和X的乘积。结点在验证时需计算向量U和X的乘积，所得结果与签名相加，如果该签名是有效的，则这两个乘积相加等价于Z与X的乘积，即为0，否则将不为18武汉理工大学硕士学位论文算法的具体实现如下GEN1工，肼，订首先选取G局，PW，如果HLWHLW即1MROODQ21WQMODQ2则有1WG1W勺MODQ20即一WGMODQ2O因此，存在整数K，使得WWKQ而另一方面，W，WQ，因此，K0，即WW，这与之前假设的WW相矛盾，因此，函数办L为抗碰撞函数。一定理42函数厅2，为抗碰撞函数，对于给定的第耐代向量C肚CL，白彤及其哈希值H2CV,ID，寻找一个CV的碰撞CV0L，CCV即H2CV，I,OH2CV,ID等价于解决DLP问题。证明首先考虑N2的情况，即CVC1，C2，如CV，ID一暖，镌。攻击者试图寻找一个碰撞CVPLC9CV使得红CY，ID一1,2OR，耐，即穗镌；磕。R2因此RIILQRXQ11若CLC1，即防白1，则有C2C2，这与CVCV矛盾。若C1FC1，则有防包一蝣、，将磕当作一个定值并定义XC2C2，则有RY,。一掰、，显然，这等价于求解DLP问题。接下来考虑N2的情况，给定CVCL，锄片及其哈希值武汉理工大学硕士学位论文HDCV，讨兀。R2TROODP则碰撞CV一需满足CY，CY并且兀，喙兀越像，即II。眩Q一1。由于CVCV,则在CV和CV中至少存在两个元素CF及CJ有CJCJ，因此有谚钆兀州靠吒1即防Q一州磕；“固定元素“，CLILSK0。【151中虽然提出了一个可以明显提高验证速度的方法，但该方法与算法本身无关，就其算法而言，其验证速度与【13】的速度相似。在文献1121中，签名的验证需要大约KN1次的模幂运算，每个模幂运算需要OOOG1OO092,次的比特操作，其中LOGOC表示编码系数的长度，因此，其签名总共需要研1切DLO甙1C110孑伊】次的比特操作。同时在1121，作者对方案【12】和方案F13的验证时间进行了对比，对于单一的消息，【12所需要的时间为144秒，而【13】所需要的时间为1654秒，且方案151所需时间与1131相同。在本节所提出的算法中，原始消息肌，并没有以向量的形式出现，为了比较方便，我们将消息的长度设定为与其它文献F12，13】中相同的长度即LENGTHMFTENGTHX1，X2，瓢。在本算法中，对消息的哈希值的计算需要疗次的模幂运算，在加两次的RSA的验证计算，因此本算法的验证总共需要进行N2次的模幂运算，即研2门LO甙1010矿驴】次比特操作。表41给出Y12，13，15】与本算法的对比数据。雷一EAE；C2葛芏图41各算法验证效率对比L二警竺蒺一竺塑一一I姓名测试打分HTTP/WWWXINGMINGCESHIORG武汉理工大学硕士学位论文由于9N，编码系数的长度LOG1O应足够的大，因此，我们可以对表41中的验证速度进行简单的对比【13，15OKL092托叻OKLOGE沙109ZOOKLOGCVL092妒OK1LOG1C109ZCP】【12】D【2力LOG1LO旷缈】OURS可见，本节所提出的算法在验证实际上远小表中的其它算法。图41为在MATLAB中对上述算法的验证效率进行仿真后得到的对比图，图中可以明显的看出本算法在验证效率上优势非常明显。47本章总结本章提出了一个新的快速签名算法来抵御网络编码中的污染攻击，该算法要求中间结点对其接收到的消息进行验证并丢弃污染的消息。由于网络编码签名算法要求中间结点对消息进行验证，因此，验证速度的快慢成为评价一个算法好坏的重要标准。本节所提出的算法具有更高的验证效率，并且通过试验表明该算法的验证速度远高于12，13，15】中的验证速度，但本算法所要求的签名长度大约为消息长度的两倍，因此本算法适用用于那行中间结点计算能力非常有限而网络传带宽足够大的网络。武汉理工大学硕士学位论文51引言第5章多源网络编码短签名算法511研究背景网络编码能为各种计算机网络及无线传感器网络提供多方面的好处，本文在第22节中已对此有所介绍。随着随机线性网络编码的提出，使得网络编码的应用领域更加广泛，对网络传输的影响更加深远。然而，网络编码却极易受到污染攻击，对此，国内外许多学者提出了许多算法用来抵御污染攻击，本文在第23节中对一些主流的算法作了简要的介绍，并在第3章和第4章也提出了两种抵抗污染攻击的算法，然而，目前为止，除了【171夕1，几乎所有的基于密码学的网络编码签名算法都只是针对单源网络中的污染攻击，对于多源网络编码中的污染攻击，这些算法都在安全性方面有很大的限制，远不能满足多源网络编码的安全性的要求。因此，多源网络编码签名算法的缺失极大的阻碍了网络编码的更广泛的应用。虽然罗蛟等人【17】介绍了一种可以用于多源网络的签名算法，但其复杂的验证方法及冗长的签名阻碍了改算法在实际网络中的应用。在多源网络编码中，有多个用户源结点需要传输，这些用户显然不希望与其它的用户分享共同的私钥。因此，在多源网络编码中，每个源结点都有自己的私钥，且私钥各不相同。多源网络编码签名算法除了要求能够抵御中间结点的污染攻击外，还要求能够防止源结点之间的消息的伪造，其在安全要求方面比单源更高，实施起来更复杂。现有的网络编码签名算法无法应用于多源网络编码中，其主要的原因在于，现有网络编码签名算法只需要用到一个私钥来对消息进行签名，而在多源网络中，这唯一的私钥显然不能被多用户共享。若为每个源结点分配一个不同的私钥，则会破坏现有算法中签名的同态性，我们以F141为例来进行说明。假设现有两个源结点S1，82需要发送消息，在【141中，口1，A2分别为这两个结点的私钥AFA2，相应的公钥分别为GLIIGQ，92一G口2；ML，M2分别为源S1、S2的源消息，其哈希值为厅L和圯，这两个消息的签名可计算为姓名测试打分HTTP/WWWXINGMINGCESHIORG武汉理工大学硕士学位论文OI|K1，I1，2根据14100介绍的验证算法，这两个源消息的签名可以顺利通过验证EO，G一P厩，GF，I1，2其中，E为双线性对映射。若令MM1朋2为两源消息的组合消息，则按照单源网络中对于签名的构造方法，该组合消息M的签名应计算为0“7LXCT2，则新的消息报文文为小，力。然而，该报文却无法通过验证，因为EA，G一“绅。H22，G若令也A。WT骘，若存在这样的6，则有EO，GEIHH2BGE聊，96可见，验证算法要求中间结点计算矿，显然，这等价于解决CDHP问题。文献12，13，151都存在类似的缺点。KORHNL9】的算法并没有用到签名函数，而是利用安全信道传输传输相应消息的哈希值，因此，在多源网络中，该算法显然不是一个抗抵赖攻击算法。另外，许多网络编码签名算法ILO，111需要利用所有待发送消息来计算消息的认证信息，这在单源网络中是可行的，因为所有的消息都来自同一个源结点，但是在多源网络中，这显然是不现实的，源结点之间不可能相互交换待发信息。因此，此类算法也不适用于多源网络编码。512算法贡献结合本人已发表的论文【411，本节将提出一种新的基于双线性对的网络编码同态签名算法，该算法可用来抵御多源网络中的污染攻击，使网络编码可以应用于更广泛的网络领域。在该算法中，每个源结点都有自己的私钥，且每个源结点的私钥各不相同，同时，本算法也是一种基于同态函数的签名算法，中间结点不仅可以利用公钥来验证消息的完整性，还可以在不知道私钥的情况下对新组合而成的消息进行有效签名，另外，本算法的公钥与报文相互独立，当源结点传输新一代的消息时，将无需更换公钥，这极大降低了网络负载。在签名长度方面，本算法所产生的签名长度与其它单源网络编码算法中最短武汉理工大学硕士学位论文的签名长度一样长约160比特，本算法的验证效率要比其他的基于椭圆曲线的验证效率要快。同时，本算法支持消息的即时传输。在计算复杂性方面，我们假设每代消息中有M个消息，每个消息为一个MN维的向量，在签名长度相同的算法中，本算法仅需1次对运算和RER次的倍点运算，而其他的基于线性对运算的签名算法，如131贝JJ需要MN1次的对运算，【14，15】需要两次对运算和MN次的倍点运算，可见，本算法更高效。52算法模型多源网络中，每个源结点独立传输信息，目的结点需要确定其所解码接收到的消息的确来自其所声称的源结点，即每个源结点不能抵御其传输行为，因此，源结点有必要提供能够区别自己消息的签名验证方式。本算法的模型与单源网络模型有很大不同，首先，本模型中需要引入多个独立的源结点，其次，本模型需要为每个源结点分配身份标识、私钥以及对应的公钥等。详细模型如下与文献27，42，431类似，将网络用一个无环有向图GDEN来表示，其中E为网络中链路的集合，矿为网络中所有结点的集合网络中有M个源结点S01芦2”加CV需要向网络中的另一个结点集合T中的所有结点传输消息，其中，每个源结点都独立的传输消息，且不知道任何其它结点的传输行为。对于每个源结点，其目的结点为丁中所有结点，对于每个目的结点，其源结点也为S中所有结点。如图51所示，每个源结点一次只传输一个消息向量，每个消息向量需要对其标号，以区分该消息所处的消息代在本节中，如果没作特别标识，将所有认为是来自同一消息代。在第耐代消息中所传输的M个源消息为XAX，X脚，其中XEOM，X加为来源结点研发送的第讨代中的消息，每个源结点在发送消息前将消息的原始全局编码向量附加在消息上，则其扩充后的源消息可表示为一一炙、JLX,L，X加，0，C，1，0，O一XN，XI,M4NF7”百其中，F为有限域，G为事先确定的安全参数。姓名测试打分HTTP/WWWXINGMINGCESHIORG武汉理工大学硕士学位论文源结点第肼代源消息添加编码向量后的第F玳源消息图51第耐代源消息处理模式每个源结点的原始编码向量需各不相同，因此，我们可以将源消息上所附带的原始编码向量当作发送该源消息的源结点的身份。如对于源结点研，可以认为其身份为笑、0，0，1,O，0、，FL，。一当目的结点解码得到的源消息其编码向量为O，O，1O，0时，该目的结点便认为、。V，I1该消息来自源结点。当中间结点接收到多个消息后，首先辨别消息所处的消息代，中间结点只对处于同一个代中的消息进行编码，其编码方式与本文前几节中所描述的方式相同。例如，对于某中间编码结点，其接收到的消息为WL，IDL，W2，涵，W，IDO,VL，IDA，V2，IDA，IDA，则该编码结点分别对第碗代和第娩代中的消息进行编码对汹代的编码为W，LC，WI，输出的消息为，IDA；对醍代的编码为，一。尼吒，输出的消息为V，ID2。值得注意的是，对于任何一代消息，其参加编码的消息一般是来自多个不同的源结点或来自不同源结点的组合消息。文献【4】从信息传输角度指出，该模型可以退化成一个单源网络编码，并虚拟IIILIIIII寓HIM叭“一一，一，一一一一一一一一一一瞰一陵；一一一一姗一啪一慨藉进武汉理工大学硕士学位论文一个所有源结点的共同源结点岛的存在图52。但是，从信息安全的角度讲，这种将多源认为是单源的假设显然是不合适的，每个源结点都需要对其所发送的消息进行签名。图52多源多宿网络编码信息传输图图52扣中表示有多个源结点需要向目的结点硝F1，2，O进行信息传输但从信息论的角度出发，【4】指出可以将所有的源结点看做一个虚拟源结点岛的下一跳图6，这样，多源网络编码的传输便退化成为单源网络编码的传输。因此，该模型在信息传输方面可以采用单源网络编码的传输方式，然而，在信息传输的完整性方面，则需将每个源区别对待。53多源网络编码短签名算法本方案中，源结点首先对其所发送的消息添加原始编码向量，然后利用其私钥对扩充后的消息进行签名，并将签名附在消息后一同发送。中问结点可以在无需解码的情况下利用公钥对消息进行验证，同时，中白J结点也可以利用签名的同态性来计算对新消息的签名。目的结点在接收到小个线性无关的有效消息向量后便可以解码源消息。艘蒺笺。疑姓名测试打分HTTP/WWWXINGMINGCESHIORG武汉理工大学硕士学位论文531算法描述在多源网络编码中，很多情况下由于各源结点彼此独立没有联系，因此在开始传送消息前，需要有一个组织者对本次消息的传送进行初始化，包括计算本网络的最大流，统计源结点的数量并合理的选择源结点，为每个源结点确定本次传输的位置包括在某些网络中不同源结点的重要性不同，为源结点分配初始编码向量等，为每个源结点生成私钥等，因此，本算法需要一个可信第三方PKG来完成上述工作。本算法的具体实现如下GENPKGPUBLICKEYGENERATION按照如下方式初始化本算法I生成算法参数秘密选择大素数玑V，使得“。V，并令QUV；GL，G2为两个Q阶乘法循环群，G为G1的生成元；口G1XGLG2是一个G1到G2的双线性映射；91，92，劭为GL1中的刀个不同的元素，喇；，由PKG在乏中秘密选取，且对于任意整数蜘有RCKT,。HO一酥；注意到参数“和，只有PKG知道，参数岛孙ZO则为公共信息。II生成公私钥对于I1，2，肌在Z中秘密选择AI使得AAJQL，2，I1并计算S岛1司F，RE；在G11中秘密选择S，使得对于户1，2，I1有SK,SKN；计算此PS，GO作为源结点研的公钥；凶，吨，磊脚是G2中的MN元素，并设，、吐，D，以，以小，叱。ALPG。，P岛，以，耻肘I；R一厂一了一F一将蜗O岛1，S如作为源函的私钥发送给毋；定义消息WL，W2,，WN,WN扎，WN力片的哈希值为HID，W一HID，W工ZM。G一其中耐为消息代序号，矿表示消息向量W最左边的，1个元素。该函数实际上是一个同态函数，对于该性质将在532节中给出证明。PKG为该算法生成的公钥为尸熙E岛孙，巩，吨”，磊艉。42武汉理工大学硕士学位论文注意到在初始化过程中，PKG需要为每个结点秘密的分配私钥，在没有安全信道的情况下，这可以通过【44】中提出的安全协议实现。SIGNSK，ID,劫对于任意源结点毋I1，2，M，给定其私钥S岛1，SK,2及N辨消息置一OM，X加，垒翌，1O，O一XN，而肿。，毋计算签名如下FLHID，XF仃IL二一S铭”COMBINE给定随机编码系数CL，C2，CF，一组消息YL，抛譬及其签名O“1，仍，中间结点按照如下方式组合消息W。2CJYI该新的组合消息的签名计算如下仃一兀。开可见，中间结点可以根据源消息及源消息的签名来构造任何属于子空间形一SPANX“，X。的消息及签名，其中XJI1，坍为源消息。VRFYPKID,W，S给定消息代序号耐，公钥P胎冠岛踟而，吨，磊州，消息WW1，W2，WN，WN1，WN力及其签名盯，定义HPK，ID，W三兀”D“H签名盯为消息W的有效签名，当且仅当EO，GOHPK，ID，叻一151注意到本算法的验证算法只需要一次对运算和MN次倍点运算。532正确性证明我们首先证明哈希函数觑，及签名函数瓯眇，为同态函数，即对于任意的向量EZF”，有觑ID,NZ刊磁D。娥ID,Z；SIGNFD,RZSIGNID,RSIGNID,Z证明假设YW，Y2，跏D，ZZL，Z2，,ZM0，则】，ZVLZL，Y2Z2JK一Z臃一A由函数日的定义可知姓名测试打分HTTP/WWWXINGMINGCESHIORG武汉理工大学硕士学位论文HID，】，Z17；，GJ耐“X一兀二。G甲乃GP4LI，“MH；。“协HID，YHID，ZCO对于任意的消息WW1，W2，OO,WN，WN1，WN州，已知该消息为源消息的线性组合，其全局编码向量为WNL，WNM，因此，W可写为如下形式W胂IML置厶”1另外，根据签名的同态性可知，W的签名可由源消息的签名组合而来，即跏,A,WIIT，罨娑厂因此，对于消息Y和Z，我们有】，。X，Z一X及跏IA,RH。罨娑厂跏C岈M罨娑厂因此，SIGNID，YZTLF，罨娑厂“；II_。警”。LF。警“。SIGNID，DSIGNID，ZNI贝,，函数觑，与跆心都为同态哈希函数。现在对式51的正确性进行证明证明根据消息W与源消息的线性关系以及函数的同态性可知，W7。W川X，HID，W；兀。日耐，X一H“，仃A兀，矿“，其中为源结点毋扩充后的源消息，毋为的签名，II，2，M。则有PP，GN办麒，ID，W武汉理工大学硕士学位论文证毕54安全分析P盯，G。兀“D“P，P口，G。M。PGJH。吲“M兀D肿J肌“O，一PP，G。P兀GJDOW,，HO兀，P样肌肘OP，GOP兀2。蜀DIWL，剐R它兀LS蜉州J，岛P盯，G。PH耐，叻7，G。E兀三。J七善“N“，GO一PPHID，叻7兀二。J七“M“，G。一P兀二。仃，兀。HID，W7。兀二。睹乎”“H“，GOPQLT，仃，何耐，X，7曲G”“WML99。32。PQF。警埘，X，7曲善”“WNI990P兀二HID，X嘶17】WNT990。P1F。【日耐，X，Q”】”H“，G一P兀。【日耐，X，QUVG一P兀三。HID，X。吣“】9，G一P兀。HID，X。啪，G41因为G2为Q阶循环群本节将分三步对本算法的安全性进行详细的讨论首先分析任意源结点伪造其它结点签名的可能性，其次对中间结点成功实施污染攻击的概率进行分析，最后将介绍本算法能防止代间重放攻击。541源结点的攻击从源结点的公钥计算其私钥将是不可行的，并且穷举攻击成功的可能性可以忽略。定理5L对于II，朋，给定公钥以，若CDHP无法破解，则计算J如使得ESKA，GOPK,是不可行的。姓名测试打分HTTP/WWWXINGMINGCESHIORG武汉理工大学硕士学位论文证明如果存在某个算法F在输入公钥眈和GO的情况下，其输出结果为S即S缸乏肋岛，GD，则可以利用该算法厂由H和旷计算出矿矿魂，P0，奶，如此便破解了CDHP问题，这与假设矛盾。_该定理指出攻击者无法通过公钥砘计算得到私钥S。若攻击者利用穷举攻击，由于啦有源ST在G1中随机选择，而群G的阶为大素数G，因此其成功的可能性为1向，当Q足够大时假设Q2160，那么这个可能性可以忽略。源结点的另一个私钥踮1AJVR，然而，M，和，只有PKG知道，因此，攻击者无法计算出S岛1，并且进行穷举攻击的概率依然为均。542中间结点的攻击本算法中消息的签名是由源结点利用私钥SK。扔生成的，不难发现，私钥啦主要是用来防止源结点之间的污染攻击，对其安全性本文在上节已经讨论过了，S幻才是用来防止除源结点之外的其他结点的污染攻击，因此，本节只讨论私钥S觑在中间结点污染攻击下的安全性。另外，为了简化证明，我们假设攻击者仅对源结点的消息和签名进行伪造，并只对一个任意一个源结点的消息和签名进行伪造。事实上，“攻击者伪造任意一个源结点的消息和签名”与“攻击者伪造任意的消息包括源消息和编码后的消息和签名”，者两种做法的难度是等价的，因为如果攻击者能伪造任意一个源结点的消息X圾其签名嘶，由源结点的任意性，那么该攻击者也能伪造其它源结点的消息，及其签名毋，五JL，2，M，盼则该攻击者就能利用这些消息线性组合成其它任意的消息因为源消息可由攻击者自行任意选择，并利用签名的同态性构造组合消息的签名。反之，若攻击者能伪造任意的消息，显然攻击者就可以伪造源消息了，因为源消息只是任意消息中的一种特殊情况。综上所述，我们可为该安全性的证明重新建立如下模型S为任一源结点，其私钥为SK，SKAVR，其中，A，由PKG秘密选择。公钥为七。对于消息X,X，L无用0，其哈希值计算如下谢，X，一兀三“G盏其签名计算如下Q一兀G翟J矗结点对签名的验证如下武汉理工大学硕士学位论文EA，GOEHID，XF，HO11我们给出安全网络编码签名算法的一般形式的定义定义51安全的网络编码签名算法在下面安全参数为七的安全游戏中，对于任意的概率多项式时间攻击算法，其获得胜利的优势可以忽略初始化挑战者4计算TPK,SK6GEN1K，并将础发送给攻击者只询问攻击者F选择子空间形C掣“，挑战者4随机的选取代号汹，并将磁和签名Q|SIGNSK，K，A,返回给F。输出攻击者F输出代号谢，签名仃幸以及向量XF”。下面将证明，只要CDHP问题无法被破解，本算法就能抵抗来自任意中间结点的污染攻击。定理52如果存在攻击者以概率成功的伪造消息及签名，那么必存在算法A可以以与概率S相关的概率破解CDHP问题。由于本算法模型中的哈希函数存在确定性、有效性且输出服从均匀分布，因此，我们可以利用随机预言模型45】来证明该定理。证明令，为攻击者，可以以概率S来破解本算法，则我们可以利用算法A以概率S来破解CDHP问题，其方法如下将GL，G2，E，岛H，GO，K向算法A公开，其中七90一G。，一G；，私钥娃对彳保密，么随后为系统设定公钥为尸肛冠岛GO