破解HFEM公鑰密碼方案

古春生

(1. 江蘇理工學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 常州 213001；2. 中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230027；3. 常州市云計(jì)算與智能信息處理重點(diǎn)實(shí)驗(yàn)室，江蘇 常州 213001）

1 引言

由于計(jì)算數(shù)論上的因式分解問題、離散對(duì)數(shù)問題和橢圓曲線對(duì)數(shù)問題存在多項(xiàng)式時(shí)間量子算法[1,2]，因此，研究既能抵抗經(jīng)典密碼分析技術(shù)，又能抵抗量子密碼分析技術(shù)的公鑰密碼方案是公鑰密碼學(xué)發(fā)展中的重要問題。目前設(shè)計(jì)抗量子計(jì)算的公鑰密碼方案成為密碼學(xué)研究的熱點(diǎn)之一。當(dāng)前密碼學(xué)界認(rèn)為能抗量子計(jì)算的公鑰密碼方案主要有基于散列問題的公鑰密碼、基于編碼問題的公鑰密碼、基于格問題的公鑰密碼、基于多變量問題的公鑰密碼等[3]。在這些公鑰密碼方案中，基于多變量的公鑰密碼因其計(jì)算速度快，密碼膨脹率低的特點(diǎn)而成為“后量子密碼學(xué)”研究的重要方向。近年來，設(shè)計(jì)構(gòu)造基于遍歷矩陣性質(zhì)的密碼原語已經(jīng)引起了研究人員的廣泛關(guān)注[4～9]。文獻(xiàn)[4～6,8]研究了GF(2k)上的遍歷矩陣性質(zhì)，并給出了其在加密數(shù)據(jù)、生成偽隨機(jī)數(shù)、生成信息摘要、Shamir三次傳遞協(xié)議等密碼學(xué)上的應(yīng)用，文獻(xiàn)[10～12]利用遍歷矩陣研究了公鑰密碼協(xié)議的半群作用問題。文獻(xiàn)[13]構(gòu)造了基于有限域上遍歷矩陣的雙側(cè)冪乘問題的公鑰加密方案。文獻(xiàn)[14]基于BMQ問題(bisection multivariate quadratic equation problem)的困難性提出了隱藏域上遍歷矩陣的公鑰密碼方案。盡管文獻(xiàn)[14]證明了有限域上BMQ問題是NP完全，但并沒有證明基于隱藏域上公鑰密碼方案的安全性。本文主要構(gòu)造破解文獻(xiàn)[14]中 HFEM(hidden field ergodic matrices)公鑰密碼方案的多項(xiàng)式時(shí)間算法。

本文多項(xiàng)式時(shí)間破解算法非常簡(jiǎn)單，即根據(jù)文獻(xiàn)[14]的方案公鑰中隱藏的遍歷矩陣性質(zhì)求出一個(gè)等價(jià)私鑰，然后利用這個(gè)私鑰對(duì)密文直接解密。具體說即通過分析發(fā)現(xiàn)文獻(xiàn)[14]的公鑰矩陣具有形式WB1, WB2，并且W可逆，矩陣 B1、 B2屬于同一個(gè)遍歷矩陣E的生成集，即，因而能夠計(jì)算出矩陣根據(jù)遍歷矩陣性質(zhì)，矩陣 B0屬于遍歷矩陣E的生成集。然后，本文利用 B0依次求出 HFEM公鑰密碼方案的一個(gè)等價(jià)私鑰。

2 趙永哲等人的HFEM公鑰密碼方案

為完整性，本節(jié)自適應(yīng)地引用文獻(xiàn)[14]中相關(guān)問題的定義和基于HFEM的公鑰密碼方案。

q遍歷矩陣生成元，記

定義 1 BMQ-問題：S為 Fq上有m個(gè)方程和2n個(gè)變量的方程組，其每個(gè)方程形式可表示為

為易于證明，筆者自適應(yīng)地引用文獻(xiàn)[14]中基于HFEM的公鑰密碼方案如下。

密鑰生成如下。

1) 隨機(jī)選擇矩陣集(A, B)。這里 A = { A1,… ,，要求滿足A線性無關(guān)，且B是遍歷矩陣E生成矩陣集 Fq[ E ]的基；

2) 隨機(jī)選擇變換矩陣 R ∈ GL2n( Fq)，并計(jì)算

3) 由RAB生成2n個(gè)BMQ多項(xiàng)式：[ρ1( x , y),…,

加密算法如下。

解密算法如下。

1) 給定私鑰sk和密文C，計(jì)算 T = ( R-1×C)

2) 給定私鑰sk和T，解出方程組 E ( A, B,T )的

3) 根據(jù)(x, y)與(α, β)等價(jià)，計(jì)算輸出明文P=x? y = α ? β 。

根據(jù)文獻(xiàn)[14]，方程組 E ( A, B ,T )定義為：這里定義，注意等式左邊符號(hào)系符號(hào)混用，僅表示矩陣符號(hào)，目的是與文獻(xiàn)[14]中原文一致，并不表示矩陣 A , B相乘后再將AB的元素按行排列后所對(duì)應(yīng)列向量。在已知(A, B)的情況下，方程組 E ( A, B ,T )易于求解。

3 破解HFEM公鑰密碼方案

盡管文獻(xiàn)[14]證明了BMQ問題是NP難的(定理1)，但文獻(xiàn)[14]并沒有歸約HFEM公鑰密碼方案的安全性到求解BMQ問題。通過分析上述HFEM公鑰密碼方案，筆者知道破解公鑰方案的關(guān)鍵是求出 VS(B)的一個(gè)基。為此，首先給出與遍歷矩陣相關(guān)的2個(gè)引理。

證明 因 f (λ)=|λ I-E|，故f(λ)為次數(shù)為n的多項(xiàng)式。用反證法，假定 f (λ)是可約的，則 f (λ)或者是不可約多項(xiàng)式的冪，或者可以表示成2個(gè)互素多項(xiàng)式的積。下面分別證明它們是矛盾的。

1) f(λ)可表示成2個(gè)互素多項(xiàng)式的乘積。

不失一般性，設(shè) f ( λ) = g1( λ)g2(λ)，deg(g1(λ))=k，1≤k＜n，deg(g2(λ))=n - k 和 g cd(g1(λ),g2(λ) ) = 1。

因E為遍歷矩陣，故 f(0)=|E |≠0，所以g1(0) ≠ 0,g2(0) ≠ 0。

由deg(g1(λ))=k和g1(0)≠0，可知剩余類環(huán)Fq[λ]/(g1)只包含qk-1個(gè)非零元素，所以剩余類集合{λi|i = 0,… ,qk-1}中存在2個(gè)非零元素λr, λs滿足 λr≡ λsm od g1(λ)，即存在正整數(shù) 0 ＜e1≤qk-1滿足 λe1≡1mod g1(λ)。

同理可證存在正整數(shù) 0 ＜e ≤qn-k-1，滿足2λe2≡1mod g2(λ)。

由gcd(g1( λ),g2(λ)) = 1，得并且 0 ＜ e e ＜ qn-1。12

因|Fq[ E ] |= qn-1和 f (λ)為遍歷矩陣E的特征多項(xiàng)式，故滿足 λe≡1modf(λ)的最小正整數(shù)是e = qn-1。

所以 ( qn- 1 )|(e1e2)，矛盾。

2)f(λ)是不可約多項(xiàng)式的冪，即f(λ)=g(λ)r,r≥ 2 。因 g (λ)為不可約多項(xiàng)式，且 g ( 0) ≠ 0 ，則e = qn/r-1是滿足 λe≡1modg(λ)的最小正整數(shù)。故f(λ) = g(λ)r|(λqn/r-1- 1 )r。

因 Fq為有限域，故 Fq中元素個(gè)數(shù)一定是某個(gè)素?cái)?shù)的冪。設(shè)素?cái)?shù)p是 Fq的特征，則 Fq有 pk個(gè)元素，這里k是 Fq在素域 Fp的擴(kuò)張次數(shù)。設(shè)v是滿足pv≥r的最小正整數(shù)。因?yàn)?，則

又因 e = qn-1是滿足 λe≡1modf(λ)的最小正整數(shù)，所以 ( qn-1)|( pv( qn/r- 1 ))。因λ≥2，矛盾。

根據(jù)遍歷矩陣特征多項(xiàng)式的不可約性可以得到有限域 Fq上模 f (λ)的多項(xiàng)式 Fq[λ]產(chǎn)生多項(xiàng)式的有限域，與遍歷矩陣同構(gòu)。

引理2 假定E為遍歷矩陣且|Fq[ E ] |= qn-1，f(λ)為E的特征多項(xiàng)式，則矩陣集 B ={E0,E1,… ,En-1}為遍歷矩陣集 Fq[E]的基。

證明 由引理1知， f(λ)為次數(shù)n的不可約多項(xiàng)式，因此，剩余類環(huán) Fq[λ]/(f)中任意元素對(duì)應(yīng)次數(shù)小于n的多項(xiàng)式 r(λ)，即又因Ek與有限域 F上次數(shù)小于n的 r (λ) = λkm od f(λ)

q一一對(duì)應(yīng)，即在有限域Fq上矩陣 Ek等于 r(E)。而r(E )中所有E的次數(shù)小于n，即 Fq[E]中任意元素可以用B表示。同理可以證明，由B生成的元素也屬于 Fq[E]∪ { 0}。

因 f (λ)為E的不可約特征多項(xiàng)式，故 f (E)為關(guān)于矩陣E滿足 g ( E ) =0的多項(xiàng)式中最小次數(shù)的多項(xiàng)式。故矩陣集B線性無關(guān)。因此，B是 Fq[E]的基。

q個(gè)基。

因?yàn)?R ∈ GL2n( Fq)，A線性無關(guān)，由文獻(xiàn)[15]可知：

rank(R) + r ank(A) - 2 n ≤ ra nk(R A) ≤ min(rank(R),rank(A) ) 。

因此，rank(RA)=n。不失一般性，設(shè)W1∈GLn( Fq)，即在有限域 Fq上 W1可逆。

又因?yàn)?B1∈GLn( Fq)，知W1B1可逆。故可以計(jì)算因此，可以計(jì)算得到和根據(jù)定理1可知 B '是 Fq[E]的基。

顯然，易于證明上述求解 B ', A'算法所需時(shí)間是多項(xiàng)式時(shí)間算法。因?yàn)槭褂酶咚瓜ㄓ?jì)算 B1的逆矩陣需要時(shí)間為 O ( n3)；計(jì)算 B '中矩陣乘積Bi，i=2,…, n 需要時(shí)間為(n-1)× O ( n3)= O ( n4)；計(jì)算 A '需要時(shí)間為2× O ( n3)= O ( n3)。這里假定 Fq上任意一次算術(shù)運(yùn)算需要時(shí)間為1個(gè)單位時(shí)間。

證明 根據(jù)定理 2，可以在多項(xiàng)式時(shí)間內(nèi)求解B', A'，且 B '也是 Fq[E]的基。

3)求解該方程組 E ( x, z)得一組非零解(x, z)

元法求逆得b。

6) 由(x, y)求出 E ( A', B ', C)的全部(q - 1 )個(gè)相互等價(jià)的解

7) 根據(jù) HFEM 公鑰密碼方案，計(jì)算輸出明文P = x ? y 。

4 破解HFEM公鑰密碼方案舉例(n=3，q=5)

本節(jié)通過實(shí)例演示破解HFEM公鑰算法。首先生成 HFEM公鑰；然后根據(jù)公鑰求解基 B '和A'；最后根據(jù) HFEM公鑰密碼方案對(duì)密文進(jìn)行解密。

4.1 生成HFEM公鑰

根據(jù)定理1可知，選擇B只要為 Fq[ E ]的基即可，易于驗(yàn)證上述選擇的B符合條件。計(jì)算輸出公鑰為

4.2 求解基 'B和 'A

現(xiàn)根據(jù)定理 2，使用公鑰RAB計(jì)算 Fq[ E]的基B'和 A '如下。

2)計(jì)算13W B逆

4.3 加密算法

給定公鑰RAB，設(shè)明文為 P =α?β=（4 2 3）?（2 3 1）。計(jì)算密文如下

4.4 解密算法

1) 根據(jù)文獻(xiàn)[14]和求解的基 B '和 A '可列方程組 E ( A', B',C)

3) 求解該方程組E( x, z)得一組非零解x=（3 4 1）,z= （ 1 0 2） 。

6) 輸出明文 P ' = x ? y 。易于驗(yàn)證明文 P = P '。

5 結(jié)束語

利用遍歷矩陣的性質(zhì)，本文給出從HFEM公鑰密碼方案的公鑰直接求解其等價(jià)私鑰的多項(xiàng)式時(shí)間算法，從而破解了文獻(xiàn)[14]設(shè)計(jì)的HFEM公鑰密碼方案。最后，通過計(jì)算示例演示HFEM公鑰密碼方案的破解過程。

[1] SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Journal on Computing, 1997, 26(5)：1484-1509.

[2] PROOS J, ZALKA C. Shor's discrete logarithm quantum algorithm for elliptic curves[J]. Quantum Information and Computation, 2003,3(4)：317-344.

[3] BUCHMANN J, DING J T. Post-quantum cryptography[A]. The Second International Workshop, PQCrypto 2008[C]. Cincinnati, USA, 17-19.

[4] 趙永哲, 黃聲烈, 姜占華. GF(2k)上的遍歷矩陣及其特性分析[J].小型微型計(jì)算機(jī)系統(tǒng), 2005, 26 (12)：2135-2139.ZHAO Y Z, HUANG S L, JIANG Z H. Ergodic matrix over GF (2k)and its properties[J]. Mini-micro Systems, 2005, 26 (12)：2135-2139.

[5] ZHAO Y Z, WANG L O, ZHANG W. Information-exchange using the ergodic matrices in GF(2)[A]. 2nd International Conference, ACNS 2004[C]. Amsterdam： Icisa Press, 2004. 388-397.

[6] 趙永哲, 裴士輝, 王洪軍等. 利用有限域上的遍歷矩陣構(gòu)造動(dòng)態(tài)加密器[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2007, 28 (11)： 2010-2014.ZHAO Y Z, PEI S H, WANG H J, et al. Using the ergodic matrices over finite field to construct the dynamic encryptor[J]. Mini-Micro Systems, 2007, 28 (11)：2010-2014.

[7] PEI S H, ZHAO H W, ZHAO Y Z. Public key cryptography based on ergodic matrices over finite field[J]. Wuhan University Journal of Natural Sciences, 2006, 11(6)：1525-1528.

[8] 趙永哲，姜占華，黃聲烈. 基于F2上遍歷矩陣的Shamir三次傳遞協(xié)議的實(shí)現(xiàn)[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2006, 27(6)：986-991.ZHAO Y Z, JIANG Z H, HUANG S L. Implementation of Shamir’s three pass protocol based on ergodic matrix over finite field[J]. Mini-Micro Systems, 2006, 27(6)：986-991.

[9] 孫永雄，趙永哲, 楊永健等. 基于遍歷矩陣的單向(陷門)函數(shù)的構(gòu)造方案[J]. 吉林大學(xué)學(xué)報(bào)： 信息科學(xué)版, 2006, 24(5)：555-560.SUN Y X, ZHAO Y Z, YANG Y J, et al. Scheme to construct one-way (trapdoor) functions based on ergodic matrices[J]. Journal of Jilin University： Information Science Edition, 2006, 24(5)：555-560.

[10] MONICO C. Semirings and Semigroup Actions in Public-Key Cryptography[D]. Notre Dame： University of Notre Dame, 2002.

[11] MAZE G. Algebraic Methods for Constructing One-Way Trapdoor Functions[D]. Notre Dame： University of Notre Dame, 2003.

[12] 黃華偉.半群作用問題在密碼學(xué)中的應(yīng)用[D]. 西安： 西安電子科技大學(xué), 2008.HUANG H W. Cryptographic Applications of Semigroup Action Problem[D]. Xi’an： Xidian University, 2008.

[13] 裴士輝,趙永哲,趙宏偉. 基于遍歷矩陣的公鑰加密方案[J]. 電子學(xué)報(bào), 2010, 38(8)：1908-1913.PEI S H, ZHAO Y Z, ZHAO H W. Public key encryption scheme based on the ergodic matrices[J]. Chinese Journal of Electronics, 2010,38(8)：1908-1913.

[14] 趙永哲,趙博,裴士輝等. HFEM 公鑰密碼方案的設(shè)計(jì)與實(shí)現(xiàn)[J]. 通信學(xué)報(bào),2011,32(6)：24-31.ZHAO Y Z, ZHAO B, PEI S H, et al. Design and implement on the HFEM public key scheme[J]. Journal on Communications, 2011,32(6)：24-31.

[15] HORN R A, JOHNSON C R. Matrix Analysis[M]. Cambridge University Press, 2005.