一种确定的背包公钥密码体制的破译方法-论文.pdf

《一种确定的背包公钥密码体制的破译方法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第24卷第6期长春大学学报Vo1．24No．62014年6月J0URNALOFCHANGCHUNUNIVERSITYJune2014一种确定的背包公钥密码体制的破译方法陈成钢(天津城建大学理学院，天津300384)摘要：背包公钥密码体制的破译方法不同于一般的统计分析方法，它主要利用公开(加密)密钥的超可达性，直接由公开密钥破译得到私人(解密)密钥，从而达到破译密文的目的。关键词：干扰点；目标；递增；超递增；可达；超可达中图分类号：TN918．1文献标志码：A文章编号：1009—3907(2014)06—0763—031背包问题1．1背包

2、问题定义公钥密码系统一直是密码学研究的重要领域之一。1979年，Merkle和Hellman⋯提出背包公钥密码体制，由于背包序列在转换机制上有弱点，1983年Shamir_2完全破译了Merkle-Hellman的背包公钥密码体制。但由于基于背包问题的公钥密码系统加解密速度快，许多更加复杂的公钥密码系统被提了出来]。同样，许多破译背包系统地方法也被提了出来¨][。本文利用密钥的超可达性，提出了一个新的确定的破解背包公钥密码体制的方法。所谓背包问题：即给定重量分别为0，，⋯，o的n个物品，现在能否把这n个物品中的几件放入一个背包中使之等于

3、一个给定的重量￡?n这个问题也就是求=0或1，i=1，2，⋯，n使满足∑i口=L，其中0，0，⋯，o和都是正整数。显然，背包问题的求解是NP完全问题，如果直接对其求解，以n=100为例，用每秒搜索10种的计算机进行穷举，一年只能完成3．1536×10H次，而完成所有的搜索，共需2÷(3．1536×10¨)=4．02×10(年)，这在时间上显然是不允许的。1．2递增、超递增序列我们称0，，⋯，为递增(超递增)序列，如果它满足卜10>口卜1(aj>∑0)2_，n，称满足上式的A=(0，口：，⋯，口)为递增(超递增)向量。1．3超递增背包问题

4、的求解并非所有的背包问题都是难解的，如果背包密钥A=(口，0：，⋯，口)为超递增，那么此背包问题就是超递增背包问题。对于超递增背包问题有快速的求解方法：(1)设L。=L，比较。与0，如果L。口，那么取=1，否则，取=0；(2)设L=L0一0，比较。与口一，如果L。n一，那么取一：1，否则，取=0；(3)如此下去，得到一系列的L，，i=，n一1，⋯，1，则向量X=(。，⋯，)就是要求的解(明文)。例如：L=120，A=(3，5，11，31，75，140)，那么由上面的方法可解得X=(1，0，1，1，1，0)。2背包公钥密码体制公钥密码体制

5、也叫非对称的密码体制，它是这样设计的：用作加密的密钥不同于用作解密的密钥，而且解密的密钥不能根据加密密钥计算出来(至少在合理假定的时间内)。加密密钥能够公开，任何人都可以用收稿日期：2014-03-09作者简介：陈成钢(1976．)，男，山东菏泽人，副教授，硕士，主要从事大学数学教学和概率统计等方面的研究。长春大学学报第24卷加密密钥加密信息，但只有相应的解密密钥才能解密信息。在背包公钥密码体制中，解密密钥为超递增增向量，但加密密钥却不是超递增增向量，利用求解一般背包问题的复杂性，使得只有持有有解密密钥的合法用户才可以解密得到明文，而其

6、他持有加密密钥的人无法解密得到明文。2．1密码的选取解密密钥为三元组(C，t，P)，其中C=(c，c，⋯，c)(C，i=1，2，⋯，n为正整数)是超递增向量，P>t>1，P>∑c且t，P互素。由解密密钥可得加密密钥B=(b，b：，⋯，b)=(Czmodp)，其中“rood”为“模”运算，为满足ztmodp=1的最小正整数。2．2加密背包公钥密码的加密就是由加密密钥B乘以明文的转置得到密文L，即nL=BX=∑b。2．3解密背包公钥密码由密文￡和解密密钥(C，t，P)求得明文的解密方法如下：(1)先求间接密文L=ztmodp；(2)由间接密

7、文￡和超递增序列c，用1．3超递增背包的解密方法，可求得明文向量3背包公钥密码体制的一种破译方法3．1预备知识在讨论破译方法前，我们先给出以下定义、引理和定理，引理和定理的详细证明见参考文献¨]。定义3．1称A=(口，0，⋯，口)为背包向量，如果口，i=1，2，⋯，n为正整数，>2。定义3．2对于n维背包向量A=(n，口，⋯，口)，如果i一1口>∑03sin(3．1)成立，那么i成为A的干扰点．定义3．3背包向量B=(6，b，⋯，6)是(A，，m)可达的当且仅当A=(a，口：，⋯，n)是超递增向量，z，m为正整数，m2且。，m互素时，其

8、中bi=(勰imodm)i：1，2，⋯，n。记为A—}(：，m)更进一步地，如果4是超递增的且m>口，那么B是(4，z，m)是超可达的。记为t=IA—}B(s，：，m)定义3．4A，z，m如定义3所述，如果