宁德市去长乐机场: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.Hill2 密码的两个实际问题:
实际问题(甲):甲方收到与之有秘密通信往来的乙方的一个密文信息,密文内容:
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
按照甲方与乙方的约定,他们之间的密文通信采用 Hill2 密码,密钥为二阶矩阵
表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
经分析这段密文是用 Hill2 密码编译的,且这段密文的字母 U C R S 依次代表字母T A C O,问能否破译这段密文的内容?
2. Hill2 密码的数学模型
一般的加密过程是这样的:
明文
其中的 “
在这个过程中,运用的数学手段是矩阵运算,加密过程的具体步骤如下:
1) 根据明文字母的表值,将明文信息用数字表示,设明文信息只需要 26 个拼音大写字母 A—Z(也可以不止 26 个,如还有小写字母、数字、标点符号等),通信双方给出这 26 个字母表值(见表 1).
2) 选择一个二阶可逆整数方阵
3) 将明文字母依次逐对分组.Hill2 密码的加密矩阵为二阶矩阵,则明文字母每 2 个一组(可以推广至 Hilln 密码,则每 n 个明文字母为一组).若最后一组仅有一个字母,则补充一个没有实际意义的哑字母,这样使每一组都由 2 个明文字母组成.查出每个明文字母的表值,构成一个二维列向 量
4)
以上 4 步即为 Hill2 密码的加密过程.
解密过程,即为上述过程的逆过程.
例:明文为 HDSDSXX (“华东师大数学系”的拼音缩写),
解:将明文相邻文母每 2 个分为一组:
HD SD SX XX (1)
最后一个字母 X 为哑字母,无实际意义.查表1得到每对字母的表值,并构造 2 维列向量:
将上述 4 个向量左乘矩阵
作模 26 运算(每个元素都加减 26 的整数倍,使其化为 0~25 之间的一个整数)得到:
反查表 1 得到每对表值对应的字母为:
PL AL OT TT (4)
这就得到了“HDSDSXX” (“华东师大数学系”的拼音缩写) 的密文.
要将这段密文解密,只要将上述加密过程逆转回去,即将密文按同样方式分组,查它们的表值即得:
(5) 是前面的 (3) 经模26运算的结果.但如何由 (5) 中的向量求得(2) 中的向量呢? 这是在模运算意义下,如何解方程组:
的问题.一个一般的 n 阶方阵可逆的充要条件为
定义1:对于一个元素属于集合
称
定义2:对
可以证明,如果
命题:元素属于
显然,所选加密矩阵必须符合该命题的条件.
问题(甲)所选择的明文字母共 26 个,
其中
表2 模 26 倒数表
1
3
5
7
9
11
15
17
19
21
23
25
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,
在模 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. 实际问题 (甲) 的修正:按照甲方与乙方的约定,他们之间的密文通信采用 Hill2 密码,密钥为二阶矩阵
2. 若将你姓名的拼音作为明文,例如:赵本山 (ZHAO BEN SHAN,含空格),密钥等参见练习 1,求其在模 27 意义下的Hill2密文.
3. 若将你姓名的拼音作为Hill2密文,例如:赵本山 (ZHAO BEN SHAN,含空格),密钥等参见练习 1,求其在模 27 意义下的明文.
4. 利用所介绍的Hill2密码体制的原理,根据给定的 26 个英文字母的乱序表值(见表4),设计与建立 Hill4密码体制的加密、解密与破译框图并建立必要的计算机程序.设英文 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) 设
(2) 设明文为
HILL CRYPTOGRAPHIC SYSTEM IS TRADJITIONAL.
利用上面的表值与加密矩阵给此明文加密,并将得到的密文解密.画出加密与解密过程的框图并编写相应的计算机程序.
5. 设已知一份密文为 Hill2 密码体系,其中出现频数最高的双字母是 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. 找出元素属于
UTCQCVFOYQUVMGMGULFOLEYHDUHOPEASWXTIFBAMWT
且已知它是根据表 1 按 Hill2 密码体制加密的,你能否将其解密?