安全背包公钥密码的要点和设计

1、安全背包公钥密码的要点和设计费向东，潘郁（南京工业大学经济与管理学院，南京 210009）摘要：为提高背包密码的安全性，本文依据背包密码以往失败的原因，列举安全背包公钥的要点：运用混乱和扩散技术充分隐藏初始序列及其冗余度；提高背包密度；模数保密；基于超递增序列的背包密码的安全性不依赖初始序列的保密。提出了一个背包密码的可证明安全性的启发性方法。据此，设计了一个新型背包密码，该密码由模乘运算实现混乱，由基于二元一次不定方程的难解函数实现扩散，充分隐藏初始序列及其冗余度，攻击者破译该背包密码的难度规约为求解此难解函数，同时能达到较高的背包密度，常规的破译方法无效。 关键词：背包公钥密码；安全要点；

2、可证明安全性；模乘运算；二元一次不定方程；难解函数中图分类号：TP309.7；TN918.4The Outline and Design of Secure Knapsack Public-key CryptosystemsFEI Xiang-dong ，DING Yan-yan，PAN Yu(1.College of Economics and Management, Nanjing University of Technology, 210009 Abstract ：In order to boost the security of knapsack public-key cryptosy

3、stem（KPC for short），this paper listed the security outline of KPC according to the causes that they had failed，that is，concealing the redundancy of initial sequence adequately by confusion and diffusion；improving the density of KPC；keeping the modulus secret；the super-increasing KPC security indepen

4、dent of the confidentiality of initial sequence. A heuristic provable security method of KPC was proposed. Accordingly ，a new KPC was designed. Modular multiplication was adopted for confusion，and a difficult solution function based on linear indifinite equation in two unknowns for diffusion，thus th

5、e redundancy of the initial sequence was concealed adequately. The difficulty for an adversary to break it is reduced to that of breaking the difficult solution function.Meanwhile，a higher knapsack density was reached. Conventional attacks were avoided. 基金项目：江苏省软科学研究计划项目(BR2010080费向东（1966.11-），男，江苏无

6、锡人，高级工程师，工学硕士，研究方向为密码算法与安全议，feixd0669Key words: knapsack public-key cryptosystem ；security outline ；provable security ；modular multiplication ；linear indifinite equation in two unknowns；difficult solution function0 引言目前在用的公钥密码都是基于因子分解或离散对数问题的，存在着如下不足：一是Shor 证明量子计算机能有效地进行因子分解和求解离散对数1，一旦量子计算机面世，则目前的公钥

7、密码全部无法使用。而就在最近，IBM 公司宣布在量子计算机的研究方面取得重大突破，已开发出可达到“实用量子计算机”最低标准的设备2；二是目前在用的公钥密码计算量大，运算速度慢，难以适应资源受限的场合。背包公钥密码以背包问题的NPC （NP-complete ，NP 完全性）性质和快速加解密优势成为解决以上不足的优选方案。因为Bennett 等人证明量子计算机上也不存在求解NPC 问题的有效算法3。一个安全的背包密码在量子计算环境下同样是安全的。但背包密码屡被破译，安全性令人担忧，其生存和发展的前提解决安全性评价问题。 目前评价公钥密码的安全性有两种方法，一是枚举安全性，把密码算法公布，一段时间

8、后没有被破译，就认为该密码算法暂时是安全的；二是可证明安全性理论，就是把密码算法的安全性规约到一个公认的数学难题，可证明安全性已成为公钥密码学领域的热点4。然而当前可证明安全的公钥密码大都是基于因子分解或离散对数问题的，学界对背包密码等快速公钥密码的安全性评价依然采用枚举安全性的方法，即讨论该密码能否抵抗已知或潜在的攻击。因此，总结了以往背包密码失败的原因，根据攻击手段，概括安全背包公钥密码的要点，是目前评价和设计安全背包密码的主要方法。 1 安全背包公钥密码要点1.1 初试序列及冗余度背包密码的设计思想通常是把一个易解背包问题通过陷门变换成一个看似困难的背包问题，陷门信息作为私钥仅被合法接收

9、者掌握，运用它可以把该问题恢复成一个易解背包问题，通过解该易解背包重构明文；而对非法接收者来说，从密文恢复明文就相当于解一个困难的背包问题。初始序列代表易解背包，具有一定规律和特性，如初始序列项之间的互素关系或超递增性，这些规律和特性形成初始序列的冗余度，背包公钥序列作为初始序列变换的最终结果，看似难解，但残留着这些冗余度。文献5指出利用初始序列或其冗余度是破译成功的必要条件。因此，加强背包密码安全性的方法为：在初始序列到公钥序列的变换过程中，运用混乱和扩散技术充分隐藏初始序列及冗余度，使得初始序列、公钥序列和密码之间的关系尽可能复杂，以至攻击者难以将三者联系起来而进行破译。1.2 背包密度0

10、-1背包密码的密度定义为：公钥序列(n a a A , . , 1=，n 位长的二进制明文(12. . i n m m m m =被加密为n n m a m a c +=. 11，其中i m 为0或1，背包密度为： /(max( i Density n lb a = ，n i ., , 1 =Coster 等人证明背包密度小于0.9408的背包密码都易遭受低密度子集和攻击6，而若背包密度大于1，又造成解密不唯一7。因此，安全的背包公钥密码密度必须在0.9408和1之间。并且，如果一个背包公钥密码的密度只是稍大于0.9408，也不能确保其能够抵御低密度子集和攻击8 14，背包公钥密码的密度应尽量

11、接近1。1.3 背包密码的模初始序列转换到公钥序列，一般要用到模运算。有些算法为了降低密文的膨胀率，将模数作为公钥的一部分予以公布，以往的经验表明，这样的背包密码几乎注定是要被破译的，模数将成为攻击成功的突破口，或被格攻击9,10或被代数攻击11,12破译。模数应该作为私钥的一部分予以保密。1.4 超递增初试序列对于基于超递增初始序列的背包密码，超递增初始序列的起始项数值较小，攻击者可根据序列维数和序列项的位长度进行猜测。因此，基于超递增背包密码的安全性不应该依赖初始序列的保密，初始序列即使公开也不影响其安全性。2 安全背包公钥密码的设计2.1 简单性原则如上所述，背包密码是将易解背包通过陷门

12、，变换成一看似难解的背包。囿于背包密码的快速加解密性质和背包密度，其设计适用简单性原则，包括规范的简单性和分析的简单性。规范的简单性，指密码算法仅采用有限个运算，这些运算是容易解释的，简单规范的优点是便于正确实现，不易隐藏错误。分析的简单性，指在密码的设计阶段就考虑其安全要点，以便密码的使用者易于理解密码算法如何抵御已知攻击，使得密码算法具有一定程度的可信度。2.2 可证明安全性的构造公钥密码就是一种陷门单向函数。对于背包公钥密码，其安全性首先规约为破解其中的陷门，如果陷门是牢不可破的，则该背包密码等价于真正的背包问题。据此，本文提出一种构造背包密码可证明安全性的启发性方法。设一背包公钥密码，

13、其初始序列B 经k 个陷门函数变换后得到公钥序列A ，即： 11( Y F B =221( Y F Y =(1 (1 (2 ( k k k Y F Y -=(1 ( k k A F Y -=各函数中的参数组成陷门信息，作为私钥保存。k F 的函数值作为公钥序列A 。如果函数k F 满足以下条件，则称为是难解函数：一，函数k F 的反函数1k F -难以表示，即(1 k Y -无法用公钥序列A 及函数k F 中的陷门信息表达；二，攻击者仅依靠函数值而不掌握函数k F 中的陷门信息，难以求解自变量(1 k Y -的值。如攻击者从公钥序列A 出发，初始序列及其冗余度被难解函数k F 掩盖，由于反函数

14、1k F -难以表达，此时，攻击者无法将公钥序列、密钥和初始序列联系起来，背包密码的安全性规约为破解该难解函数从而获得(1 k Y -。如攻击者从初始序列出发，假设(1 k Y -可以用初始序列和函数1F 、2F (1 k F -中的陷门信息表示，由于攻击者不掌握陷门信息，(1 k Y -的值对攻击者而言是未知数，此时公钥序列、密钥和初始序列之间的关系由函数k F 表达，背包密码的安全性依然规约为破解该难解函数而获得(1 k Y -。如果k F 、(1 k F -1F 不是难解函数，其反函数容易表达，则公钥序列、密钥和初始序列之间的关系可以由1F 的反函数表示，如果该关系是较为简单的线性关系，

15、可能是可以破译的 13，14。3 新型背包公钥密码算法根据上述设计方法，提出一种新型背包公钥密码。3.1 基于二元一次不定方程的难解函数二元一次整系数不定方程是初等数论15中最基本的不定方程，形式如下：a fv eu =+，其中，e 、f 和a 是已知整数，u 和v 是待解的未知数。 若该方程有解0U 和0V ，则其它一切解具有以下形式：0101u U f t v V e t=+=- 其中，1(, e e e f = ，1(, f f e f = ，(, e f 为e 和f 的最大公因子，t 为任意整数。 如果0U 和0V 为正整数，并且10f U ，10e V ，易见0U 和0V 是该方程的

16、唯一正整数解。设陷门函数( F x 由以下方式形成：2( j x u v F x eu fv =+=+其中，2j 为固定值，x 为自变量，e 和f 为陷门信息。自变量x 分组后，代入二元一次整系数不定方程生成函数值。( F x 为难解函数：一是其反函数无法表示，即2j x u v =+无法用函数值和陷门信息e 、f 表达；二是从目前的数学方法看，攻击者仅依赖函数值而不掌握陷门信息e 、f ，无法求解u 和v 。3.2 算法描述(1 选超递增初始序列 ,., ,., (1n i b b b B =， max(1i b b =，n i ., , 1 =(2 选互素的正整数w 和m ，满足=n i

17、i bm 1(3 运用乘数w ，对B 序列项i b 进行模乘运算，将B 转换D 序列：(; ,., 1 , mod n i m wb d i i =(n d d D ,. , 1=，设|m =h，则max(|i d =h，n i ., , 1 =|m 表示m 的比特位长度，下同。(4 对D 序列项i d 进行对称分组：i d 的长度以h=|m 位计（如高位不足，以0计），左起第2h j =位分为左、右长度相等两部分，形成i u 和i v ，|i i u v =，其中i j i i v u d +*=2；(5 选互素的正整数e 和f ，满足1n i i e v =，1n i i f u = 令i

18、 i i a eu fv =+ ，n i ., , 1 =公钥为：序列(n a a A , . , 1=；私钥为：e , f ，1w -，m超递增初始序列B 作为固定值嵌入算法中。加密：二进制明文(12. . i n x x x x =，0i x =或1，被加密为(n 11 . x a x a c n +=。 解密(1 解不定方程eu fv c +=，方法为：运用扩展欧几里德算法，计算X 和Y ，使得1eX fY += ；易见XC 和YC 是方程的一组解，以此计算出该不定方程的正整数解u 和v ；(2 计算v u dj +*=2 ； (3 计算 (mod1m d w z *=-(4 运用超递增

19、初始序列B 计算得明文x3.3 安全性分析初始序列通过两个陷门函数变换到公钥序列：模乘运算函数和基于二元一次方程的难解函数。前者为混乱技术，后者为扩散技术。第(3步模乘运算为乘法群运算，即在一个整数域中，用一个整数代替另一整数。其优点是雪崩效应明显，w 、m 及初始序列项i b 的微小变化，将引起模乘结果i d 的剧烈变化，尤其当乘数w 较大时。缺点是变换为线性，不足以隐藏初始序列及冗余度，有多种方法可以破译之13，16。第(4和第(5步将D 序列项i d 分为长度相等的两部分i u 和i v ，分别扩展e 倍和f 倍后叠加，i u 和i v所残留的冗余度扩散到整个公钥序列项i a 中，同时进

20、一步加大雪崩效应。对背包公钥密码的攻击主要有明文恢复攻击和密钥恢复攻击。前者是指从密文出发求解明文，后者是指重构密钥的构造过程，现分别讨论。3.3.1 明文恢复攻击如1.2节所述，背包密度应远大于0.9408、接近1才能保证安全。以n=512为例说明本密码算法的密度。(1 选超递增初始序列 ,., ,., (5121b b b B i =(2 选互素的正整数w 和m ，设|m =514(3 运用w 和m ，对初始序列B 进行模乘运算，得到D 序列(512,., 1 , mod =i m wb d i i ；其中max(|i d =514(4 对D 序列项i d 进行对称分组：以514 b长度计

21、，左起第257 b的位置分为左、右两部分，形成i u 和i v ，其中i i iv u d +*=2572 (5 选整数e 和f ，满足5121i i e v =，5121i i f u = ，e 和f 可取长度为266 b的正整数，由此，公钥序列A 中max(|i a =266+257+1=524 b ，n i ., , 1 =背包密度Density =512/524=0.9771 。从公钥膨胀效果看，运用二元一次整系数不定方程生成公钥序列，相当于一次模乘运算，有利于提高背包密度。3.3.2 密钥恢复攻击初始序列变换到公钥序列所运用的函数如下：（1）模乘运算函数1F1( i i F b wb

22、 km =-，1,2. i n =令1( i i d F b =，1,2. i n =（2）基于二元一次不定方程的难解函数2F ：*221,2. ( ji i i i i i d u v i n F d eu fv =+=+ 令公钥序列项2( ii a F d =，1,2. i n =在1F 函数中，由于i b 是公开的，攻击者可通过构造一个联立丢番图逼近问题，再运用格基规约算法求出k ，具体步骤参见文献17。但攻击者不掌握陷门信息w 和m ，所以i d 对攻击者来说是未知的。如2.2所述，攻击者无论从公钥序列A 出发，还是从初始序列B 出发，算法的安全性都规约为破解难解函数2F 。在本算法中

23、，D 序列是关键。攻击者只要获得D 序列，即使不掌握初始序列B ，只要利用其超递增性质再运用Shamir 破译法16就能解得w 、m 和初始序列B ，或它们的等价值。从这个角度看，初始超递增序列也没保密的必要。3.3.3 关于安全性的进一步讨论本文 3.2 节所提出的算法为基本型背包公钥密码，类似于RSA 基本型，为确定型加密算法，不满足有关公钥加密体制的安全性定义18,19。如：两者都不满足密文不可区分性（Indistinguishability ，IND ）；RSA 基本型不是CCA2（适应性选择密文攻击，Adaptive Chosen Ciphertext Attack）安全的，由于基本

24、型背包公钥密码是线性加密机制，即若m = m 1+ m 2 ，则c = c 1+ c 2，其中c 为明文m 对应的密文，该密码同样不是CCA2安全的。目前，对公钥密码的安全性要求达成的共识为IND-CCA2。为此，需要在加密前对明文填充随机信息，或对密文填充随机信息，使之成为一个概率加密算法，同时要求算法具备密文合法性测试（又称“明文感知性”，Plaintext Awareness，PA ）功能，以满足IND-CCA2 安全性。具体实现方案有待进一步深入研究。4 举例选超递增序列为：B =（58037，29018，14510，7253，3627，1813，907，453，227，113，57，

25、28，15，7，3，2）取模m=965613，w=724210，w 模m 的逆w -1=4，计算得：d1=738719=(10110100010110011111 2d2=490061=(011101111010010011012d3=486434=(011101101100001000102d4=726023=(101100010100000001112d5=242310=(001110110010100001102d6=724663=(101100001110101101112d7=241630=(001110101111110111102d8=724323=(10110000110101

26、1000112d9=241460=(001110101111001101002d10=724238=(101100001101000011102d11=724224=(101100001101000000002d12=7=(000000000000000001112d13=241407=(001110101110111111112d14=241405=(001110101110111111012d15=241404=(001110101110111111002d16=482807=(011101011101111101112其中，d12=7，数值太小，令d12= d12+m=7+965613=

27、965620=(11101011101111110100 2在d i 中间位置，即第10 b处分割d i ，形成U 序列和V 序列：U=（721，478，475，709，236，707，235，707，235，707，707，942，235，235，235，471）V=（415，589，34，7，646，695，990，355，820，270，256，1012，767，765，764，503）1618035i i u=，1618888i i v =；取e=8987，f=8135 ；存在（e ，f ）=1 计算i i i a eu fv =+，得公钥序列A ：A =（9855652，908730

28、1，4545415，6428728，7376142，6934134，10165595，9241734，8782645，8550259，8436369，16698374，8351490，8335220，8327085，8324782）设需加密的明文为x=1010100100100101计算得密文c= a1+ a3+ a5+ a8+ a11+ a14+ a16=56115314解密运算：解不定方程 8987813556115314u v +=得 u=3552 v=2974d=u*210+v=3640222b= w-1d mod m=4*3640222 mod 965613=76693解超递增背包得

29、：x=1010100100100101从本例中得出以下结论：乘数w 应尽可能接近模数m ，使初始序列B 中相临项的模乘结果显著不同，以加强雪崩效应；如果模乘结果D 序列项的值太小或汉明重量太低，可以加上模数m 掩盖；初始序列B 中相邻项之间的倍数关系不应相同，否则倍数关系可能传递到模乘结果D 序列中。选择一个理想的初始序列有一定难度，所以在本算法的设计中，将一个精选的初始序列嵌入算法，而不必由每个用户自行选择。5 结语本文总结了以往背包密码失败的原因，列举出安全背包公钥的要点，提出一种背包密码的可证明安全性的启发性方法。据此，设计了一个新型背包密码，该密码由模乘运算实现混乱，运用基于二元一次不

30、定方程的难解函数实现扩散，充分隐藏初始序列及其冗余度。攻击者无论是从公钥序列出发，还是从初始序列出发，该算法的破译难度都规约为破解该难解函数，同时能达到较高的背包密度，常规的破译方法不再有效。参考文献：1 Shor P WPolynomial time Algorithms for Prime Factorization and Discrete Logarithms on aQuantum ComputerJSIAM Journal of Computing，1997，26(5：1484-15092 IBM Research Advances Device Performance for Q

31、uantum ComputingEB/OL.2012-3-9.0669063 Bennett C H，Bernstein E，Brassard G，et a1Strengths and Weaknesses of QuantumComputingJSIAM Journal onComputing，1997，26(5：1510-15234 陈杰. 公钥密码体制安全性证明关键技术及应用研究D.上海交通大学博士学位论，20085 丁燕艳，费向东，潘郁. 重新认识背包公钥密码的安全性J . 计算机应用，2012，32（3）：694-6986 Coster M J, Joux A, LaMacchia B A, et al. Improved low-density subset sum algorithmsJ. Computational Complexity, 1992, 2(2: 111-128.7 Kunihiro NNew D