浅谈背包公钥密码体制

背包密码体制之背包算法姓名：张全英学号：20143967专业：信息与计算科学1班学院：数学与信息科学摘要：网络和信息安全正在成为一个国家政治、军事、经济以及社会生活正常运行的基础,它将是一个国家综合实力的重要体现。而密码学是信息安全的核心。公钥密码又是将加密、解密密钥甚至加密、解密函数分开,用户只保留解密密钥,而将加密密钥和加密函数一起公之于众,是密码学的重要组成部分。背包公钥和RSA一样是著名的公钥体制之一,特别是背包公钥的安全基础是背包问题,这是一个NP难问题。虽然在提出不久就遭到破解,但是在提出的背包公钥系统的改进方案中依然有几个被证明是安全的。背包公钥是首个把NP问题用于公钥密码的密码体制,而其他现阶段应用的公钥密码体制都是基于因式分解或离散对数问题的,他们都不是NP问题构造的,因此背包公钥体制的研究是十分有意义的。本文从背包体制的常用攻击方法入手,寻找被破解的原因,并针对这些原因提出了新的构造思路,利用非超递增序列构造背包体制。利用非超递增序列构造背包公钥有2个必须解决的问题是加密结果的不唯一性和解密的困难性。本文对一种同余多模背包序列进行分析,并利用得出的性质构造一种新的L序列,并证明了L序列能解决以上2个问题,并提出了利用L序列构造背包公钥体制的方案。为了加快加解密速度,还提出了模M和W-1的逆向构造算法。然后给出了非超递增背包公钥体制的模拟实现。关键字：模逆，欧几里德算法，同余式，超递增序列目录：1.公钥密码的原理2.公钥密码的数学基础：一个公开密钥密码系统必须满足的条件是：A.通讯双方A和B容易通过计算产生出一对密钥（公开密钥K1，私钥密钥K2）。B.在知道公开密钥K1和待加密报文M的情况下，对于发送方A，很容易通过计算产生对应的密文：C.C=Ek1（M）D.接收方B使用私有密钥容易通过计算解密所得的密文以便恢复原来的报文：E.M=Dk2（C）=Dk2[Ek1（M）]F.除A和B以外的其他人即使知道公钥k1，要确定私钥K2在计算上也是不可行的。G.除A和B以外的其他人即使知道公钥k1和密文C，要想恢复原来的明文C在计算上也是不可行的。3.数论基础知识：这些要求最终可以归结到设计一个单向陷门函数。4.单向函数：单项陷门函数：一个单向函数是满足下列条件的函数：它将一个定义域映射到值域，使得每个函数值有一个唯一的原像，同时还要满足下列条件：函数值计算很容易，而逆计算是不可行的。所谓单向陷门函数是这样的函数，即除非知道某种附加的信息，否则这样的函数在一个方向上容易计算，而在另外的方向上要计算是不可行的。有了附加的信息，函数的逆就可以在多项式时间内计算出来。一个实用的公开密钥密码系统的建立和发展依赖于找到一个单向陷门函数。5.公开密钥密码分析6.公钥密码的的应用和优缺点7.背包问题（KnapsackProblem）：贪心算法程序等引言：基于背包密码算法是密码学历史上最早被设计出来的几个公钥密码算法之一.由于背包密码的快速加解密优势和背包问题是NP完全问题,很长一段时间内背包算法受到普遍的关注.自从Hellman提出第一个背包算法以来,密码学界提出了很多背包型加密算法.然而,这些背包算法易于遭受低密度子集和攻击、GCD攻击、联立丢番图逼近攻击以及正交格攻击等.背包密钥密码体制所依赖的困难问题,大多数公钥密码体制可以分为两大类:一类是建立在数论问题基础之上,另一类则以背包问题为基础.这两种类型的公钥密码体制各数论难题的公钥密码系统保密性较强,但加、解密速度比较慢;基于背包问题的公钥密码系统的加、解密速度较快,但随着各种攻击的出现,其安全性似乎越来越得不到保障.基于此,为了兼顾加、解密算法的速度和安全性,对基于背包问题的现有公钥密码算法和GF(p)上椭圆曲线密码体制进行了深入的研究。正文：公钥密码体制的核心思想是：加密和解密采用不同的密钥。这是公钥密码体制和传统的对称密码体制最大的区别。对于传统对称密码而言，密文的安全性完全依赖于密钥的保密性，一旦密钥泄漏，将毫无保密性可言。但是公钥密码体制彻底改变了这一状况。在公钥密码体制中，公钥是公开的，只有私钥是需要保密的。知道公钥和密码算法要推测出私钥在计算上是不可行的。这样，只要私钥是安全的，那么加密就是可信的。显然，对称密码和公钥密码都需要保证密钥的安全，不同之处在于密钥的管理和分发上面。在对称密码中，必须要有一种可靠的手段将加密密钥（同时也是解密密钥）告诉给解密方；而在公钥密码体制中，这是不需要的。解密方只需要保证自己的私钥的保密性即可，对于公钥，无论是对加密方而言还是对密码分析者而言都是公开的，故无需考虑采用可靠的通道进行密码分发。这使得密钥管理和密钥分发的难度大大降低了。两种密码体制的特征对比表1将对称密码和公钥密码的特征进行了对比。如前所述，公钥密码体制使用两个密钥，习惯上，为了将其与对称密码体制中的密钥相区分，把公钥密码体制中使用的两个密钥分别称为公钥和私钥。公钥是可公开的，而私钥则是要保密的。公钥密码的两种基本用途公钥密码的两种基本用途是用来进行加密和认证。为了便于说明，不妨假设消息的发送方为A，相应的公钥对为（PUA,PRA）。这里，PUA表示A的公钥，PRA表示A的私钥。同理，假设消息的接收方为B，相应的公钥对为（PUB,PRB）。其中，PUB表示B的公钥，PRB表示B的私钥。对于A而言，既知道自己的公钥PUA，也知道B的公钥PUB。通常，就将A所知道的公钥集合称为公钥环。当需要对消息进行加密时，A从自己的公钥环中取出接收方的公钥，对消息进行加密，然后将消息发送给接收方。接收方收到加密消息后，用自己的私钥对密文进行解密。这个过程如图1所示。公钥密码体制原理简介及补遗-2-方为A，相应的公钥对为（PUA,PRA）。这里，PUA表示A的公钥，PRA表示A的私钥。同理，假设消息的接收方为B，相应的公钥对为（PUB,PRB）。其中，PUB表示B的公钥，PRB表示B的私钥。对于A而言，既知道自己的公钥PUA，也知道B的公钥PUB。通常，就将A所知道的公钥集合称为公钥环。当需要对消息进行加密时，A从自己的公钥环中取出接收方的公钥，对消息进行加密，然后将消息发送给接收方。接收方收到加密消息后，用自己的私钥对密文进行解密。这个过程如图1所示。图1公钥密码用于加密由于A是用B的公钥PUB对消息进行加密，因此只有用B的私钥PRB才能解密密文C，而B的私钥PRB是由B秘密保存的。由于攻击者没有B的私钥PRB，因此攻击者要想仅根据密文C和B的公钥PUB解密消息是不可能的。由此，就实现了保密性的功能。除了用于实现保密性之外，公钥密码还可以用来实现认证功能。过程如图2所示对比图1，可以看到用公钥密码实现认证和用于保密的区别。最主要的不同在于加解密密钥的使用上，当用公钥密码实现保密功能时，是用接收方的公钥对消息进行加密，接收方用自己的私钥对消息进行解密；而当用公钥密码实现认证功能时，是用发送方的私钥对消息进行加密，接收方收到之后，用发送方的公钥恢复出明文消息M。由于只有发送方A拥有私钥PRA，因此只要接收方B能够正确解密出密文C，就可以认为消息的确是由发送方A发出的。这样就实现了对发送方的身份的认证。不过，这种简单的公钥认证模型的问题是：第一，这种方式只能对发送端进行认证；第二，由于攻击者也可以知道A的公钥，因此攻击者也可以解密出密文消息C，也就是说，这里只能实现认证能力，而无法实现保密能力。如果要同时实现保密和认证功能，需要对消息进行两次加密。应满足的条件公钥密码应满足的5个基本条件是由Diffie和Hellman给出的，这里，假设消息的发送方为A，消息的接收方为B：z产生密钥对（公钥PU，私钥PR）在计算上是容易的；z已知B的公钥PUb和要发送给B的消息M，A产生相应的密文在计算上是容易的：C=E(PUb,M)z接收方B用自己的私钥PRb解密所接收的密文以恢复明文消息在计算上是容易实现的：M=D(PRb,C)=D[PRb,E(PUb,M)]z假设攻击者已知公钥PUb，要确定出对应的私钥PRb在计算上是不可行的；z假设攻击者已知公钥PUb和密文C，要恢复明文M在计算上是不可行的；以上5个条件就是公钥密码的基本要求。通常，现代公钥密码还满足以下条件：z既可以用公钥作为加密密钥，也可以用私钥作为加密密钥。如果用公钥作为加密密钥，那么私钥就是解密密钥；如果用私钥作为加密密钥，那么公钥就是解密密钥。比如，著名的RSA密码就满足上述附加条件。但是，这一条件并不是必须的。RSA的基本数学原理公钥密码体制的代表当数RSA密码算法。RSA算法从提出至今已有将近三十年历史，是使用最广泛的通用公钥加密方法。RSA是一种分组密码，其明文和密文的基本单元都是0到n-1之间的整数，一般而言，n21024。因此，每一个分组的大小必须小于或等于log2n，由于n通常小于21024，因此实际中使用的RSA算法的分组大小都小于等于1024比特位。假设明文分组为M，密文分组为C，则RSA加密过程如下：C=Memodn解密过程为：M=Cdmodn=(Me)dmodn=Medmodn通信的双方均已知n，发送方已知e，只有接收方知道d。由此，公钥加密算法的公钥为PU={e,n}，私钥为PR={d,n}。根据前面所述的公钥密码应满足的条件可知，RSA算法必须能够满足下列条件：1.可以找到e,d和n，使得对所有Mn，有Medmodn=M；2.对于所有Mn，计算Memodn和Cdmodn是容易的；3.由e和n确定d在计算上是不可能的。加解密的过程如图3所示。0-1背包问题【问题描述】：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。一、贪心算法贪心算法是我们在《算法设计技巧与分析》这门课中所学习到的几种重要的算法之一，顾名思义，贪心算法总是作出在当前看来最好的选择。也就是该算法并不从整体最优考虑，它所作出的选择只是在某种意义上的从局部的最优选择，寻找到解决问题的次优解的方法。虽然我们希望贪心算法得到的最终结果也是整体最优的，但是在某些情况下，该算法得到的只是问题的最优解的近似。1、贪心法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。2、该算法存在问题：1.不能保证求得的最后解是最佳的；2.不能用来求最大或最小解问题；3.只能求满足某些约束条件的可行解的范围。2、实现该算法的过程：Begin从问题的某一初始解出发；while能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解3、关于贪心算法在背包问题中的应用的探讨(1)问题描述0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包(1)或不装入背包(0)。不能将物品i装入背包多次，也不能只装入部分的物品i。背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。背包问题可以定义如下：给出n个大小为s1,s2,…,sn,值为v1,v2,…,vn的项目，并设背包容量为C，要找到非负实数x1,x2,…,xn,使和在约束下最大。(2)动态规划解决方案：是解决0/1背包问题的最优解(i)若i=0或j=0,V[i,j]=0(ii)若jsi,V[i,j]=V[i-1,j](仅用最优的方法，选取前i-1项物品装入体积为j的背包，因为第i项体积大于j,装不下这一项，所以背包里面的i-1项就达到最大值)(iii)若i0和j=si,Max{V[i-1,j],V[i-1,j-si]+vi}(第一种情况是包中的