安全背包公钥密码的要点及设计.docVIP

PAGE  PAGE 11 安全背包公钥密码的要点和设计 费向东基金项目：江苏省软科学研究计划项目(BR2010080) 费向东（1966.11-），男，江苏无锡人，高级工程师，工学硕士，研究方向为密码算法与安全议， HYPERLINK mailto:feixd0669@ feixd0669@ ，潘郁 （南京工业大学经济与管理学院，南京 210009） 摘要：为提高背包密码的安全性，本文依据背包密码以往失败的原因，列举安全背包公钥的要点：运用混乱和扩散技术充分隐藏初始序列及其冗余度；提高背包密度；模数必威体育官网网址；基于超递增序列的背包密码的安全性不依赖初始序列的必威体育官网网址。提出了一个背包密码的可证明安全性的启发性方法。据此，设计了一个新型背包密码，该密码由模乘运算实现混乱，由基于二元一次不定方程的难解函数实现扩散，充分隐藏初始序列及其冗余度，攻击者破译该背包密码的难度规约为求解此难解函数，同时能达到较高的背包密度，常规的破译方法无效。 关键词：背包公钥密码；安全要点；可证明安全性；模乘运算；二元一次不定方程；难解函数 中图分类号：TP309.7；TN918.4 The Outline and Design of Secure Knapsack Public-key Cryptosystems FEI Xiang-dong ，DING Yan-yan，PAN Yu (1.College of Economics and Management, Nanjing University of Technology, 210009) Abstract：In order to boost the security of knapsack public-key cryptosystem（KPC for short），this paper listed the security outline of KPC according to the causes that they had failed，that is，concealing the redundancy of initial sequence adequately by confusion and diffusion；improving the density of KPC；keeping the modulus secret；the super-increasing KPC security independent of the confidentiality of initial sequence. A heuristic provable security method of KPC was proposed. Accordingly，a new KPC was designed. Modular multiplication was adopted for confusion，and a difficult solution function based on linear indifinite equation in two unknowns for diffusion，thus the redundancy of the initial sequence was concealed adequately. The difficulty for an adversary to break it is reduced to that of breaking the difficult solution function.Meanwhile，a higher knapsack density was reached. Conventional attacks were avoided. Key words: knapsack public-key cryptosystem ；security outline ；provable security ；modular multiplication ；linear indifinite equation in two unknowns；difficult solution function 0 引言 目前在用的公钥密码都是基于因子分解或离散对数问题的，存在着如下不足：一是Shor证明量子计算机能有效地进行因子分解和求解离散对数[1]，一旦量子计算机面世，则目前的公钥密码全部无法使用。而就在最近，IBM公司宣布在量子计算机的研究方面取得重大突破，已开发出可达到“实用量子计算机”最低标准的设备[2]；二是目前在用的公钥密码计算量大，运算速度慢，难以适应资源受限的场合。 背包公钥密码以背包问题的NPC（NP-complete