安全背包公鑰密碼的要點和設(shè)計93755

1、安全背包公鑰密碼的要點和設(shè)計費向東基金項目：江蘇省軟科學(xué)研究計劃項目(BR2010080)費向東（1966.11-），男，江蘇無錫人，高級工程師，工學(xué)碩士，研究方向為密碼算法與安全議，feixd0669 ，潘郁（南京工業(yè)大學(xué)經(jīng)濟與管理學(xué)院，南京 210009）摘要：為提高背包密碼的安全性，本文依據(jù)背包密碼以往失敗的原因，列舉安全背包公鑰的要點：運用混亂和擴散技術(shù)充分隱藏初始序列及其冗余度；提高背包密度；模數(shù)保密；基于超遞增序列的背包密碼的安全性不依賴初始序列的保密。提出了一個背包密碼的可證明安全性的啟發(fā)性方法。據(jù)此，設(shè)計了一個新型背包密碼，該密碼由模乘運算實現(xiàn)混亂，由基于二元一次不定方程的難解

2、函數(shù)實現(xiàn)擴散，充分隱藏初始序列及其冗余度，攻擊者破譯該背包密碼的難度規(guī)約為求解此難解函數(shù)，同時能達到較高的背包密度，常規(guī)的破譯方法無效。關(guān)鍵詞：背包公鑰密碼；安全要點；可證明安全性；模乘運算；二元一次不定方程；難解函數(shù)中圖分類號：TP309.7；TN918.4 The 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 Techno

3、logy, 210009)Abstract：In order to boost the security of knapsack public-key cryptosystem（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

4、 density of KPC；keeping the modulus secret；the super-increasing KPC security independent 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

5、 function based on linear indifinite equation in two unknowns for diffusion，thus the 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

6、. Conventional attacks were avoided.Key words: knapsack public-key cryptosystem ；security outline ；provable security ；modular multiplication ；linear indifinite equation in two unknowns；difficult solution function0 引言目前在用的公鑰密碼都是基于因子分解或離散對數(shù)問題的，存在著如下不足：一是Shor證明量子計算機能有效地進行因子分解和求解離散對數(shù)1，一旦量子計算機面世，則目前的公鑰密碼

7、全部無法使用。而就在最近，IBM公司宣布在量子計算機的研究方面取得重大突破，已開發(fā)出可達到“實用量子計算機”最低標(biāo)準(zhǔn)的設(shè)備2；二是目前在用的公鑰密碼計算量大，運算速度慢，難以適應(yīng)資源受限的場合。背包公鑰密碼以背包問題的NPC（NP-complete，NP完全性）性質(zhì)和快速加解密優(yōu)勢成為解決以上不足的優(yōu)選方案。因為Bennett等人證明量子計算機上也不存在求解NPC問題的有效算法3。一個安全的背包密碼在量子計算環(huán)境下同樣是安全的。但背包密碼屢被破譯，安全性令人擔(dān)憂，其生存和發(fā)展的前提解決安全性評價問題。目前評價公鑰密碼的安全性有兩種方法，一是枚舉安全性，把密碼算法公布，一段時間后沒有被破譯，就認

8、為該密碼算法暫時是安全的；二是可證明安全性理論，就是把密碼算法的安全性規(guī)約到一個公認的數(shù)學(xué)難題，可證明安全性已成為公鑰密碼學(xué)領(lǐng)域的熱點4。然而當(dāng)前可證明安全的公鑰密碼大都是基于因子分解或離散對數(shù)問題的，學(xué)界對背包密碼等快速公鑰密碼的安全性評價依然采用枚舉安全性的方法，即討論該密碼能否抵抗已知或潛在的攻擊。因此，總結(jié)了以往背包密碼失敗的原因，根據(jù)攻擊手段，概括安全背包公鑰密碼的要點，是目前評價和設(shè)計安全背包密碼的主要方法。1 安全背包公鑰密碼要點1.1 初試序列及冗余度背包密碼的設(shè)計思想通常是把一個易解背包問題通過陷門變換成一個看似困難的背包問題，陷門信息作為私鑰僅被合法接收者掌握，運用它可以把

9、該問題恢復(fù)成一個易解背包問題，通過解該易解背包重構(gòu)明文；而對非法接收者來說，從密文恢復(fù)明文就相當(dāng)于解一個困難的背包問題。初始序列代表易解背包，具有一定規(guī)律和特性，如初始序列項之間的互素關(guān)系或超遞增性，這些規(guī)律和特性形成初始序列的冗余度，背包公鑰序列作為初始序列變換的最終結(jié)果，看似難解，但殘留著這些冗余度。文獻5指出利用初始序列或其冗余度是破譯成功的必要條件。因此，加強背包密碼安全性的方法為：在初始序列到公鑰序列的變換過程中，運用混亂和擴散技術(shù)充分隱藏初始序列及冗余度，使得初始序列、公鑰序列和密碼之間的關(guān)系盡可能復(fù)雜，以至攻擊者難以將三者聯(lián)系起來而進行破譯。1.2 背包密度0-1背包密碼的密度定

10、義為：公鑰序列，n位長的二進制明文被加密為，其中為0或1，背包密度為： ，Coster等人證明背包密度小于0.9408的背包密碼都易遭受低密度子集和攻擊6，而若背包密度大于1，又造成解密不唯一7。因此，安全的背包公鑰密碼密度必須在0.9408和1之間。并且，如果一個背包公鑰密碼的密度只是稍大于0.9408，也不能確保其能夠抵御低密度子集和攻擊8 14，背包公鑰密碼的密度應(yīng)盡量接近1。1.3 背包密碼的模初始序列轉(zhuǎn)換到公鑰序列，一般要用到模運算。有些算法為了降低密文的膨脹率，將模數(shù)作為公鑰的一部分予以公布，以往的經(jīng)驗表明，這樣的背包密碼幾乎注定是要被破譯的，模數(shù)將成為攻擊成功的突破口，或被格攻擊

11、9,10或被代數(shù)攻擊11,12破譯。模數(shù)應(yīng)該作為私鑰的一部分予以保密。1.4 超遞增初試序列對于基于超遞增初始序列的背包密碼，超遞增初始序列的起始項數(shù)值較小，攻擊者可根據(jù)序列維數(shù)和序列項的位長度進行猜測。因此，基于超遞增背包密碼的安全性不應(yīng)該依賴初始序列的保密，初始序列即使公開也不影響其安全性。2 安全背包公鑰密碼的設(shè)計2.1 簡單性原則如上所述，背包密碼是將易解背包通過陷門，變換成一看似難解的背包。囿于背包密碼的快速加解密性質(zhì)和背包密度，其設(shè)計適用簡單性原則，包括規(guī)范的簡單性和分析的簡單性。規(guī)范的簡單性，指密碼算法僅采用有限個運算，這些運算是容易解釋的，簡單規(guī)范的優(yōu)點是便于正確實現(xiàn)，不易隱藏

12、錯誤。分析的簡單性，指在密碼的設(shè)計階段就考慮其安全要點，以便密碼的使用者易于理解密碼算法如何抵御已知攻擊，使得密碼算法具有一定程度的可信度。2.2 可證明安全性的構(gòu)造公鑰密碼就是一種陷門單向函數(shù)。對于背包公鑰密碼，其安全性首先規(guī)約為破解其中的陷門，如果陷門是牢不可破的，則該背包密碼等價于真正的背包問題。據(jù)此，本文提出一種構(gòu)造背包密碼可證明安全性的啟發(fā)性方法。設(shè)一背包公鑰密碼，其初始序列經(jīng)k個陷門函數(shù)變換后得到公鑰序列，即：各函數(shù)中的參數(shù)組成陷門信息，作為私鑰保存。的函數(shù)值作為公鑰序列。如果函數(shù)滿足以下條件，則稱為是難解函數(shù)：一，函數(shù)的反函數(shù)難以表示，即無法用公鑰序列及函數(shù)中的陷門信息表達；二，

13、攻擊者僅依靠函數(shù)值而不掌握函數(shù)中的陷門信息，難以求解自變量的值。如攻擊者從公鑰序列出發(fā)，初始序列及其冗余度被難解函數(shù)掩蓋，由于反函數(shù)難以表達，此時，攻擊者無法將公鑰序列、密鑰和初始序列聯(lián)系起來，背包密碼的安全性規(guī)約為破解該難解函數(shù)從而獲得。如攻擊者從初始序列出發(fā)，假設(shè)可以用初始序列和函數(shù)、中的陷門信息表示，由于攻擊者不掌握陷門信息，的值對攻擊者而言是未知數(shù)，此時公鑰序列、密鑰和初始序列之間的關(guān)系由函數(shù)表達，背包密碼的安全性依然規(guī)約為破解該難解函數(shù)而獲得。如果、不是難解函數(shù)，其反函數(shù)容易表達，則公鑰序列、密鑰和初始序列之間的關(guān)系可以由的反函數(shù)表示，如果該關(guān)系是較為簡單的線性關(guān)系，可能是可以破譯的

14、 13，14。3 新型背包公鑰密碼算法根據(jù)上述設(shè)計方法，提出一種新型背包公鑰密碼。3.1 基于二元一次不定方程的難解函數(shù)二元一次整系數(shù)不定方程是初等數(shù)論15中最基本的不定方程，形式如下：，其中，、和是已知整數(shù)，和是待解的未知數(shù)。若該方程有解和，則其它一切解具有以下形式： 其中， ， ，為和的最大公因子，為任意整數(shù)。如果和為正整數(shù)，并且，易見和是該方程的唯一正整數(shù)解。設(shè)陷門函數(shù)由以下方式形成：其中，為固定值，為自變量，和為陷門信息。自變量分組后，代入二元一次整系數(shù)不定方程生成函數(shù)值。 為難解函數(shù)：一是其反函數(shù)無法表示，即無法用函數(shù)值和陷門信息、表達；二是從目前的數(shù)學(xué)方法看，攻擊者僅依賴函數(shù)值而不

15、掌握陷門信息、，無法求解和。3.2 算法描述(1) 選超遞增初始序列，(2) 選互素的正整數(shù)和，滿足(3) 運用乘數(shù)，對序列項進行模乘運算，將轉(zhuǎn)換序列： ，設(shè)=h，則=h， 表示的比特位長度，下同。(4) 對序列項進行對稱分組：的長度以h=位計（如高位不足，以0計），左起第位分為左、右長度相等兩部分，形成和，其中； (5) 選互素的正整數(shù)和，滿足， 令 ，公鑰為：序列；私鑰為：,，超遞增初始序列作為固定值嵌入算法中。 加密：二進制明文，或1，被加密為。 解密(1) 解不定方程，方法為：運用擴展歐幾里德算法，計算X和Y，使得 ；易見和是方程的一組解，以此計算出該不定方程的正整數(shù)解和 ；(2) 計

16、算 ；(3) 計算 (4) 運用超遞增初始序列計算得明文x3.3 安全性分析初始序列通過兩個陷門函數(shù)變換到公鑰序列：模乘運算函數(shù)和基于二元一次方程的難解函數(shù)。前者為混亂技術(shù)，后者為擴散技術(shù)。第(3)步模乘運算為乘法群運算，即在一個整數(shù)域中，用一個整數(shù)代替另一整數(shù)。其優(yōu)點是雪崩效應(yīng)明顯，、及初始序列項的微小變化，將引起模乘結(jié)果的劇烈變化，尤其當(dāng)乘數(shù)較大時。缺點是變換為線性，不足以隱藏初始序列及冗余度，有多種方法可以破譯之13，16。第(4)和第(5)步將序列項分為長度相等的兩部分和，分別擴展倍和倍后疊加，和所殘留的冗余度擴散到整個公鑰序列項中，同時進一步加大雪崩效應(yīng)。對背包公鑰密碼的攻擊主要有明

17、文恢復(fù)攻擊和密鑰恢復(fù)攻擊。前者是指從密文出發(fā)求解明文，后者是指重構(gòu)密鑰的構(gòu)造過程，現(xiàn)分別討論。3.3.1 明文恢復(fù)攻擊如1.2節(jié)所述，背包密度應(yīng)遠大于0.9408、接近1才能保證安全。以n=512為例說明本密碼算法的密度。(1) 選超遞增初始序列(2) 選互素的正整數(shù)w和m ，設(shè)=514 (3) 運用w和m，對初始序列進行模乘運算，得到序列；其中=514(4) 對序列項進行對稱分組：以514 b長度計，左起第257 b的位置分為左、右兩部分，形成和，其中(5) 選整數(shù)和，滿足， ，和可取長度為266 b的正整數(shù)，由此，公鑰序列中=266+257+1=524 b ，背包密度=512/524=0.

18、9771 。從公鑰膨脹效果看，運用二元一次整系數(shù)不定方程生成公鑰序列，相當(dāng)于一次模乘運算，有利于提高背包密度。3.3.2 密鑰恢復(fù)攻擊初始序列變換到公鑰序列所運用的函數(shù)如下：（1）模乘運算函數(shù)，令， （2）基于二元一次不定方程的難解函數(shù)：令公鑰序列項，在函數(shù)中，由于是公開的，攻擊者可通過構(gòu)造一個聯(lián)立丟番圖逼近問題，再運用格基規(guī)約算法求出，具體步驟參見文獻17。但攻擊者不掌握陷門信息和，所以對攻擊者來說是未知的。如2.2所述，攻擊者無論從公鑰序列出發(fā)，還是從初始序列出發(fā)，算法的安全性都規(guī)約為破解難解函數(shù)。在本算法中，序列是關(guān)鍵。攻擊者只要獲得序列，即使不掌握初始序列，只要利用其超遞增性質(zhì)再運用S

19、hamir破譯法16就能解得、和初始序列，或它們的等價值。從這個角度看，初始超遞增序列也沒保密的必要。3.3.3 關(guān)于安全性的進一步討論本文 3.2 節(jié)所提出的算法為基本型背包公鑰密碼，類似于RSA 基本型，為確定型加密算法，不滿足有關(guān)公鑰加密體制的安全性定義18,19。如：兩者都不滿足密文不可區(qū)分性（Indistinguishability，IND）；RSA 基本型不是CCA2（適應(yīng)性選擇密文攻擊，Adaptive Chosen Ciphertext Attack）安全的，由于基本型背包公鑰密碼是線性加密機制，即若m = m1+ m2 ，則c = c1+ c2，其中c為明文m 對應(yīng)的密文，該

20、密碼同樣不是CCA2安全的。目前，對公鑰密碼的安全性要求達成的共識為IND-CCA2。為此，需要在加密前對明文填充隨機信息，或?qū)γ芪奶畛潆S機信息，使之成為一個概率加密算法，同時要求算法具備密文合法性測試（又稱“明文感知性”，Plaintext Awareness，PA）功能，以滿足IND-CCA2安全性。具體實現(xiàn)方案有待進一步深入研究。4 舉例選超遞增序列為：=（58037，29018，14510，7253，3627，1813，907，453，227，113，57，28，15，7，3，2）取模m=965613，w=724210，w 模m的逆w-1=4，計算得：d1=738719=(101101

21、00010110011111 )2 d2=490061=(01110111101001001101)2d3=486434=(01110110110000100010)2d4=726023=(10110001010000000111)2d5=242310=(00111011001010000110)2d6=724663=(10110000111010110111)2d7=241630=(00111010111111011110)2d8=724323=(10110000110101100011)2d9=241460=(00111010111100110100)2d10=724238=(101100

22、00110100001110)2d11=724224=(10110000110100000000)2d12=7=(00000000000000000111)2d13=241407=(00111010111011111111)2d14=241405=(00111010111011111101)2d15=241404=(00111010111011111100)2d16=482807=(01110101110111110111)2其中，d12=7，數(shù)值太小，令d12= d12+m=7+965613=965620=(11101011101111110100 )2在di 中間位置，即第10 b處分割d

23、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），；取e=8987，f=8135 ；存在（e，f）=1計算，得公鑰序列：=（9855652，9087301，4545415，6428728，7376142，6934134，10165595，9241734，8782645， 8550259，8436369，16698374，8351490，8335220，832

24、7085，8324782）設(shè)需加密的明文為x=1010100100100101計算得密文c= a1+ a3+ a5+ a8+ a11+ a14+ a16=56115314解密運算：解不定方程 得 u=3552 v=2974d=u*210+v=3640222b= w-1d mod m=4*3640222 mod 965613=76693解超遞增背包得：x=1010100100100101從本例中得出以下結(jié)論：乘數(shù)w應(yīng)盡可能接近模數(shù)m，使初始序列B中相臨項的模乘結(jié)果顯著不同，以加強雪崩效應(yīng)；如果模乘結(jié)果序列項的值太小或漢明重量太低，可以加上模數(shù)m掩蓋；初始序列中相鄰項之間的倍數(shù)關(guān)系不應(yīng)相同，否則倍

25、數(shù)關(guān)系可能傳遞到模乘結(jié)果序列中。選擇一個理想的初始序列有一定難度，所以在本算法的設(shè)計中，將一個精選的初始序列嵌入算法，而不必由每個用戶自行選擇。5 結(jié)語本文總結(jié)了以往背包密碼失敗的原因，列舉出安全背包公鑰的要點，提出一種背包密碼的可證明安全性的啟發(fā)性方法。據(jù)此，設(shè)計了一個新型背包密碼，該密碼由模乘運算實現(xiàn)混亂，運用基于二元一次不定方程的難解函數(shù)實現(xiàn)擴散，充分隱藏初始序列及其冗余度。攻擊者無論是從公鑰序列出發(fā)，還是從初始序列出發(fā)，該算法的破譯難度都規(guī)約為破解該難解函數(shù)，同時能達到較高的背包密度，常規(guī)的破譯方法不再有效。參考文獻：1 Shor P WPolynomialtime Algorithm

26、s for Prime Factorization and Discrete Logarithms on a Quantum ComputerJSIAM Journal of Computing，1997，26(5)：1484-15092 IBM Research Advances Device Performance for Quantum ComputingEB/OL.2012-3-9. 0669063 Bennett C H，Bernstein E，Brassard G，et a1Strengths and Weaknesses of Quantum ComputingJSIAM Jou

27、rnal onComputing，1997，26(5)：1510-15234 陳杰. 公鑰密碼體制安全性證明關(guān)鍵技術(shù)及應(yīng)用研究D.上海交通大學(xué)博士學(xué)位論，20085 丁燕艷，費向東，潘郁.重新認識背包公鑰密碼的安全性J.計算機應(yīng)用，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 Definition of Density on Knapsack CryptosystemsC/Advances in Cryptology-Africacrypt 2008：LNCS 5023Berli