嚴(yán)深海

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

0 引 言

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

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

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

1 問題N 的解

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

由行列式計(jì)算得：

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

考慮到φ1，φ2，φ3的特殊結(jié)構(gòu)，可整理式（2）為：

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

式（3）是一個(gè)方程個(gè)數(shù)小于變量個(gè)數(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 當(dāng)λ≠μ，u1u3u5≠0，u2≠-（u3γ4+u1γ5）/[（λ3+μ3）u1u3]時(shí)，式（4）有解，且解的表達(dá)式為：

（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，故成立：

當(dāng)λ≠μ，整理上式有：

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

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

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

且解的表達(dá)式為：

（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 密碼體系的設(shè)計(jì)及算例

首先，新的HILL 密碼體系（簡記NEW-HILL）設(shè)計(jì)如下：

系統(tǒng)設(shè)置：選大素?cái)?shù)p（通常大于216），在GF（p）中運(yùn)算：

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：計(jì)算出γi（i=1，2，3，4，5，6，7，8），求解問題N 得u4，

構(gòu)造出密鑰矩陣：A=γ2U+γV+W.

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

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

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

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

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

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

Bob：計(jì)算

Alice和Bob：分別計(jì)算出

且求解問題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 密碼體系增強(qiáng)以下功能：NEW-HILL 密碼體系的密鑰保存管理更加方便，這是因?yàn)榧用芫仃囀莿討B(tài)產(chǎn)生的,不是由通信雙方事先選定后直接保存待用的，從而減少了密鑰存儲管理的困難；通信雙方參與構(gòu)造密鑰矩陣，增強(qiáng)了不可抵賴性；組織者參與且見證構(gòu)造密鑰矩陣， 增強(qiáng)了不可偽造性；密鑰矩陣的使用更安全，每次通信時(shí)隨機(jī)求出加密矩陣，完成一次通信即可廢棄這個(gè)密鑰矩陣，能夠?qū)崿F(xiàn)一次一密，增強(qiáng)了抗攻擊性；NEW-HILL 密碼體系算法簡練，便于固化為硬件，重復(fù)使用. 總之，文中對Hill 密碼體制進(jìn)行改進(jìn)后得到的NEW-HILL密碼體系能適應(yīng)現(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)典密碼學(xué)與現(xiàn)代密碼學(xué)[M]. 葉阮鍵，曹 英，張長富，譯. 北京:清華大學(xué)出版社，2005.

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

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

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

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

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

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

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

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

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

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