浅谈背包公钥密码体制全解.docx

浅谈背包公钥密码体制全解.docx

《浅谈背包公钥密码体制全解.docx》由会员分享，可在线阅读，更多相关《浅谈背包公钥密码体制全解.docx（25页珍藏版）》请在冰点文库上搜索。

浅谈背包公钥密码体制全解

背包密码体制之背包算法

姓名：

张全英

学号：

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之间的整数，一般而言，n<21024。

因此，每一个分组的大小必须小于或等于log2n，由于n通常小于21024，因此实际中使用的RSA算法的分组大小都小于等于1024比特位。

假设明文分组为M，密文分组为C，则RSA加密过程如下：

C=Me mod n 

解密过程为：

M=Cd mod n=（Me）d mod n=Med mod n 

通信的双方均已知n，发送方已知e，只有接收方知道d。

由此，公钥加密算法的公钥为PU={e,n}，私钥为PR={d,n}。

根据前面所述的公钥密码应满足的条件可知，RSA算法必须能够满足下列条件：

1.可以找到e,d和n，使得对所有M

2.对于所有M

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）若j

（iii）若i>0和j>=si,Max{V[i-1,j],V[i-1,j-si]+vi}（第一种情况是包中的i-1项已经达到最大值，第二种情况是i-1项占j-si的体积再加上第i项的总的价值，取这两种情况的最大值。

）

//sj和vj分别为第j项物品的体积和价值，C是总体积限制。

//V[i,j]表示从前i项{u1,u2,…,un}中取出来的装入体积为j的背包的物品的最大//价值。

[13]

（3）贪心算法解决背包问题有几种策略：

（i）一种贪婪准则为：

从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。

这种策略不能保证得到最优解。

例如，考虑n=2,w=[100,10,10],p=[20,15,15],c=105。

当利用价值贪婪准则时，获得的解为x=[1,0,0]，这种方案的总价值为20。

而最优解为[0,1,1]，其总价值为30。

（ii）另一种方案是重量贪婪准则是：

从剩下的物品中选择可装入背包的重量最小的物品。

虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。

考虑n=2,w=[10,20],p=[5,100],c=25。

当利用重量贪婪策略时，获得的解为x=[1,0],比最优解[0,1]要差。

（iii）还有一种贪婪准则，就是我们教材上提到的，认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。

有的参考资料也称为价值密度pi/wi贪婪算法。

这种策略也不能保证得到最优解。

利用此策略试解n=3,w=[20,15,15],p=[40,25,25],c=30时的最优解。

虽然按pi/wi非递（增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。

而且这是解决普通背包问题的最优解，因为在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。

（4）贪心算法解决背包问题的算法实现：

代码如下：

#includestructgoodinfo

{

floatp;//物品效益

floatw;//物品重量

floatX;//物品该放的数量intflag;//物品编号

};//物品信息结构体

voidInsertionsort（goodinfogoods[],intn）

{//插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序

intj,i;

for（j=2;j<=n;j++）

{

goods[0]=goods[j];

i=j-1;

while（goods[0].p>goods[i].p）

{

goods[i+1]=goods[i];

i--;

}

goods[i+1]=goods[0];

}

}//按物品效益，重量比值做升序排列

voidbag（goodinfogoods[],floatM,intn）

{

floatcu;

inti,j;

for（i=1;i<=n;i++）

goods[i].X=0;

cu=M;//背包剩余容量

for（i=1;i

{

if（goods[i].w>cu）//当该物品重量大与剩余容量跳出

break;

goods[i].X=1;

cu=cu-goods[i].w;//确定背包新的剩余容量

}

if（i<=n）

goods[i].X=cu/goods[i].w;//该物品所要放的量

/*按物品编号做降序排列*/

for（j=2;j<=n;j++）

{

goods[0]=goods[j];

i=j-1;

while（goods[0].flag

{

goods[i+1]=goods[i];

i--;

}

goods[i+1]=goods[0];

}

cout<<"最优解为:

"<

for（i=1;i<=n;i++）

{

cout<<"第"<

";

cout<

}

}

voidmain（）

{

cout<<"|--------运用贪心法解背包问题---------|"<

intj,n;floatM;

goodinfo*goods;//定义一个指针

while（j）

{

cout<<"请输入物品的总数量：

";

cin>>n;

goods=newstructgoodinfo[n+1];//

cout<<"请输入背包的最大容量：

";

cin>>M;

cout<

inti;

for（i=1;i<=n;i++）

{goods[i].flag=i;

cout<<"请输入第"<

";

cin>>goods[i].w;

cout<<"请输入第"<

";

cin>>goods[i].p;

goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比

cout<

}

Insertionsort（goods,n）;

bag（goods,M,n）;

cout<<"press<1>torunagian"<

cout<<"press<0>toexit"<>j;

}

}

[例]即教材例7.6,假如有容量为９（C=9）的背包，要装入４（n=4）种体积为２，３，４和５的物品，它们的价值分别是３，４，５和７。

对这个问题课本是用动态规划的方式给予实现通过列表格可知，有两种方案可以达到最优解，装物品价值为５和７或者是装入物品价值为３，４和５。

这样我们获得的价值是１２。

现在我们来讨论用上述贪心算法把这个问题看成普通背包问题进行讨论，以这个实例运行程序可以有这样的结果：

（WindowsXP系统，MicrosoftVisualC++2005

这样得到的结果是价值为3体积是２的放1,价值是３体积是４的放0.666667，价值是５体积是７的放１，最后得到的结果是占的体积是9.000001,（期望值是Ｃ＝９），而总的价值是12.66668，（动态规划我们得出的结论是12），所以我们可以看到用贪心算法解决普通背包问题时得到的解是最优解。

二、分支限界法

1、设计思想与分析：

对物品的选取与否构成一棵解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。

对此我们有以下几点结论：

A）分支限界法迭代次数与物品单位重量价值数组的取值范围关系紧密。

首先，按照搜索算法的理论知识，我们知道0－1背包问题是一个子集树问题，在最坏的情形下，我们在给定迭代次数不超过一个限制值（m）的话（在我们的算法中，迭代次数与算法过程中创建的部分子集树的结点数相同），我们所能解决的问题规模为[log（n+1）]-1,事实上，我们在实验中给定m＝100000，物品个数为n＝30，在特别情形下（即下面所要说的物品的单位重量价值非常均匀的情形下）迭代溢出的可能很大。

其次，我们的实验结论是物品的单位重量价值越均匀（即分布在一个较小的区间范围内），分支限界法所需的迭代次数越大。

而此时的贪心算法所得到的解的相对误差也越小，所以如果不是在严格要求求精确解或给定很小的精度范围内的解的话，不妨使用贪心算法先找一个近似解试试。

B）分支限界法迭代次数跟物品重量与背包容量的比关系紧密。

因为物品重量与背包容量的比越小，则背包能装的物品个数就越多，所生成的子集树的深度也就越大，因而在一般情况下（例如在剪枝率差不多的情况下）所需的迭代次数也就越大。

C）分支限界法迭代次数与背包容量占物品总重的百分比关系关系也很紧密，但同时还与其他参数有关，如上面提到的物品重量与背包容量的比等，它们之间的关系十分复杂。

我们只能笼统的说，分支限界法迭代次数随着背包容量占物品总重的百分比的增加总体上先升后降。

需要指出的，这只是最笼统的估计，事实上情形要复杂的多。

D）分支限界法解决问题的最大实际输入大小的小结。

在给定迭代次数不超过一个限制值（m）时，最坏的情形下（物品的单位重量价值非常均匀时）只能解决[log（m+1）]-1个实际输入大小的问题。

但在物品的单位重量价值的均匀性较为宽松时，我们的程序也能解决较大规模的问题，我们在实验中取m为100000时，一般都能以较大可能在这种宽松条件下解决好几百甚至上千的实际输入大小的问题。

但在物品的单位重量价值很均匀时，往往连30个物品都难以解决。

一般情形下，我们的程序能解决的问题规模大致为50左右，超过100时堆溢出的可能较大。

2、算法实现

#include

structgood

{

intweight;

intbenefit;

intflag;//是否可以装入标记

};

intnumber=0;//物品数量

intupbound=0;

intcurp=0,curw=0;//当前效益值与重量

intmaxweight=0;

good*bag=NULL;

voidInit_good（）

{

bag=newgood[number];

for（inti=0;i

{

cout<<"请输入第件"<

";

cin>>bag[i].weight;

cout<<"请输入第件"<

";

cin>>bag[i].benefit;

bag[i].flag=0;//初始标志为不装入背包

cout<

}

}

intgetbound（intnum,int*bound_u）//返回本结点的c限界和u限界

{

for（intw=curw,p=curp;num

{

w=w+bag[num].weight;

p=w+bag[num].benefit;

}

*bound_u=p+bag[num].benefit;

return（p+bag[num].benefit*（（maxweight-w）/bag[num].weight））;

}

voidLCbag（）

{

intbound_u=0,bound_c=0;//当前结点的c限界和u限界

for（inti=0;i

{

if（（bound_c=getbound（i+1,&bound_u））>upbound）//遍历左子树

upbound=bound_u;//更改已有u限界,不更改标志