Hill密码的加密解密

【实验十】Hill密码的加密、解密与破译

一、实验目的

本实验主要涉及代数，利用模运算下的矩阵乘法、求逆矩阵、线性无关、线性空间与线性变换等概念和运算，学习Hill密码体制的加密、解密和破译过程

二、实验任务

任务五

找出元素属于Z26的所有可能的Hill2密码加密矩阵。若截获了如下一段密文： UTCQCVFOYQUVMGMGULFOLEYHDUHOPEASWXTIFBAMWT

且已知它是根据表10.1按Hill2密码体制加密的，你能否将其解密?

表10. 1 明文字母的表值 A 1 N 14 B 2 O 15 C 3 P 16 D 4 Q 17 E 5 R 18 F 6 S 19 G 7 T 20 H 8 U 21 I 9 V 22 J 10 W 23 K 11 X 24 L 12 Y 25 M 13 Z 0 分析：对于第一问，找出元素属于Z26的所有可能的Hill2密码加密矩阵，我们只需要用枚举法即可。关键在于第二问的解密，根据我们编写的C++程序，共有约15万个可能的加密矩阵，也就对应着同等数量的可能明文。所以问题的重点就在于如何从这么多数量的明文中筛选出有意义的信息。

1、找出元素属于Z26的所有可能的Hill2密码加密矩阵

C++源代码（枚举加密矩阵部分）：

chain_mat* head=new chain_mat; //加密矩阵用链表储存 head->next=NULL;

chain_mat* now=head;

int n=0;

for(int a=0;a<26;a++) for(int b=0;b<26;b++) for(int c=0;c<26;c++) for(int d=0;d<26;d++) { intdet=a*d-b*c;

if(det%2!=0&&det!=0) //判断是否模26可逆 {

chain_mat* newm=new chain_mat; newm->dat[0][0]=a; newm->dat[0][1]=b; newm->dat[1][0]=c; newm->dat[1][1]=d;

n++; //累加符合要求的矩阵数量 now->next=newm; now=now->next; now->next=NULL;

} }

运行结果：n=157248

由于矩阵数量过多，我们将其存储在matrixlist.txt文件中

C++源代码（输出矩阵部分）：

voidoutput_mat(chain_mat* head) {

ofstreamoutfile;

outfile.open(\chain_mat* now=head->next; while(now!=NULL) {

outfile<dat[0][0]<<'\\t'<dat[0][1]<<'\\n'<dat

[1][0]<<'\\t'<dat[1][1]<<\now=now->next; }

outfile.close(); }

下面给出matrixlist.txt中部分内容（完整文件将发至邮箱）： 0 1 1 0

========== 0 1 1 1

========== 0 1 1 2

========== 0 1 1 3

========== 0 1 1 4

========== 0 1 1 5

========== 0 1 1 6

========== 0 1 1 7

========== 0 1 1 8

========== 0 1 1 9

========== 0 1 1 10

==========

2.解密题中密文

首先需要做的是对矩阵进行模逆运算

C++源代码（模26逆矩阵运算部分）： voidinv(chain_mat* m1) {

intdet=m1->dat[0][0]*m1->dat[1][1]-m1->dat[0][1]*m1->dat[1][0]; det=reci(det); inttmp;

tmp=m1->dat[0][0]*det;m1->dat[0][0]=m1->dat[1][1]*det;m1->dat[1][1]=tmp;

m1->dat[0][1]*=-1*det;m1->dat[1][0]*=-1*det; for(inti=0;i<2;i++) for(int j=0;j<2;j++) {

m1->dat[i][j]%=26; if(m1->dat[i][j]<0)

m1->dat[i][j]+=26; } }

然后用逆矩阵乘密文向量，得到可能明文序列，存入名为me1的string数组中

C++源代码（模26逆矩阵运算部分）： n=0;

while(now!=NULL)

{

inv(now);

for(inti=0;i

int s1=now->dat[0][0]*co1[i]+now->dat[0][1]*co1[i+1]; int s2=now->dat[1][0]*co1[i]+now->dat[1][1]*co1[i+1]; s1%=26;s2%=26; if(s1<0)s1+=26; if(s2<0)s2+=26; if(s1==0)

s1=26; if(s2==0)

s2=26; me1[n]+=('A'+s1-1); me1[n]+=('A'+s2-1); } n++;

inv(now);

now=now->next; }

至此，我们得到了157248条可能的明文，接下来就要考虑筛选的问题。我们首先猜测明文是汉语拼音，根据拼音的字母排列特点，我们设计了字典式的筛选方法，即将拼音中出现频率较高的双字母组合先列出，然后与明文比对，如果出现了特定字母组合则将此字符串对应的“评级”提高。处理完毕后选出“评分”最高的那条明文。

C++源代码（“评分”部分）：

intcountword_MDR(string str[],int n) {

int m=0;int index=0;int loc=0; intlen=str[0].length();

stringdic[]={\I\

\,\

\,\

\,\

\

\};

for(inti=0;i

intn_aoe=0; index=0;

for(int j=0;j

if(str[i][j]=='A'||str[i][j]=='O'||str[i][j]=='E'||str[i][j]=

='I'||str[i][j]=='U'||str[i][j]=='V')n_aoe++; for(int j=0;j<87;j++) { intpos=0;

while(str[i].find(dic[j],pos)!=string::npos) { index++;

pos=str[i].find(dic[j],pos)+1; } }

if(m

returnloc; }

以题中密文进行测试，运行结果见下图：

程序返回了有意义的明文，“微软公司即将推出新一代奔腾”，且加密矩阵为：

52 311

为检验此筛选方法的有效性，我们又以教材中的例题进行测试： QSIUYSBACPGZSAVCOVKPEWCPADKPPABUJCQLYXQEZAACPP 运行结果如下图：

同样，程序也返回了正确的明文，且加密矩阵也与教材相符。

三、实验小结

通过对Hill密码解密问题的思考与探究，我们加深了对于矩阵的理解，同时也灵活运用了我们的编程知识，并最终得到了正确的结果，同时在一步步分析问题并解决问题的路途中我们同样收获颇丰。然而实验也留下一个遗憾：类似的筛选方法难以运用于以英文作为明文的密码上。

本文来源：https://www.bwwdw.com/article/4o3t.html