一阶双曲构建Hill密码及计算机模拟

一阶双曲构建Hill密码及计算机模拟

汤永龙，黄锦

汤永龙，黄锦

（吉首大学信息管理与工程学院，湖南张家界427000）

摘要：本文讨论用偏微分方程构建Hill密码的方法。以一阶线性非齐次双曲方程混合问题的形式给出加、解密问题的模型，由差分格式算法设计可用于加、解密的矩阵方程。改进的Hill密码系统中，矩阵变化多样、密钥空间大且便于传输和管理。最后用Matlab编制软件实现并对部分结果进行分析。

关键词：密码；一阶双曲方程；Hill密码；模拟

中图分类号：TB24文献标识码：A文章编号：1007-9599(2010)05-0000-02

HillCipherBasedOnFirst-OrderHyperbolicEquation&ComputerSimulation

TangYonglong,HuangJin

(JishouUniversity,InformationManagementandEngineeringInstitute,Zhangjiajie,427000,China)

Abstract:ThispaperdevotestoconstructHillcipherbyusingpartialdifferentialequations(PDEs).Encryptionanddecryptionmodelsbasedonthefirst-orderhyperbolicequationwithmixedboundaryconditionsareproposed.MatrixfunctionsaccordingtothedifferenceschemesareDesigned.TheimprovedHillcipherhassomeadvantageattributes,forexample,thevariabilityofmatrix,thesufficiencyofkeyspaceandtheconvenienceofkeysmanagementandtransmission.AcomputersimulationsoftwareisestablishedbyMatlab.Analysistotheexperimentalresultsisgiven.

Keywords:Cryptograpphy;First-orderhyperbolicequation;Hillcipher;Simulator

一、引言

密码研究通常主要使用代数、数论、概率统计等离散数学工具。直到1987年，G.R.Blakley和WilliamRundell才开始把分析数学应用于密码学研究[1]。他们提出一种所谓的“热流密码体制”，把偏微分方程及其反向问题的理论应用于信息安全领域。国内学者对这种热流密码体制进行相关研究，取得了一些进展[2，3]。借鉴这种思想，我们使用一阶双曲方程构建类似于Hill密码的分组密码，取得了良好效果。

Hill密码体制由LesterS.Hill在1929年提出[4]。它的基本原理是将n个明文字母通过线性变换为n个密文字母，解密时只需要进行一次逆变换，密钥就是其变换矩阵。由于Hill密码体制的密钥是一个矩阵，难于传输和管理，而且密钥单一，在已知明文攻击下容易被破译，所以Hill密码体制早已退出历史舞台。本文利用偏微分方程混合问题及其反向问题来构造矩阵方程，矩阵中的元素与方程的系数相关。由于系数可以是时间和空间变量的函数，因此矩阵可随时间变化。这样传输方只需传递一个偏微分方程，接收方即可得到一个变化的矩阵方程。方程中密钥丰富，选择范围广，可确保一次一密，解决了原有Hill密码体制中所存在的问题，增强了其抗攻击性和破解难度。

二、加密和解密模型

本文构建的加密模型为如下一阶双曲混合初边值问题：

t=0，u=φ(x)(1)

(t，0)=u(t，1)=0

其中A(t，x)，B(x)和C(t，x)是连续可微函数，A(t，x)非正或非负。且。我们取t=0时的值u(0，x)=φ(x)作为明文，t=1时的值u(1，x)=ψ(x)作为密文，边值条件可当作分组密码中每一组的分界，A(t，x)，B(x)，C(t，x)为密钥。事实上，在对方程进行求解时，由于A(t，x)的符号对于定解条件要求有着较大的不同，因此A(t，x)的符号也可当成密钥使用。

解密模型使用上述方程的反向问题进行构造：

t=0，v=ψ(x)(2)

v(t，0)=v(t，1)=0

使用(1)和(2)的局部解，我们可构建对称密码体制。局部解存在性的证明可参考相关文献[5]，我们在此省略。

三、差分格式和矩阵变换

前节给出了加、解密问题的偏微分方程模型，但实际应用时，为便于计算机模拟，往往要寻求方程的数值解。一阶双曲方程的差分格式有很多，本文使用Lax-Wendroff格式，这是变系数方程使用最多的差分格式之一。

在矩形区域[0，1]×[0，1]中，取空间步长h=△x=1/J的等距格点xj=jh，j=0，1，2，…，J；取时间步长τ=△t=1/K的等距格点tk=kτ，k=0，1，2，…，K，记格点(j，k)处的值

=u(jh，kτ)。假定A(t，x)>0，则加密问题(1)的Lax-Wendroff差分格式为：

(3)

式中，j=1，2，…，J-1，k=0，1，2，…，K-1。容易证明(3)式的收敛性，为了证明它的稳定性，我们使用能量法。当A(t，x)满足，而且网格比满足时，格式稳定[6，7]。

(3)可写成如下的矩阵方程：

(4)

如果Gk可逆，则(4)式写成：

(5)

式中，

我们取时间t=0时的值作为明文，使用矩阵变换(4)进行迭代，当时间t=1时，得到的值即为密文。从(4)式可看出，这是一个分组密码体制模型，分组的长度为J-1。解密时，使用方程(5)进行变换，这时的初值变为，迭代过程是倒推的。

由于矩阵Gk中的密钥A(t，x)是关于时间和空间变量的函数，每一步迭代时，矩阵中的值并不相同，也即矩阵Gk是一个随时间变化的矩阵，这就是本系统优越于传统Hill密码系统的地方。解密时，为了正确地从密文反解得到相应的明文，除要掌握A(t，x)，B(x)，C(t，x)这些方程中的密钥对外，Gk中△x、△t的值，以及矩阵变换次数K都必须知道，因此也可把它们当作密钥对来使用。

由此，我们借助一阶双曲方程的混合问题，通过写出它的差分格式，得到用于加密、解密的变换矩阵，从而找到了一种构建分组密码的新方法。

四、计算机模拟结果分析

根据矩阵方程(4)和(5)，用Matlab7.1编写加、解密的模拟软件。程序中，建立文件key.m实现密钥函数A(t，x)，B(x)，C(t，x)的输入，文件data.m实现明文（或密文）的输入，这样可方便设定不同的密钥和选取不同明文进行加、解密的计算机模拟，通过比较分析优选出合适的密钥。实验中取定明文函数φ(x)=25(x2-x3+sin(11x-11x2)，分组长度J=100，迭代次数K=100，通过改变A(t，x)、B(x)、C(t，x)的值测试系统。实验所得的图中，明文函数、密文函数的图形用曲线表示，解密后的图形用*表示。

图1测试密钥C(t，x)

图1固定A(t，x)=0.15(x+|cos(10+2xt)|)，B(x)=x3，对C(t，x)进行测试。(a)中C(t，x)≡0，明文与密文几乎重叠，密码系统的抗攻击能力很弱。(b)中C(t，x)=100cos(25x-40t)+100t，密文函数ψ(x)的图像相对于明文函数φ(x)有很大变化，极值点位置明显受到C(t，x)的影响而不再仅仅依赖于明文，因而具有较强的保密性。(c)中C(t，x)=50x-cos(x+t2)-200t，表明由于C(t，x)选取不当，正的明文加密后出现了负的密文。

图2测试密钥A(t，x)

图2固定B(x)=x3，C(t，x)=100cos(25x-40t)+100t，对A(t，x)进行测试。由图看出，A(t，x)可使密文的波峰偏移，并且能改变密文的波峰个数；(b)显示当A(t，x)的值取得太小时，密文与明文的图形极点峰值和波峰的个数都相似，明文的信息容易被泄露。

图3测试密钥B(t，x)

图3固定A(t，x)=0.15(x+|cos(10+2xt)|)，C(t，x)=100cos(25x-40t)+100t，对B(x)进行测试。由图可见，B(x)的变化主要引起密文图形幅值随时间变小，但图形的性态基本保持一致。

模拟结果表明：（1）解密后的图形与明文图形基本上合二为一，其差异从图形上已难以辨别，可见解密效果很好；（2）采用非齐次方程能有效地提高密码体制的抗攻击能力，但非齐次项要选择合适。

实验中我们还测试到，当不用加密密钥来解密时，得到的结果与明文差别极大，要还原出明文几乎是不可能的。

五、结论

这种由一阶双曲混合问题构建的Hill密码体制，设计思想明确，编程简单，加、解密速度快（对每一明密文组进行加、解密的时间不超过5秒），效果好。密钥的传输管理简单，只需要对三个密钥函数及关键变量进行传输，即可得到随时间变化的矩阵方程。系统中密钥对的选择范围广，可以做到数据加密的“一次一密”，增加了通信的安全性。但因目前还没有相关的方程理论作保障，合适的密钥只有经多次试验才能得出。

另外，由于方程理论的制约，对于已知数量的明文密文对时是否能还原出密钥函数，目前尚未能得出一般性结论，其规律性还有待进一步研究。

参考文献：

[1]BlakleyGR,Rundell.Cryptosystemsbasedonananalogofheatflow.AdvancesinCryptology--CRYPTO'87，306-329，1987[C].Berlin：Springer-Verlag,1988

[2]宋惠元,楚泽甫,赵新田.热流密码体制线性模型加、解密理论及实验方法分析.密码学进展一一CHINACRYPTO’92,第二届中国密码学学术会论文集,24-33,1992[C].北京:科学出版社,1992

[3]唐林山,江成顺.一种结合混沌的热流密码图像加密算法.计算机工程与应用,2007,43(3):37-39.

[4]DouglasR.Stinson著,冯登国译.密码学原理与实践[M].北京:电子工业出版社,2003.

[5]LiTa-Tsien.GlobalClassicalSolutionsforQuasilinearHyperbolicSystems[M].JohnWiley&Sons,1994.

[6]应隆安,滕振寰.双曲型守恒律方程及其差分方法[M].北京:科学出版社,1991

[7]胡健伟,汤怀民.微分方程数值方法[M].北京:科学出版社,1999

作者简介：汤永龙，1961-，男。吉首大学信息管理与工程学院副教授。主要从事应用数学和信息安全研究。

基金项目：本文得到湖南省教育厅自然科学基金项目（09C791）的资助