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

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