自从1978年MERKLE和HELLMAN率先提出了MH背包密码体制以来,一直到20世纪90年代,背包密码都是公钥密码方面的最热门的研究方向,密码学界认为它是最有发展前途的密码算法。它和RSA公钥体制被认为是两个最具潜力的公钥体制。公开密钥密码体制非常适用于微机系统和分布式控制的加密,现在已成为全世界计算机密码学研究的重点,而基于背包密码公开密钥密码体制与公钥密码体制相比,具有可快速求解的特点。虽然超递增背包具有相当的安全隐患,并且现有的一次背包问题大多被破解,因为其自身具有加解密速度快,易于软硬件实施等诸多优点,一些钟爱于背包密码的学者仍然在进行不断的探索和研究,试图找到更为安全快速的背包公钥密码算法。本论文选题围绕背包问题的安全性和效率展开。对关于背包问题的公钥加密体制进行了详细的研究与分析,在原来的基础上,对已有的背包密码加密算法进行了改进。本文提出了一些新型的背包密码方案,这些方案的实施既能提高背包体制的安全性不高问题,同时又能保持背包体制的优点,最后通过C代码实现了算法。论文的主要工作包括以下几个方面：一、关于背包问题的公钥加密体制研究基于背包问题的背包密码是第一个公钥系统。一般背包问题的英文为Knapsack problem (KP),是一种组合优化的NP完全问题。背包问题可以描述为：给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。它的求解方法可以概括为精确算法和近似算法,其中精确算法有动态规划法、回溯法、分支限界法等,近似算法有遗传算法、贪婪法、粒子群算法、蚁群算法等。由于精确算法的时间复杂性和空间复杂性等缺点,近年来利用近似算法求解背包问题成为重点。背包公钥序列和一般的随机序列有所不同,背包公钥序列是由初始序列通过陷门函数生成的,而非法解密者不知道初始序列。我们可以把初始序列到背包公钥序列的过程也看作是一个加密过程,初始序列为明文,陷门函数为加密算法,背包公钥序列为密文,从计算的复杂度来讲,如果初始序列到公钥序列的过程被看做是没有安全隐患的,那么从公钥出发来逆向求解初始序列的过程(陷门函数的逆过程)可以看作是不可能的,算法实现起来的时间和空间复杂度极大,这样就把该背包问题变成了一个NPC问题,相应的,这个算法就会被看做是一个值得使用的公钥算法。关于背包密码的主要问题便是它们的安全性问题。自从Merkle等人提出第一个基于背包问题的公钥密码方案以来,研究人员设计出许多基于背包问题的密码方案。该类方案易于受到Shamir攻击和低密度攻击,设计抵抗这些攻击的新型背包公钥密码方案一直是公钥密码研究的热点之一。二、设计了一种新型的背包密码方案,即方案3.1。构造一个新型的背包体制,实质上就是重新选择一个陷门函数,或者在原来的基础上加上一个或多个陷门函数。本论文选择一个新的陷门函数,即随机生成一个超递增序列A,选取数(Q,R),且满足Q>R并且Q与R互素,用(Q,R)将超递增序列A伪装成一个序列B,二者满足条件：通过bi对明文进行加密,形成密文。解密者知道私人密钥即原始的超递增序列A,需通过关系式的逆变换,即由bi推导出ai即可实现由密文到明文的推导,即解密操作。方案3.1具体描述为：密钥生成算法(1) 随机选取超递增序列A=(a1,…,an)；(2) 随机选取(Q,R),Q>R并且Q与R互素；(3) 由(A,Q,R)计算B=(b1,…,bn),使(4) 公钥为B,私钥为(A,Q,R)。加密算法(1) 明文为x=(x1,…,xn)∈{0,1}",接收方的公钥为B=(b1,…,bn);(2) 将密文发送给接收方。解密算法(1) 接收方计算(2) 则有：其中(3) 对每一个可能的r值,令SA=S+r,并由(A,SA)求解x=(x1,…,xn),若能求出合法的x,则将其加入候选解集合X；(4) 若X为空集,则无解；若X中只有一个解,则其即为明文x；否则,只能确定x∈X,此时必须通过认证手段才能唯一确定明文x。通过对算法进行误差分析得出：在解密过程中需要考虑到误差若能找到误差的上下限,则能确保解密的准确性。通过对方案3.1的实例测试,验证了该方案的可行性。三、对方案3.1进行的改进,即方案4.1。方案3.1有一个缺陷,那就是B中元素的大小关系与A中元素的大小关系是一致的,若bi<bj,则必有ai<aj。因此若A是超递增的,则B也很可能是超递增的,这导致该方案很容易被破解。此可对原方案进一步改进,思路是在方案3.1的基础上再增加一个模乘变换,改进后的方案如方案4.1：密钥生成算法(1) 随机选取超递增序列A=(a1,…,an)；(2) 随机选取0<W<M且gcd(M,W)=1；(3) 计算A’=(a1’,…,an’),使a’i=W·ai(mod M)；(4) 随机选取(Q,R), Q>R并且Q与R互素；(5) 由(A’,Q,R)计算B=(b1,…,bn),使(6) 公钥为B,私钥为(A,Q,R,M).加密算法(1) 明文为x=(x1,…,xn)∈{0,1}",接收方的公钥为B=(b1,…,bn);(2) 将密文发送给接收方。解密算法(1) 接收方计算, 则有：其中(2) 对每一个可能的r值,令s’A=S+r,计算SA=W-1·S’A(modM),然后由(A,SA)求解x=(x1,…,xn),若能求出合法的x,则将其加入候选解集合X；(3) 若X为空集,则无解；若X中只有一个解,则其即为明文x；否则,只能确定x∈X,此时必须通过认证手段才能唯一确定明文x。改进后的方案4.1在方案3.1的基础上增加了一个模乘变换,从而提高了算法的强度。四、对MH方案的改进,即方案5.1。通过对MH方案的攻击分析,可知攻击主要是针对其私钥背包为超递增序列、并且公钥背包是私钥背包经模乘变换得到,而模乘变换对“超递增”特性无法有效屏蔽所致。若能通过某种途径对超递增的私钥背包先行变换,使得变换后的背包不再具有超递增属性,然后再对之进行模乘变换,如此便可使对MH方案的攻击对新方案无效。但如此改进的难点在于：对私钥背包超递增属性的“破坏”,不应导致解密无法进行,即破坏必须是可恢复的。方案5.1的具体描述为：密钥生成算法(1) 随机选取δ=(δ1,…,δn)∈{0,1}";(2) 令任选超递增背包A=(r<a1,a2,…,an);(3) 随机选取奇数0<W<M且gcd(M,W)=1;(4) 令 △=[M/2],计算B=(b1,…,bn),其中bi=W(ai+δi·△)(mod M)(i=1,…,n);(5) 公钥为B,私钥为(A,δ)。加密算法(1) 明文x=(x1…,xn)∈{0,1}";(2) 密文解密算法(1) 计算S’=W-1 s(mod M),则必有：其中0≤r’≤r(3) 对每一个可能的0≤r’≤r值,分别令SA=(S’-r’)(mod M)和SA=(A’-△-r’)(mod M),然后由(A,SA)求解x=(x1,…,xn),若能求出合法的x,则将其加入候选解集合x；(4) 若X为空集,则无解；若X中只有一个解,则其即为明文x；否则,只能确定x∈X,此时必须通过认证手段才能唯一确定明文x。五、各方案应用模式的分析、实现和验证本文根据各方案的特点,分析了其应用模式：在实际应用中必须对确定算法进行“概率性”改造,即在加密算时引入“随机性”,以使对同一个明文的每次加密都能得到不同的密文。具体方法是在加密前对明文增加冗余信息,或在加密后对密文增加冗余信息,这里的填充应该是随机的,以便产生一个非确定的加密算法。论文使用C语言程序对各个算法加以实现,并给出了关键实现代码,从而实现了对算法的验证。