一、希尔密码产生的必然性
随着科技的日新月异和人们对信用卡、计算机的依赖性的加强,密码学显得愈来愈重要。密码学是一门关于加密和解密、密文和明文的学科。若将原本的符号代换成另一种符号,即可称之为广义的密码。狭义的密码主要是为了保密,是一种防止窃文者得知内容而设的另一种符号文字,也是一般人所熟知的密码。

使用信用卡、网络账号及密码、电子信箱、电子签名等都需要密码。为了方便记忆,许多人用生日、电话号码、门牌号码记做密码,但是这样安全性较差。

为了使密码更加复杂,更难解密,产生了许多不同形式的密码。密码的函数特性是明文对密码为一对一或一对多的关系,即明文是密码的函数。传统密码中有一种叫移位法,移位法基本型态是加法加密系统-C=P+s(mod m)。一般来说,我们以1表示A,2表示B,……,25表示Y,26表示Z,以此类推。由于s=0时相当于未加密,而0≤s≤m-1(s≥m都可用0≤s≤m-1取代),因此,整个系统只有(m-1)种变化。换言之,只要试过(m-1)次,机密的信息就会泄漏出去。

由此看来,日常生活中的密码和传统的密码的可靠性较差,我们有必要寻求一种容易将字母的自然频度隐蔽或均匀化,从而有利于统计分析的安全可靠的加密方法。希尔密码[1]能基本满足这一要求。

二、希尔密码算法原理

希尔加密算法的基本思想是,将d个明文字母通过线性变换将它们转换为d个密文字母。解密只要作一次逆变换就可以了,密钥就是变换矩阵本身。

希尔密码是多字母代换密码的一种。多字母代换密码可以利用矩阵变换方便地描述,有时又称为矩阵变换密码。令明文字母表为Z,若采用L个字母为单位进行代换,则多码代换是映射f:Z→Z。若映射是线性的,则f是线性变换,可以用Z上的L×L矩阵K表示,K=(k)为密钥。若是满秩的,则变换为一一映射,且存在有逆变换K,使KK=KK=I。将L个字母的数字表示为Z上的L维矢量m=(m,m,…,m),相应的密文矢量c=(c,c,…,c)为mK=c,以K作为解密矩阵,可由c恢复出相应的明文c•K=m。

在军事通讯中,常将字符(信息)与数字对应(为方便起见,我们将字符和数字按原有的顺序对应,事实上这种对应规则是极易被破解的):
abcde…x y z
12345…242526
如信息“NOSLEEPPING”对应着一组编码14,15,19,12,5,5,16,16,9,14,7。但如果按这种方式直接传输出去,则很容易被敌方破译。于是必须采取加密措施,即用一个约定的加密矩阵K乘以原信号B,传输信号为C=KB(加密),收到信号的一方再将信号还原(破译)为B=KC。如果敌方不知道加密矩阵,则很难破译。

加密 

第一步,设定加密矩阵为K=112-120113,即在希尔密码中设q=26,L=3,选取满秩3×3阶可逆矩阵。我们之所以取3×3可逆方阵,也是为了计算方便,相应的安全性就要低一些。

第二步,将信息14,15,19,12,5,5,16,16,9,14,7分为4个列矩阵:X=141519,X=1255,X=16169,X=1470,其中X中的“0”是虚设的,其目的是为了与列矩阵X,X,X的行数一致。列矩阵的行数3和个数4完全依赖于加密后的信息所对应的数字的多少和加密矩阵阶数决定。

第三步,将信息加密。进行矩阵的乘法运算:
Y=KX=112-120213141519=6716100;
Y=KX=112-1202131255=27-244;
Y=KX=112-12021316169=501675;
Y=KX=112-1202131470=21035。
加密后的新码为67,16,100,27,-2,44,50,16,75,21,0。Y中的35虽然是多余的信息,但要连同密码一起发给对方,对方在破解密码时要参与计算。

解密 

第一步,求密匙矩阵K的逆矩阵[2]K。K可用Mathematica计算。
Inverse123-120213∥MatrixForm=-614-3125-1-3,
即K=-614-3125-1-3。

第二步,由得Y=KX得X=KY(i=1,2,3,4),再次进行矩阵乘法运算:
X=KY=-614-3125-1-3671610=141519;
X=KY=-614-3125-1-327-244=1255;
X=KY=-614-3125-1-3501675=16169;
X=KY=-614-3125-1-321035=1470。
这样原来的信息编码为14,15,19,12,5,5,16,16,9,14,7。

第三步,对照编码表,即可获得对方发来的信息内容为“NOSLEEPPING”。

三、希尔密码算法安全性分析

不难看出,希尔密码算法中有两个非常重要的条件。第一个条件是字符(信息)与数字对应表,当加密矩阵的阶数n(本文实例中的加密矩阵的阶数n=3)越大,破译的难度就会增大,此时计算量也大,我们可以借助有关数学软件如Mathematica提高运算效率。第二个条件是加密矩阵,如何定义、求解这个矩阵对于密码的加密和破译至关重要。

从破译密码的角度来看,传统的密码有一个致命弱点,就是破译者可从统计出来的字符频率中找到规律,进而找出破译的突破口,尤其是在计算机技术高度发达的今天,破译的速度更快。希尔密码算法则完全克服了这一缺陷,它通过采用线性代数中的矩阵乘法运算和逆运算,能够较好地抵抗频率分析,很难被攻破。

希尔密码体系为破译者至少设置了三道关口,加大了破译难度。破译希尔密码的关键是猜测文字被转换成几维向量(列矩阵的行数)、所对应的字母表是怎样排列的,更为重要的是要设法获取加密矩阵A。要破解密码,向量的维数、字母的排列表和加密矩阵三者缺一不可。古今中外的谍报战中,敌对双方总是千方百计地获取破解对方密码的钥匙,但要想获取希尔密码的三把钥匙谈何容易。

世界上没有攻不破的密码,希尔密码也不例外。希尔密码算法的缺点在于线性变换的安全性很脆弱,易被攻击击破,黑客正是利用各种密码的弱点来向用户频频发起攻击的。尽管如此,希尔密码仍不失为一种简便高效的密码。