重新认识背包公钥密码的安全性

.页眉.页脚..重新认识背包公钥密码的安全性摘要:针对背包密码屡被破译的局面,分析了其中原因。指出背包公钥序列是由初始序列变换而来的,初始序列由易解背包形成,存在着冗余度,因此背包公钥序列不可能是完全随机的,利用这些冗余度是破译成功的必要条件,目前大多数被破译的背包密码只使用了模乘运算等混乱技术,这不足以隐藏初始序列的冗余度。为此引入了加法扩散技术,以分散初始序列的冗余度,使攻击者在破译过程中难以利用,举实例说明了项内扩散和项间扩散两种扩散技术。分析表明,运用扩散技术后,能抵御目前已知的攻击方法。

关键词:背包公钥密码;冗余度;模乘运算;混乱;扩散

securityreconsiderationofknapsackpublickeycryptosystem

dingyanyan,feixiangdong,panyu*

(

schoolofeconomicsandmanagement,nanjinguniversityoftechnology,nanjingjiangsu210009,china

)

abstract:

concerningthesituationthatknapsackpublickeycryptosystemhasbeenbrokenrepeatedly,thispaperanalyzedthecause.itisexpoundedthataknapsackpublickeysequenceisgeneratedbytransforminganinitialsequencecomposedofaneasyknapsackproblemwithredundancy;hence,aknapsackpublickeysequenceisunlikelycompletelyrandom.currently,mostbrokenknapsackcryptosystemsonlyuseconfusion,suchasmodularmultiplication,soasnottoconcealtheredundancyoftheinitialsequenceadequately.itisnecessarytoutilizetheredundancyforbreakingacryptosystem.therefore,additiondiffusionwasintroducedinthispapertodiffusetheredundancyofaninitialsequence,sothatanadversarycannotmakeuseoftheredundancywhenbreakingacryptosystem.inneritemdiffusionandinteritemdiffusionwereillustrated.theanalysisindicatesthecryptosystemissecureagainsttheknownattackswithdiffusion.

keywords:

knapsackpublickeycryptosystem;redundancy;modularmultiplication;confusion;diffusion

0引言

背包密码自1978年提出[1]直到20世纪90年代,一直是公钥密码领域的研究热点,被认为是最有前途的密码算法。背包密码的安全性是基于求子集和问题的困难性,设计思想是把易解背包问题伪装成一个看似困难的背包问题,其方法就是使用陷门。陷门信息作为私钥仅被合法接收者掌握,运用它可以把该问题恢复成一个易解背包问题,通过解该易解背包可重构明文;而对非法接收者来说,从密文恢复明文就相当于解一个困难的背包问题。但存在着以下难题:如果陷门隐藏得不充分,则攻击者可以从公钥出发求解出对应的陷门信息;如果隐藏得充分,则背包密度可能降低。coster等[2]证明背包密度小于0.9408的背包密码都易遭受低密度子集和攻击；而若背包密度大于1,又造成解密不唯一。因此,构造一个安全的背包密码异常困难,目前其中的绝大多数都被破译了,普遍认为背包密码的前景暗淡[3-4]。

背包公钥序列有别于随机数序列，因为前者是由初始序列变换而来的,并以此隐藏陷门。可以把初始序列看作被加密的消息,初始序列到公钥的变换过程可以看成是加密过程,背包公钥序列看作加密后的密文。从计算复杂性理论上讲,如果加密过程(初始序列到公钥的变换过程)是安全的,那么从密文(公钥)出发破译该算法的时间和空间复杂性极大,直至等价于求解一个npc问题,那么该算法被认为是一个安全的背包公钥密码。

初始序列由易解背包形成,具有一定规律和特性,如mh背包[1]中初始序列的超递增性，王氏密码中初始序列差值的超递增性。这些规律和特性形成初始序列的冗余度[8],冗余度作为算法的一部分,是公开的。背包公钥序列作为初始序列变换的最终结果,残留着这些冗余度。事实上,任何公钥密码的公钥必然隐藏着全部或部分私钥信息,不存在完全随机的公钥。

如果初始序列是随机数序列,其冗余度为零,由于破译者无法搜寻和验证密钥,即使是仅进行一次模乘运算的mh背包[1]都是无法破译的,无论是格攻击法[7],还是shamir攻击法[9],都必须利用初始序列的冗余度进行破译。利用初始序列的冗余度是破译成功的必要条件。其中,shamir攻击法的唯一解距离为4,即攻击者至少需要利用超递增初始序列中的4项。

一个背包公钥算法是安全的,其必要条件是能够防止破译者从公钥出发利用初始序列的冗余度。

2.2混乱和扩散

shonnon[8]提出了隐藏被加密消息中冗余度的两种方法:混乱和扩散。

混乱是指在加密过程中使明文、密钥以及密文之间的关系尽可能复杂,以掩盖明文和密文之间的关系。基本方法是代替,用密文字符代替明文字符。除非对密钥长度没限制,如“一次一密”,否则仅用混乱是不够的。

扩散是指使每一位明文的变化尽可能多地影响到密文的变化,将明文冗余度分散到密文中;也指将每一位密钥的影响尽可能扩展到较多的密文中。基本方法是换位(又称置换)。通常单独用扩散也易被破译。

不论是“混乱”还是“扩散”,都必须是可逆的,即经过逆向操作能还原初始数据。

2.3模乘运算

混乱实现的方式有多种[10]:

数据加密标准（dataencryptionstandard,des）采用s盒,国际数据加密算法（internationaldataencryptionalgorithm,idea）采用模乘运算。背包公钥适合采用模乘运算实现混乱。

模乘运算表示为:

b≡wu(modm)

其中:m为模,w为乘数,u为被乘数,b为模m的余。

存在如下关系:

b=wu-k*m(2)

其中k为某个正整数。

背包密码系统中的模乘运算为乘法群运算,在一个整数域中,用一个整数代替另一整数。

其优点是当w和u较大时,雪崩效应明显,即w或u变化一位,将引起b的剧烈变化。

缺点是变换为线性:被乘数u中的每位同等扩张后取模p的余,各位之间仍然在模p整数域中保持着原有的关系,u中的存在冗余度,被完整地传递到b中,易被破译者利用。如:u和m存在公因子g,从式(2)可知,g也是b的因子。

即使通过多次模乘运算构造多重mh背包,仍不能充分隐藏初始序列的冗余度,破译者能够从公钥序列出发利用该冗余度,进而破译[11]。

王氏密码仅运用中国剩余定理进行一次迭代变换,关系如下:

2.4加法扩散

如上所述,仅依靠混乱技术还不能确保安全,需要引进扩散技术,以分散初始序列的冗余度,使得破译者难以利用。

扩散技术有多种类型[10],基本方法是换位,如des,但对于背包密码来说,换位将引起加法进位的改变,难以还原,故换位法不适用;idea采用模加、模异或运算实现扩散。

背包公钥密码的背包值是初始序列各项及其变换形式的子集和。鉴于加法易于通过逆运算减法恢复原值,因此,初始序列的冗余度适合采取加法的方式来实现扩散。

不同背包公钥的初始序列所包含的冗余度是不同的,为分散这些冗余度所采用的加法扩散技术也是不同的,必须依具体情况而定,但总体原则有两条:一是在模乘运算的基础上,进一步加强雪崩效应;二是使破译者从公钥出发难以利用初始序列的冗余度。

从形态上分,加法扩散技术分为项内扩散和项间扩散技术。将一项分成两部分,相互叠加,隐藏冗余度,称为项内扩散;各项之间相互叠加,隐藏冗余度,称为项间扩散。

3基于项内扩散技术的背包公钥密码

下面运用模乘运算和中国剩余定理,结合项内扩散技术,构造新型背包公钥密码。

4.4.2私钥恢复攻击

模m′群有如下关系:

w′-1a”i-tim′=a′i;1≤i≤k

破译者可以从公钥出发,运用格基规约算法[6]推算出ti,但由于m′是保密的,破译者要继续下去,需要利用a”i或a′i中遗留的冗余度,但这些冗余度都被隐藏了,破译者无法利用,文献[13]所展示的攻击法无法成功。即使攻击者从公钥出发追踪到a′i,由于a′i是模m加运算后的余,也不能通过联立方程组的方法解出ai。

5结语

在背包密码普遍不被看好的情况下,本文以新的视角对其进行研究和分析。本文认为,背包公钥序列是由初始序列变换来的,初始序列代表着易解背包,具有一定的规律和特性,故背包公钥序列不可能是完全随机的。这些规律和特性形成初始序列的冗余度,利用此冗余度是破译成功的必要条件。可以将初始序列看作需加密的文本,变换看作加密过程,公钥序列看作密文。背包公钥算法的安全性有两个方面:一是保证背包密度,抵御低密度子集和攻击；二是优化变换过程,使攻击者难以从公钥出发利用初始序列的冗余度。目前大多数被破译的背包公钥密码只使用了属混乱技术的模乘运算,不能充分隐藏初始序列的冗余度,本文引入加法扩散技术,进一步隐藏初始序列的冗余度,使攻击者难以利用。以实际例子说明了两种加法扩散技术,即项内扩散技术和项间扩散技术。分析表明,运用了扩散技术后,攻击者难以利用初始序列的冗余度,目前已知的破译方法不再奏效。

参考文献:

[1]

merklerc,hellmanmh.hidinginformationandsignaturesintrapdoorknapsacks[j].ieeetransactionsoninformationtheory,1978,24(5):525-530.

[2]costermj,jouxa,lamacchiaba,etal.improvedlowdensitysubsetsumalgorithms[j].computationalcomplexity,1992,2(2):111-128.

[3]odlyzkoam.theriseandfallofknapsackcryptosystems[eb/ol].[20100510]./~odlyzko/doc/arch/knapsack.survey.pdf.

[4]laimk.knapsackcryptosystems:thepastandthefuture[eb/ol].[20110915]./~mingl/knapsack.html.

[5]王保仓,韦永壮,胡予濮.基于随机背包的公钥密码[j].电子与信息学报,2010,32(7):1580-1584.

[6]lenstraak,lenstrahw,jr,lovaszl.factoringpolynomialswithrationalcoefficients[j].mathematischeannalen,1982,261(4):513-534.

[7]王保仓,巨春飞.对一个背包公钥密码的格攻击[j].计算机应用研究,2010,27(4):1466-1492.

[8]shannonce.communicationtheoryofsecrecysystems[j].bellsystemtechnicaljournal,1949,28(4):656-715.

[9]shamira.apolynomialtimealgorithmforbreakingthebasicmerklehellmancryptosystem[j].ieeetransactionsoninformationtheory,1984,30(5):699-704.

[10]schneierb.应用密码学[m].吴世忠,祝世雄,张文政,等译.北京:机械工业出版社,2000:185-250.

[11]lagariasjc.knapsackpublickeycryptosystemsanddiophantineapproximation[c]//proceedingsofcrypto83.berlin