两种背包型的公钥密码算法的安全性分析

背包密码体制作者: 指导老师：摘要背包公钥加密是第一个具体实现了的公钥加密的方案.本文主要分析背包公钥加密算法的数学理论基础，描述背包公钥加密算法的体制，讨论背包公钥加密算法的加密算法与解密算法的过程和原理。

采用MH法通过掩盖超递增背包序列，进而对背包公钥加密算法加以该进，用实例加以实现，并对它的安全性进行讨论和分析.关键字模逆; 同余式; 欧几里德算法; 超递增序列；掩盖超递增序列1 引言加密技术是一门古老而深奥的学科，它对一般人来说是陌生而神秘的，因为长期依赖，它只在很少的范围内，如军事、外交、情报等部门使用.计算机机密技术是研究计算机信息加密、解密及其变换科学，是数学和计算机的交叉学科，也是一门新兴的学科，但它已成为计算机安全主要的研究方向，也是计算机安全课程教学中主要内容.密码学（Cryptology）一词源自希腊语“krypto’s”及“logos”两词，意思为“隐藏”及“消息”.它是研究信息系统安全保密的科学.其目的为两人在不安全的信道上进行通信而不被破译者理解他们通信的内容.密码学根据其研究的范围可分为密码编码学和密码分析学.密码编码学研究密码体制的设计，对信息进行编码实现隐蔽信息的一门学问，密码分析学是研究如何破译被加密信息或信息伪造的学问.它们是相互对立、相互依存、相互促进并发展的.密码学的发展大致可以分为3个阶段：第一阶段是从几千年前到1949年.这一时期密码学还没有成为一门真正的科学，而是一门艺术.密码学专家常常是凭自己的直觉和信念来进行密码设计，而对密码的分析也多给予密码分析者（即破译者）的直觉和经验来进行的.第二阶段是从1949年到1975年.1949年，美国数学家、信息论的创始人Shannon,Claude Elwood发表了《保密系统的信息理论》一文，它标志这密码学阶段的开始.同时以这篇文章为标志的信息论为对称密钥密码系统建立了理论基础，从此密码学成为一门科学.由于保密的需要，这时人们基本上看不到关于密码学的文献和资料，平常人们是接触不到密码的.1976年Kahn出版了一本叫做《破译者》的小说，使人们知道了密码学.20世纪70年代初期，IBM发表了有关密码学的几篇技术报告，从而使更多的人了解了密码学的存在，但科学理论的产生并没有使密码学失去艺术的一面，如今，密码学仍是一门具有艺术性的科学.第三阶段为1976年至今.1976年，Diffie和Hellman发表了《密码学的新方向》一文，他们首次证明了在发送端和接受端不需要传输密码的保密通信的可能性，从而开创了公钥密码学的新纪元.该文章也成了区分古典密码和现代密码的标志.1977年，美国的数据加密标准（DES）公布.这两件事情导致了对密码学的空前研究.从这时候起，开始对密码在民用方面进行研究，密码才开始充分发挥它的商用价值和社会价值，人们才开始能够接触到密码学.这种转变也促使了密码学的空前发展.密码学发展至今，已有两大类密码系统：第一类为对称密钥（Symmetric Key）密码系统，第二类为非对称密钥(Public Key)密码系统.和RSA公钥体制一起，背包公钥体制被认为是两个著名的公钥体制之一.1978年Merkle 和Hellman首先提出了一个现在称为MH背包体制的密码体制，虽然它和其几个变形在20世纪80年代初被Shamir等人破译了，但是，它的思想和有关理论首先解释了公钥密码算法的本质，所以仍然具有深刻的理论研究价值.自从Merkle和Hellman提出第一个背包型公钥密码以来，许多陷门背包被提了出来.背包型公钥密码的设计极大地丰富了公钥密码，在陷门背包的发展过程中，人们使用了各种各样的技术来设计陷门背包.比如，使用加法背包的公钥加密，使用紧凑背包的公钥加密，使用二次背包即矩阵覆盖的公钥加密，使用模背包的公钥加密，使用丢翻图方程的公钥密码等.背包型公钥加密由于其加解速度快而备受关注，然而，现有的背包型公钥密码几乎都被证明是不安全的.陷门背包的设计思想是从一个简单的背包问题出发来进行构造：把易解的背包问题伪装成一个看似困难的背包问题，这易伪装的方法就是陷门信息.合法的接受者Alice由于掌握了陷门信息因而能够把该问题恢复成一个易解背包问题，通过求解该易解背包问题，Alice能够重构明文，而对于非法的接受者Eve来说，他从密文恢复明文就意味着求解一个困难的背包问题.2 背包公钥加密算法的数学理论2.1 素数与因式分解定义1：如果一个自然数m可以被另一个自然数n除尽，则称m整除n，记为：n|m.定义2：除1外，只能被1和其本身整除的自然数称为素数，不是1，且非素数的正整数称为合数.2.2 欧几里德算法2.2.1欧几里德算法的概述欧几里德（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。

重新认识背包公钥密码的安全性摘要:针对背包密码屡被破译的局面,分析了其中原因。

指出背包公钥序列是由初始序列变换而来的,初始序列由易解背包形成,存在着冗余度,因此背包公钥序列不可能是完全随机的,利用这些冗余度是破译成功的必要条件,目前大多数被破译的背包密码只使用了模乘运算等混乱技术,这不足以隐藏初始序列的冗余度。

为此引入了加法扩散技术,以分散初始序列的冗余度,使攻击者在破译过程中难以利用,举实例说明了项内扩散和项间扩散两种扩散技术。

分析表明,运用扩散技术后,能抵御目前已知的攻击方法。

关键词:背包公钥密码;冗余度;模乘运算;混乱;扩散security reconsideration of knapsack public key cryptosystemding yan yan, fei xiang dong, pan yu *(school of economics and management, nanjing university of technology, nanjing jiangsu 210009, china)abstract:concerning the situation that knapsack public keycryptosystem has been broken repeatedly, this paper analyzed the cause. it is expounded that a knapsack public key sequence is generated by transforming an initial sequence composed of an easy knapsack problem with redundancy; hence, a knapsack public key sequence is unlikely completely random. currently, most broken knapsack cryptosystems only use confusion, such as modular multiplication, so as not to conceal the redundancy of the initial sequence adequately. it is necessary to utilize the redundancy for breaking a cryptosystem. therefore, addition diffusion was introduced in this paper to diffuse the redundancy of an initial sequence, so that an adversary can not make use of the redundancy when breaking a cryptosystem. inner item diffusion and interitem diffusion were illustrated. the analysis indicates the cryptosystem is secure against the known attacks with diffusion.key words:knapsack public key cryptosystem; redundancy; modular multiplication; confusion; diffusion0 引言背包密码自1978年提出 [1] 直到20世纪90年代,一直是公钥密码领域的研究热点,被认为是最有前途的密码算法。

背包密码体制作者: 指导老师：摘要背包公钥加密是第一个具体实现了的公钥加密的方案.本文主要分析背包公钥加密算法的数学理论基础，描述背包公钥加密算法的体制，讨论背包公钥加密算法的加密算法与解密算法的过程和原理。

采用MH法通过掩盖超递增背包序列，进而对背包公钥加密算法加以该进，用实例加以实现，并对它的安全性进行讨论和分析.关键字模逆; 同余式; 欧几里德算法; 超递增序列；掩盖超递增序列1 引言加密技术是一门古老而深奥的学科，它对一般人来说是陌生而神秘的，因为长期依赖，它只在很少的范围内，如军事、外交、情报等部门使用.计算机机密技术是研究计算机信息加密、解密及其变换科学，是数学和计算机的交叉学科，也是一门新兴的学科，但它已成为计算机安全主要的研究方向，也是计算机安全课程教学中主要内容.密码学（Cryptology）一词源自希腊语“krypto’s”及“logos”两词，意思为“隐藏”及“消息”.它是研究信息系统安全保密的科学.其目的为两人在不安全的信道上进行通信而不被破译者理解他们通信的内容.密码学根据其研究的范围可分为密码编码学和密码分析学.密码编码学研究密码体制的设计，对信息进行编码实现隐蔽信息的一门学问，密码分析学是研究如何破译被加密信息或信息伪造的学问.它们是相互对立、相互依存、相互促进并发展的.密码学的发展大致可以分为3个阶段：第一阶段是从几千年前到1949年.这一时期密码学还没有成为一门真正的科学，而是一门艺术.密码学专家常常是凭自己的直觉和信念来进行密码设计，而对密码的分析也多给予密码分析者（即破译者）的直觉和经验来进行的.第二阶段是从1949年到1975年.1949年，美国数学家、信息论的创始人Shannon,Claude Elwood发表了《保密系统的信息理论》一文，它标志这密码学阶段的开始.同时以这篇文章为标志的信息论为对称密钥密码系统建立了理论基础，从此密码学成为一门科学.由于保密的需要，这时人们基本上看不到关于密码学的文献和资料，平常人们是接触不到密码的.1976年Kahn出版了一本叫做《破译者》的小说，使人们知道了密码学.20世纪70年代初期，IBM发表了有关密码学的几篇技术报告，从而使更多的人了解了密码学的存在，但科学理论的产生并没有使密码学失去艺术的一面，如今，密码学仍是一门具有艺术性的科学.第三阶段为1976年至今.1976年，Diffie和Hellman发表了《密码学的新方向》一文，他们首次证明了在发送端和接受端不需要传输密码的保密通信的可能性，从而开创了公钥密码学的新纪元.该文章也成了区分古典密码和现代密码的标志.1977年，美国的数据加密标准（DES）公布.这两件事情导致了对密码学的空前研究.从这时候起，开始对密码在民用方面进行研究，密码才开始充分发挥它的商用价值和社会价值，人们才开始能够接触到密码学.这种转变也促使了密码学的空前发展.密码学发展至今，已有两大类密码系统：第一类为对称密钥（Symmetric Key）密码系统，第二类为非对称密钥(Public Key)密码系统.和RSA公钥体制一起，背包公钥体制被认为是两个著名的公钥体制之一.1978年Merkle 和Hellman首先提出了一个现在称为MH背包体制的密码体制，虽然它和其几个变形在20世纪80年代初被Shamir等人破译了，但是，它的思想和有关理论首先解释了公钥密码算法的本质，所以仍然具有深刻的理论研究价值.自从Merkle和Hellman提出第一个背包型公钥密码以来，许多陷门背包被提了出来.背包型公钥密码的设计极大地丰富了公钥密码，在陷门背包的发展过程中，人们使用了各种各样的技术来设计陷门背包.比如，使用加法背包的公钥加密，使用紧凑背包的公钥加密，使用二次背包即矩阵覆盖的公钥加密，使用模背包的公钥加密，使用丢翻图方程的公钥密码等.背包型公钥加密由于其加解速度快而备受关注，然而，现有的背包型公钥密码几乎都被证明是不安全的.陷门背包的设计思想是从一个简单的背包问题出发来进行构造：把易解的背包问题伪装成一个看似困难的背包问题，这易伪装的方法就是陷门信息.合法的接受者Alice由于掌握了陷门信息因而能够把该问题恢复成一个易解背包问题，通过求解该易解背包问题，Alice能够重构明文，而对于非法的接受者Eve来说，他从密文恢复明文就意味着求解一个困难的背包问题.2 背包公钥加密算法的数学理论2.1 素数与因式分解定义1：如果一个自然数m可以被另一个自然数n除尽，则称m整除n，记为：n|m.定义2：除1外，只能被1和其本身整除的自然数称为素数，不是1，且非素数的正整数称为合数.2.2 欧几里德算法2.2.1欧几里德算法的概述欧几里德（Euclid）算法是数论中的一个基本技术，是求两个正整数的最大公因子的简化过程。

背包密码体制背包问题介绍:给定⼀些物体，每个物体有不同的重量，是否有可能将这些物体放⼊⼀个背包，使背包的重量等于⼀个给定的值。

背包算法为第⼀个推⼴的公开密钥加密算法。

虽然后来发现这个算法不安全，但仍值得研究，因为它表⽰了如何将NP完全问题⽤于公开密钥算法(好吧,这个我不知道是什么意思~)。

举例：这些物体的重量分别为1,5,6,11,14,20，则可将重5，6，11的物体放⼊，装成⼀个重22的背包。

但是⽆法装成⼀个重24的背包。

背包问题：等于⼀个给定的值。

解为选择物品装⼊的情况，装⼊⽤1，未装⼊⽤0.例⼦中对给定值22的解为{0,1,1,1,0,0}这个问题需要的时间随物体的数量的增加成指数时间。

基本原理⾸先，背包算法⽤于信息安全(密码法)，我们总得搞清楚什么是明⽂，密⽂，密钥吧？！举例：明⽂： 1 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 0密钥： 1 5 6 11 14 20 1 5 6 11 14 20 1 5 6 11 14 20密⽂： 1+5+6+20＝32 5+11+14＝30 5+6＝11从上⾯可以总结：明⽂为物品的装⼊情况，是1/0的序列，⽽且明⽂长度等于物体的个数，表⽰从中选取物体装⼊背包密⽂为选取物体的质量和密钥为背包问题中物品重量序列算法安全性体现为：若攻击者获得密⽂、密钥，也⽆法在线性时间内求明⽂(物品的装⼊情况)算法的关键算法的关键是有两个不同的背包重量序列，这两个重量序列对于给定的相同的值，解相同（物品的装⼊情况相同）前者物品的重量列表是递增的，后者则是⽆序的前者可以解密，看下⾯~~1、构造递增序列背包易解的背包问题：若物品的重量列表为⼀个超递增序列，则该背包问题很容易解的。

⽐如递增序列：1 3 6 13 27 52举例：⾮递增背包是⼀个难问题背包算法先找到⼀个递增背包的重量序列作为私钥，再由此构造⼀个序列(有相同解的⼀般背包问题的序列)作为公钥(重要!)如何构造公钥呢？2、从私钥构造公钥经过上⾯的计算，序列为：{62 93 81 88 102 37}作为公钥3、加密4、解密解密这⾥我遇到⼀个问题：如何求n－1，即如何求n关于模m的逆元？？(注意:这⾥必须搞懂，不然下⼀篇博客RSA算法就肯定不懂的!)为了⽅便我整理，我把求逆元相关的过程截图出来，⼤家也可以点链接去看~ ending~。

RSA公钥加密算法及其安全性讨论RSA algorithm for public-key encryption and its security摘要：RSA是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的所有密码攻击，已被ISO推荐为公钥数据加密标准。

RSA算法基于一个十分简单的数论事实：将两个大素数相乘十分容易，但那时想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

但是，RSA的安全性依赖于大数的因子分解，却并没有从理论上证明破译RSA的难度与大数分解难度等价，即RSA的重大缺陷是无法从理论上把握它的保密性能到底如何。

随着计算能力的不断进步和各种攻击方法的出现，RSA算法是否真的安全。

关键词：RSA，公钥，加密，大数分解，攻击，安全性1 RSA加密算法1.1公钥简介密码体制按密钥类型分为对称密钥和不对称密钥。

对称密钥即加密、解密用的是同一个密钥，又称为私钥。

不对称密钥即公钥加密，加密、解密用的是不同的密钥，一个密钥“公开”，即公钥，另一个自己秘密持有，即私钥，加密方用公钥加密，只有用私钥才能解密——史称公钥加密体系：PKI。

1.2 RSA算法简介RSA加密算法是一种非对称加密算法。

RSA加密算法是Ron Rivest、Adi Shamirh和Len Adleman于1977年在美国麻省理工学院开发出来的，次年首次对外公开宣布，是第一个既能用于数据加密也能用于数字签名的算法。

RSA就是他们三人姓氏开头字母拼在一起组成的。

RSA是建立在“大整数的素因子分解是困难问题”基础上的，其安全性取决于大数分解，也就是大数分解质因数的困难性。

换言之，对一极大整数做因式分解愈困难，RSA演算法愈可靠。

假如有人找到一种快速因式分解的演算法的话，那么用RSA加密的信息的可靠性肯定会急剧下降，但找到这样的演算法的可能性是非常小的，今天只有短的RSA钥匙才可能被强力方式解破。

到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。

不同加密算法的安全性比较分析一、引言在信息交流的现代社会中，加密算法已经成为了保障个人和企业隐私安全的重要手段，各种加密算法的不断出现和更新也对信息安全领域带来了新的挑战。

本文旨在对常见的几种加密算法进行安全性比较分析，为读者提供更全面的信息安全保障建议。

二、对称加密算法对称加密算法又称共享密钥算法，将消息加密和解密使用相同的密钥，传输效率高，但密钥的安全问题使其逐渐无法适应日益复杂的信息交互环境。

1. DES算法DES算法是一种分组密码算法，密钥长度为56位，以8个字节为一组对明文进行加密。

虽然DES算法被证明存在一些安全漏洞，但其仍然被广泛应用。

2. AES算法AES算法是一种分组密码算法，密钥长度可为128位、192位或256位，对明文进行加密前需要对明文进行填充处理，加密速度较快且安全性较高，是目前被广泛应用的对称加密算法之一。

三、非对称加密算法非对称加密算法也称公钥密码算法，包含公钥和私钥两种密钥，公钥用于加密数据，私钥用于解密数据，安全性高但加密解密速度较慢。

1. RSA算法RSA算法是最早也是应用最广泛的非对称加密算法之一，基于大数因数分解的困难性，密钥长度可达到2048位以上，加密解密可靠性高，但相应的加密解密速度较慢，随着计算机技术的不断发展，RSA算法也存在一定的安全风险。

2. ECC算法ECC算法是基于椭圆曲线离散对数问题设计的非对称加密算法，密钥短、加密速度快、加密强度高，在移动设备、嵌入式系统等场景下应用广泛，但安全性也需要时刻关注。

四、哈希算法哈希算法也称散列算法，将任意长度的消息压缩成固定长度的摘要信息，生成的摘要信息不可逆，安全性高，但不适用于加密。

1. MD5算法MD5算法是一种广泛应用的哈希算法，在网络传输和文本文件校验等领域被广泛使用，但由于其容易被碰撞攻击，目前MD5算法已经逐步被安全性更高的哈希算法取代。

2. SHA-2算法SHA-2算法是一种安全性更强的哈希算法，分为256位、384位和512位三种版本，其安全性被广泛认可并得到了广泛的应用。

背包加密的工作原理
背包加密，也被称为id加密算法，是一种非对称加密算法。

它的工作原理如下：
1.生成密钥对：首先，需要生成一对公钥和私钥。

私钥只能由发送方拥有，而公钥则可以向任何人公开。

2.明文转换：将要加密的明文按照一定的规则进行转换，例如将明文中的每个字符转换为对应的ASCII码。

3.加密操作：将转换后的明文与公钥进行计算，得到密文。

计算公式为：密文= 明文* 公钥(mod n)，其中n为一个大素数。

4.解密操作：将密文与私钥进行计算，得到解密后的明文。

计算公式为：明文= 密文* 私钥(mod n)。

在实际使用中，为了提高安全性，一般会选择一个非常大的素数n作为模数，并确保生成的公私钥对满足一定的条件，以保证加密和解密的正确性。

背包加密的安全性依赖于底层的数学难题，如素数分解问题和离散对数问题的困难性。

目前，由于量子计算的快速发展，背包加密算法已经不再被认为是安全的，因为量子计算能够有效地解决这些数学难题。

因此，在实际使用中，人们更倾向
于使用其他更安全的加密算法，如RSA算法。

一种新的背包型公钥密码算法
张卫东;王保仓;胡予濮
【期刊名称】《西安电子科技大学学报（自然科学版）》
【年(卷),期】2009(036)003
【摘要】基于一类易解背包问题构造了一个新的背包型公钥密码体制.该公钥密码体制未使用超递增背包序列,因此可以抵抗Shamir的密钥恢复攻击.证明该公钥密码具有较高的背包密度,因此可以抵抗低密度子集和攻击.证明了该密码体制能够抵抗一些暴力攻击及联立丢番图逼近攻击.该公钥密码的加密只使用了n个加法运算,解密只需要n个模2的除法运算,因此具有很快的加解密速度,而且易于软硬件实现.【总页数】6页(P506-511)
【作者】张卫东;王保仓;胡予濮
【作者单位】西安电子科技大学,计算机网络与信息安全教育部重点实验室,陕西,西安,710071;西安电子科技大学,计算机网络与信息安全教育部重点实验室,陕西,西安,710071;西安电子科技大学,计算机网络与信息安全教育部重点实验室,陕西,西安,710071
【正文语种】中文
【中图分类】TN911.22
【相关文献】
1.两种背包型的公钥密码算法的安全性分析 [J], 韩立东;刘明洁;毕经国
2.一种新的背包公钥密码体制 [J], 王衍波
3.一种新的基于神经网络混沌吸引子的公钥密码算法 [J], 刘年生;郭东辉
4.一种Fibonacci型背包公钥密码体制 [J], 韩桂琴;王永茂
5.一种具有单连续变量的背包问题的新V型转换函数二进制粒子群算法求解方法[J], 王泽昆
因版权原因，仅展示原文概要，查看原文内容请购买。

各类数据加密算法的安全性分析与比较一、引言随着信息技术的迅猛发展，数据的保护和安全性成为了互联网时代的重要议题。

数据加密算法是一种重要的解决方案，通过对数据进行加密可以有效地保护数据的机密性和完整性。

本文将对各类数据加密算法的安全性进行分析与比较，旨在为用户选择适合自己需求的加密算法提供参考。

二、对称加密算法对称加密算法也被称为私钥密码算法，加密和解密使用相同的密钥。

其中最常见的对称加密算法有DES、3DES、AES等。

1. DES（Data Encryption Standard）DES是一种最早被广泛使用的对称加密算法，密钥长度为56位。

然而，由于DES密钥长度较短，已经容易受到暴力破解的攻击，因此安全性有所不足。

2. 3DES（Triple Data Encryption Standard）3DES是DES的改进版，采用了对称密钥的三重加密，即使用3个不同的密钥进行三次DES加密。

相较于DES，3DES的密钥长度为112或168位，提高了安全性。

然而，3DES的计算速度相对较慢，不适合处理大数据量的加密。

3. AES（Advanced Encryption Standard）AES是一种目前广泛应用的对称加密算法，密钥长度可为128、192或256位。

AES采用了高级的块加密算法，能够更好地抵抗暴力破解和差分分析等攻击手段。

由于安全性较高且计算速度相对快速，AES被广泛应用于各类数据加密中。

三、非对称加密算法非对称加密算法，也称为公钥密码算法，采用不同的密钥进行加密和解密。

其中最常用的非对称加密算法有RSA和Diffie-Hellman算法。

1. RSA（Rivest-Shamir-Adleman）RSA是一种基于大素数分解的加密算法，其安全性基于大数分解的困难性。

RSA算法具有较高的安全性，但加解密过程较为复杂，计算速度较慢，特别是处理大数据量时，会导致性能的下降。

2. Diffie-HellmanDiffie-Hellman算法是一种密钥交换协议，用于安全地在不安全的通信信道上交换密钥。