改進的HFEM公鑰密碼方案在數字簽名上的應用設計

宋 嚴，趙永哲

(1.長春師范大學網絡中心，吉林 長春 130032；2.吉林大學計算機科學與技術學院，吉林 長春 130012)

改進的HFEM公鑰密碼方案在數字簽名上的應用設計

宋 嚴1，趙永哲2

(1.長春師范大學網絡中心，吉林 長春 130032；2.吉林大學計算機科學與技術學院，吉林 長春 130012)

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

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

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

1 背景理論

1.1 HFM-PKC方案設計

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

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

(4) Rank(AB)=2n.

1.2HFEM的實現

HFEM公鑰密碼方案主要由密鑰生成、加密、解密3個部分構成.

HFEM公鑰密碼方案密鑰生成部分為其提供CA使用，為每個用戶產生一對私鑰和公鑰，其實現方法如下：

(5) 由RB生成2n個Fq上的BMQ多項式

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

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

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

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

1.3HFEM效率分析

2 I-HFEM的設計與實現

2.1 I-HFEM的設計思想

由前面對HFEM解密算法的效率分析，不難發現其開銷主要由解密算法第2步的開銷決定.所以應將優化的重點放在如何才能減少解密算法第2步的開銷.在原HFM-PKC方案的基礎上，對約束條件進行了精煉，新的約束條件變為[5]：

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

(4) Rank(AB)=2n.

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

密鑰生成部分：

(3) 由RAB生成2n個Fq上的BMQ多項式ρ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=α?β.

效率分析：

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

2.2I-HFEM的實現

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

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

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

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

密鑰生成部分：

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

(7) 由RAB生成2n個Fq上的BMQ多項式ρ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的主要區別

3 基于I-HFEM的數字簽名方案設計

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

簽名為：

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

驗證簽名為：

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

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

注：100次實驗結果.

由表1可以看出如下規律：

[1] 趙永哲，趙博，裴士輝，等.HFEM公鑰密碼方案的設計與實現[J].通信學報，2011，32(6)：24-31.

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

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

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

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

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

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

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

[9] 趙永哲，裴士輝，王洪軍，等.利用有限域上的遍歷矩陣構造動態加密器[J].小型微型計算機系統，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

(責任編輯：石紹慶)

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

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

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

TN 915.08 [學科代碼] 520·1060

A