基于HFE公鑰密碼的單向殼核函數(shù)構(gòu)造方案

王 芳, 袁 哲

(白城師范學(xué)院 傳媒學(xué)院, 吉林 白城 137000； 吉林大學(xué) 機械科學(xué)與工程學(xué)院, 長春 130022)

0 引 言

公鑰密碼是信息安全和可信計算的精髓和核心。到目前為止, 已經(jīng)提出了很多種不同的公鑰密碼體制, 其可分成兩大類： 1) 基于大整數(shù)因子分解的公鑰密碼, 如RSA公鑰密碼體制； 2) 基于離散對數(shù)問題的公鑰密碼, 如ECC(Error Correcting Code)公鑰密碼體制。隨著科技的進步, 量子計算機的出現(xiàn)對RSA和ECC公鑰密碼構(gòu)成了巨大威脅。因此, 急需尋找一種新的公鑰密碼替代這些安全性受到威脅的公鑰密碼[1-4]。

隨著密碼技術(shù)的快速發(fā)展, 20世紀數(shù)學(xué)將成為下一代公鑰密碼的堅實基礎(chǔ)。有限域中的多變元二次方程組問題(MQ: Multivariate Quadratic)是被廣泛認可的一種替代方案。目前人們已經(jīng)研究出了一些基于MQ問題比較成型的方案, 其中主要方案有隱藏域方程(HFE: Hidden Field Equations)、 UOV(Unbalanced Oil and Vinegar Scheme)、 STS (Stepwise Triangular Systems)、 MIC*(Matsumoto-Imai Scheme)、 ιIC(ι-Invertible Cycles)。雖然有人經(jīng)過深入研究, 提出了一些對MQ問題的攻擊方案[1], 但人們針對這些攻擊方案, 已將這些基本方案進行了變形, 如(HFEv-)、 STS(UOV)、 (ιICi+)等[5,6]。

基于MQ問題的公鑰密碼具有較好的發(fā)展前景, 具有加密速度和驗證簽名速度快, 抵御量子攻擊潛力大等優(yōu)點。筆者借鑒了HFE公鑰密碼的設(shè)計思想[7-13], 構(gòu)造出一種應(yīng)用靈活, 安全性更高的函數(shù), 即單向殼核函數(shù)。

1 HFE公鑰密碼原理

此求解問題是基于解有限域上的MQ問題, 是NP困難問題[5-13]。HFE公鑰密碼體制正屬于這樣的MQ問題, 其加密/解密過程如圖1所示。

圖1 HFE公鑰密碼加密/解密過程

1) 確定參數(shù)。① 確定基本有限域Fq和元組n； ② 構(gòu)造的可逆線性變換S, 可逆非線性變換P以及可逆線性變換T； ③ 根據(jù)第②步所得, 計算公鑰Kθ=T°P°S, 用于加密； ④ 把S、P、T的逆函數(shù)(S-1,P-1,T-1)作為私鑰Kd, 用于解密。

2) 加密過程。利用公鑰Kθ, 加密明文x, 得到密文y=EKθ(x)=T(P(S(x)))。

3) 解密過程。利用私鑰Kd, 解密所得的密文y, 對密文先做T-1(y)運算, 然后做P-1(T-1(y))運算, 最后做S-1(P-1(T-1(y)))得到明文x。

2 單向殼核函數(shù)的構(gòu)造

2.1 單向殼核函數(shù)的引入

圖2 單向函數(shù)結(jié)構(gòu) 圖3 單向陷門函數(shù)結(jié)構(gòu)

由單向函數(shù)的定義可知, 當x已知時, 計算y=f(x)非常容易, 而當y已知, 求解x滿足y=f(x), 則非常困難。所以, 單向函數(shù)類似于將已知的x放入封閉的盒子里(見圖2)。

已知陷門k的條件下, 求解x, 使y=f(x)是非常容易的。由此可見, 單向陷門函數(shù)類似于將已知的x放入到帶有暗門的盒子里(見圖3)。

結(jié)合單向函數(shù)及單向陷門函數(shù)各自的結(jié)構(gòu)特點, 筆者提出了一種特點更鮮明的單向殼核函數(shù), 這種函數(shù)的兩種結(jié)構(gòu)如圖4所示。

a 第1種結(jié)構(gòu) b 第2種結(jié)構(gòu)

圖4引入了殼函數(shù)S、 核函數(shù)C、 剝殼函數(shù)S-1與剝核函數(shù)C-1。其中, 單向殼核函數(shù)SC(x)=S°C(x)=S(C(x)), 即殼函數(shù)S及核函數(shù)C二者的復(fù)合計算。

2.2 基于HFE公鑰密碼體制的構(gòu)造方案

圖5 基于HFE思想所構(gòu)造的單向殼核函數(shù)的原理圖

單向殼核函數(shù)的概念以及兩種結(jié)構(gòu)已經(jīng)被引入, 下面將利用HFE公鑰密碼的設(shè)計思想構(gòu)造單向殼核函數(shù)的第1種結(jié)構(gòu), 即殼函數(shù)S與核函數(shù)C同為單向函數(shù)?；贖FE公鑰密碼所構(gòu)造的單向殼核函數(shù)的原理如圖5所示。

殼函數(shù)S和核函數(shù)C具有相同的構(gòu)造形式, 類似于HFE公鑰密碼變換過程中的函數(shù)P(x)。它們的相同點是： 具有相似的結(jié)構(gòu), 又都是在F的擴展域E上進行運算。不同點是： HFE中的P(x)是可逆變換, 為了確保P(x)可逆, 其中常數(shù)r不能太大； 而單向殼核函數(shù)中的殼函數(shù)S與核函數(shù)C都是單向函數(shù), 無需滿足可逆性, 其中常數(shù)r可以很大。

2.3 安全分析

1) GB方法與XL方法。由于XL方法可以看成是GB方法的一個特例, 只需說明單向殼核函數(shù)可以抵抗GB攻擊即可。對于隨機選取的MQ方程組, 當m≤n時, 計算GB時所產(chǎn)生的中間多項式的次數(shù)往往增長快速, 為O(2n)。所以, 當n取值較大時, 此類算法在空間和時間上不可行。當選取的單向殼核函數(shù)的MQ方程組具有真隨機性, 在m≤n時, 計算GB時所產(chǎn)生的中間多項式的次數(shù)增長快速, 當n取值很大時, 此類算法在空間和時間上不可行。單向殼核函數(shù)的殼函數(shù)S(x)和核函數(shù)C(x)是單向不可逆的, 導(dǎo)致多項式的次數(shù)會很大。因此, GB方法與XL方法對單向殼核函數(shù)無法進行有效的攻擊。

2) 重線性化方法。重線性化次數(shù)的增大, 導(dǎo)致線性相關(guān)方程數(shù)量也在迅速增加, 且這種方法僅適用于超定義的MQ方程組。對于HFE公鑰密碼的攻擊, 重線性化方法主要利用P(x)變換的可逆性(常數(shù)r不能太大)這個弱點進行攻擊的。這種攻擊方法對HFE的攻擊有效, 但對單向殼核函數(shù)卻毫無作用。因為單向殼核函數(shù)的殼函數(shù)S(x)與核函數(shù)C(x)都為單向函數(shù), 不可逆, 要求r很大。但r的不斷增大, 導(dǎo)致線性相關(guān)的方程數(shù)量迅速增長, 次數(shù)也隨之變大。因此, 重線性化方法對單向殼核函數(shù)無法進行有效的攻擊。

3) DR方法。DR方法只是對E(x1,…,xn)稀疏時有效, 否則Dixon矩陣的尺寸至少為O(2n), 易知DR方法對于求解一般MQ方程組的實際意義不大。在選取單向殼核函數(shù)的MQ方程組時, 可以選擇具有真隨機性的MQ方程組。因此, DR方法對單向殼核函數(shù)無法進行有效攻擊。

4) 指定變元法。假如q較小, 則可任意給定r個變元, 使m>(n-r), 倘若m個方程和n-r個變元的MQ問題可解, 可以用GB、 XL等方法求解。但由于可選具有真隨機性的單向殼核函數(shù)MQ方程組, 函數(shù)具有單向性的特征, 指定變元法對單向殼核函數(shù)的攻擊仍然無用。

3 結(jié) 語

筆者引入了單向殼核函數(shù)公鑰密碼體制, 根據(jù)HFE公鑰密碼的設(shè)計思想, 構(gòu)造了單向殼核函數(shù), 并給予了安全性分析, 證明了該新型的公鑰密碼具有很強的安全性。單向殼核函數(shù)的提出, 給出了一種新型的公鑰密碼體制, 經(jīng)過深入研究, 將會具有更廣闊的應(yīng)用前景。

參考文獻：

[1]WILLIAM STALLINGS. 密碼編碼學(xué)與網(wǎng)絡(luò)安全原理與實踐 [M]. 北京: 電子工業(yè)出版社, 2001.

WILLIAM STALLINGS. Cryptography and Network Security Principles and Practice [M]. Beijing: Publishing House of Electronic Industry, 2001.

[2]曹珍富. 公鑰密碼學(xué) [M]. 哈爾濱: 黑龍江教育出版社, 1993.

CAO Zhen-fu. Public Key Cryptography [M]. Harbin: Heilongjiang Education Press, 1993.

[3]袁哲, 趙永哲, 張文睿, 等. 敏感數(shù)據(jù)安全傳輸方法 [J]. 吉林工程技術(shù)師范學(xué)院學(xué)報, 2008, 24(1): 73-77.

YUAN Zhe, ZHAO Yong-zhe, ZHANG Wen-rui, et al. Sensitive Data Secure Transmission Methods [J]. Jilin Engineering and Technical Teachers College, 2008, 24(1): 73-77.

[4]袁哲, 趙永哲, 李光偉, 等. 利用有限域上遍歷矩陣實現(xiàn)基于隱藏基的密鑰交換 [J]. 吉林大學(xué)學(xué)報: 理學(xué)版, 2009, 47(4): 783-789.

YUAN Zhe, ZHAO Yong-zhe, LI Guang-wei, et al. Finite Fields Hidden Base Ergodic Matrix-Based Key Exchange [J]. Journal of Jilin University: Science Edition, 2009, 47 (4): 783-789.

[5]CHRISTOPHER WOLF. Hidden Field Equations (HFE)-Variations and Attacks [EB/OL]. [2013-04-15]. http://www.christopher-wolf.de/dpl, 2003.

[6]NICOLAS COURTOIS. The HFE Public Key Encryption and Signature [EB/OL]. [2013-04-15]. http://www.minran K.org/hfe/, 2005.

[7]NICOLAS COURTOIS. The Security of Hidden Field Equations (HFE) [C]∥Cryptographers’ Track RSA Conf, LNCS 2020. Berlin: Spring Verlag, 2001: 266-281.

[8]FELL H, DIFFIE W. Analysis of a Public Key Approach Based on Polynomial Substitution [C]∥Crypto’85, LNCS 218. Berlin: Spring Verlag, 1985: 340-349.

[9]LOUIS GOUBIN, JACQUES PARTARIN. Trapdoor One-Way Permutations and Multivariate Polynomials [C]∥ISICS’97, LNCS 1334. Berlin: Spring Verlag, 1997: 356-368.

[10]JACQUES PARTARIN. Hidden Field Equations (HFE) and Isomorphism of Polynomial (IP): Two New Families of Asymmetric Algorithms [C]∥EuropCrypt’96, LNCS1070. Berlin: Spring Verlag, 1996: 33-48.

[11]AVIAD KIPNIS, ADI SHAMIR. Cryptanalysis of the HFE Public Key Cryptosystem [C]∥Crypto’99, LNCS 1666. Berlin: Spring Verlag, 1999: 19-30.

[12]陳輝焱, 王連強, 呂述望. 關(guān)于HFE密碼系統(tǒng)的密鑰問題研究 [J]. 計算機研究與發(fā)展, 2007, 44(7): 1205-1210.

CHEN Hui-yan, WANG Lian-qiang, Lü Shu-wang. About HFE Key Cryptography Research [J]. Computer Research and Development, 2007, 44(7): 1205-1210.

[13]楊敏, 孟慶樹, 張煥國. 基于ECC和HFE的糾錯密碼構(gòu)造 [J]. 計算機工程與應(yīng)用, 2008, 44(27): 31-32.

YANG Min, MENG Qing-shu, ZHANG Huan-guo. HFE-Based Error Correction Code ECC and Construction [J]. Computer Engineering and Applications, 2008, 44(27): 31-32.