Hill密码加密的密文破译

姓名：谭周兴 学号：13091076

明文：breathtaking 密文：RUPOTENTOIFV

Hill密码：将明文的每个字母当作26进制数字：A=0, B=1, C=2... 一串字母当成n

维向量，跟一个n×n的矩阵M相乘，再将得出的结果MOD26，得到密文。密钥矩阵M必须是在Z26上可逆才能译码。

明文对应的数字：1，17，4，0，19，7，19，0，10，8，13，6 密文对应的数字：17，20，15，14，19，4，13，19，14，8，5，21

分析：一共有12位数字，则密钥矩阵可能是1*1、2*2、3*3、4*4、6*6、12*12（为12的因子）维的。根据已有的明密文不能破译4*4及其以上的密钥矩阵，另外明文里面含有0，从而排除1*1的情况，因而考虑2*2阵和3*3阵。

1、2*2矩阵：

将明文按行写成一些2*2矩阵，如A1=[

14

1717]，B=[015

20

]。A1M（mod26）=B，矩阵14

A1在实数域内是可逆矩阵，判断A1在Z26上是否可逆，计算det（A1）（mod 26）=10，

与26不互素，故A1不可逆，M无法根据A1得到。

40

继续上述步骤，A2=[]。计算det（A2）（mod 26）=2，与26不互素，故

197A2不可逆，M无法根据A2得到。

det（A3）（mod 26）=23，和M互素，如图计算A3的代数余子式A*=（detA）*A-1mod26（矩阵元素元素属于实数域）和A-1.A-1=A*|A|-1（这里的矩阵元素和行列式的逆属于Z26.|A|-1计算用如下代码即可：

#include void main() {int i,a;

scanf(\"%d\for(i=0;i<=25;i++){ if((a*i)%26==1) break;}

printf(\"%d\

算得M=[13 1;12 9]。但经过验算发现该密钥对于（1，17），（4，0）等加密出来的密文与题目提供的密文不同，因此M不是我们所需要的。

用上述步骤算出的M没有一个满足条件，故考虑3*3矩阵 2、3*3矩阵：

A1=[1 17 4;0 19 7;19 0 10]，det（A1）mod26=19.用上述程序算得19的逆为11.M=[3 21

20;4 15 23;6 14 5]，如下图所示：

同样对余下的明密文进行验证，发现结果是相符的。

所以M有可能是密钥矩阵。

同样的方法计算A2=[0，19，7;19，0，10;8，13，6]

计算密钥矩阵M：

验算前三个明密文：

算得与密文不一致，舍弃。

综上所述密钥矩阵有可能为M=[3 21 20;4 15 23;6 14 5]。

3、感想和体会 Matlab很好用。

如果我们能够熟练的运用这些软件，解决问题的效率将会大大提高。

二阶的矩阵全部不可以，这中间应该有内在的规律，可能是因为2和26不互素的关系，没有想明白。