matlab 实验六　古典密码与破译

实验六　古典密码与破译

 一、问题背景和实验目的
二、相关函数（命令）及简介
三、实验内容

四、自己动手

　

一、问题背景和实验目的

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

在斗争或竞争中，一方要将信息传递给己方的接收者，同时又要防止其他人 (特别是敌方) 知道信息的内容．他采用的一种方式是：将原来的信息(称为 明文) 经过加密，变成密文之后发送出去，使敌方即使得到密文也读不懂，而合法的接收者收到密文之后却可以按照预先约定好的方法加以解密，再翻译成明文．而敌方却要千方百计从密文破译出明文来．一方如何编制密码使之不易被破译，另一方则要找到其弱点加以破译，这就构成了密码学的主要内容．

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

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

 

二、相关函数（命令）及简介

1．input('一些提示语句')：由键盘输入表达式．

注：a=input('')，对不同的变量类型 a，输入时要注意相应的格式，若 a 为字符则要加' '，若a 为矩阵则要加[ ]等．

2．length(a)：给出数组 a 的长度．

3．mod(m, n)：求 m 被 n 整除后的余数．

4．det(a)：求矩阵 a 的行列式．

5．inv(a)：求矩阵 a 的逆矩阵．

6．reshape(a, m, n)：将矩阵 a 重排成 m*n 的矩阵．

例如：

a=1:10; b=reshape(a, 2, 5)

b= 1   3   5   7   9

2   4   6   8  10

7．double('字符')：将'字符'内的字符转化成 ASCII 码．

8．char(a)：将 a 的每个数值转化为字符．

例如：

c=double('love')

c = 108  111  118  101

char(c)

ans = love

9．[m, n]=size(a)：求矩阵a的维数.

10．gcd(m, n)：求m, n的最大公约数．

11．fprintf(fid, format, A, ...)：以指定格式将数据写入文件，若无参数fid，则输出到屏幕．

 

三、实验内容

1.Hill₂ 密码的两个实际问题：

实际问题(甲)：甲方收到与之有秘密通信往来的乙方的一个密文信息，密文内容：

W K V A C P E A O C I X G W I Z U R O Q W A B A L O H D K C E A F C L W W C V L E M I M C C

按照甲方与乙方的约定，他们之间的密文通信采用 Hill₂ 密码，密钥为二阶矩阵且汉语拼音的 26 个字母与 0～25 之间的整数建立一一对应的关系，称之为字母的表值，具体的表值见表 1．问这段密文的原文是什么?

表1明文字母的表值

A	B	C	D	E	F	G	H	I	J	K	L	M
1	2	3	4	5	6	7	8	9	10	11	12	13
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
14	15	16	17	18	19	20	21	22	23	24	25	0

 

实际问题(乙)：甲方截获了一段密文：

M O F A X J E A B A U C R S X J L U Y H Q A T C Z H W B C S C P

经分析这段密文是用 Hill₂ 密码编译的，且这段密文的字母 U C R S 依次代表字母T A C O，问能否破译这段密文的内容?

2. Hill₂ 密码的数学模型

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

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

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

在这个过程中，运用的数学手段是矩阵运算，加密过程的具体步骤如下：

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

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

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

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

以上 4 步即为 Hill₂ 密码的加密过程．

解密过程，即为上述过程的逆过程．

例：明文为 HDSDSXX (“华东师大数学系”的拼音缩写)，，求这段明文的Hill₂密文．

解：将明文相邻文母每 2 个分为一组：

HD  SD  SX  XX                         (1)

最后一个字母 X 为哑字母，无实际意义．查表1得到每对字母的表值，并构造 2 维列向量：

                         (2)

将上述 4 个向量左乘矩阵，得到 4 个 2 维列向量：

                        (3)

作模 26 运算(每个元素都加减 26 的整数倍，使其化为 0～25 之间的一个整数)得到：

反查表 1 得到每对表值对应的字母为：

PL  AL  OT  TT                          (4)

这就得到了“HDSDSXX” (“华东师大数学系”的拼音缩写) 的密文．

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

                        (5)

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

                               (6)

的问题．一个一般的 n 阶方阵可逆的充要条件为 ．但在模 26 意义下矩阵可逆与一般的矩阵可逆有所不同．记整数集合，m 为一正整数，模 m 可逆定义如下：

定义1：对于一个元素属于集合  的 n 阶方阵，若存在一个元素属于集合的方阵，使得

称 为模 m 可逆，为的模 m 逆矩阵，记为．

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

定义2：对的一个整数，若存在的一个整数，使得，称为的模倒数或乘法逆，记作．

可以证明，如果与无公共素数因子，则有唯一的模倒数(素数是指除了 1 与自身外，不能被其他非零整数整除的正整数)，反之亦然．例如，. 利用这点，可以证明下述命题：

命题：元素属于的方阵模可逆的充要条件是，和没有公共素数因子，即和 互素．

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

问题(甲)所选择的明文字母共 26 个，，26 的素数因子为 2 和 13，所以上的方阵 可逆的充要条件为不能被 2 和 13 整除．设，若满足命题的条件，不难验证：

其中是的倒数．显然，是中的数．

中有模 26 倒数的整数及其倒数可见表 2．

表2 模 26 倒数表

	1	3	5	7	9	11	15	17	19	21	23	25
-1	1	9	21	15	3	19	7	23	11	5	17	25

表2 可用下列程序求得：

m=26;

for a=1:m

 for i=1:m

if mod(a*i, m)==1

fprintf('The INVERSE (mod %d) of number: %d is: %d\n', m, a, i)

end; end; end

 

注意：附录1给出的 Matlab 程序，可以用于判断一个2 阶方阵在模 26 意义下是否可逆，并在可逆的前提下求出其逆矩阵．

读者可结合下列演算的实例加以验证．

利用表 1 可以演算出的如下：

于是，可以简单地计算得到：

再进行模 26 运算后得到：

即得到明文：HD  SD  SX  X(X)．

用 Matlab 编程进行加密算法的程序参见附录 2．而用 Matlab 编写的相应的解密算法程序参见附录 3．

 

表 3 问题 (甲) 的解

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

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

GU DIAN MI MA SHI YI ZI FU WEI JI BEN JIA MI DAN YUAN DE MI MA

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

以下来解实际问题 (乙)．

实际问题 (乙) 属于破译问题．前面的加密与解密过程类似于在二维向量空间进行线性变换与其逆变换，每个明文向量是一个上的二维向量，乘以加密矩阵后，仍为上的一个二维向量．由于加密矩阵为可逆矩阵，所以，如果知道了两个线性无关的二维明文向量与其对应的密文向量，就可以求出它的加密矩阵及．

问题 (乙) 的密文中只出现一些字母，当然它可以是汉语拼音，或英文字母或其他语言的字母．所以可猜测秘密信息是由 26 个字母组成，设．通常由破译部门通过大量的统计分析与语言分析确定表值．假如，所确定的表值为表 1，已知

注：前的为密文，后的为明文．

按照表1，

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

记，则，记，其中．

以下在模 26 意义下对进行一系列初等行变换将变成单位矩阵，则相应的将变成，即．

经过以上的一系列推导，可得

相应的 Matlab 程序参见附录 4.

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

| HE | WI LL | VI SI T| A | CO LL EG E | T HI S | A FT ER NO ON |

分析这段文字，如果依竖线所划分成的词汇，则这段密文可理解为如下一段文字：

''He will visit a college this afternoon''．

这样，可以认为破译成功．

 

四、自己动手

1. 实际问题 (甲) 的修正：按照甲方与乙方的约定，他们之间的密文通信采用 Hill₂ 密码，密钥为二阶矩阵且汉语拼音的 26 个字母以及空格(字母 A~Z 的表值为 1~26，空格的表值为 0）与 0～26 之间的整数建立一一对应的关系，称之为字母的表值，试修正表 1、表 2 以及附录中的程序，以给出模 27 意义下矩阵可逆的判别方法和具体求法．

2. 若将你姓名的拼音作为明文，例如：赵本山 (ZHAO BEN SHAN，含空格)，密钥等参见练习 1，求其在模 27 意义下的Hill₂密文．

3. 若将你姓名的拼音作为Hill₂密文，例如：赵本山 (ZHAO BEN SHAN，含空格)，密钥等参见练习 1，求其在模 27 意义下的明文．

4. 利用所介绍的Hill₂密码体制的原理，根据给定的 26 个英文字母的乱序表值(见表4)，设计与建立 Hill₄密码体制的加密、解密与破译框图并建立必要的计算机程序．设英文 26 个字母以下面的乱序表与中的整数对应：

表4

A	B	C	D	E	F	G	H	I	J	K	L	M
5	23	2	20	10	15	8	4	18	25	0	16	13
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
7	3	1	19	6	12	24	21	17	14	22	11	9

(1) 设，验证矩阵能否作为 Hill₄密码体制的加密矩阵．用框图画出你的验算过程，并编写相应的计算机程序．

 

(2) 设明文为

HILL CRYPTOGRAPHIC SYSTEM IS TRADJITIONAL．

利用上面的表值与加密矩阵给此明文加密，并将得到的密文解密．画出加密与解密过程的框图并编写相应的计算机程序．

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

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

6. 找出元素属于的所有可能的 Hill₂ 密码加密矩阵．若截获了如下一段密文

UTCQCVFOYQUVMGMGULFOLEYHDUHOPEASWXTIFBAMWT

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