一种基于多密码体制的混合加密算法

杨 宏 宇， 宁 宇 光， 王 玥

( 中国民航大学 计算机科学与技术学院， 天津 300300 )

0 引 言

为解决对称密码密钥配送难和公钥密码加密速度慢的问题，混合密码系统被提出并且广泛使用．混合密码系统组成机制包含如下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密码加密流程分析入手，将其规律分割明文转换为随机分割明文，不再针对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密码对该密钥加密．该混合加密算法中密钥空间的改变，实现了一次一密混合密码系统．

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密码的密钥，其优点是避免了生成加密矩阵时大量复杂的运算[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的规模依次减小，当需要生成阶数较大的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，得到加密后的密文矩阵，将密文矩阵转化为行向量并组合在一起成为最终密文发送到接收方；

(5)用RSA加密算法对随机数加密和传送；

(6)解密时先用RSA算法解密随机数，再依据随机数按Hill算法解密．

表1 字符表

3.2 算法分析

根据图1可知，计算机在运行RSA-Hill混合加密算法时，不再需要生成行列式为±1的随机矩阵A，即detA=±1，仅需要生成一系列随机数．通过这种方式能提高算法的执行效率和性能，减少计算机系统资源的消耗．

在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机上搭建实验环境．(1)硬件配置：Inter Core i3-2350M CPU @ 2.30 GHz，4.0 GB RAM．(2)软件环境：Windows 7 64位操作系统，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节分析选用方法1确定k值，即k=150．记录并统计对不同大小文件的加密耗时，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节的方法2．

假设攻击者可获得加密后的密文信息，在实验中所设计的攻击步骤如下：

步骤1获取加密后的数据块，将其合并为密文向量；

步骤2攻击者已知明文是由不同阶数Pascal矩阵加密的且明文长度为n，但明文的分割信息未知；

步骤3根据明文长度，确定Pascal矩阵阶数O的区间范围；

步骤4用该区间范围内的所有Pascal矩阵对密文向量尝试解密；

步骤5统计还原出的单词数占总单词数的比例F．

图3显示了不同阶数Pascal矩阵对明文信息还原的比例．由图3可知，还原明文信息的比例最高接近4.0%，所以尝试使用不同阶数Pascal矩阵破解密文的方案不可行．但30阶Pascal矩阵可以还原的明文单词数最多，因为n=1 024 B，k=32，随机分割数中生成30的概率要比其他数大，所以用相应逆矩阵解密获得的信息可能会更多．如果在加密之前对明文向量进行一系列变换，可还原的有效单词数会更少，还原明文的比例会更小．所以，暴力破解无法有效还原明文．

图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密码体系的文件加密系统的研究和实现[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]. 哈尔滨: 哈尔滨工业大学, 2013.

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