随机散列函数安全性与签名者作弊

《随机散列函数安全性与签名者作弊》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10期李志敏等：随机散列函数安全性与签名者作弊·107·随机散列函数安全性与签名者作弊李志敏，王励成，郑世慧，杨义先（北京邮电大学网络与交换技术国家重点实验室信息安全中心，北京100876）摘要：现有对抗碰撞散列函数的攻击，严重威胁到先“散列”再“签名”的签名算法的安全性。使用随机散列构造RMX来构造此类签名算法的安全性可以不依赖于底层散列函数的离线碰撞稳固性，但前提必须假设签名者不作弊。通过改变随机数的选取方式以及增加消息提供者的签名验证对使用RMX算法的签名算法进行了改进，改进后的算法不需要再假定

2、签名者是诚实的。此外，对Halevi等人提出的随机函数构造的安全性进行了研究，并给出了关于该构造的一个安全紧规约。关键词：散列函数；先“散列”再“签名”的数字签名算法；随机散列法；RMX中图分类号：TP309.7文献标识码：A文章编号：1000-436X(2008)10-0101-07Securityofrandomizedhashingandsigner’scheatingLIZhi-min,WANGLi-cheng,ZHENGShi-hui,YANGYi-xian(InformationSecuri

3、tyCenter,StateKeyLaboratoryofNetworkingandSwitchingTechnology,BeijingUniversityofPostsandTelecommunications,Beijing100876,China)Abstract:Thecollisionattacksagainstpopularhashfunctionshaveaprofoundeffectonthesecurityofhash-then-signdigitalsignatures.Thera

4、ndomizedRMXscheme,whenusedinconjunctionwithhash-then-signsignatureschemes,freestheseschemesfromtheircurrentessentialdependencyonfullcollisionresistance,ontheassumptionthatthesignerdoesn’tcheat.RMXschemeisenhancedthroughchangingthechoosemethodoftherandomv

5、alueaswellastheverificationprocessorbymessageprovider.Thesecurityoftheenhancedschemedoesnotneedtheassumptionthatthesignerishonestatall.Inaddition,thesecurityofanotherrandomizedconstructionisdiscussedandatightreductionisalsogivenout.Keywords:hashfunction;

6、hash-then-signsignatureschemes;randomhashing;RMX第10期李志敏等：随机散列函数安全性与签名者作弊·107·1引言收稿日期2008-06-02；修回日期：2008-09-24基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB311203）；国家自然科学基金资助项目（90718001）；高等学校学科创新引智计划资助项目（B08004）FoundationItems:TheNationalBasicResearchProgramofC

7、hina(973Program)(2007CB311203);TheNationalNaturalScienceFoundationofChina(90718001);The111ProjectofChina(B08004)散列函数H，可作用于任意长度的消息M，并返回固定长度的散列值H(M)。散列函数在数字签名方案中有非常广泛的应用，现有实际的签名算法如RSA，DSA等都遵循着先“散列”再“签名”的模式：首先使用散列函数将消息散列，然后对散列值进行签名。此时如果消息M，M¢对于某个散列函数具有相同的散列

8、值，那么当使用对应的签名算法时，M，M¢有相同的签名。因此签名算法要求底层使用的散列函数是抗碰撞的。然而现有对抗碰撞散列函数的攻击[1~8]第10期李志敏等：随机散列函数安全性与签名者作弊·107·，特别是对MD5，SHA-1的分析使人们意识到签名体制的安全性完全依赖于底层散列函数的离线抗碰撞性是一件非常危险的事情。为了降低签名算法对散列函数的离线抗碰撞性的依赖，Halevi和Krawczyk[9]于AsiaCrypt’06上提出了“随机散