安全背包公钥密码的要点和设计

《安全背包公钥密码的要点和设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、安全背包公钥密码的要点和设计费向东基金项目：江苏省软科学研究计划项目(BR2010080)费向东（1966.11-），男，江苏无锡人，高级工程师，工学硕士，研究方向为密码算法与安全议，feixd0669@sina.com，潘郁（南京工业大学经济与管理学院，南京210009）摘要：为提高背包密码的安全性，本文依据背包密码以往失败的原因，列举安全背包公钥的要点：运用混乱和扩散技术充分隐藏初始序列及其冗余度；提高背包密度；模数保密；基于超递增序列的背包密码的安全性不依赖初始序列的保密。提出了一个背包密码的可证明安全性的启发性方

2、法。据此，设计了一个新型背包密码，该密码由模乘运算实现混乱，由基于二元一次不定方程的难解函数实现扩散，充分隐藏初始序列及其冗余度，攻击者破译该背包密码的难度规约为求解此难解函数，同时能达到较高的背包密度，常规的破译方法无效。关键词：背包公钥密码；安全要点；可证明安全性；模乘运算；二元一次不定方程；难解函数中图分类号：TP309.7；TN918.4TheOutlineandDesignofSecureKnapsackPublic-keyCryptosystemsFEIXiang-dong，DINGYan-yan，PANYu

3、(1.CollegeofEconomicsandManagement,NanjingUniversityofTechnology,210009)Abstract：Inordertoboostthesecurityofknapsackpublic-keycryptosystem（KPCforshort），thispaperlistedthesecurityoutlineofKPCaccordingtothecausesthattheyhadfailed，thatis，concealingtheredundancyofini

4、tialsequenceadequatelybyconfusionanddiffusion；improvingthedensityofKPC；keepingthemodulussecret；thesuper-increasingKPCsecurityindependentoftheconfidentialityofinitialsequence.AheuristicprovablesecuritymethodofKPCwasproposed.Accordingly，anewKPCwasdesigned.Modularmu

5、ltiplicationwasadoptedforconfusion，andadifficultsolutionfunctionbasedonlinearindifiniteequationintwounknownsfordiffusion，thustheredundancyoftheinitialsequencewasconcealedadequately.Thedifficultyforanadversarytobreakitisreducedtothatofbreakingthedifficultsolutionf

6、unction.Meanwhile，ahigherknapsack11densitywasreached.Conventionalattackswereavoided.Keywords:knapsackpublic-keycryptosystem；securityoutline；provablesecurity；modularmultiplication；linearindifiniteequationintwounknowns；difficultsolutionfunction0引言目前在用的公钥密码都是基于因子分解或

7、离散对数问题的，存在着如下不足：一是Shor证明量子计算机能有效地进行因子分解和求解离散对数[1]，一旦量子计算机面世，则目前的公钥密码全部无法使用。而就在最近，IBM公司宣布在量子计算机的研究方面取得重大突破，已开发出可达到“实用量子计算机”最低标准的设备[2]；二是目前在用的公钥密码计算量大，运算速度慢，难以适应资源受限的场合。背包公钥密码以背包问题的NPC（NP-complete，NP完全性）性质和快速加解密优势成为解决以上不足的优选方案。因为Bennett等人证明量子计算机上也不存在求解NPC问题的有效算法[3]

8、。一个安全的背包密码在量子计算环境下同样是安全的。但背包密码屡被破译，安全性令人担忧，其生存和发展的前提解决安全性评价问题。目前评价公钥密码的安全性有两种方法，一是枚举安全性，把密码算法公布，一段时间后没有被破译，就认为该密码算法暂时是安全的；二是可证明安全性理论，就是把密码算法的安全性规约到一个公认的数学难题，可证