楊 宏 宇， 寧 宇 光， 王 玥

( 中國民航大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 天津 300300 )

0 引 言

為解決對稱密碼密鑰配送難和公鑰密碼加密速度慢的問題，混合密碼系統(tǒng)被提出并且廣泛使用．混合密碼系統(tǒng)組成機制包含如下4個過程：用對稱密碼加密明文、通過偽隨機數(shù)生成器生成對稱密碼加密中使用的會話密鑰、用公鑰密碼加密會話密鑰、從外部賦予公鑰密碼加密時使用的密鑰[1]．

Shoup[2]通過提出KEM-DEM結(jié)構(gòu)形式化定義了混合加密模型．但是一些密碼體制由于密鑰形式或安全性無法依據(jù)KEM-DEM結(jié)構(gòu)與其他密碼構(gòu)成混合密碼，所以符合該結(jié)構(gòu)的密碼體制較少．

基于RSA和Hill的混合密碼構(gòu)建仍處于探索階段，不少研究已經(jīng)開始將RSA與Hill兩種密碼體制配合使用．Rahman等[3]提出的Hill++算法通過引入隨機矩陣作為密鑰增強了Hill密碼對已知明文攻擊的抵抗性．但是該算法僅對加密矩陣進行了改進，需要復(fù)雜的代數(shù)運算．Goel等[4]通過在RSA密碼加密前對明文進行Hill加密，增強了RSA密碼對暴力攻擊的抵抗性．但該方法沒有構(gòu)造混合密碼，仍存在對稱密碼密鑰配送難和公鑰密碼加密速度慢的問題．李文鋒[5]提出了基于有限域矩陣構(gòu)造技術(shù)的RSA-Sign-Hill算法，該算法用生成Hill密碼加密矩陣時產(chǎn)生的關(guān)鍵數(shù)字l作為會話密鑰，導(dǎo)致其會話密鑰過于單一，生成加密矩陣算法的代價較高，無法抵抗已知明文攻擊等密碼分析手段．

國內(nèi)外對Hill密碼的研究重點是對其加密矩陣的改進，但Hill密碼屬于古典密碼，存在定長分割明文產(chǎn)生啞元、生成加密矩陣時間復(fù)雜度高兩個固有問題．目前，針對這兩個固有問題的研究已經(jīng)取得了一定的成果．劉海峰等[6-7]通過設(shè)定加密矩陣滿足行和相等性質(zhì)解決了啞元問題．但加密矩陣的約束增加，導(dǎo)致Hill密碼密鑰空間減小，其抗攻擊性減弱．Putera等[8]利用遺傳算法改進Hill密碼的密鑰生成，提高密鑰生成速度．但該方法仍然局限于改進Hill密碼的加密矩陣．

上述研究并未從本質(zhì)上提高Hill密碼的安全性．針對上述問題，本文的研究思路是從Hill密碼加密流程分析入手，將其規(guī)律分割明文轉(zhuǎn)換為隨機分割明文，不再針對Hill密碼加密矩陣進行改進，而將其密鑰從加密矩陣轉(zhuǎn)換為對明文的隨機分割數(shù)，通過加密隨機分割數(shù)增強Hill密碼的安全性．為此，本文提出明文隨機分割的方法，將RSA密碼與Hill密碼融合，設(shè)計RSA-Hill混合加密算法．與以往的混合加密構(gòu)造方式不同，本文將會話密鑰轉(zhuǎn)換為明文的隨機分割數(shù)，用Pascal 矩陣代替Hill密碼的密鑰隱藏明文信息，并采用RSA密碼加密明文隨機分割數(shù)以保證算法的安全性．

1 多密碼體制分析

1.1 問題分析

多密碼體制是將兩種或兩種以上的密碼相結(jié)合，并使各密碼相互兼容的一種方案．現(xiàn)已有較為成熟的多密碼混合加密方案，如DES-RSA[9]、AES-ECC[10]等．但對于RSA和Hill密碼，由于Hill密碼的密鑰為隨機矩陣，二者結(jié)合難度較大，根據(jù)KEM-DEM結(jié)構(gòu)模型，構(gòu)建基于RSA和Hill混合密碼存在以下兩個難點：

(1)若基于RSA和Hill混合加密算法中會話密鑰是行列式為±1的隨機矩陣且每一次需要的隨機矩陣階數(shù)不固定，則采用偽隨機數(shù)生成器無法高效生成會話密鑰．

(2)混合密碼體制使用公鑰密碼加密會話密鑰．若會話密鑰是矩陣，則RSA等公鑰密碼無法加密數(shù)據(jù)量大且具有結(jié)構(gòu)的會話密鑰．

針對上述兩個難點，本文利用明文隨機分割方法將RSA和Hill相結(jié)合．若分割明文的隨機數(shù)作為會話密鑰，則偽隨機數(shù)生成器快速、高質(zhì)量生成會話密鑰的同時，也可使用RSA密碼對該密鑰加密．該混合加密算法中密鑰空間的改變，實現(xiàn)了一次一密混合密碼系統(tǒng)．

1.2 密鑰空間分析

Hill加密算法的密鑰空間

KH={Hm×m|m∈Z+，|Hm×m|=±1}

(1)

設(shè)n為明文長度，基于RSA和Hill混合加密算法的密鑰空間

(2)

Hill加密算法中密鑰是隨機選取的，但為保證加密矩陣是可逆的且逆矩陣中的元素全部為整數(shù)，使得解密后可以得到正確的明文，密鑰的選取要滿足加密矩陣是非退化的且行列式為±1[11]．對于密鑰空間K，每一次加密過程中偽隨機數(shù)生成器可以有效生成隨機密鑰，并且可用RSA密碼對其加密．

由于密鑰空間K的存在，可以避免對Hill密碼中加密矩陣進行改進．本文選用Pascal矩陣代替Hill密碼的密鑰，Pascal矩陣的取值空間

KP={Pm×m|m∈Z+}

(3)

根據(jù)式(1)、(3)可知，KP是KH的子集．若密鑰空間減小，Pascal矩陣則無法作為Hill密碼的密鑰．但在基于RSA和Hill混合加密算法中會話密鑰不再是Pascal矩陣，而是明文的隨機分割數(shù)．使用Pascal矩陣代替Hill密碼的密鑰，其優(yōu)點是避免了生成加密矩陣時大量復(fù)雜的運算[11]，解決了密鑰傳輸困難等問題．通過對Pascal矩陣生成算法的改進，可以提高混合密碼加解密的速度．

2 Pascal公式的推廣

從實現(xiàn)方法上看，Pascal公式是依據(jù)相鄰兩行間的關(guān)系生成Pascal矩陣，且不局限于逐行生成[12]．但Pascal公式還可以推廣，得到更一般的形式．

2.1 假 設(shè)

Pascal公式的組合意義證明以及由組合意義推導(dǎo)出的一般性公式第1步都是在集合S中任取i(1≤i≤k)個元素，所以不妨以S中選取的元素個數(shù)劃分Pascal公式的階數(shù)．

……

2.2 i階Pascal公式證明

i階Pascal公式為

(4)

證明在S中選取i(1≤i≤k)個元素(x1，x2，…，xi)，S的k-組合的集合劃分成2i種集合．用1表示xi在集合中，用0表示xi不在集合中．所以集合的劃分情況如下：

綜上所述，根據(jù)雙計數(shù)原理可得

2.3 分 析

(1)從1階Pascal公式到2階Pascal公式、3階Pascal公式、…、i階Pascal公式中n的規(guī)模依次減小，當需要生成階數(shù)較大的Pascal矩陣時，可以利用相對高階的Pascal公式，以減小運算復(fù)雜度．

(2)在生成Pascal矩陣時運用i階Pascal公式，可以消除行數(shù)的限制．即在生成Pascal矩陣第i行的數(shù)據(jù)時可以依賴j(1≤j

(3)在使用i階Pascal公式時，由于公式本身取值范圍的限制，必須先給出前i行數(shù)據(jù)作為生成所需階數(shù)Pascal矩陣的基礎(chǔ)．

3 基于RSA和Hill的混合加密算法

3.1 RSA-Hill混合加密算法

RSA-Hill混合加密流程設(shè)計如下：

(1)已知明文M，對照字符表(如表1所示)得到將要加密的數(shù)字明文，計算明文長度n；

(2)生成一系列隨機數(shù)n1，n2，…，nk，且n=n1+n2+…+nk；

(3)按生成的隨機數(shù)將明文M劃分為M1，M2，…，Mk，生成對應(yīng)的Pascal矩陣P1，P2，…，Pk；

(4)明文加密計算C1=M1P1，C2=M2P2，…，Ck=MkPk，得到加密后的密文矩陣，將密文矩陣轉(zhuǎn)化為行向量并組合在一起成為最終密文發(fā)送到接收方；

(5)用RSA加密算法對隨機數(shù)加密和傳送；

(6)解密時先用RSA算法解密隨機數(shù)，再依據(jù)隨機數(shù)按Hill算法解密．

表1 字符表

3.2 算法分析

根據(jù)圖1可知，計算機在運行RSA-Hill混合加密算法時，不再需要生成行列式為±1的隨機矩陣A，即detA=±1，僅需要生成一系列隨機數(shù)．通過這種方式能提高算法的執(zhí)行效率和性能，減少計算機系統(tǒng)資源的消耗．

在RSA-Hill混合加密算法中，通過滿足n=n1+n2+…+nk條件的一系列隨機數(shù)分割明文，可以避免Hill密碼中因定長分割明文所產(chǎn)生的啞元問題．同時，由于隨機數(shù)的個數(shù)要少于明文數(shù)，并且每一次對明文加密生成的隨機數(shù)都不一樣．從這個角度上講，該算法實現(xiàn)了一次一密．

3.3 應(yīng)用實例

(1)對給定明文M：Attack time at 5 PM，按照表1得到數(shù)字明文如下：

36 29 29 10 12 20 29 18 22 14 10 29 5 51 48

通過計算可得明文長度n=15；

(2)生成隨機數(shù)：4 3 7 1；

(3)用隨機數(shù)對明文進行劃分：

M1=(36 29 29 10)T

M2=(12 20 29)T

M3=(18 22 14 10 29 5 51)T

M4=(48)T

圖1 算法框架圖

對應(yīng)生成的Pascal矩陣為P4、P3、P7、P1；

(4)對明文進行加密計算：

C1=P4M1=(36 1 59 28)T

C2=P3M2=(12 32 17)T

C3=P7M3=(18 40 12 8 3 6 52)T

C4=P1M4=(48)T

組合生成最終密文：36 1 59 28 12 32 17 18 40 12 8 3 6 52 48，則文字密文為A1XscwhiEc836QM；

(5)用RSA加密體制對隨機數(shù)加密，相關(guān)參數(shù)如下：p=7，q=13，n=p×q=91，φ(n)=(p-1)(q-1)=72，e=17．計算得到d=17，加密后的密文為23 61 63 1．

解密過程為上述過程的逆過程．

4 實驗與安全性分析

為驗證本文加密算法的性能，在PC機上搭建實驗環(huán)境．(1)硬件配置：Inter Core i3-2350M CPU @ 2.30 GHz，4.0 GB RAM．(2)軟件環(huán)境：Windows 7 64位操作系統(tǒng)，Matlab R2010b．

4.1 Pascal矩陣性能分析

假設(shè)明文長度為n，字母占1 B，則明文大小為nB，生成一系列隨機數(shù)n1，n2，…，nk，且滿足n=n1+n2+…+nk．首先根據(jù)明文長度確定k值，生成一系列滿足上述條件的隨機數(shù)，然后選擇i階Pascal公式生成Pascal矩陣．由于Pascal矩陣的個數(shù)等于隨機數(shù)的個數(shù)，Pascal矩陣的階數(shù)等于隨機數(shù)的值，所以根據(jù)隨機數(shù)ni(i=1，2，…，k)的值生成與其相等階數(shù)的k個Pascal矩陣．

在滿足n=n1+n2+…+nk的條件下確定k值的方法有兩種：

方法1 選擇固定個數(shù)的隨機數(shù)；

方法2 根據(jù)明文長度確定隨機數(shù)個數(shù)，如k=n1/2．

上述兩種方法對不同明文長度生成其所需Pascal矩陣的耗時情況如表2所示．當選用方法1時，k=150；當選用方法2時，k=n1/2．

表2 不同明文長度生成Pascal矩陣耗時

影響Pascal矩陣生成耗時的因素包括：

(1)Pascal矩陣的個數(shù)．因明文長度n增加，根據(jù)方法2，隨機數(shù)的個數(shù)相應(yīng)增加，所以Pascal矩陣的個數(shù)也會增加．

(2)Pascal矩陣的階數(shù)．在明文長度n確定的情況下，隨機數(shù)的個數(shù)k也可確定；若明文長度增加，則ni(i=1，2，…，k)也會增加，即Pascal矩陣的階數(shù)越高，生成矩陣所需時間越長．

從表2可知，對于較小的文本，為了增加密文的抗攻擊性，可選擇方法2確定k值；而對于較大的文本，為了減少明文的加密時間，可選擇方法1確定k值．

4.2 各算法對不同大小文件加密耗時對比

本實驗將RSA-Hill混合加密算法與文獻[13]中提到的DES、AES、DES-RSA加密算法對不同大小文件的加密耗時進行對比．在Matlab中實現(xiàn)了RSA-Hill混合加密算法對大小為1、2、3、4和10 MB文件進行加密，根據(jù)4.1節(jié)分析選用方法1確定k值，即k=150．記錄并統(tǒng)計對不同大小文件的加密耗時，4種加密算法對不同大小文件的加密耗時如圖2所示．

圖2 各算法對不同大小文件的加密耗時對比

由圖2可知，當文件大小不大于3 MB時，RSA-Hill混合加密算法的加密耗時與DES、DES-RSA算法差別不大．當文件大小為4 MB時，RSA-Hill混合加密算法的加密耗時大于DES、AES算法，但與DES-RSA混合加密算法基本相當．原因是對于大文件，RSA-Hill混合加密算法加密所需Pascal矩陣的階數(shù)較高，矩陣運算的耗時也會相應(yīng)較長．所以RSA-Hill混合加密算法適合加密小于4 MB的文件．

4.3 攻擊實驗與安全性分析

本實驗主要驗證經(jīng)RSA-Hill混合加密算法加密后的密文還原程度．實驗樣本為1 KB大小的明文，k值的確定采用4.1節(jié)的方法2．

假設(shè)攻擊者可獲得加密后的密文信息，在實驗中所設(shè)計的攻擊步驟如下：

步驟1獲取加密后的數(shù)據(jù)塊，將其合并為密文向量；

步驟2攻擊者已知明文是由不同階數(shù)Pascal矩陣加密的且明文長度為n，但明文的分割信息未知；

步驟3根據(jù)明文長度，確定Pascal矩陣階數(shù)O的區(qū)間范圍；

步驟4用該區(qū)間范圍內(nèi)的所有Pascal矩陣對密文向量嘗試解密；

步驟5統(tǒng)計還原出的單詞數(shù)占總單詞數(shù)的比例F．

圖3顯示了不同階數(shù)Pascal矩陣對明文信息還原的比例．由圖3可知，還原明文信息的比例最高接近4.0%，所以嘗試使用不同階數(shù)Pascal矩陣破解密文的方案不可行．但30階Pascal矩陣可以還原的明文單詞數(shù)最多，因為n=1 024 B，k=32，隨機分割數(shù)中生成30的概率要比其他數(shù)大，所以用相應(yīng)逆矩陣解密獲得的信息可能會更多．如果在加密之前對明文向量進行一系列變換，可還原的有效單詞數(shù)會更少，還原明文的比例會更?。裕┝ζ平鉄o法有效還原明文．

圖3 不同階數(shù)Pascal矩陣還原明文的比例

5 結(jié) 語

本文提出了一種基于RSA和Hill的混合加密算法．通過隨機分割明文解決了構(gòu)建RSA-Hill混合加密算法的兩個難題．RSA-Hill混合加密算法不再對Hill密碼的加密矩陣進行復(fù)雜的改進，將會話密鑰轉(zhuǎn)換為明文的隨機分割數(shù)，實現(xiàn)了一次一密的加密流程，避免了啞元的出現(xiàn)．該混合加密算法具有較強的抗攻擊性和較好的加密效率．

未來的研究重點是對RSA-Hill混合密碼的安全性進行形式化定義和證明．

[1] 結(jié)城浩. 圖解密碼技術(shù)[M]. 周自恒,譯. 北京:人民郵電出版社, 2015.

HIROSHI Yuki.GraphicCryptographyTechnology[M]. ZHOU Ziheng, trans. Beijing: Posts & Telecom Press, 2015. (in Chinese)

[2] SHOUP V. A proposal for an ISO standard for public-key encryption (version 2.1) [J].InternationalAssociationforCryptologicResearch, 2001:1-52.

[3] RAHMAN M N A, ABIDIN A F A, YUSOF M K,etal. Cryptography: A new approach of classical Hill cipher [J].InternationalJournalofSecurityandItsApplications, 2013,7(2):179-190.

[4] GOEL A S, PUGLIA D, LUNAWAT S,etal. Enhancing security by adding Hill cipher to modified RSA algorithm [J].InternationalJournalofAppliedEngineeringResearch, 2014,9(9):1053-1061.

[5] 李文鋒. 基于RSA和Hill密碼體系的文件加密系統(tǒng)的研究和實現(xiàn)[D]. 贛州: 江西理工大學(xué), 2007.

LI Wenfeng. The research and implementation of file encryption system based on RSA and Hill cryptosystem [D]. Ganzhou: Jiangxi University of Science and Technology, 2007. (in Chinese)

[6] 劉海峰,何立勇,郭改慧,等. Hill密碼體系中的加密矩陣與啞元[J]. 西南大學(xué)學(xué)報(自然科學(xué)版), 2014,36(11):138-142.

LIU Haifeng, HE Liyong, GUO Gaihui,etal. The dummy and encryption matrix in the Hill coding system [J].JournalofSouthwestUniversity(NaturalScienceEdition), 2014,36(11):138-142. (in Chinese)

[7] 萬福永,戴浩暉. Hill2密碼體系加密過程中的啞元問題[J]. 數(shù)學(xué)的實踐與認識, 2007,37(8):87-90.

WAN Fuyong, DAI Haohui. The design of dummy variable in Hill2coding system [J].MathematicsinPracticeandTheory, 2007,37(8):87-90. (in Chinese)

[8] PUTERA A, SIAHAAN U, RAHIM ROBBI. Dynamic key matrix of Hill cipher using genetic algorithm [J].InternationalJournalofSecurityandItsApplications, 2016,10(8):173-180.

[9] 翁云翔. 基于DES和RSA的混合加密算法研究與設(shè)計[J]. 電子設(shè)計工程, 2016,24(17): 42-44, 47.

WENG Yunxiang. Research and design of hybrid encryption algorithm based on DES and RSA [J].ElectronicDesignEngineering, 2016,24(17):42-44, 47. (in Chinese)

[10] 劉 帥,王 平,邢建春,等. 混合加密算法的改進和設(shè)計方案[J]. 微型機與應(yīng)用, 2016,35(8):15-17.

LIU Shuai, WANG Ping, XING Jianchun,etal. Improvement and design of hybrid encryption algorithm [J].Microcomputer&ItsApplications, 2016,35(8):15-17. (in Chinese)

[11] 王 容,廖群英,王云瑩,等. Hill加密算法的改進[J]. 四川師范大學(xué)學(xué)報(自然科學(xué)版), 2015,38(1):8-14.

WANG Rong, LIAO Qunying, WANG Yunying,etal. Improvement of Hill encryption algorithm [J].JournalofSichuanNormalUniversity(NaturalScience), 2015,38(1):8-14. (in Chinese)

[12] BRUALDI R A.IntroductoryCombinatorics[M]. 5thed. Upper Saddle River: Person Education Inc., 2009.

[13] 吳明航. DES和RSA混合加密算法的研究[D]. 哈爾濱: 哈爾濱工業(yè)大學(xué), 2013.

WU Minghang. Research on DES and RSA hybrid encryption algorithm [D]. Harbin: Harbin Institute of Technology, 2013. (in Chinese)