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

(1.吉林大學 計算機科學與技術學院，長春 130012;2.華東師范大學 計算機科學與軟件工程學院，上海 200062)

0 引 言

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

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

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

本文重點研究了如何設計實現(xiàn)半陷門單向函數(shù)，以及如何基于半陷門單向函數(shù)來構造公鑰密碼。

1 半陷門單向函數(shù)的設計與實現(xiàn)

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

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

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

由于半陷門單向函數(shù)分別涉及單向性和陷門性，所以在設計時要同時對二者進行構思，這就需要選擇合適的困難問題。為便于描述，文中常用的術語和基本符號如表1所示。

表1 基本符號

1.1 子集和問題與背包密碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 ft的安全性分析

(1)

(2)

式中：m為滿足1

(3)

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

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

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

1.4 ft的改進方案

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

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

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

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

(6)隨機選取(1,2,…,2n)的置換π，并用(π,M,W)對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 基于半陷門單向函數(shù)的公鑰密碼

2.1 方案構思

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

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

問題的關鍵是：對于給定的半陷門單向函數(shù)ft，如何構造滿足上述條件的函數(shù)g。

2.2 方案實現(xiàn)

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

2.2.1 密鑰生成算法：

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

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

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

2.2.2 加密算法：

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

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

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

2.2.3 解密算法：

(2)Fori:=1 TomDo

EndFor

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

3 分析驗證

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

由STOF_PKC的解密算法，易知：

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

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

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

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

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

表2 實驗結果

由實驗結果，可以看出：

(5)

3.2 STOF_PKC的安全性分析

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

(1)1≤i1

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

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

(6)

(7)

(8)

對于n>16，由

(9)

k=16,…,n-1

可得：

(10)

(11)

4 結束語

本文引入了“半陷門單向函數(shù)”的概念，并給出了基于半陷門單向函數(shù)來構造公鑰密碼的思路。在此基礎上，給出了一種新的背包密碼方案STOF_PKC，并證明了破解STOF_PKC等價于求解B中的Semi-SSP。因此，若B中的Semi-SSP是難解的，則STOF_PKC便是安全的。但尚有一些新問題有待解決，比如是否存在其他實現(xiàn)半陷門單向函數(shù)的方法、是否存在其他基于半陷門單向函數(shù)的公實現(xià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.