1、对一种背包公钥密码的分析和改良对一种背包公钥密码的分析和改良费向东，丁燕艳，潘郁（南京工业大学经济与治理学院，南京 210009）摘要：分析一个称为随机背包的公钥密码算法，论述背包公钥序列是由初始序列运算变换来的，初始序列存在冗余度，因此背包公钥序列不可能是完全随机的。目前大多数被破译的背包公钥算法只利用了属于混乱技术的模乘运算，这不足以隐藏初始序列的冗余度，利用这些冗余度是破译成功的必要条件。为此，本文引入加法扩散技术以分散始序列的冗余度，设计了新的公钥密码算法，解决者在破译进程中无法利用该冗余度。关键词：背包公钥密码；随机；冗余度；模乘运算；混乱；扩散中图分类号：Analysis and
2、improvement of a knapsack Public-key CryptosystemFei Xiang-dong, Ding Yan-yan，Pan Yu(School of Economics and Management, Nanjing University of Technology, 210009)Abstract：Analyzing a so-called random knapsack public-key cryptosystem，it is expounded that a knapsack public-key sequence is gained by tr
3、ansforming an initial sequence with redundancy，hence a knapsack public-key sequence is impossibly random. So far，most knapsack cryptosystems that have been broken only use confusion ，such as modular multiplication，as can not conceal the redundancy of the initial sequence adequately. It is necessary
4、to utilize the redundancy for breaking the cryptosystem successfully. Therefore，addition diffusion is introduced in this paper to diffuse the redundancy of an initial new knapsack public-key cryptosystem with diffusion is devised，so that the adversary can not make use of the redundancy when breaking
5、 the cryptosystem. Key words: Knapsack public-key cryptosystem；Radom；Redundancy；Modular multiplication；Confusion；Diffusion；1 引言公钥密码是确保信息安全和网络安全的重要技术，背包公钥作为最先提出的公钥密码之一，曾经是业界的希望和热点，但大多数背包公钥算法都被破译了 1。背包公钥的安全性是基于求解子集和问题的困难性，设计思想一般是把易解背包问题假装成一个看似困难的背包问题，这一假装方式确实是嵌入陷门，陷门信息作为私钥仅被合法接收者把握，运用它能够把该问题恢复成一个易解背包问
6、题，通过解该易解背包问题重构明文；而关于非法接收者来讲，从密文恢复明文就相当于解一个困难的背包问题。但存在着以下难题：若是陷门隐藏得不充分，则解决者能够从公钥动身求解出对应的陷门信息；若是隐藏得充分，则背包密度可能降低，Coster等人证明若背包密度小于的背包公钥系统都易蒙受低密度子集和解决2，而若背包密度大于1，又带来解密不唯一的问题。因此，构造一个安全的背包公钥密码系统异样困难，业内普遍以为背包公钥算法已经死亡。但由于背包公钥算法的快速加解密优势和背包问题的NPC性质，专门适合应用于物联网等资源受限的场合，故背包公钥算法仍然具有相当的吸引力。最近，王保仓等学者提出了基于随机背包的公钥加密算
7、法3（以下简称“王背包算法”），以为该算法具有如下优势：加解密速度快；基于随机背包问题而不是易解背包问题构造的；在解决者不把握私钥情形下该密码算法能抗击直接求解背包问题的解决，包括低密度解决和联立丢番图逼近解决等；证明解决者能够恢复私钥信息与解决者能够分解一个大整数是等价的。总之，该算法是一个安全高效的公钥加密算法。若是一个背包密码算法是真正基于随机背包而不是基于易解背包问题的，那么解决者从公钥动身所进行的推断将无法验证是不是正确，必然是无法破译的。但本文指出，王背包算法的构造并非是随机的，公钥隐藏着陷门信息。分析表明，运用格规约算法4，再利用整数计划方式，就能够够不可忽略的概率破译该密码算法
8、。 2 王背包算法描述整数m的二进制表示记为(m)2。该公钥密码算法描述如下。密钥生成 该算法的公、私钥生成算法如下：随机选取n个背包项形成初始序列U = (u1，un ) ，其中ui均为正整数，计算序列V = (v1，vn )，其中vi= ui 2n-i，i = 1，n。随机选取两个不同的素数p和q，使得：p ，q 2max，- （2-1）利用中国剩余定理计算序列A = (a1，an)，0aipq1即，ai ui (mod p)，ai vi (mod q ), i =1，n 那个地址ai是取模N = pq 的非负最小剩余。输出背包序列A为公钥，用户保留p和q为私钥。加密 n比特长的二进制明文
9、(m)2 = ( m1mn ) ，其中mi= 0或1，被加密为c = a1m1+ anmn 。解密 接收到密文c 后，作如下计算即可恢复明文。第一计算cp = c(mod p) , cq = c(mod q )，那个地址cp 取模p的非负最小剩余，即0cpp-1，cq取模q的绝对最小剩余，即q/2 cqq/2。则明文(m)2 =(cpcq)2，即cp cq 的二进制表示确实是m1mn ，其中m1是cp cq二进制表示的最高位，m2是cp cq 二进制表示的次高位，依次类推，mn是(cp cq)2的最低位。3 王背包算法的非随机性公钥序列A = (a1，an)，其中0aipq1，p大于序列U的所
10、有项之和，q大于序列v的所有项之和。由于密文c=a1m1+ anmn ，其中mi= 0或1，因此，这是一个0-1背包问题，背包密度概念为：D=n/log2(max ai)公钥序列A是由初始序列U和V经中国剩余定理变换而来的。初始序列U和V并非是完全随机的，U的项和V的项之间的差为2n-i，该差值为超递增序列，ui = vi+ 2n-i，i = 1，n 。即，序列U是序列V上叠加了一超递增序列形成的。由于0aipq1，公钥项ai的最大长度能够是pq的长度，即：log2(max ai) log2(pq)。依照（2-1）式，p的长度大于ui的长度，q的长度大于vi的长度，i = 1，n 。如前所述，
11、背包密度须大于才能保证安全，即，pq的长度不能大于n/比特。因此，初始序列U的项ui的取值是不能随机的，如u1 =22n，则v1= 22n 2n-1，v1的长度为2n-1比特，现在pq的长度确信大于n/比特，背包密度小于，无法保证安全。为了保证背包密度大于，ui和vi的长度必需尽可能小，尤其是关于u1和v1，其差值最大，为2n-1保证ui和vi的长度尽可能小的方案是vi取绝对值尽可能小的负数，而ui的最大长度确实是u1的长度。现在q的最大长度r必需知足以下关系： n/(n-2+r)计算得：r+V各项的长度都小于q，故vi是比特位数更小的负整数。现在序列U的各项尽管可能不形成超递增关系，但vi的
12、绝对值小于2r-1，因此有如下关系：ui+(2r-1) ui+1+ ui+2+ un等同于超递增关系，适合运用整数计划方式求解。其中，p的长度远远大于q的长度，能够参照文献5该算法作者本人演示的方式或文献15前脸部份的方式求出U的各项及p，进而破解整个算法。4 从头熟悉背包公钥算法 背包公钥算法之安全性背包公钥序列有别于随机数序列是因为前者是由初始序列变换而来的，并以此隐藏陷门。能够把初始序列看做被加密的消息，初始序列到公钥的变换进程能够看成是加密进程，背包公钥序列看做加密后的密文。从计算复杂性理论上讲，若是加密进程（初始序列到公钥的变换进程）是安全的，那么从密文（公钥）动身破译该算法的时刻和
13、空间复杂性极大，乃至等价于求解一个NPC问题，那么该算法就被以为是一个安全的背包公钥密码算法。初始序列代表着易解背包，是有必然规律和特性的，如MH背包6中初始序列的超递增性、“王背包算法”中初始序列差值的超递增性。这些规律和特性形成初始序列的冗余度7，冗余度作为算法的一部份，是公布的。背包公钥序列作为初始序列变换的最终结果，残留着这些冗余度。事实上，任何公钥密码的公钥必然隐藏着私钥信息（全数或部份），不存在完全随机的公钥。若是初始序列是随机数序列，其冗余度为零，破译者在没有取得初始序列的情形下，无法搜寻和验证所要破译的密钥，该背包公钥是无法破译的。因此，破译者利用初始序列的冗余度是破译成功的最
14、低要求。不管是Shamir对MH背包的解决8，仍是其它解决法，都必需利用初始序列的冗余度进行破译，其中，Shamir解决法的唯一解距离为4，即解决者至少需要利用超递增初始序列中的4项。一个背包公钥算法是安全的，其必要条件是能够避免破译者从公钥动身利用初始序列及冗余度。 混乱和扩散Shonnon提出了隐藏被加密消息中冗余度的两种方式7：混乱（confusion）和扩散（diffusion）。混乱是指在加密变换进程中使明文、密钥和密文之间的关系尽可能地复杂化，用于掩盖明文和密文之间的关系，以防破译者采纳统计分析法进行破译解决。大体方式是代替，明文字符被密文字符代替。一样来讲，仅用代替是不够的。二战
15、中德国的恩尼格马是一复杂的代替算法，但被破译了。扩散是指要将算法设计得使每一比特明文的转变尽可能多地阻碍到输出密文序列的转变，确实是将明文冗余度度分散到密文中使之分散开来，以便隐蔽明文的统计特性；扩散的另一层意思是将每一名密钥的阻碍也尽可能迅速地扩展到较多的输出密文比特中去。大体方式是换位（又称置换）。通常，单独用扩散也容易被破译。不论是“混乱”仍是“扩散”，每一步都必需是可逆的，即密文通过逆向的混乱或扩散操作以后能还原出初始数据。 模乘运算混乱技术的实现方式有多种9，DES采纳“S盒”，IDEA采纳模乘运算。背包公钥算法都采纳模乘运算实现混乱。模乘运算表示为：b wu (mod m )其中，
16、m为模，b为w乘以u后取模m的余。存在如下关系：b= wu-k*m （4-3-1）k为某个正整数。模乘运算为乘法群运算，在正整数域中，依照必然的线性关系，用一个整数代替另一整数。其优势是当w和u较大时，雪崩效应明显，即w或u转变一名，将引发b的猛烈转变。其缺点是变换为线性：乘数u中的每位一样扩张后取模p的余，列位之间仍然在模p那个整数域中维持着原有的关系，若是u中的存在冗余度，则被完整地传递到b中，容易被破译者利用。举两例：（1）若是u和m存在公因子g，从式（4-3-1）可知，g也是b的因子；（2）关于b1 wu1 (mod m )，若是b1n-j，d i= ei*2n-j+vi ，“”表示“
17、远远大于”； (5) 选正整数t，知足(ei +t*vi) ，q 运用中国剩余定理，生成n项公钥A = (a1，an)，即0 a i pq1，ai ui (mod p)，ai vi (mod q ), i =1，n 私钥为：p，q，t，w-1，m 其中，w-1为w模m的逆。而超递增初始序列B作为固定值嵌入算法中。 加密二进制明文x=(x1，xn )，xi为0或1，被加密为c=a1x1+ +an 解密(1) 计算 u = c (mod p) , v = c (mod q )(2) 计算 e = u - t*v(3) 计算 d = e*2n-j + v(4) 计算 y = w-1*d mod m
18、(5) 运用超递增初始序列B计算得明文x 安全性分析以上算法的第(3)和第(6)步为模乘运算关系，属混乱技术。第(4)步和第(5)步实施不对称分组，将n比特位的di分为左、右二部份，左部长度远大于右部，右部扩展t倍后叠加到左部，使得超递增初始序列bi各项之间及模乘因子w的微小转变在整个项分散开来，弥补当bi和w低位转变时，模乘结果雪崩效应不明显的缺点。不对称分组及扩展叠加技术为项内扩散技术。关于背包公钥密码算法有两种大体的解决：明文恢复解决和密钥恢复解决。前者指从密文动身来求解明文，后者是指从公钥动身寻觅密钥，现讨论这两种解决。5.4.1 明文恢复解决如上所述，背包密度只有处在和1之间背包公钥
19、算法才是安全的。以n=512为例，说明本算法构造的背包密度能够大于。(1) 选初始序列 B = (b1，bi，b512)(2) 选互素的w和m，m须大于B中所有项的和，由于初始序列B的超递增性质，m最小可选513比特位与w互素的正整数。(3) 运用w和m，对B序列进行模乘运算，转换为D序列 di w bi (mod m ) i =1，512 由于m的位数是513比特，因此，di的位数不大于513比特。(4) 将513比特位的di进行不对称分组：在第352比特的位置分为左、右二部份，形成ei和vi，长度别离为352比特和161比特，d i= ei*2161+ vi (5) 选正整数t，知足ei
20、+t*vi ，q 运用中国剩余定理，生成512项公钥A = (a1，a512)，即0a ipq1，ai ui (mod p)，ai vi (mod q ), i =1，512下面考察p和q的位数：512个ui相加，最多扩展log2512=9比特。因此，p能够取361比特位的素数。同理，q能够取170比特位的素数。由此，公钥A的项应该为361+170=531比特。背包密度D=512/531=，处在和1之间。5.4.2 密钥恢复解决本算法的初始序列B是固定的，能够公布的，因此，对安全性的要求类似于要求一个对称密码能够抵御“已知明文解决”。第一，本算法运用不对称分组方式，将序列D分成序列U和V，各序
21、列中的项存在以下关系：di= (ui-t vi)*2n-i+ vi 。其中，t能够是100比特以上的整数，由于t的存在，破译者无法运用解多重MH背包的方式10，11破译本算法。第二，即便解决者从公钥动身逆向破译取得了U和V序列，必需猜想t取得D序列后，再进行格解决5或Shamir解决法8继续破译。5.4.1节已经阐明，关于512项的背包算法，ui和vi的长度能够相差191比特，t能够是100比特位以上的正整数，要猜想解决100比特以上的正整数是不可计算的。由此，t的存在，使得破译者难以取得D序列，无法从公钥动身利用初始序列及冗余度。再则，若是破译者从初始序列B动身，也不能以此恢复私钥，证明如下
22、：第（3）步运用模乘因子w对序列B= (b1，bn)进行模乘运算，将B序列转换序列D：di wbi (mod m) （5-4-2）D = (d1，dn) i =1，n由（5-4-2）式，可得：bi w-1di (mod m) i =1，n 上式能够以为是一个MH背包关系：D作为初始序列，B作为公钥序列，w-1作为模乘因子。但破译者不明白序列D的信息，关于破译者来讲，序列D的冗余度是零，不管是运用格解决法5仍是Shamir破译法8，都不能恢复私钥w和m 。 举例说明取超递增序列为：b1=58037，b2=29018，b3=14510，b4=7253，b5=3627，b6=1813，b7=907，
23、b8=453，b9=227，b10=113，b11=57，b12=28，b13=15，b14=7，b15=3，b16=2取模m=965613=(0001001 )2w=724210，w 模m的逆w-1=4计算得：d1=738719=(0011111 )2 d2=490061=(0001101)2d3=486434=(0100010)2d4=726023=(0000111)2d5=242310=(0000110)2d6=724663=(0110111)2d7=241630=(0011110)2d8=724323=(1100011)2d9=241460=(0010100)2d10=724238=(
24、0001110)2d11=724224=(0000000)2d12=7=(00000000000000000111)2d13=241407=(0011111)2d14=241405=(0011101)2d15=241404=(0011100)2d16=482807=(0110111)2在第13比特位与第14比特位间（从左到右）分割di，形成ei和vi ，取t=3，得：u1=e1+t*v1=()2=5864 v1=(0011111)2=31u2=e2+t*v2=(0)2=4059 v2=(1001101)2=77u3=e3+t*v3=(0)2=3902 v3=(0100010)2=34u4=e4
25、+t*v4=()2=5693 v4=(0000111)2=7u5=e5+t*v5=(00)2=1911 v5=(0000110)2=6u6=e6+t*v6=()2=5826 v6=(0110111)2=55u7=e7+t*v7=(0)2=2169 v7=(1011110)2=94u8=e8+t*v8=()2=5955 v8=(1100011)2=99u9=e9+t*v9=(00)2=2042 v9=(0110100)2=52u10=e10+t*v10=()2=5700 v10=(0001110)2=14u11=e11+t*v11=()2=5658 v11=(0000000)2=0u12=e12+t*v12=(0000000010101)2=21 v12=(0000111)2=7u13=e13+t*v13=(0)2=2266 v13=(1111111)2=127u14=e14+t*v14=(0)2=2260 v14=(1111101)2=125u15=e15+t*v15=(0)2=2257 v15=(1111100)2=124u16=e16+t*v16=()2=4128 v16=(1110111)2=119取p=59713，q=977运用中国剩余定理计算公钥，得：a1=43775493 a2=41206029 a3=28188438 a4=
