文档介绍：背包密码体制之背包算法姓名:张全英学号:20143967专业:信息与计算科学1班学院:数学与信息科学摘要:网络和信息安全正在成为一个国家政治、军事、经济以及社会生活正常运行的基础,它将是一个国家综合实力的重要体现。而密码学是信息安全的核心。公钥密码又是将加密、解密密钥甚至加密、解密函数分开,用户只保留解密密钥,而将加密密钥和加密函数一起公之于众,是密码学的重要组成部分。背包公钥和RSA一样是著名的公钥体制之一,特别是背包公钥的安全基础是背包问题,这是一个NP难问题。虽然在提出不久就遭到破解,但是在提出的背包公钥系统的改进方案中依然有几个被证明是安全的。背包公钥是首个把NP问题用于公钥密码的密码体制,而其他现阶段应用的公钥密码体制都是基于因式分解或离散对数问题的,他们都不是NP问题构造的,因此背包公钥体制的研究是十分有意义的。本文从背包体制的常用攻击方法入手,寻找被破解的原因,并针对这些原因提出了新的构造思路,利用非超递增序列构造背包体制。利用非超递增序列构造背包公钥有2个必须解决的问题是加密结果的不唯一性和解密的困难性。本文对一种同余多模背包序列进行分析,并利用得出的性质构造一种新的L序列,并证明了L序列能解决以上2个问题,并提出了利用L序列构造背包公钥体制的方案。为了加快加解密速度,还提出了模M和W-1的逆向构造算法。然后给出了非超递增背包公钥体制的模拟实现。关键字:模逆,欧几里德算法,同余式,超递增序列目录::一个公开密钥密码系统必须满足的条件是:(公开密钥K1,私钥密钥K2)。,对于发送方A,很容易通过计算产生对应的密文:=Ek1(M):=Dk2(C)=Dk2[Ek1(M)],要确定私钥K2在计算上也是不可行的。,要想恢复原来的明文C在计算上也是不可行的。:这些要求最终可以归结到设计一个单向陷门函数。:单项陷门函数:一个单向函数是满足下列条件的函数:它将一个定义域映射到值域,使得每个函数值有一个唯一的原像,同时还要满足下列条件:函数值计算很容易,而逆计算是不可行的。所谓单向陷门函数是这样的函数,即除非知道某种附加的信息,否则这样的函数在一个方向上容易计算,而在另外的方向上要计算是不可行的。有了附加的信息,函数的逆就可以在多项式时间内计算出来。一个实用的公开密钥密码系统的建立和发展依赖于找到一个单向陷门函数。(KnapsackProblem):贪心算法程序等引言:,,,这些背包算法易于遭受低密度子集和攻击、GCD攻击、,大多数公钥密码体制可以分为两大类:一类是建立在数论问