admin 为了提高背包加密体制的安全性，在对MH背包公钥及Shamir攻击、低密度攻击方法进行深入研究的基础上，我们提出了一种基于超递增序列的背包加密算法，对针对原始背包的超递增性攻击起到了很好的抵抗作用。
一、构造无冲突非超递增序列
传统背包加密体制的设计思想都是从一个简单的背包问题出发，把一个易解的背包伪装成一个看似困难的背包，这里所说的易解背包就是一个超递增序列，序列中的元素要满足第n项(n>1)大于前(n-1)项的和。超递增序列容易构造，使用方便，但它已被证明存在严重的不安全性，而提高其安全性的一个途径就是使用非超递增序列，但使用一般的非超递增序列会产生加密“冲突”。如，使用序列(2，4，6，8，10)构造背包，把(10100)和(00010)利用MH公钥系统进行加密，密文都是8，这给解密带来了困难。若能够构造出无冲突的非超递增序列，并把其应用于背包公钥加密体制中，则加密系统的安全性将会得到提高。
定义1 对于一个严格递增的正 A=(a1，a2，…，an），如果对任意的1≤k≤n，均有a1+a2+…+ak-1<ak，则序列A称为超递增序列，否则序列A称为非超递增序列。
定义2 对于一个严格递增的正整数序列A=(a1，a2，…，an），如果存在1≤i1，i2…iv≤n及1≤j1，j2…jv≤n，且{1≤i1，i2…iv}n{j1，j2…jv}=φ，使得aj1+aj2…+ajv=ai1+ai2…+aiv，则该序列A称为冲突序列，反之A称为无冲突序列。
定义3 如果一个序列既是非超递增序列，又是无冲突序列，则称该序列为无冲突非超递增序列。
根据上述定义可知，序列{1，3，6，13，27，52}是一个超递增序列，而序列{3，5，7，13，27，54}、{4，5，7，9，16，38}均是非超递增序列，但序列{4，5，7，9，16，38}中存在冲突，因而不是无冲突非超递增序列。
下面我们给出一种构造无冲突非超递增序列的新方法。
定理1 若正整数序列A=(a1，a2，…，an）满足以下条件：
(1)an<an+1；
(2)a2+…+an<an+1<a1+a2+…+an。 则序列A为无冲突的非超递增序列。 证明：设序列A的长度为k，对k进行数学归纳证明： (1)当k=2时，显然有a2>a1，序列中无冲突项；
(2)当k=3时，因为a1+a2>a3+a2>a1，则a1，a2，a3，(al+a2)，(a1+a3)，(a2+a3)，(a1+a2+a3)互不相等，所以序列中无冲突项；
(3)假设k≤n时结论都成立，下面证明当k=n+l时，序列也满足无冲突项要求。
假设序列a1，a2，…，an，an+1中有冲突项，即存在：
1)若等号两边均无an+1项，则与归纳假设矛盾；
2)若等号两边均有an+1项，则两边同时减去an+1项，此时与1)-样，产生矛盾。
3)若等号两边仅有一边含有an+1项，不失一般性，有：
若Ai1+ai2，+…ain-1=0，则：a1+a2...+an>an+1>a2+...an可知等号不成立；
若Ai1+ai2，+…ain-1≠0，则：
但是由于A>C，B>D，因而上式不成立，产生矛盾。
故当k=n+1时，序列满足无冲突项要求。
由(1)，(2)可知，对于任意长度的正整数序列均满足无冲突项要求，即A是一个无冲突的非超递增序列，定理得证。
二、背包加密算法之非超递增序列
基于满足定理1的无冲突的非超递增序列，下面给出一个改进的背包公钥加密算法，它的思想和MH背包加密体制的思想基本一样，但在产生私钥时使用无冲突的非超递增序列。
1、公钥和私钥的产生
(1)由收信方产生一个长度为n随机正整数序列Y=(y1，y2，…，yn)。
(2)构造一个满足定理1的无冲突非超递增序列A=[al，a2，…，an]，同时产生模数P：
(3)收信方根据非超递增序列A和模数P及随机序列Y构造出序列B=(b1,b2,...bn)，其中bi满足bi=ai+Pyi(i=1，2，…，n)，即B=A+PY。
(4)收信方将B作为公钥公开，将A和P作为私钥保存，并将随机向量Y销毁。
2、加密和解密过程
(1)加密过程
发信方用公钥B对二进制消息M=[m1，m2，…，mn]进行加密，得到密文C=b1m1+b2m2，...,+bnmn。
(2)解密过程
收信方用私钥A=[a1，a2，…，an]和模数P对密文C=b1m1+b2m2，...,+bnmn进行解密，得到：
由于私钥A=[a1，a2，…，an]是全局递增序列但不是超递增序列，要求得明文M，需按以下步骤进行：
求得的M=[m1，m2，…，mn]即为明文。
3、举例验证
假设接收方选定非超递增序列A=[5，7，11，19，41，79]，发送方要发送明文M=[1，1，1，0，0，1]，执行以下步骤：
(1)根据A求得模数P=163；
(2)由系统产生随机向量Y= [657，3029，7568，2935，5995，2097]；
(3)接收方用Y和P将非超递增序列A转换为普通的随机序列B；
(4)接收方将B作为公钥，将A和P作为私钥，并销毁Y；
(5)发送方利用公钥B加密明文M=[1，1，1，0，0，1]，得到密文C= 2176315，并将C发送给接收方；
(6)接收方对接收到的密文C=2176315，根据私钥P=163，计算出Mr= 2176315(mod163)= 102，并由循环（*）求得解密明文M。
需要特别注意的是：在普通背包解密中，若检测到23>19时，直接得到23-19=4，并将此处的明文置为1，但在本文解密算法中，需要与a1作比较，因此要跳过19，并将明文置为0。
另外，由于非超递增序列和超递增序列的性质一样，只有唯一解，所以只要找到一个解，不必再进行其他尝试。
该方法有效地避免了利用非超递增序列构造背包的过程中出现的难题，同时还具有高的安全性能，在抵抗Shamir攻击和低密度攻击方面都具有良好的性能。
小知识之公钥加密公钥加密，也叫非对称（密钥）加密（public key encryption），属于通信科技下的网络安全二级学科，指的是由对应的一对唯一性密钥（即公开密钥和私有密钥）组成的加密方法。它解决了密钥的发布和管理问题，是目前商业密码的核心。在公钥加密体制中，没有公开的是明文，公开的是密文，公钥，算法。
