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

[实验十] Hill密码的加密、解密与破译

一、实验目的

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

(1)甲方收到与之有秘密通信往来的乙方的一个密文信息，密文内容： W O W U Y S B A C P G Z S A V C O V K P E W C P A D K P P A B U J C Q L Y X Q E Z A A C P P

按照甲方与乙方的约定，他们之间的密文通信采用Hill2密码，密钥为

12二阶矩阵 A且汉语拼音的26个字母与0~25之间的整数建立一一对

03应的关系，称之为字母的表值，具体的表值见表10. 1 明文字母的表值。问这段密文的原文是什么？

表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 (2)甲方截获了一段密文： O J W P I S W A Z U X A U U I S E A B A U C

R S I P L B H A A M M L P J J O T E N H 经分析这段密文是用Hill2密码编译的，且这段密文的字母UCRS依次代表字母TACO，问能否破译这段密文的内容？

三、Hill2密码的数学模型 Ⅰ、加密与解密过程

Hill2密码是一种传统的密码体制，它的加密过程可用以下框图描述：

明文------

加密器------密文------普通信道------解密器

密码分析（敌方截获）----- 明文

在这个过程中，运用的数学手段是矩阵运算，加密过程的具体步骤如下： 1．根据明文字母的表值将明文信息用数字表示，设明文信息只需要26个拼音字母A~Z（也可能不止26个，如还有数字、标点符号等），通信双方给出这26个字母表值（见表10.1明文字母的表值）。

2．选择一个二阶可逆整数方阵A，称为Hill2密码的加密矩阵，它是这个加密体制的“密钥”（是加密的关键，仅通讯双方掌握）。问题(1)已给出了这个二阶矩阵。

3．将明文字母依次逐对分组。Hill2密码的加密矩阵为二阶矩阵，则明文字母2个一组（可以推广至Hilln密码，则每n个明文字母为一组）。若最后一组只有一个字母，则补充一个没有实际意义的哑字母，这样使每一组都由2个明文字母组成。查出每个明文字母的表值，构成一个二维列向量α。 4．A乘以α，得一新的2维列向量β=Aα，由的两个分量反查字母表值得到的两个字母即为密文字母。 以上4步即为Hill2密码的加密过程。解密过程，即为上述过程的逆过程。

12

例如，明文为YI CHU FA，A=。 03



将明文相邻2个字母分为一组：YI CH UF AA，最后一个字母A是为使最后一组的字母数为2而添加的，无实际意义。根据表值可构造相应2维列向量：

2532116，1 (*) 9，8，用矩阵A左乘上述4个向量，得到4个新的列向量：

431933318，27，24，3， 为与表值对应作模26运算得到：

1719731，24，18，3 关于模m运算，可以验证，对两个正整数a1，a2进行加，减或乘的模m运算有如下规律：

这样，这4个新的2维列向量对应的字母为 QA SX GR CC 这段文字即为明文“YI CHU FA”的密文。

要将这段密文解密，只要将上述加密过程逆转回去，即将密文按同样方式分组，查他们的表值即得：

1719731，24，18，3 但如何由该组中的向量求得(*)中的向量呢？这是在模运算意义下，如何求解方程组：Aα=β的问题。一个一般的n阶方阵可逆的充要条件为det A≠0。 在模26意义下矩阵可逆与一般的矩阵可逆有所不同。记整数集合Zm={0,1,2,…,m−1}，m为一正整数，模m可逆定义如下：

定义1 对于一个元素属于集合Zm的n阶方阵A，若存在一个元素属于Zm集合的方阵B，使得 AB=BA=E(mod m)称A为模m可逆，B为A的模m逆矩阵，记为B=A(mod m)

-1

E(mod m)的意义是，每一个元素减去m的整数倍后，可以化成单位矩阵。例如， 2752E(mod26) 2627 定义2 对Zm的一个整数a，若存在Zm的一个整数b，使得ab=1(mod m），称b为a的模m倒数或乘法逆，记作b=a−(mod m)。

可以证明，如果a与m无公共素数因子，则a有唯一的模m倒数（素数是指除了1与自身外，不能被其他非零整数整除的正整数）。例如，3−=9。利用这点，可以证明下述命题：

命题 元素属于Zm的方阵A模m可逆的充要条件是，m和det A没有公共素数因子。显然，所选加密矩阵必须符合该命题的条件。

问题（1）所选择的明文字母共26个，m=26，26的素数因子为2和13，所以Z26上的方阵A可逆的充要条件为det A（mod m）不能被2和13整除。设abA，若A满足命题的条件，可验证 cd1

1

其中(ad−bc)−是(ad-bc)(mod 26)的倒数。显然，(ad-bc)(mod 26)为Z26中的数。Z26中有模26倒数的整数及其倒数可见表10.2。 根据上述命题与表10.2，问题（1）所选加密矩阵A的行列式det A=3没有2与13这两个素数因子，所以A模26可逆。

1

这样，在模26的意义下，求解Aα=β的问题即可解决：

α=A−β(mod 26)

1

根据上面所述的加密与解密过程可知，问题（1）有解。 将译出的明文依汉语拼音写出，经组合得： MEI GUO JIANG ZAI TAI PING YANG JIN XING HAI DI HE SHI YAN 即为“美国将在太平洋进行海底核试验”。 Ⅱ、破译过程

问题（2）属于破译问题。前面的加密与解密过程类似于在二维向量空间进行线性变换与其逆变换。每个明文向量是一个Zm上的二维向量，乘以加密矩阵后，仍为Zm上的一个二维向量。由于加密矩阵A为可逆矩阵，所以，如果知道两个线性无关的二位明文向量与其对应的密文向量，就可以求出它的加密矩阵A及A. 问题（2）的密文中只出现一些字母，当然它可以是汉语拼音，或英文字母或其他语言的字母。所以可猜测秘密信息是由26个字母组成，设m=26。通常由破译部门通过大量的统计分析与语言分析确定表值。假如，所确定的表值为表10.1，已知

-1

在模26的意义下，,它有模

26倒数，所以，β1，β2在模26意义下线性无关。类似地，也可以验证det α1，α2=11(mod 26)线性无关。记P=β1，β2，C=α1，α2，则P=AC，A=PC−。这样，可以利用模26意义下的初等行变换，求得(A)，因而可以求出A。利

-1T

-11

用A即可将问题(2)的密文解出。

-1

。

利用与问题(1)同样的解密方法，可以求得，这段密文的明文为：

CL IN TO N|I S|G OI NG| TO| VI SI T|A| CO

UN TR Y|I N|M ID DL E|E AS T|T

分析这段文字，如果依竖线所划分成的词汇，则这段密文可理解为如下一段文字： “Clinton is going to visit a country in Middle East”, 最后一个字母是哑字母。这样，可以认为破译成功。 四、实验任务

1．在问题(2)中，若已知密文的前4个字母OJMP分别代表TACO，问能否将此段密文破译？

2.利用所介绍的Hill2密码体制的原理，根据给定的26个英文字母的乱序表值（见表10.3），设计与建立Hill4密码体制的加密、解密与破译框图并建立必要的计算机程序。设英文26个字母以下面的乱序表与Z26中的整数对应：

表10. 3

A 5 N 7 B 23 O 3 C 2 P 1 D 20 Q 19 E 10 R 6 F 15 S 12 G 8 T 24 H 4 U 21 I 18 V 17 J 25 W 14 K 0 X 22 L 16 Y 11 M 13 Z 9 86 (1)设A51059510，验证矩阵A能否作为Hill4密码体制的加密矩阵849611469用框图画出你的演算过程，并编写相应的计算机程序。

(2)设明文为 HILL CRYPTOGRAPHIC SYSTEM IS TRADITIONAL. 利用上面的表值与加密矩阵给此明文加密，并将得到的密文解密。画出加密与解密过程的框图并编写相应的计算机程序。

(3)已知在上述给定表值下的一段Hill4密码的密文为JCOW ZLVB DVLE QMXC， 对应的明文为 DELAY OPERATIONSU. 能否确定对应的加密矩阵？给出你的判断过程。

3.设已知一份密文为Hill2密码体系，其中出现频数最高的双字母是RH和NI，而在明文语言中，出现频数最高的双字母为TH和HE。由这些信息按表10.4给出的表值能得到什么样的加密矩阵？

表10. 4明文字母的表值

A 0 N 13 B 1 O 14 C 2 P D 3 Q E 4 R F 5 S G 6 T H 7 U I 8 V J 9 W K L M 10 11 12 X Y Z 15 16 17 18 19 20 21 22 23 24 25 4.如下的密文据表10.1以Hill2加密，密文为

VIKYNOTCLKYRJQETIRECVUZLNOJTUYDIMHRCFITQ

已获知其中相邻字母LK表示字母KE，试破译这份密文。

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

UTCQCVFOYQUVMGMGULFOLEYHDUHOPEASWXTIFBAMWT

且已知它是根据表10.1按Hill2密码体制加密的，你能否将其解密？ 五、采用方法与实验结果

1、已知， 密文 明文 密文 明文 按表可知，

OJTAWPCOO1520T1A11J101AM133C2A22P1615Odet(1,2)15101316(mod26)110(mod26)6

它没有数论倒数，所以1，2在模26意义下线性相关，无法得到模26可逆的加密矩阵A，故不能破译该密文。 2、（1）验算过程

MATLAB程序：

disp('输入密钥(矩阵)的维数'); n=input('');

disp('输入密钥(矩阵,按行输入)'); key=zeros(n,n); for j=1:n for k=1:n

key(j,k)=input(''); end end

d=round(mod(det(key),26));%求矩阵的行列式

if d==0,2,4,6,8,10,12,13,14,16,18,20,22,24%判断矩阵是否可逆

error('A不可作为加密矩阵'); sprintf('A可作为加密矩阵') end

输入矩阵A 计算det A det A是否能被2或13整除 Y N A可作为加密矩阵 A不可作为加密矩阵 实验结果：A可作为加密矩阵

（2）明文为HILL CRYPTOGRAPHIC SYSTEM IS TRADITIONAL 密文为KEGT KPNJ KYXR LAOL MZTP VYTU NHZS CEGD ZRPZ

序号 1 分组明文 H I L L C R 明文表值 4 18 16 16 2 1 密文表值 0 10 8 24 0 1 分组密文 K E G T K P 明文表值 4 18 16 16 2 1 分组明文 H I L L C R 2 Y P 3 T I G R A P H I C S Y S T E M I S T R A D I T I O N A L 11 1 24 3 8 6 5 1 4 18 2 12 11 12 24 10 13 18 12 24 6 5 20 18 24 18 3 7 5 16 7 25 0 11 22 6 16 5 3 16 13 9 24 1 17 11 24 21 7 4 9 12 2 10 8 20 9 6 1 9 N J K Y X R L A O L M Z T P V Y T U N H Z S C E G D Z R P Z 11 1 24 3 8 6 5 1 4 18 2 12 11 12 24 10 13 18 12 24 6 5 20 18 24 18 3 7 5 16 Y P T I G R A P H I C S Y S T E M I S T R A D I T I O N A L 4 5 6 7 8 9 MATLAB程序：

加密程序 %输入密钥 disp('输入密钥(矩阵)的维数'); n=input(''); disp('输入密钥(矩阵,按行输入)'); key=zeros(n,n); for j=1:n for k=1:n 解密程序 %输入密钥 disp('输入密钥(矩阵)的维数'); n=input(''); disp('输入密钥(矩阵,按行输入)'); key=zeros(n,n); for j=1:n for k=1:n key(j,k)=input(''); end end key(j,k)=input(''); end end d=round(mod(det(key),26));%求矩阵的行列式 d=round(mod(det(key),26));%求矩阵的行列式 if d==0%判断矩阵是否可逆 error('密钥矩阵不可逆，无法实现Hill密码'); end %输入明文 message=input('输入明文 \\n','s'); m=size(message); m=m(2); if mod(m,n)~=0 error('输入错误，明文长度应为矩阵维数的倍数'); end for i=1:m %输入密文 message=input('输入密文 \\n','s'); m=size(message); m=m(2); if mod(m,n)~=0 error('输入错误，密文长度应为矩阵维数的倍数'); end for i=1:m if message(i)>='A' && message(i)<='Z' message(i)=message(i)-64; %字母翻译为数字 switch message(i) if message(i)>='A' && message(i)<='Z' case 1 message(i)=message(i)-64; %字母翻译为数字 switch message(i) case 1 message(i)=5; case 2 message(i)=23; case 3 message(i)=2; case 4 message(i)=20; message(i)=5; case 2 message(i)=23; case 3 message(i)=2; case 4 message(i)=20; case 5 message(i)=10; case 6 message(i)=15; case 5 message(i)=10; case 6 message(i)=15; case 7 message(i)=8; case 8 message(i)=4; case 9 message(i)=18; case 10 message(i)=25; case 11 message(i)=26; case 12 message(i)=16; case 13 message(i)=13; case 14 message(i)=7; case 15 message(i)=3; case 16 message(i)=1; case 17 message(i)=19; case 18 message(i)=6; case 19 case 7 message(i)=8; case 8 message(i)=4; case 9 message(i)=18; case 10 message(i)=25; case 11 message(i)=26; case 12 message(i)=16; case 13 message(i)=13; case 14 message(i)=7; case 15 message(i)=3; case 16 message(i)=1; case 17 message(i)=19; case 18 message(i)=6; case 19 message(i)=12; case 20 message(i)=24; case 21 message(i)=12; case 20 message(i)=24; case 21 message(i)=21; case 22 message(i)=17; case 23 message(i)=14; case 24 message(i)=22; case 25 message(i)=11; case 26 message(i)=9; end else error('输入错误，应该输入字母'); end end %加密 i=1; while i26 A(i)=mod(A(i),26); end if A(i)==0 A(i)=26; end %数字翻译为字母 switch A(i) case 1 A(i)=16; case 2 A(i)=3; case 3 A(i)=15; case 4 A(i)=8; case 5 A(i)=1; case 6 A(i)=18; case 7 A(i)=14; case 8 A(i)=7; case 9 A(i)=26; case 10 A(i)=5; case 11 r1=19; case 15 r1=7; case 17 r1=23; case 19 r1=11; case 21; r1=5; case 23 r1=17; case 25 r1=25; otherwise disp('d倒数不存在'); end detk=det(key); invk=inv(key); k=detk*invk; key2=round(mod(r1*k,26)); i=1; while i26 B(i)=round(mod(B(i),26)); A(i)=25; case 12 A(i)=19; case 13 A(i)=13; case 14 A(i)=23; case 15 A(i)=6; case 16 A(i)=12; case 17 A(i)=22; case 18 A(i)=9; case 19 A(i)=17; case 20 A(i)=4; case 21 A(i)=21; case 22 A(i)=24; case 23 A(i)=2; case 24 A(i)=20; case 25 A(i)=10; end if B(i)==0 B(i)=26; end %数字翻译为字母 switch B(i) case 1 B(i)=16; case 2 B(i)=3; case 3 B(i)=15; case 4 B(i)=8; case 5 B(i)=1; case 6 B(i)=18; case 7 B(i)=14; case 8 B(i)=7; case 9 B(i)=26; case 10 B(i)=5; case 11 B(i)=25; case 12 case 26 A(i)=11; end A(i)=A(i)+64; end str=char(A); fprintf('密文为%s',str) B(i)=19; case 13 B(i)=13; case 14 B(i)=23; case 15 B(i)=6; case 16 B(i)=12; case 17 B(i)=22; case 18 B(i)=9; case 19 B(i)=17; case 20 B(i)=4; case 21 B(i)=21; case 22 B(i)=24; case 23 B(i)=2; case 24 B(i)=20; case 25 B(i)=10; case 26 B(i)=11; end B(i)=B(i)+64; end str2=char(B); fprintf('\\n对密文解密后明文为%s\\n',str2) （3）由给定条件知

YDRQOJDZOVAMNCELOL，VP，LY，XS

EEICUWAB密文 明文 密文 明文 密文 明文 密文 明文

J2520DC210EO13A1116L， W145AZ911YL163O2A22V171P， B2310ED206RV175A3A33L1624T， E1018IQ193OM137N4A44X2212S。 C221U在模26的意义下，

它有模26倒数，所以，β1，β2，β3，β4在模26意义下线性无关。类似地，也可以验证det(α1,α2，α3，α4)=−31887( mod 26)=15(mod 26)线性无关。记P=(β1，β2，β3，β4)，C=(α1，α2，α3，α4)，则P=AC，A=PC−。这样，可以利用模26意义下的初等行变换，求得加密矩阵A。初等变换的过程如下：

1

3．所确定的表值为表10.5，

在模26的意义下，

它有模26倒数，所以，β1，β2在模26意义下线性无关。类似地，也可以验证

det(α1，α2)=27(mod 26)=1(mod 26)线性无关。

记P=(β1，β2)，C=(α1，α2)，则P=AC，A=PC−。这样，可以利用模26意义下的初等行变换，求得加密矩阵A。初等变换的过程如下：

1

LK4.已知KE  密文 明文 按表可知，

L1211KAK115E 假设加密矩阵为 可得到同余方程组

ab11a5b12A 11c5d11 cd思路：当a从0遍历到25时，由于gcd(11,5)=1，b有唯一解。同理当c从0遍历到25时，d有唯一解。故同余方程组至多有26*26=676个解，将所有可能的A求逆，再作用到密文上，得到至多676个可能明文，再从中寻找有意义的解。

命令 %输入密文 message=input('输入密文\\n','s'); m=size(message); m=m(2); if mod(m,2)~=0 error('输入错误，密文长度应为矩阵维数的倍数'); 结果 运行结果中，有意义的解仅有以下这条： 对密文解密后明文为CANYOUMAKEANOMELETTEWITHOUTBREAKINGEGGSS,密钥为(5,7;2,3) 其中最后一个S是哑字母。这组明文组合得 CAN YOU MAKE AN OMELETTE WITHOUT BREAKING EGGS？ end for i=1:m if message(i)>='A' && message(i)<='Z' message(i)=message(i)-64; else error('输入错误，应该输入字母'); end end %满足条件的密钥矩阵 for i=0:675 key=zeros(2,2); k=round(mod(i,26)); j=round((i-k)/26); key(1,1)=j; key(2,1)=k; for l=0:25 if round(mod((11*j+5*l),26))==12 key(1,2)=l; end end for l=0:25 if round(mod((11*k+5*l),26))==11 key(2,2)=l; end end d=round(mod(det(key),26));%求矩阵的行列式 if gcd(d,26)~=1 continue end %r1为d的逆 switch d case 1 r1=1; case 3 r1=9; case 5 r1=21; case 7 r1=15; case 9 意为“你可以不打破鸡蛋而做出煎蛋吗？”在英语中对应着一条谚语： “You can't make an omelette without breaking eggs.”即,不打破鸡蛋就炒不成蛋饼；不花代价就难成大事。我们解密的时候确实也花了一些时间和精力上的代价。 r1=3; case 11 r1=19; case 15 r1=7; case 17 r1=23; case 19 r1=11; case 21; r1=5; case 23 r1=17; case 25 r1=25; end detk=det(key); invk=inv(key); k2=detk*invk; key2=round(mod(r1*k2,26)); i2=1; while i226 B(i)=round(mod(B(i),26)); end if B(i)==0 B(i)=26; end B(i)=B(i)+64; end str2=char(B); fprintf('\\n对密文解密后明文为%s,密钥为(%d,%d;%d,%d)\\n',str2,key(1,1),key(1,2),key(2,1),key(2,2)) end 5.首先找出所有可能的Hill2密码加密矩阵。

%首先穷举法

穷举法 for i=1:456975 key=zeros(2,2); j=round(mod(i,26)); k=round(mod((i-j)/26,26)); l=round(mod((i-j-26*k)/676,26)); m=round(mod((i-j-26*k-676*l)/17576,26)); key(1,1)=j; key(1,2)=k; key(2,1)=l; key(2,2)=m; d=round(mod(det(key),26));%求矩阵的行列式 if gcd(d,26)~=1 continue end fprintf('\\n可能密钥为(%d,%d;%d,%d)\\n',key(1,1),key(1,2),key(2,1),key(2,2)) end %运行结果屏幕装不下= = %改进版 %输入第一行两个密钥元素 disp('输入密钥(1,1)'); b=input(''); disp('输入密钥(1,2)'); c=input(''); %满足条件的密钥矩阵 for i=0:675 key=zeros(2,2); key(1,1)=b; key(1,2)=c; k=round(mod(i,26)); j=round((i-k)/26); key(2,1)=j; key(2,2)=k; d=round(mod(det(key),26));%求矩阵的行列式 if gcd(d,26)~=1 continue end fprintf('\\n可能密钥为(%d,%d;%d,%d)\\n',key(1,1),key(1,2),key(2,1),key(2,2)) end 依次将676种首行元素的排列输入即可得到所有可能的2维加密矩阵。

命令 翻译密文。 %输入密文 message=input('输入密文 \\n','s'); m=size(message); m=m(2); if mod(m,2)~=0 error('输入错误，密文长度应为矩阵维数的倍数'); end for i=1:m if message(i)>='A' && message(i)<='Z' message(i)=message(i)-64; end 结果 经过尝试，当首行元素输入为(5,2)时，可得结果如下： 对密文解密后明文为WEIRUANGONGSIJIJIANGTUICHUXINYIDAIBENTENGG,密钥为(5,2;3,11)。 其中末尾字母G是哑字母。拼音文意为“微软公司即将推出新一代奔腾”。 end %输入第一行两个密钥元素 disp('输入密钥(1,1)'); b=input(''); disp('输入密钥(1,2)'); c=input(''); %满足条件的密钥矩阵 for i=0:675 key=zeros(2,2); key(1,1)=b; key(1,2)=c; k=round(mod(i,26)); j=round((i-k)/26); key(2,1)=j; key(2,2)=k; d=round(mod(det(key),26));%求矩阵的行列式 if gcd(d,26)~=1 continue end %r1为d的逆 switch d case 1 r1=1; case 3 r1=9; case 5 r1=21; case 7 r1=15; case 9 r1=3; case 11 r1=19; case 15 r1=7; case 17 r1=23; case 19 r1=11; case 21; r1=5; case 23 r1=17; case 25 r1=25; end detk=det(key); invk=inv(key); k2=detk*invk; key2=round(mod(r1*k2,26)); i2=1; while i226 B(i)=round(mod(B(i),26)); end if B(i)==0 B(i)=26; end B(i)=B(i)+64; end str2=char(B); fprintf('\\n对密文解密后明文为%s,密钥为(%d,%d;%d,%d)\\n',str2,key(1,1),key(1,2),key(2,1),key(2,2)) end 六、联想与猜测

1．实验中可以看出，简单增加加密矩阵的阶数即可增大破译的难度；另一方面，矩阵阶数越大，可用来做加密矩阵的选择越多，也是加大了密码的可靠性。但是二次加密的方法（加密一次后对密文重新选择加密矩阵再次加密）对增大密码强度没有帮助。（两个模26可逆的N阶矩阵相乘后结果是一个新的模26可逆的N阶矩阵。）

2．对一些比较长的明文加密时，可考虑每一行或每一段文字使用不同的加密矩阵进行加密，这样可以防止出现密文被截获后可按照字母出现频率进行解

密的可能。一篇明文用多个加密矩阵可以充分改变字母出现的频率。