宋 嚴(yán)，趙永哲

(1.長春師范大學(xué)網(wǎng)絡(luò)中心，吉林 長春 130032；2.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長春 130012)

改進(jìn)的HFEM公鑰密碼方案在數(shù)字簽名上的應(yīng)用設(shè)計(jì)

宋 嚴(yán)1，趙永哲2

(1.長春師范大學(xué)網(wǎng)絡(luò)中心，吉林 長春 130032；2.吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長春 130012)

通過討論HFEM公鑰密碼方案中解密的效率問題，提出了改進(jìn)的HFEM公鑰密碼方案(I-HFEM).給出了I-HFEM方案的定義和算法，證明了I-HFEM方案的私鑰尺寸以及解密開銷都較原方案大為減少，并通過實(shí)例說明了I-HFEM方案在數(shù)字簽名領(lǐng)域上應(yīng)用的重要意義.

HFM公鑰密碼；HFEM；I-HFEM；簽名方案；有限域上的遍歷矩陣

HFEM公鑰密碼方案[1]在2009年申請了專利后，開始在數(shù)字簽名領(lǐng)域使用.所謂HFEM，即隱藏有限域上遍歷矩陣的公鑰密碼(Hidden Field Ergodic Matrices’ Public Key Cryptography)，它是基于有限域上BMQ問題的難解性以及遍歷矩陣的特性所實(shí)現(xiàn)的一種新的公鑰密碼方案.所謂BMQ問題，是指有限域上的二等分多變元二次方程組求解問題(Bisectional Multivariate Quadratic Equations Solving Problem).該問題已經(jīng)被證明是一個(gè)NP完全問題.但原始的HFEM方案存在私鑰尺寸較大以及解密效率較低的缺點(diǎn)，因此，本文對其進(jìn)行了改進(jìn)，改進(jìn)后的方案記為I-HFEM(Improved HFEM).與HFEM方案相比，I-HFEM不僅減小了私鑰尺寸，還大大提高了解密的效率.

1 背景理論

1.1 HFM-PKC方案設(shè)計(jì)

所謂HFM-PKC，即“隱藏域上矩陣的公鑰密碼[2](Hidden Field Matrices’ Public Key Cryptography)”是基于有限域上BMQ問題的困難性以及有限域上矩陣的性質(zhì)所實(shí)現(xiàn)的一種公鑰密碼.HFM-PKC的實(shí)現(xiàn)需要滿足如下條件的矩陣集合A和B：

(3) |VS(A)VS(B){0}|=(qn-1)2/(q-1)；

(4) Rank(AB)=2n.

1.2HFEM的實(shí)現(xiàn)

HFEM公鑰密碼方案主要由密鑰生成、加密、解密3個(gè)部分構(gòu)成.

HFEM公鑰密碼方案密鑰生成部分為其提供CA使用，為每個(gè)用戶產(chǎn)生一對私鑰和公鑰，其實(shí)現(xiàn)方法如下：

(5) 由RB生成2n個(gè)Fq上的BMQ多項(xiàng)式

(6) 公鑰為(Fq，ρ=[ρ1(x，y)，…，ρ2n(x，y)]，私鑰為(B1M，B2，λ).

(4) 利用高斯消元法求出w的逆矩陣w-1∈〈Q2〉；

(6) 則(x，y)必與(α，β)等價(jià)，由此可還原出P=x?y=α?β.

由有限域上遍歷矩陣的性質(zhì)[3]可知(A=B1M，B=B2)滿足條件(1)和(2).又由exp(Q1，M，Q2)=1和M∈R2(Q1，Q2)，可知(A，b)亦滿足條件(3)和(4).這樣的(A，B)數(shù)量眾多，所以HFEM方案是可行的.

1.3HFEM效率分析

2 I-HFEM的設(shè)計(jì)與實(shí)現(xiàn)

2.1 I-HFEM的設(shè)計(jì)思想

由前面對HFEM解密算法的效率分析，不難發(fā)現(xiàn)其開銷主要由解密算法第2步的開銷決定.所以應(yīng)將優(yōu)化的重點(diǎn)放在如何才能減少解密算法第2步的開銷.在原HFM-PKC方案的基礎(chǔ)上，對約束條件進(jìn)行了精煉，新的約束條件變?yōu)閇5]：

(3) |VS(A)VS(B){0}|=(qn-1)2/(q-1)；

(4) Rank(AB)=2n.

如果存在眾多滿足上述約束條件的(A，B)，則可實(shí)現(xiàn)改進(jìn)的HFM-PKC方案.

密鑰生成部分：

(3) 由RAB生成2n個(gè)Fq上的BMQ多項(xiàng)式ρk(x，y)=Rk[x?y](1≤k≤2n)；

(4) 公鑰為(Fq，ρ=[ρ1(x，y)，…，ρ2n(x，y)]，私鑰為(A，B，λ).

解密部分：

(4) 利用高斯消元法求出w的逆矩陣w-1∈VS(B){0}；

(6) 由(x，y)還原出明文P=x?y=α?β.

效率分析：

改進(jìn)的HFM-PKC方案的私鑰尺寸[6]為[(n3+6n2)log2q] B，比原來的(4n3log2q) B減少了將近3/4.更為重要的是，這使得解密算法的開銷大大降低.下面對其詳細(xì)分析：

2.2I-HFEM的實(shí)現(xiàn)

(ab)[r1，r2]=(a[r1，r2])b=(x1A1[r1，r2]+…+xnAn[r1，r2])(y1B1+…+ynBn)=T[r1，r2].

由此可得Fq上具有2n個(gè)變元和2n個(gè)方程的BMQ方程組E(A[r1，r2]，B，T[r1，r2])：

由E(A[r1，r2]，B，T[r1，r2])的構(gòu)造，可知其恰好對應(yīng)于E(A，B，T)中的第(r1-1)n+1至r1n以及第(r2-1)n+1至r2n這2n個(gè)方程，即E(A[r1，r2]，B，T[r1，r2])為E(A，B，T)的“子方程組”.又由Rank(AB)=2n和相關(guān)定理可知，必存在i，j∈{1，…，n}，且E(A[i，j]，B，T[i，j])中的2n個(gè)方程彼此線性無關(guān).所以E(A[i，j]，B，T[i，j]必與E(A，B，T)等價(jià)，即二者同解.

令(A′=A[i，j]={A1[i，j]，…，A[i，j]}，B′=B)，則(A′，B′)滿足所有的新約束條件.由此可實(shí)現(xiàn)I-HFEM.

密鑰生成部分：

(5) 如果Rank([AB])<2n，則轉(zhuǎn)(4)；

(7) 由RAB生成2n個(gè)Fq上的BMQ多項(xiàng)式ρk(x，y)=Rk[x?y](1≤k≤2n)；

(8) 公鑰為(Fq，ρ=[ρ1(x，y)，…，ρ2n(x，y)]，私鑰為(A，B，λ).

解密部分：

(3) 如果T[1]≠0，則令k=1，否則令k=2；

(6) 由(x，y)還原出明文P=x?y=α?β.

2.3I-HFEM與HFEM的主要區(qū)別

3 基于I-HFEM的數(shù)字簽名方案設(shè)計(jì)

設(shè)簽名者Peggy的公鑰和私鑰分別為(Fq，ρ=[ρ1(x，y)，…，ρ2n(x，y)]和(A，B，λ)，則Peggy和驗(yàn)證者Vic可按如下方式對消息進(jìn)行簽名和驗(yàn)證簽名.

簽名為：

(5) (H，sm)即為Peggy對消息m的簽名.

驗(yàn)證簽名為：

(2) Vic用Peggy的公鑰計(jì)算d″m=(ρ1(sm)，…，ρ2n-t(sm))；

表中無法被簽名的消息摘要數(shù)量及所占比例

注：100次實(shí)驗(yàn)結(jié)果.

由表1可以看出如下規(guī)律：

[1] 趙永哲，趙博，裴士輝，等.HFEM公鑰密碼方案的設(shè)計(jì)與實(shí)現(xiàn)[J].通信學(xué)報(bào)，2011，32(6)：24-31.

[2] 趙博，趙宏偉，蘇晉璇，等.MPKC的中心映射與公鑰形式[J].吉林大學(xué)學(xué)報(bào)：理學(xué)版，2012，50(4)：719-725.

[3] 裴士輝，趙永哲，趙宏偉.基于遍歷矩陣的公鑰加密方案[J].電子學(xué)報(bào)，2010，38(8)：1908-1913.

[4] 趙永哲，趙搏，裴士輝.有限域上遍歷矩陣的特性研究[J].數(shù)學(xué)學(xué)報(bào)，2012，55(3)：457-468.

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

[6] 趙永哲，黃聲烈，姜占華.GF(2k)上的遍歷矩陣及其特性分析[J].小型微型計(jì)算機(jī)系統(tǒng)，2005，26(12):2135-2139.

[7] 趙永哲，姜占華，黃聲烈.基于F2上遍歷矩陣的Sham ir三次傳遞協(xié)議的實(shí)現(xiàn)[J].小型微型計(jì)算機(jī)系統(tǒng)，2006，27(6):986-991.

[8] 孫永雄，趙永哲，楊永健，等.基于遍歷矩陣的單向(陷門)函數(shù)的構(gòu)造方案[J].吉林大學(xué)學(xué)報(bào):信息科學(xué)版，2006，24(5):555-560.

[9] 趙永哲，裴士輝，王洪軍，等.利用有限域上的遍歷矩陣構(gòu)造動(dòng)態(tài)加密器[J].小型微型計(jì)算機(jī)系統(tǒng)，2007，28(11):2010-2014.

Abstract:This paper explores the decipherment efficiency in the HFEM public key cryptography plan，puts forward the improved HFEM public key cryptography plan (I-HFEM)，gives the definition and algorithm，proves that the private key size of I-HFEM plan and the decipherment cost will have a great reduction than the original one，and illustrates that I-HFEM plan has very important applied significance in the field of digital signature.

Keywords:HFEM public key cryptography；HFEM；I-HFEM；signature plan；ergodic matrices over the finite field

(責(zé)任編輯：石紹慶)

The application design of improved HFEM public key cryptography plan on signature

SONG Yan1，ZHAO Yong-zhe2

(1.Center of Network，Changchun Normal University，Changchun 130032，China；2.School of Computer Science and Technology，Jilin University，Changchun 130012，China)

1000-1832(2014)03-0069-06

10.11672/dbsdzk2014-03-014

2013-07-11

“十一五”國家密碼發(fā)展基金資助項(xiàng)目(2006L014J00002)；吉林省教育廳科學(xué)技術(shù)研究項(xiàng)目(吉教科合字[2008]第346號).

宋嚴(yán)(1982—)，男，碩士，實(shí)驗(yàn)師；趙永哲(1961—)，男，碩士，教授，主要從事密碼學(xué)和信息安全研究.

TN 915.08 [學(xué)科代碼] 520·1060

A