背包密码体制 作者： 指导老师： **背包公钥加密是第一个具体实现的公钥加密方案。本文主要分析了背包公钥加密算法的数学理论基础，描述了背包公钥加密算法的体制，讨论了背包公钥加密算法的加密算法和解密算法的过程和原理。利用MH方法对超增背包序列进行掩码处理，然后对背包公钥加密算法进行改进，结合实例实现，并对其安全性进行讨论和分析。 关键词 同余性；欧氏算法；超增序列；掩码超增序列 引言 加密技术是一门古老而深奥的学科，对普通人来说陌生而神秘，由于长期依赖，只在军事、外交、情报等部门等小范围内使用。计算机保密技术是研究计算机信息加密、解密与变换的科学。 它是数学和计算机的交叉学科，也是一门新兴学科，但已成为计算机安全的主要研究方向，也是计算机安全课程教学的主要内容。密码学（）一词来源于希腊文“'s”和“logos”，意为“隐藏”和“信息”，是研究信息系统安全性和保密性的科学，其目的是使两个人在不安全的信道上进行通信而不被破译者所理解。密码学按其研究范围可分为密码学和密码分析学。密码学研究密码系统的设计和对信息进行编码以隐藏信息的科学。密码分析学是研究如何破译加密信息或伪造信息的科学。它们相互对立，相互依存，相互促进，不断发展。密码学的发展大致可分为几个阶段：第一阶段是从几千年前到1949年。在此期间，密码学尚未成为一门真正的科学，而是一门艺术。 密码专家往往凭着自己的直觉和信念来设计密码，而对密码的分析也同样是靠密码分析员（即译码员）的直觉和经验。第二阶段是1949年至1975年。1949年，美国数学家、信息论创始人发表了《保密系统的信息论》一文，标志着密码学的这一阶段的开始。同时，以此文为标志的信息论为对称密钥密码体制建立了理论基础，从此密码学成为了一门科学。由于保密的需要，当时人们基本上看不到任何有关密码学的文献和资料，普通人更是无从接触密码。一本名为《密码破译者》的小说出版，让人们了解了密码学。20世纪70年代初，IBM发表了几篇有关密码学的技术报告，让更多的人意识到了密码学的存在。然而，科学理论的出现并没有让密码学失去艺术的一面。 时至今日，密码学依然是一门艺术性的科学。第三个阶段是1976年至今。1976年，和发表了《密码学的新方向》一文，在文中他们首次证明了在发送方和接收方无需输入密码即可进行保密通信的可能性，从而开创了公钥密码学的新时代。该文章也成为区分古典密码学和现代密码学的标志。1977年，美国数据加密标准（DES）公布。这两件事，引发了人们对密码学前所未有的研究。从这个时候开始，密码学的民用研究开始了，密码学开始充分发挥其商业和社会价值，人们开始能够接触到密码学。这一转变也促使密码学得到了空前的发展。密码学发展至今，主要有两大类密码体制：第一类是对称密钥（）密码体制，第二类是非对称密钥（）密码体制。 RSA公钥体制与MH公钥体制并称为两大著名公钥体制之一的背包公钥体制。 和 最早提出了现在称为MH背包体制的密码体制。虽然它和它的几种变型在20世纪80年代初就被别人破译了，但是它的思想和相关理论首次阐释了公钥密码算法的本质，因此至今仍具有深厚的理论研究价值。 自从 和 提出第一个背包公钥密码以来，又提出了许多陷门背包。背包公钥密码的设计极大地丰富了公钥密码学。在陷门背包的发展过程中，人们采用了各种各样的技巧来设计陷门背包。例如，利用加法背包式的公钥加密，由于加解密速度快，而备受关注。但是，几乎所有现有的背包公钥密码都被证明是不安全的。陷门背包的设计思路是从一个简单的背包问题构造而来：把本来容易解决的背包问题伪装成一个看似很难解决的背包问题。 伪装的方法就是陷门信息，合法接收者Alice由于掌握了陷门信息，可以将问题还原为一个易于解决的背包问题，通过解决易于解决的背包问题，Alice可以重构出明文，但是对于非法接收者Eve来说，从密文恢复明文意味着解决一个很难的背包问题。 背包公钥加密算法的数学理论 2.1 素数与因式分解 定义1：若一个自然数m能被另一自然数n整除，则称m能被n整除，记为：n|m。 定义2：除1以外，只能被1和自身整除的自然数称为素数，非1且不是素数的正整数称为合数。 2.2 欧几里得算法 2.2.1 欧几里得算法概述 欧几里得（）算法是数论中的一项基本技术，它是寻找两个正整数的最大公约数的简化过程。
广义欧几里得算法不仅可以求两个正整数的最大公约数，而且当两个正整数互质时，还可以求一个数关于另一个数的乘法逆元。欧几里得算法基于下面的基本理论：引理：对任意非负整数a和正整数b，gcd(a,b)=gcd(b,amod 证明：b为正整数，所以a可以表示为a=kb+r，amodb=r，其中k为整数，所以modb=a-kb。又有d|b，所以d|kb。由d|a和d|可知，d有公约数。 于是可以得出a,b的公因数集为b,amod2.2.2 欧几里得算法设计 欧几里得算法设计如下： 由于gcd(a,b)=gcd(|a|,|b|)，设算法中输入的两个正整数分别为a,则欧几里得算法如下： (=gcd(f,d);=gcd(f,d); 其中函数gcd为求两个正整数的最大公约数。设输入的两个正整数为a和b，则算法如下： (inta,(ab,b);(a,ba);2.3 求逆元 2.3.1 相关概念与定理 乘法逆元定义： 若gcd(a,b)=1，则若b在moda（设ba）下有乘法逆元，即存在一个数恒为真。
此时x在moda下就是b的逆元素。将上面的推广到欧几里得算法中，我们先求gcd(a,b)，当gcd(a,b)=1时，就可以返回b的逆元素。 2.3.2 模逆算法用类C实现广义欧氏算法，求乘法逆元： (=1,x2=0,x3=f; inty1=0,y2=1,y3=d; intt1,t2,t3; int(y3==0)x3=gcd(f,d); (y3==1)y3=gcd(f,d);; q=x3/y3; t1=x1-q*y1; t2=x2-q*y2; t3=x3-q*y3; x1=y1; x2=y2; x3=y3; y1=t1; y2=t2; y3=t3; 背包公钥加密算法 背包问题又称子集和问题，已被证明是一个NP完全问题，尚无有效算法。1979年， R.和A.提出了一种解决一般背包问题的算法，算法的时间复杂度为O(2)。一般情况下该问题不能在多项式时间内求解，但在某些特殊情况下，仍有可能在多项式时间内求解。 3.1 背包问题简介 背包问题可以简单地描述：设物品的重量分别为：1，2，4，8，16，32kg，背包载重23kg，请问背包中共有多少件物品？这是一个容易求解的背包问题。由二进制表达式：23=1+2+4+16，可以立即知道背包的重量分别为：1，2，4，16kg。
背包问题一般的数学描述为：给定一个背包向量a=(a1,a2,a3,a4,…,an)，和一个背包载重量S，求向量X=（x1,x2,…xn）使得S =a1*x1+a2*x2+a3*x3+…+an*xn。问方程是否有二进制解xi=0或1（其中i为自然数：1,2,3,…,n）。如果有二进制解，求它的解。有些特殊的背包问题很容易解，比如上面的例子，就是递增背包问题aiaj，又称为易背包问题。如果ai是随机分布的背包问题，则很难解，称为难背包问题。3.2 易背包问题超递增背包问题就是一个易背包问题。 假设已知ai(其中1,2,3,4,…,n)，有aaj。为了满足低密度子集与攻击的条件，我们设一个水平不等式：k^n ai，其中k代表进制，即恒为2，也就是本文中恒为二进制。Q=x3/y3判断x3，y3返回逆元素y2t1=x1-Qy1，t2=x2-Qy2，t3=x3-Qy3x1=y1，x2=y2，x3=y3y1=t1，y2=t2，y3=t3Y3=1无逆元素Y3=0分别为x1，x2，y3，y1，y2，y3赋值给定S为后端积，从右到左检查A的每一个元素，判断其是否在解中。
若s=an，则an重复上述过程到an-1，一直进行直到检查ai是否在解中，检查完毕后得到x=(x1,x2,x3,…,xn)，即为密文。3.3 MH方法及简单背包密码算法的改进1978年，斯坦福大学的RCE提出了背包陷门背包公钥方法，简称MH方法。MH方法的基本思想是先选定一个简单背包，然后再选定陷门信息，这样易解的背包问题就转化为困难的背包问题。如果知道陷门信息，这个困难的背包问题又变成了一个容易解决的背包问题。因此MH方法又称为陷门背包密码方法。 陷门背包的设计思路几乎都是从一个简单的背包问题构造出来的：把容易解决的背包问题伪装成看似很难的背包问题。伪装的方法就是陷门信息。合法的接收者Alice，因为主