基于有限域中的一類逆二次特征問題設計的新HILL密碼體系

嚴深海

（贛南師范學院數(shù)學與計算機科學學院，江西贛州341000）

0 引 言

文中研究下述有限域中的一類逆二次特征問題[1-2]及其在設計一類新HILL 密碼體系方面中的應用.

問題N 對于預先給定的素數(shù)ρ 和λ，μ∈GF（p），V、W∈GF（p5×5），尋找U∈GF（p5×5），滿足：

Hill 密碼體系[3-4]是Lester S.Hill 1929 年提出的， 該加密算法將含有m 個字母的明文塊加密成含有同等多個字母的密文塊. 通過求單模數(shù)矩陣的逆A-1mod p 或求單模數(shù)線性同余方程組， 將密文解密成明文，它的提出標志著矩陣理論在密碼體系設計中的應用. 游林等[5]則研究了有限域上n 元一次同余方程組的編碼解法. 但HILL 密碼體系也存在弱點，例如加密矩陣的存儲管理問題，它不具有簽名功能， 難敵通訊雙方的信息偽造和抵賴，HILL 密碼體系在很長時間內不被人們使用. 近年文獻[6-8]研究了加密矩陣的動態(tài)構造和結合其他信息安全技術實現(xiàn)HILL 密碼體系的簽字功能. 文獻[9]研究了基于多模數(shù)矩陣方程設計的密鑰交換方案，文獻[10]研究了基于求解多模數(shù)線性同余方程組來設計新的HILL 密碼體系，文獻[11]研究了基于單模數(shù)多變量二次同余方程組設計的密碼體系. 文中則將逆二次特征問題[12-13]用于新HILL 密碼體系的設計.

1 問題N 的解

根據(jù)U,V,W 的特殊結構，可整理得：

由行列式計算得：

由引理1 知問題N 中式（1）等價于φ（λ）=0，φ（μ）=0，即：

考慮到φ1，φ2，φ3的特殊結構，可整理式（2）為：

這里，γ1=v2v4w2w4，γ2=v1v4w1w4，γ3=v1v3w1w3，γ4=-v1w1，γ5=-v2w2，γ6=-v3w3，γ7=-v4w4，γ8=1.

式（3）是一個方程個數(shù)小于變量個數(shù)的非線性方程組，觀察后知，該方程組可線性化為：

其中：η11=λ3u1（u5γ6+u3γ7），η12=λ3u5（u3γ4+u1γ5），η13=λ6u1u3u5，η21＝μ3u1（u5γ6+u3γ7），η22=μ3u5（u3γ4+u1γ5），η23=μ6u1u3u5，η20＝η10＝-（u1γ1+u3γ2+u5γ5）.

考慮到式（4）中兩方程的右端相等，容易求解：

引理2 當λ≠μ，u1u3u5≠0，u2≠-（u3γ4+u1γ5）/[（λ3+μ3）u1u3]時，式（4）有解，且解的表達式為：

（1）u1，u3，u5為任意非零數(shù).

（2）u2≠-（u3γ4+u1γ5）/（u1u3），可以任取.

（3）u4＝-u1u2（u5γ6+u3γ7）/{u5[u3γ4+u1γ5+（λ3+μ3）·u1u2u3]}

證 明：由式（4）知η20＝η10，故成立：

當λ≠μ，整理上式有：

當u1u3u5≠0，u2≠-（u3γ4+u1γ5）]/（u1u3）可保證u4的表達式如下，且分母不為零：

考慮到問題N 中有限域GF（p）的要求，容易得到：

定 理 問題N 有解的條件是：

且解的表達式為：

（2）可以任取u2∈GF（p）-{ξ}，ξ＝-（u3γ4+u1γ5）·[（λ3+μ3）u1u3]-1mod p.

（3）u4≡-u1u2（u5γ6+u3γ7）{u5[u3γ4+u1γ5+（λ3+μ3）·u1u2u3]}-1mod p.

2 新HILL 密碼體系的設計及算例

首先，新的HILL 密碼體系（簡記NEW-HILL）設計如下：

系統(tǒng)設置：選大素數(shù)p（通常大于216），在GF（p）中運算：

Alice：任選私鑰（λ，v*）∈GF（pn），v*=（v1，v2，v3，v4），且傳送給Bob.

通常n 大于100， 文中為說明算法的可行性，只取n=5，以下同理.

Bob： 任選私鑰（μ，w*）∈GF（p5），w*=（w1，w2，w3，w4），且傳送給Alice.

Alice和Bob：計算出γi（i=1，2，3，4，5，6，7，8），求解問題N 得u4，

構造出密鑰矩陣：A=γ2U+γV+W.

Alice： 按長度為5 將明文的分組為計算出明文段mi的密文ci≡Amimod p 且傳給Bob.

Bob：在GF（p）的中求密鑰矩陣A 的逆矩陣A-1mod p，計算出密文段ci的明文，mi≡A-1cimod p匯總得明文m=m1，m2，…，m5.

下面，通過算例說明NEW-Hill 密碼體系的可行性.

系統(tǒng)設置：選p=137，在GF（137）中運算

Alice：選私鑰（λ，v*）∈GF（1375），且傳送給Bob，其中：λ=19，v*=（v1，v2，v3，v4）＝（60，46，34，28）.

Bob：選私鑰（μ，w*）∈GF（1375），且傳送給Alice，其中： ,且傳給組織者（見證人）.

Bob：計算

Alice和Bob：分別計算出

且求解問題N 得u4=8. 得到密鑰矩陣：

Alice： 利用密鑰矩陣A 加密明文m=（81，36，94，19，37）為密文:

將密文c 傳給Bob.

Bob：在GF（137）中求密鑰矩陣A 的逆矩陣A-1mod p，且將收到的密文c 解密為明文：

綜上可知，NEW-HILL 密碼體系比傳統(tǒng)的HILL 密碼體系增強以下功能：NEW-HILL 密碼體系的密鑰保存管理更加方便，這是因為加密矩陣是動態(tài)產(chǎn)生的,不是由通信雙方事先選定后直接保存待用的，從而減少了密鑰存儲管理的困難；通信雙方參與構造密鑰矩陣，增強了不可抵賴性；組織者參與且見證構造密鑰矩陣， 增強了不可偽造性；密鑰矩陣的使用更安全，每次通信時隨機求出加密矩陣，完成一次通信即可廢棄這個密鑰矩陣，能夠實現(xiàn)一次一密，增強了抗攻擊性；NEW-HILL 密碼體系算法簡練，便于固化為硬件，重復使用. 總之，文中對Hill 密碼體制進行改進后得到的NEW-HILL密碼體系能適應現(xiàn)代密碼體制的需求.

[1] Lancaster P, Prells U. Inverse problems for damped vibrating systems[J].Journal of Sound and Vibration,2005，283（3）):891-914.

[2] Dong B, Matthew M Lin, Moody T Chu. Parameter reconstruction of vibration systems from partial eigeninformation [J]. Journal of Sound and Vibration, 2009，327(3): 391-401.

[3] Richard Spillman. 經(jīng)典密碼學與現(xiàn)代密碼學[M]. 葉阮鍵，曹 英，張長富，譯. 北京:清華大學出版社，2005.

[4] 楊曉元，魏立線. 計算機密碼學[M]. 西安：西安交通大學出版社，2007.

[5] 游 林，王升國. 有限域上一次同余方程組的編碼解法[J]. 大學數(shù)學，2008，24(4):59-63.

[6] 黃賢通，李文鋒，任金威. 基于矩陣廣義特征逆問題實現(xiàn)的具有數(shù)字簽名功能的Hill 密碼體制[J] . 航空計算技術，2007，37( 2) :9- 12.

[7] 任金威， 李文鋒. 由RSA 實現(xiàn)的具有數(shù)字簽名功能的Hill 密碼體制[J]. 計算機安全，2007(1):38-40.

[8] 宋明明， 涂登平. 基于矩陣問題實現(xiàn)的具有數(shù)字簽名功能的Hill 密碼體制[J]. 廣西民族大學學報： 自然科學版，2010，16(3):56-59.

[9] 黃賢通， 湯紹春. 基于多模數(shù)矩陣方程設計的密鑰交換方案[J].贛南師范學院學報，2011(3):15-18.

[10] 林殊芳，湯紹春. 一類帶有冗余信息的Hill 密碼體系[J]. 江西理工大學學報，2010，31 (3):60-63.

[11] 嚴深海. 基于單模數(shù)多變量二次同余方程組設計的密碼體系[J].江西理工大學學報，2012，33 (3):76-80.

[12] 王正盛. 阻尼彈簧一質點系統(tǒng)中的逆二次特征值問題[J]. 高等學校計算數(shù)學學報，2005，3(27):217-224.

[13] 吳春紅. 幾類矩陣的逆特征值問題[D]. 廈門：廈門大學，2009.