基于半陷門(mén)單向函數(shù)的公鑰密碼

趙 博, 秦貴和, 趙永哲, 楊文迪

(1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春 130012;2.華東師范大學(xué) 計(jì)算機(jī)科學(xué)與軟件工程學(xué)院，上海 200062)

0 引 言

1976年，Diffie和Hellman[1]發(fā)表了著名文章《密碼學(xué)的新方向”，文章引入了“公鑰密碼”的概念，并提出基于“陷門(mén)單向函數(shù)(Trapdoor one-way function)”來(lái)構(gòu)造公鑰密碼的思想。不久，第一批公鑰密碼方案便被提了出來(lái)，它們分別是Merkle和Hellman基于背包問(wèn)題的MH密碼體制[2]以及Rivest、Shamir和Adelman基于整數(shù)分解問(wèn)題的RSA密碼體制[3]。隨后Rabin、ElGamal、ECC等公鑰密碼體制也相繼問(wèn)世。

進(jìn)入到21世紀(jì)，現(xiàn)有公鑰密碼(RSA、ElGamal、ECC等)日益受到量子計(jì)算的威脅[4,5]，為了應(yīng)對(duì)挑戰(zhàn)，國(guó)際密碼學(xué)界提出了“后量子密碼學(xué)(Post-quantum cryptography，PQC)”的新學(xué)科方向。PQC的主要目標(biāo)便是研究能抵抗量子計(jì)算的公鑰密碼(Quantum resistant public key cryptography)，目前主要基于量子計(jì)算機(jī)不擅長(zhǎng)計(jì)算的數(shù)學(xué)難題(比如NPC問(wèn)題)來(lái)設(shè)計(jì)密碼，該類(lèi)密碼主要有如下幾個(gè)研究方向：基于格上困難問(wèn)題的密碼[6]、基于糾錯(cuò)碼譯碼問(wèn)題的密碼[7]、基于多變量的密碼[8]、基于辮子群(Braid Group)的密碼[9]以及基于背包問(wèn)題的密碼[2,10]。

但目前所提出的抗量子計(jì)算公鑰密碼方案中的絕大多數(shù)都已被證明是不安全的。盡管不斷有新方案被提出，但從構(gòu)造方法來(lái)看，這些方案不外乎兩大類(lèi)：其一是基于“陷門(mén)單向函數(shù)”，這類(lèi)公鑰密碼占絕大多數(shù)，其關(guān)鍵在于如何設(shè)計(jì)陷門(mén)。其二則是基于“非對(duì)稱(chēng)密鑰交換”，其關(guān)鍵在于如何實(shí)現(xiàn)非對(duì)稱(chēng)的密鑰交換，這往往要用到“單向函數(shù)”。一般說(shuō)來(lái)，尋找單向函數(shù)要比尋找陷門(mén)單向函數(shù)容易得多，但單向函數(shù)不可逆，故不能直接用來(lái)實(shí)現(xiàn)公鑰密碼。而利用陷門(mén)單向函數(shù)雖可直接實(shí)現(xiàn)公鑰密碼，但由于“陷門(mén)性”和“單向性”的固有矛盾，使得二者很難兼顧。為了構(gòu)造陷門(mén)，就必然要犧牲單向性；反之亦然。

本文重點(diǎn)研究了如何設(shè)計(jì)實(shí)現(xiàn)半陷門(mén)單向函數(shù)，以及如何基于半陷門(mén)單向函數(shù)來(lái)構(gòu)造公鑰密碼。

1 半陷門(mén)單向函數(shù)的設(shè)計(jì)與實(shí)現(xiàn)

為了同時(shí)兼顧陷門(mén)性和單向性，本文引入了“半陷門(mén)單向函數(shù)(Semi-trapdoor one-way function,STOF)”的概念，其定義如下：

定義1 “半陷門(mén)單向函數(shù)”是一族“半可逆”的陷門(mén)函數(shù)：ft:X→Y，滿足：

(1)已知ft和x∈X，計(jì)算y=ft(x)是容易的。

由于半陷門(mén)單向函數(shù)分別涉及單向性和陷門(mén)性，所以在設(shè)計(jì)時(shí)要同時(shí)對(duì)二者進(jìn)行構(gòu)思，這就需要選擇合適的困難問(wèn)題。為便于描述，文中常用的術(shù)語(yǔ)和基本符號(hào)如表1所示。

表1 基本符號(hào)

1.1 子集和問(wèn)題與背包密碼

“子集和問(wèn)題(Subset sum problem,SSP,)”是“0-1背包問(wèn)題”的一個(gè)特例。其定義如下：

SSP是著名的NPC問(wèn)題。大多數(shù)背包密碼都是基于SSP來(lái)構(gòu)造的。為了保證解密的唯一性，公鑰背包向量還必須滿足USS(Unique Subset Sum)，即唯一子集和條件。但已有的的背包密碼通常無(wú)法抵御“低密度攻擊”，背包向量的“密度”定義如下：

由文獻(xiàn)[11-13]，若DA>1，則A通常不滿足USS條件。事實(shí)上，很多USS背包向量的密度都?1。早期算法[14]可破解密度小于0.6463的背包密碼，改進(jìn)后算法[15]則可破解密度小于0.9408的背包密碼。故為了抵御低密度攻擊，公鑰背包除應(yīng)滿足USS條件外，還應(yīng)具有高密度(大于0.9408)，但這二者往往很難兼顧，這也是設(shè)計(jì)背包密碼的難點(diǎn)所在。

若DA<1∧DA≈1，則A中SSP通常有唯一解。而若DA>1∧DA≈1，則A中SSP通常有多解。這兩種情形均易受到基于格的攻擊[16,17]。只有當(dāng)DA≈1時(shí)，對(duì)A中SSP無(wú)有效的解法。Impagliazzo和Naor亦證明，當(dāng)DA=1時(shí)，求解A中SSP是最困難的[18]。多年來(lái)，對(duì)SSP最快的通用解法仍是Schroeppel和Shamir在1981年提出的[19]，算法的時(shí)空復(fù)雜度分別為O(n·2n/2)和O(n·2n/4)。最近才有人對(duì)其進(jìn)行了優(yōu)化[20]，但改進(jìn)算法仍是指數(shù)級(jí)的，只是將時(shí)間復(fù)雜度降為O(n·2n/3)。

若在[1,2n]中均勻隨機(jī)選擇A=(a1,…,an)，則A通常是難解的。實(shí)驗(yàn)發(fā)現(xiàn)，如此得到的A通常不滿足USS條件。實(shí)際上，當(dāng)DA≈1時(shí)，判定A是否滿足USS條件亦是NPC問(wèn)題[21]。

1.2 基于SSP的半陷門(mén)單向函數(shù)

可基于SSP的難解和易解性來(lái)設(shè)計(jì)半陷門(mén)單向函數(shù)。為此引入“半超遞增背包向量”的定義如下：

顯然，對(duì)于半超遞增背包向量，可快速求出其SSP解的后半部，且易證如下定理：

(1)A中SSP易解當(dāng)且僅當(dāng)A[1,n]中SSP易解。

(2)A為USS背包當(dāng)且僅當(dāng)A[1,n]為USS背包。

(3)若A[1,n]中SSP是難解的，則求解A中SSP的前半部亦是困難的。

基于半超遞增背包向量，可得半陷門(mén)單向函數(shù)ft:{0,1}2n→N的設(shè)計(jì)方案如下：

(1)選擇安全參數(shù)n；

(4)隨機(jī)選取M,W∈N+，其中:

(5)隨機(jī)選取(1,2,…,2n)的置換π，并用(π,M,W)對(duì)A模乘變換得B=(b1,b2,…,b2n)，其中bπ(i)=Wai(modM)；

(6)以t=(A,π,M,W-1)為陷門(mén)(A不用全保存，僅保存A[n+1,2n]即可)，并將B公開(kāi)；

1.3 ft的安全性分析

(1)

(2)

式中：m為滿足1

(3)

由式(3)可得等價(jià)的陷門(mén)t′=(A″,π′,M′,U)，從而完全破解ft，其中：

由于B是直接由A經(jīng)模乘變換所得，故可基于Lenstra關(guān)于固定變?cè)獢?shù)量的整數(shù)規(guī)劃問(wèn)題可在多項(xiàng)式時(shí)間內(nèi)求解，以及A的“半超遞增”性來(lái)破解(M′,U)[14,22]。而ft在該攻擊下是不安全的。

與MOOC融合的路徑選擇，是國(guó)內(nèi)外圖書(shū)館界開(kāi)展理論探討與實(shí)踐探索的重點(diǎn)內(nèi)容。智力支持、技術(shù)支持、信息資源支持、實(shí)體空間支持，是圖書(shū)館與MOOC融合的4條主要路徑。從已有研究?jī)?nèi)容看，國(guó)內(nèi)圖書(shū)館界主要側(cè)重論述通過(guò)開(kāi)展版權(quán)服務(wù)、信息素養(yǎng)教育、嵌入課程輔導(dǎo)等提供智力支持，通過(guò)開(kāi)展課程制作協(xié)助、學(xué)習(xí)者行為搜集分析與研判、MOOC平臺(tái)技術(shù)優(yōu)化等提供技術(shù)支持來(lái)與MOOC進(jìn)行融合。然而，目前國(guó)內(nèi)支持MOOC發(fā)展的相關(guān)政策及法律環(huán)境尚不完善，圖書(shū)館現(xiàn)有智力資源、技術(shù)力量與MOOC的發(fā)展需要尚不匹配，圖書(shū)館所能提供的智力支持和技術(shù)支持與國(guó)內(nèi)現(xiàn)階段MOOC發(fā)展的實(shí)際需求之間相差較遠(yuǎn)。

1.4 ft的改進(jìn)方案

改進(jìn)思路是使(xπ(n+1),…,xπ(2n))不是由(xπ(n+1),…,xπ(2n))∈{0,1}n直接經(jīng)模乘變換得到，而是由無(wú)明顯特征的背包向量經(jīng)模乘變換得到，如此可使上述攻擊無(wú)效，改進(jìn)方案如下：

(1)選擇安全參數(shù)n。

(5)隨機(jī)選取Δ=(δ1,δ2，…,δ2n)∈{-1,0,1}2n，ω∈ZM；并用(M,Δ,ω)對(duì)A進(jìn)行變換得C=(c1,c2,…,c2n)=A+Δ·ω(modM)，即：

ci=(ai+δiω)(modM)(i=1,2,…,2n)。

(6)隨機(jī)選取(1,2,…,2n)的置換π，并用(π,M,W)對(duì)C模乘變換得B=(b1,b2,…,b2n)，即：bπ(i)=Wci(modM) (i=1,2,…,2n)。

(2)Fork=-n2Ton1Do

S:=(SC-kω)(modM);

Fori=2nDownto (n+1) Do

If(S≥ai) Then

xπ(i):=1;

S:=S-ai;

Else

xπ(i):=0;

EndIf

EndFor

Xk:=(xπ(n+1),…,xπ(2n));

輸出Xk;

EndIf

EndFor

(4)

2 基于半陷門(mén)單向函數(shù)的公鑰密碼

2.1 方案構(gòu)思

由于半陷門(mén)單向函數(shù)不能單獨(dú)用來(lái)構(gòu)造公鑰密碼。所以我們的方案構(gòu)思是：以(ft,g)為公鑰，t為私鑰。這里ft:X→Y是半陷門(mén)單向函數(shù)，而函數(shù)g:X→Z則應(yīng)滿足：

(1)由g和x∈X，計(jì)算z=g(x)是容易的。

問(wèn)題的關(guān)鍵是：對(duì)于給定的半陷門(mén)單向函數(shù)ft，如何構(gòu)造滿足上述條件的函數(shù)g。

2.2 方案實(shí)現(xiàn)

基于上述思路，本文給出了一種新的公鑰密碼方案，即STOF_PKC。STOF_PKC是基于第1節(jié)所構(gòu)造的半陷門(mén)單向函數(shù)ft，以及F2上一個(gè)n×2n矩陣G來(lái)實(shí)現(xiàn)的，方案由密鑰生成、加密、解密三個(gè)算法構(gòu)成，具體如下：

2.2.1 密鑰生成算法：

(1)選擇安全參數(shù)n；

(2)構(gòu)造半陷門(mén)單向函數(shù)ft，其陷門(mén)t=(A,Δ,ω,π,M,W)，輸出參數(shù)為B；

(5)以t為私鑰，(B,G)為公鑰。

2.2.2 加密算法：

明文消息為x=(x1,x2,…,x2n)∈{0,1}2n{0}，發(fā)送方對(duì)x加密過(guò)程如下：

(1)獲得接收方的公鑰(B,G)；

(3)將密文(y,z)發(fā)送給接收方。

2.2.3 解密算法：

(2)Fori:=1 TomDo

EndFor

(3)算法結(jié)束，所輸出者即為候選明文(集)。

3 分析驗(yàn)證

3.1 STOF_PKC解密的正確性和唯一性分析

由STOF_PKC的解密算法，易知：

(1)若明密文之間是一對(duì)一的，則密文經(jīng)解密后可唯一確定明文。

(2)若明密文之間是多對(duì)一的，則密文經(jīng)解密后能得到一個(gè)明文集合，且該集合恰好包含與給定密文對(duì)應(yīng)的所有明文。

(3)若密文不對(duì)應(yīng)任何明文，則密文解密后得空集。

理想情形是每一個(gè)密文都僅對(duì)應(yīng)唯一的明文，此時(shí)不僅可提高解密效率，還可保證解密的唯一性。令明文空間P={0,1}2n{0}，則STOF_PKC滿足解密唯一性的充要條件是：不存在x,x′∈P(x≠x′)使ft(x)=ft(x′)∧G·x=G·x′。

設(shè)B的所有22n-1種非零子集和共有n_ss種取值，其中只與唯一子集和對(duì)應(yīng)的取值共有n_uss種，則n_uss≤n_ss，且B滿足USS條件當(dāng)且僅當(dāng)n_uss=n_ss。顯然，若B滿足USS條件，則STOF_PKC必滿足解密唯一性。但這是NPC問(wèn)題，無(wú)有效的判定算法。所以通過(guò)實(shí)驗(yàn)來(lái)對(duì)此進(jìn)行分析，實(shí)驗(yàn)對(duì)不同的n，獨(dú)立生成10 000個(gè)ft實(shí)例，然后對(duì)DB、n_ss、n_uss計(jì)算平均值，并統(tǒng)計(jì)B滿足USS條件的出現(xiàn)數(shù)量，結(jié)果見(jiàn)表2。

表2 實(shí)驗(yàn)結(jié)果

由實(shí)驗(yàn)結(jié)果，可以看出：

(5)

3.2 STOF_PKC的安全性分析

首先給出Semi-SSP(半子集和問(wèn)題)的定義：

(1)1≤i1

SSP和Semi-SSP的區(qū)別在于，前者對(duì)每個(gè)背包分量都要精確判定其是否屬于給定的“子集和”，而后者只需對(duì)一半背包分量進(jìn)行精確判定。若SSP可解，則Semi-SSP必可解，反之亦然。即Semi-SSP也是NPC問(wèn)題。關(guān)于STOF_PKC的安全性，有：

定理2 破解STOF_PKC等價(jià)于求解B中的Semi-SSP。

(6)

(7)

(8)

對(duì)于n>16，由

(9)

k=16,…,n-1

可得：

(10)

(11)

4 結(jié)束語(yǔ)

本文引入了“半陷門(mén)單向函數(shù)”的概念，并給出了基于半陷門(mén)單向函數(shù)來(lái)構(gòu)造公鑰密碼的思路。在此基礎(chǔ)上，給出了一種新的背包密碼方案STOF_PKC，并證明了破解STOF_PKC等價(jià)于求解B中的Semi-SSP。因此，若B中的Semi-SSP是難解的，則STOF_PKC便是安全的。但尚有一些新問(wèn)題有待解決，比如是否存在其他實(shí)現(xiàn)半陷門(mén)單向函數(shù)的方法、是否存在其他基于半陷門(mén)單向函數(shù)的公實(shí)現(xiàn)簽名等，需要進(jìn)行更深入的探索。

[1] Diffie W，Hellman M E. New directions in cryptography[J]. IEEE Transactions on Information Theory, 1976, 22:644-654.

[2] Merkle R C,Hellman M E. Hiding information and signatures in trapdoor knapsacks[J]. IEEE Transactions on Information Theory, 1978, 24:525-530.

[3] Rivest R L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the Acm, 1983, 26:96-99.

[4] Shor P W. In algorithms for quantum computation: Discrete logarithms and factoring, foundations of computer Science[C]∥Proceedings on Symposium,Murray Hill,NJ,USA, 1994:124-134.

[5] Grover L K. A fast quantum mechanical algorithm for database search[C]∥Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing,Philade lphia,PA,USA, 1996:212-219.

[6] Poulakis D. On the cryptographic long term security[J]. Journal of Applied Mathematics & Bioinformatics, 2013,3(1):1-15.

[7] Courtois N, Finiasz M, Sendrier N. In how to achieve a mceliece-based digital signature scheme[C]∥ International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, 2001: 157-174.

[8] Porras J, Baena J, Ding J Zhfe.A new multivariate public key encryption scheme[Z].Post-Quantum Cryptogaphy,2014:229-245.

[9] Dehornoy P. Using shifted conjugacy in braid-based cryptography[J]. Computer Science,2006,418:65-73.

[10] Okamoto T,Tanaka K,Uchiyama S. Quantum public-key cryptosystems[J]. International Journal of Theoretical Physics, 2011, 51:912-924.

[11] Elkies N D. An improved lower bound on the greatest element of a sum-distinct set of fixed order[J]. Journal of Combinatorial Theory, 1986, 41:89-94.

[12] Guy R K. Unsolved Problems in Number Theory[M].New York-Berlin:Springer-Verlag,2001:17-35.

[13] Kate A, Goldberg I. Generalizing cryptosystems based on the subset sum problem[J]. International Journal of Information Security,2011, 10:189-199.

[14] Brickell E F. Breaking iterated knapsacks[C]∥Advances in Cryptology, Proceedings of CRYPTO’84, Santa Barbara, California, USA, 1984:342-358.

[15] Coster M J,Joux A, Lamacchia B A, et al.Improved low-density subset sum algorithms[J]. Computational Complexity 1999, 2:111-128.

[16] Joux A. A practical Attack Against Knapsack based Hash Functions (Extended )[M].Berlin Heidelberg:Springer,1994:58-66.

[18] Impagliazzo R, Naor M. Efficient cryptographic schemes provably as secure as subset sum[J]. Journal of Cryptology,1996,9:199-216.

[19] Schroeppel R, Shamir A. AT=O(2n/2),S=O(2n/4) algorithm for certain NP-complete problems[J]. Siam Journal on Computing, 1981,10(3): 456-464.

[20] Li Qing-hua, Li Ken-li, Jiang Sheng-yi, et al. An optimal parallel algorithm for the knapsack problem[J]. Journal of Software, 2003, 14(14):891-896.

[21] Christos H Papadimitriou. On the complexity of unique solutions[J]. Journal of the ACM, 1984, 31(2):392-400.

[22] Shamir A. A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem[J].IEEE Transactions on Information Theory,1984,30(5):699-704.