夏伟 潘瑜

1青海师范大学计算机学院 青海 810000 2江苏理工学院计算机工程学院 江苏 213001

0 引言

自1978年Merkle和Hellman首先提出了一个现在称为M-H背包体制的密码算法之后，基于背包的密码一直是密码研究者研究的热点，研究人员设计出许多基于背包问题的密码方案。虽然M-H背包方案以及它的一些改进算法在20世纪80年代初被Shamir等人给破译了，但随后仍有不少其他改进方案被提出来。既然基于背包的公钥密码体制不安全，为什么大量的研究人员还在进行研究，提出改进方案呢？分析其中原因，发现有三点：第一，背包密码体制加解密非常迅速，实用性很强；第二，背包密码本身是基于背包问题的，背包问题的NPC(NP完全性)特性使其完全可以应用到加密体制中去；第三，现实中有很多资源受限制的应用环境，比如内存受限，时间受限等等，这些都为背包密码提供了很好的实用环境。所以，背包密码体制的研究者依然层出不穷，他们都想找到一种相对比较安全的改进算法来实现背包密码算法的安全应用。

1 王氏密码的改进算法

1.1 算法介绍

丁燕艳等人在文献[1]中对王氏密码进行了安全性分析，说明了仅通过模乘运算与中国剩余定理构造的背包公钥算法都是不安全的，原因在于不能充分隐藏初始序列的冗余，存在安全漏洞。他们提出了要引进扩散技术，以分散初始序列的冗余度，使破译者难以利用，从而提出了王氏密码的一种改进算法。

1.2 算法描述

1.2.1 密钥生成算法