数学实验课件：Hill密码与破译

Hill密码与破译

保密通讯在军事、政治、经济斗争和竞争中的重要性是不言而喻的.

在斗争或竞争中，一方要将信息传递给己方的接收者，同时又要防止其他人(特别是敌方)知道信息的内容.

他采用的一种方式是：将原来的信息(称为明文)经过加密，变成密文之后发送出去，使敌方即使得到密文也读不懂，而合法的接收者收到密文之后却可以按照预先约定好的方法加以解密，再翻译成明文.

而敌方却要千方百计从密文破译出明文来.一方如何编制密码使之不易被破译，另一方则要找到其弱点加以破译，这就构成了密码学的主要内容.

从密码学的发展来看，密码可分为古典密码(即以字符为基本加密单元的密码)，以及现代密码(即以信息块为基本加密单元的密码).这里我们将介绍Hill密码的加密和破译原理.

本章介绍古典密码中加密和解密原理.Hill2密码加密12.1Hill2密码解密12.2CONTENTSMATLAB求解12.312.1Hill2密码加密

一般的加密过程是这样的：

明文→加密器→密文→普通信道→解密器→明文

其中的“→普通信道→解密器”这个环节容易被敌方截获并加以分析.

在这个过程中，运用的数学手段是矩阵运算，加密过程的具体步骤如下：ABCDEFGHIJKLM12345678910111213NOPQRSTUVWXYZ1415161718192021222324250表12-1明文字母的表值

1)根据明文字母的表值，将明文信息用数字表示，设明文信息只需要26个拼音大写字母A—Z(也可以不止26个，如还有小写字母、数字、标点符号等)，通信双方给出这26个字母表值(见表12-1).

2)选择一个二阶可逆整数方阵A，称为Hill2密码的加密矩阵，它是这个加密体制的“密钥”(是加密的关键，仅通信双方掌握).

3)将明文字母依次逐对分组.Hill2密码的加密矩阵为二阶矩阵，则明文字母每2个一组(可以推广至Hilln密码，则每n个明文字母为一组).若最后一组仅有一个字母，则补充一个没有实际意义的哑字母，这样使每一组都由2个明文字母组成.查出每个明文字母的表值，构成一个二维列向量α.

4)A乘以α，得一新的2维列向量β=Aα，由β的两个分量反查字母表值得到的两个字母即为密文字母.

以上4步即为Hill2密码的加密过程.解密过程，即为上述过程的逆过程.例12.1明文为WAWDZG(“我爱我的祖国”的拼音缩写)，

，求这段明文的Hill2密文.解将明文相邻字母每2个分为一组：

WAWDZG(12-1)查表12-1得到每对字母的表值，并构造2维列向量：

(12-2)将上述3个向量左乘矩阵，得到3个2维列向量：

(12-3)作模26运算(每个元素都加减26的整数倍，使其化为0～25之间的一个整数)得到：反查表12-1得到每对表值对应的字母为：

YCELNU(12-4)这就得到了密文“YCELNU”.12.2Hill2密码破译

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

(12-5)

(12-5)是前面的(12-3)经模26运算的结果.但如何由式(12-5)中的向量求得(12-2)中的向量呢？这是在模运算意义下，如何解方程组：

Aα=β

(12-6)的问题.一个一般的n阶方阵可逆的充要条件为det(A)≠0.但在模26意义下矩阵可逆与一般的矩阵可逆有所不同.记整数集合

，m为一正整数，模m可逆定义如下：定义12.1

对于一个元素属于集合zm的n阶方阵A，若存在一个元素属于集合zm的方阵B，使得称A为模m可逆，B为A的模m逆矩阵，记为B=A-1(modm).

的意义是，每一个元素减去m的整数倍后，可以化成单位矩阵.

例如：

定义12.2

对于Zm的一个整数a，若存在Zm中的中一个整数

b，使得

，则称b为

a的模倒数或乘法逆，记作

.

可以证明，如果

a与

m无公共素数因子，则

a有唯一的模

m倒数(素数是指除了1与自身外，不能被其他非零整数整除的正整数)，反之亦然.

例如，

.

命题

元素属于Zm的方阵

A模

m

可逆的充要条件是，m和det(A)没有公共素数因子，即m和det(A)互素.

显然，所选加密矩阵必须符合该命题的条件.

a1357911151719212325a-11921153197231151725表12-2模26倒数表表12-2可用下列程序求得：m=26;fora=1:m

fori=1:m

ifmod(a*i,m)==1

fprintf('TheINVERSE(mod%d)ofnumber:%dis:%d\n',m,a,i)end;end;end若

则的模26逆矩阵：例12.3甲方收到与之有秘密通信往来的乙方的一个密文信息，密文内容：WKVACPEAOCIXGWIZUROQWABALOHDKCEAFCLWWCVLEMIMCC按照甲方与乙方的约定，他们之间的密文通信采用Hill2密码，密钥为二阶矩阵问这段密文的原文是什么？

解已知密钥

的逆矩阵是

，根据解密方法，得到分组明文见表12-3.

于是，实际问题(甲)的解为：

GUDIANMIMASHIYIZIFUWEIJIBENJIAMIDANYUANDEMIMA

即为：“古典密码是以字符为基本加密单元的密码”.

12.3MATLAB求解C

=char(A)

将数组

A

转换为字符数组

从32到127的整数对应于可打印的ASCII字符.ASCII字符表中65到90的整数代表大写字母A到Z（见表12-3）.序号分组密文密文表值明文表值分组明文1WK2311721GU2VA22149DI3CP316114AN4E513M

A19I5O1513M

C31A6I919S

X248H7G79I

W2325Y8I99I

Z00Z9U219I

R186F10O1521U

Q1723W11W235E

A19I表12-3分组明文12BA210J

19I13L122B

O155E14H814N

D410J15K119I

C31A16E513M

A19I17F64D

C31A18L1214N

W2325Y19W2321U

C31A20V2214N

L124D21E55E

M1313M22I99I

M1313M23C31A

C31A例12.3字符函数char举例.>>A=[776584766566];>>C=char(A)C='MATLAB'>>whosCNameSizeBytesClassAttributesC1x612char>>a='Hello,World';>>double(a)ans=列1至9721011081081114487111114列10至11108100例12.4加密过程可以通过MATLAB编程直接得到密文，程序如下：m=26;enmat=[12;03];ZERO=64;c=[];e1=[];astr=input('输入要加密的明文文字(全部为大写字母)：')whileany(double(astr)>90|double(astr)<65)astr=input('输入错误，应该全部为大写字母：')enda1=double(astr);lh=length(a1);ifmod(length(a1),2)==1a1=[a1,a1(length(a1))];enda1=a1-ZERO;fori=1:length(a1)ifa1(i)==26a1(i)=0;endendc=reshape(a1,2,length(a1)/2);d1=mod(enmat*c,m);e1=reshape(d1,length(a1),1);e1=e1';e1=e1+ZERO;fori=1:length(e1)ife1(i)==64e1(i)=90;endende1=e1(1:lh);char(e1)%将e1的每个数值转换为字符例12.5

解密过程可以通过MATLAB编程直接得到原文，程序如下：m=26;enmat=[1,2;0,3];demat=[1,8;0,9];ZERO=64;c=[];e1=[];astr=input('输入要解密的密文文字（全部为大写字母）：')while

any(double(astr)>90|double(astr)<65)

astr=input('输入错误，全部应该为大写字母：')enda1=double(astr);lh=length(a1);if

mod(length(a1),2)==1

a