使用希尔密码加解密文件：实现数据安全传输

【任务描述】

希尔（Hill）密码是运用基本矩阵原理的替代密码，由数学家Lester S.Hill在1929年发明。希尔（Hill）密码是一种分组密码。它将n个连续的明文字母串加密成n个连续的密文字母串。它的意义在于第一次在密码学中用到了代数方法（线性代数、模的运算）。

（1）使用搜索引擎查找希尔（Hill）密码的加密机制。

（2）使用希尔（Hill）密码加密消息“meetme at the usual place at ren rather than eight o'clock”，密钥为，要求写出计算过程和结果。

【任务分析】

希尔（Hill）密码加解密涉及矩阵与逆矩阵的运算。

【知识准备】

1.矩阵的运算法则

（1）矩阵与矩阵相乘。两个矩阵相乘的必要条件：第一个矩阵的列数必须＝第二个矩阵的行数。

例如，第一个矩阵是m×n的矩阵，第二个矩阵是n×p的矩阵，则二者相乘的结果就是m×p的矩阵，且得到的矩阵中的元素具有以下特点：

第一行第一列元素为第一个矩阵第一行的每个元素和第二个矩阵第一列的每个元素乘积的和。依此类推，第i行第j列的元素就是第一个矩阵第i行的每个元素与第二个矩阵第j列的每个元素的乘积的和，如图3-19所示。

图3-19　矩阵乘法规则

（2）矩阵的求逆运算。逆矩阵的概念：设A是数域上的一个n阶矩阵，若在相同数域上存在另一个n阶矩阵B，使得AB＝BA＝E，则称B是A的逆矩阵，而A被称为可逆矩阵（注：E为单位矩阵）。

逆矩阵的唯一性：若矩阵A是可逆的，则A的逆矩阵是唯一的。

n阶矩阵A可逆的充分必要条件是它能表示成一系列初等矩阵的乘积，即A＝Q1Q2·…·Q m，从而推出可逆矩阵可以经过一系列初等行变换化成单位矩阵，即必有一系列初等矩阵Q1Q2·…·Q m，使得

则

把A、E这两个n阶矩阵凑在一起，做成一个n×2n阶矩阵（A，E），按矩阵的分块乘法，式（3-1）、式（3-2）可以合并写成

这样就可以求出矩阵A的逆矩阵A-1。

说明：此方法适用于求元素为具体数字的矩阵的逆矩阵。

2.希尔（Hill）密码的加解密算法

希尔（Hill）密码的加解密算法的基本思想是将n个明文字母通过线性变换转化为n个密文字母，解密时只需作一次逆变换即可，密钥就是变换矩阵。

设明文m＝（m1＋m2＋…＋mn），密文c＝（c1，c2，…，cn），密钥为Z26上的n×n阶可逆方阵K＝（kij）n×n，则

【任务实施】

1.了解希尔（Hill）密码的加解密算法

1）希尔（Hill）密码的概念

希尔（Hill）密码事实上是一个矩阵乘法体系，加密密钥是一个矩阵K，密钥就是K-1，每个字母当作26进制数字：A当作0，B当作1，C当作2，……一串字母当成n维向量，跟一个n×n的矩阵相乘，再将得出的结果mod 26，如图3-20所示。(www.xing528.com)

图3-20　希尔（Hill）密码的加解密

注意：

（1）用作加密的矩阵（即密钥）必须是可逆的，否则就不可能解密。

（2）只有矩阵的行列式和26互质，该矩阵才是可逆的。

2）希尔（Hill）密码算法

希尔（Hill）密码算法的基本思想是：将n个明文字母通过线性变换转换为n个密文字母。解密只要作一次逆变换，密钥就是变换矩阵本身。

希尔（Hill）密码属于多码代换密码，可以利用矩阵变换方便地描述，有时又称为矩阵变换密码。

令明文字母表为Z，若采用L个字母为单位进行代换，则多码代换是映射f：Z→Z。若映射是线性的，则f是线性变换，可以用Z上的L×L矩阵K表示，K＝（k）为密钥。若是满秩的，则变换为一一映射，且存在逆变换K-1，使KK-1＝K-1 K＝I。将L个字母的数字表示为Z上的L维矢量m＝（m1，m2，…，mL），相应的密文矢量c＝（c1，c2，…，cL）为m K＝c，以K-1作为解密矩阵，可由c恢复出相应的明文c·K-1＝m。

3）使用手工计算进行希尔（Hill）密码的加解密

（1）首先，列出26个字母与数字的对应关系（可由加解密双方约定），如表3-2所示。

表3-2　字母与数字的对应关系

根据希尔（Hill）密码的加密方法C＝KP mod 26（注：C是密文，K是密钥，P是明文），将明文两两分组为“me etme at th eu su al pl ac ea tt en ra th er th an ei gh to cl oc kx”。

根据前文的介绍可得最终密文为“GVUIGVKODZYPUHEKJHUZWFZFWSJSDZMUD ZMYCJQMFWWUQRKR”。

（2）求密钥K＝的逆矩阵K-1。

通过K-1和密文可以破解出明文。

2.使用CAP4软件进行希尔（Hill）密码的加解密

CAP4软件内置了希尔（Hill）密码加解密算法，使用CAP4软件进行希尔（Hill）密码的加解密更加方便快捷。

【动手做一做】

（1）甲方收到乙方的一封密文信息，密文如下：

WOWUYSBACPGZSAVCOVKPEWCPADKPPABUJCQLYXQEZAACPP

按约定，他们之间采用Hill 2密码通信，密钥是二阶矩阵A＝，且汉语拼音的26个字母与0～25之间的整数建立一一对应关系，称之为字母的表值如表3-3所示。问这段密文

表3-3　字母的表值

解：

①设明文信息只需要26个字母（A～Z），通信双方给出这26个字母的表值，根据表值将明文信息用数字表示。

②选择一个二阶可逆方阵A，即密钥矩阵。

③将明文字母依次逐对分组，Hill 2密码的加密矩阵为二阶矩阵，明文字母两个一组（Hill n密码，n个明文字母为一组），若最后一组只有一个字母，则补充一个无意义的字母，称为哑字母。由明文字母的表值查出每一组两个明文字母的表值，得到一个二维列向量α。

④A左乘以α得到一个新的二维向量β＝Aα，反查字母的表值得到密文字母，从而完成加密过程。

（2）甲方截获了一段密文“OJWPISWAZUXAUUISEABAUCRSIPLBHAAMMLPJJOTENH”，经过分析，这段密文是使用Hill 2密码加密的，而且目前仅知道密文UCRS代表TACO，请破解这段密文的内容。