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

楊 宏 宇， 寧 宇 光， 王 玥

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

0 引 言

為解決對(duì)稱密碼密鑰配送難和公鑰密碼加密速度慢的問題，混合密碼系統(tǒng)被提出并且廣泛使用．混合密碼系統(tǒng)組成機(jī)制包含如下4個(gè)過程：用對(duì)稱密碼加密明文、通過偽隨機(jī)數(shù)生成器生成對(duì)稱密碼加密中使用的會(huì)話密鑰、用公鑰密碼加密會(huì)話密鑰、從外部賦予公鑰密碼加密時(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++算法通過引入隨機(jī)矩陣作為密鑰增強(qiáng)了Hill密碼對(duì)已知明文攻擊的抵抗性．但是該算法僅對(duì)加密矩陣進(jìn)行了改進(jìn)，需要復(fù)雜的代數(shù)運(yùn)算．Goel等[4]通過在RSA密碼加密前對(duì)明文進(jìn)行Hill加密，增強(qiáng)了RSA密碼對(duì)暴力攻擊的抵抗性．但該方法沒有構(gòu)造混合密碼，仍存在對(duì)稱密碼密鑰配送難和公鑰密碼加密速度慢的問題．李文鋒[5]提出了基于有限域矩陣構(gòu)造技術(shù)的RSA-Sign-Hill算法，該算法用生成Hill密碼加密矩陣時(shí)產(chǎn)生的關(guān)鍵數(shù)字l作為會(huì)話密鑰，導(dǎo)致其會(huì)話密鑰過于單一，生成加密矩陣算法的代價(jià)較高，無法抵抗已知明文攻擊等密碼分析手段．

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

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

1 多密碼體制分析

1.1 問題分析

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

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

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

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

1.2 密鑰空間分析

Hill加密算法的密鑰空間

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

(1)

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

(2)

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

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

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

(3)

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

2 Pascal公式的推廣

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

2.1 假 設(shè)

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

……

2.2 i階Pascal公式證明

i階Pascal公式為

(4)

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

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

2.3 分 析

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

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

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

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

3.1 RSA-Hill混合加密算法

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

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

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

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

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

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

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

表1 字符表

3.2 算法分析

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

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

3.3 應(yīng)用實(shí)例

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

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

通過計(jì)算可得明文長度n=15；

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

(3)用隨機(jī)數(shù)對(duì)明文進(jìn)行劃分：

M1=(36 29 29 10)T

M2=(12 20 29)T

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

M4=(48)T

圖1 算法框架圖

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

(4)對(duì)明文進(jìn)行加密計(jì)算：

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加密體制對(duì)隨機(jī)數(shù)加密，相關(guān)參數(shù)如下：p=7，q=13，n=p×q=91，φ(n)=(p-1)(q-1)=72，e=17．計(jì)算得到d=17，加密后的密文為23 61 63 1．

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

4 實(shí)驗(yàn)與安全性分析

為驗(yàn)證本文加密算法的性能，在PC機(jī)上搭建實(shí)驗(yàn)環(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，生成一系列隨機(jī)數(shù)n1，n2，…，nk，且滿足n=n1+n2+…+nk．首先根據(jù)明文長度確定k值，生成一系列滿足上述條件的隨機(jī)數(shù)，然后選擇i階Pascal公式生成Pascal矩陣．由于Pascal矩陣的個(gè)數(shù)等于隨機(jī)數(shù)的個(gè)數(shù)，Pascal矩陣的階數(shù)等于隨機(jī)數(shù)的值，所以根據(jù)隨機(jī)數(shù)ni(i=1，2，…，k)的值生成與其相等階數(shù)的k個(gè)Pascal矩陣．

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

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

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

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

表2 不同明文長度生成Pascal矩陣耗時(shí)

影響Pascal矩陣生成耗時(shí)的因素包括：

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

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

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

4.2 各算法對(duì)不同大小文件加密耗時(shí)對(duì)比

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

圖2 各算法對(duì)不同大小文件的加密耗時(shí)對(duì)比

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

4.3 攻擊實(shí)驗(yàn)與安全性分析

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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

未來的研究重點(diǎn)是對(duì)RSA-Hill混合密碼的安全性進(jìn)行形式化定義和證明．

[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)的研究和實(shí)現(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é)報(bào)(自然科學(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é)的實(shí)踐與認(rèn)識(shí), 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ì)[J]. 電子設(shè)計(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ìn)和設(shè)計(jì)方案[J]. 微型機(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ìn)[J]. 四川師范大學(xué)學(xué)報(bào)(自然科學(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)