对一种背包公钥密码分析和改进

《对一种背包公钥密码分析和改进》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、对一种背包公钥密码的分析和改进费向东通信作者：费向东，feixd0669@sina.com，电话：18913742812，丁燕艳，潘郁（南京工业大学经济与管理学院，南京210009）摘要：分析一个称为随机背包的公钥密码算法，阐述背包公钥序列是由初始序列运算变换来的，初始序列存在冗余度，因此背包公钥序列不可能是完全随机的。目前大多数被破译的背包公钥算法只使用了属于混乱技术的模乘运算，这不足以隐藏初始序列的冗余度，利用这些冗余度是破译成功的必要条件。为此，本文引入加法扩散技术以分散始序列的冗余度，设计了新的公钥密码算法，攻击者

2、在破译过程中无法利用该冗余度。关键词：背包公钥密码；随机；冗余度；模乘运算；混乱；扩散中图分类号：TN918.1AnalysisandimprovementofaknapsackPublic-keyCryptosystemFeiXiang-dong,DingYan-yan，PanYu(SchoolofEconomicsandManagement,NanjingUniversityofTechnology,210009)Abstract：Analyzingaso-calledrandomknapsackpublic-keyc

3、ryptosystem，itisexpoundedthataknapsackpublic-keysequenceisgainedbytransforminganinitialsequencewithredundancy，henceaknapsackpublic-keysequenceisimpossiblyrandom.Sofar，mostknapsackcryptosystemsthathavebeenbrokenonlyuseconfusion，suchasmodularmultiplication，ascannotc

4、oncealtheredundancyoftheinitialsequenceadequately.Itisnecessarytoutilizetheredundancyforbreakingthecryptosystemsuccessfully.Therefore，additiondiffusionisintroducedinthispapertodiffusetheredundancyofaninitialsequence.Anewknapsackpublic-keycryptosystemwithdiffusioni

5、sdevised，sothattheadversarycannotmakeuseoftheredundancywhenbreakingthecryptosystem.Keywords:Knapsackpublic-keycryptosystem；Radom；Redundancy；Modularmultiplication；12Confusion；Diffusion；1引言公钥密码是确保信息安全和网络安全的重要技术，背包公钥作为最早提出的公钥密码之一，曾经是业界的希望和热点，但大多数背包公钥算法都被破译了[1]。背包公钥的安

6、全性是基于求解子集和问题的困难性，设计思想通常是把易解背包问题伪装成一个看似困难的背包问题，这一伪装方法就是嵌入陷门，陷门信息作为私钥仅被合法接收者掌握，运用它可以把该问题恢复成一个易解背包问题，通过解该易解背包问题重构明文；而对于非法接收者来说，从密文恢复明文就相当于解一个困难的背包问题。但存在着以下难题：如果陷门隐藏得不充分，则攻击者可以从公钥出发求解出对应的陷门信息；如果隐藏得充分，则背包密度可能降低，Coster等人证明若背包密度小于0.9408的背包公钥系统都易遭受低密度子集和攻击[2]，而若背包密度大于1，又带

7、来解密不唯一的问题。因此，构造一个安全的背包公钥密码系统异常困难，业内普遍认为背包公钥算法已经死亡。但由于背包公钥算法的快速加解密优势和背包问题的NPC性质，特别适合应用于物联网等资源受限的场合，故背包公钥算法仍然具有相当的吸引力。最近，王保仓等学者提出了基于随机背包的公钥加密算法[3]（以下简称“王背包算法”），认为该算法具有如下优点：加解密速度快；基于随机背包问题而不是易解背包问题构造的；在攻击者不掌握私钥情况下该密码算法能抵抗直接求解背包问题的攻击，包括低密度攻击和联立丢番图逼近攻击等；证明攻击者能够恢复私钥信息与攻

8、击者能够分解一个大整数是等价的。总之，该算法是一个安全高效的公钥加密算法。如果一个背包密码算法是真正基于随机背包而不是基于易解背包问题的，那么攻击者从公钥出发所进行的推断将无法验证是否正确，必然是无法破译的。但本文指出，王背包算法的构造并不是随机的，公钥隐藏着陷门信息。分析表明，运用格规约算法[4]，再