重新认识背包公钥密码的安全性  

Security reconsideration of knapsack public-key cryptosystem

作　　者：丁燕艳[1] 费向东[1] 潘郁[1] 

机构地区：[1]南京工业大学经济与管理学院,南京210009

出　　处：《计算机应用》2012年第3期694-698,共5页journal of Computer Applications

基　　金：江苏省软科学研究计划项目(BR2010080)

摘　　要：针对背包密码屡被破译的局面,分析了其中原因。指出背包公钥序列是由初始序列变换而来的,初始序列由易解背包形成,存在着冗余度,因此背包公钥序列不可能是完全随机的,利用这些冗余度是破译成功的必要条件,目前大多数被破译的背包密码只使用了模乘运算等混乱技术,这不足以隐藏初始序列的冗余度。为此引入了加法扩散技术,以分散初始序列的冗余度,使攻击者在破译过程中难以利用,举实例说明了项内扩散和项间扩散两种扩散技术。分析表明,运用扩散技术后,能抵御目前已知的攻击方法。Concerning the situation that knapsack public-key cryptosystem has been broken repeatedly,this paper analyzed the cause.It is expounded that a knapsack public-key sequence is generated by transforming an initial sequence composed of an easy knapsack problem with redundancy;hence,a knapsack public-key sequence is unlikely completely random.Currently,most broken knapsack cryptosystems only use confusion,such as modular multiplication,so as not to conceal the redundancy of the initial sequence adequately.It is necessary to utilize the redundancy for breaking a cryptosystem.Therefore,addition diffusion was introduced in this paper to diffuse the redundancy of an initial sequence,so that an adversary can not make use of the redundancy when breaking a cryptosystem.Inner-item diffusion and inter-item diffusion were illustrated.The analysis indicates the cryptosystem is secure against the known attacks with diffusion.

关 键 词：背包公钥密码 冗余度 模乘运算 混乱 扩散 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构] TN918.4[自动化与计算机技术—计算机科学与技术]