重新認识背包公钥密码的安全性.docVIP

重新认识背包公钥密码的安全性 摘 要:针对背包密码屡被破译的局面,分析了其中原因。指出背包公钥序列是由初始序列变换而来的,初始序列由易解背包形成,存在着冗余度,因此背包公钥序列不可能是完全随机的,利用这些冗余度是破译成功的必要条件,目前大多数被破译的背包密码只使用了模乘运算等混乱技术,这不足以隐藏初始序列的冗余度。为此引入了加法扩散技术,以分散初始序列的冗余度,使攻击者在破译过程中难以利用,举实例说明了项内扩散和项间扩散两种扩散技术。分析表明,运用扩散技术后,能抵御目前已知的攻击方法。 关键词:背包公钥密码;冗余度;模乘运算;混乱;扩散  security reconsideration of knapsack publickey cryptosystem  ding yanyan, fei xiangdong, pan yu* ( school of economics and management, nanjing university of technology, nanjing jiangsu 210009, china ) abstract: 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. key words: knapsack publickey cryptosystem; redundancy; modular multiplication; confusion; diffusion  0 引言 背包密码自1978年提出[1]直到20世纪90年代,一直是公钥密码领域的研究热点,被认为是最有前途的密码算法。背包密码的安全性是基于求子集和问题的困难性,设计思想是把易解背包问题伪装成一个看似困难的背包问题,其方法就是使用陷门。陷门信息作为私钥仅被合法接收者掌握,运用它可以把该问题恢复成一个易解背包问题,通过解该易解背包可重构明文;而对非法接收者来说,从密文恢复明文就相当于解一个困难的背包问题。但存在着以下难题:如果陷门隐藏得不充分,则攻击者可以从公钥出发求解出对应的陷门信息;如果隐藏得充分,则背包密度可能降低。coster等[2]证明背包密度小于0.9408的背包密码都易遭受低密度子集和攻击；而若背包密度大于1,又造成解密不唯一。因此,构造一个安全的背包密码异常困难,目前其中的绝大多数都被破译了,普遍认为背包密码的前景暗淡[3-4]。 背包公钥序列有别于随机数序列，因为前者是由初始序列变换而来的,并以此隐藏陷门。可以把初始序列看作被加密的消息,初始序列到公钥的变换过程可以