一種基于多密碼體制的混合加密算法

楊 宏 宇， 寧 宇 光， 王 玥

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

0 引 言

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

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

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

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

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

1 多密碼體制分析

1.1 問題分析

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

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

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

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

1.2 密鑰空間分析

Hill加密算法的密鑰空間

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

(1)

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

(2)

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

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

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

(3)

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

2 Pascal公式的推廣

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

2.1 假 設

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

……

2.2 i階Pascal公式證明

i階Pascal公式為

(4)

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

綜上所述，根據雙計數原理可得

2.3 分 析

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

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

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

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

3.1 RSA-Hill混合加密算法

RSA-Hill混合加密流程設計如下：

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

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

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

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

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

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

表1 字符表

3.2 算法分析

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

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

3.3 應用實例

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

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

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

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

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

M1=(36 29 29 10)T

M2=(12 20 29)T

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

M4=(48)T

圖1 算法框架圖

對應生成的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加密體制對隨機數加密，相關參數如下：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矩陣性能分析

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

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

方法1 選擇固定個數的隨機數；

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

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

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

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

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

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

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

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

本實驗將RSA-Hill混合加密算法與文獻[13]中提到的DES、AES、DES-RSA加密算法對不同大小文件的加密耗時進行對比．在Matlab中實現了RSA-Hill混合加密算法對大小為1、2、3、4和10 MB文件進行加密，根據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矩陣的階數較高，矩陣運算的耗時也會相應較長．所以RSA-Hill混合加密算法適合加密小于4 MB的文件．

4.3 攻擊實驗與安全性分析

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

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

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

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

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

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

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

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

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

5 結 語

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

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

[1] 結城浩. 圖解密碼技術[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)的研究和實現[D]. 贛州: 江西理工大學, 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]. 西南大學學報(自然科學版), 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]. 數學的實踐與認識, 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的混合加密算法研究與設計[J]. 電子設計工程, 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] 劉 帥,王 平,邢建春,等. 混合加密算法的改進和設計方案[J]. 微型機與應用, 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]. 四川師范大學學報(自然科學版), 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è)大學, 2013.

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