大票密码学

2021年1月20日发(作者：白鹭属)
密码学

(
第
二
讲
)

古典密码

古典密码

张焕国

武汉大学计算机学院

目

录

1
,
密码学的基本概念

密码学的基本概念

古典密码
2
,
古典

密码
3
,
数据加密标准
(DES)
,
数据加密标准
(DES
)
4
,
高级数据加密标准
(AES)
高级

数据加密标准
(AES)
5
,
中国商用密码
(SMS4)
,
中国商用密码
(SMS4)
6 ,
分组密码的应用技术
7 ,
序列密码
8 ,
习题课
:
复习对称密码
9 ,
公开密钥密码
(1) ,
公开密钥密码
(1

目

录

10,
公开密钥密码
(2 10 ,
公开密钥密码
(2) 11,
数字签名
(1 11,
数
字签名
(1) 12,
数字签名
(2 12,
数字签名
(2) 13, HASH
函数
13 , HASH
函数
14, 14 ,
认证
15, 15 ,
密钥管理
16, PKI
技术
16 , PKI
技术

17,
习题课
:
复习公钥密码
17 ,
习题课
:
复习公钥密码
18,
总复习
/ 18 ,
总复习
/
检查
:
综合实验

一
,
古典密码

一
,
古典密码

虽然用近代密码学的观点来看
,
许多

古典密码是很不安全的
,
或者说是
极易

破译的
.
但是我们不能忘记古典密码在

破译的
.
但是我们不能忘
记古典密码在

历史上发挥的巨大作用
.
历史上发挥的巨大作用
.
另外
,
编制古典密码的基本方法对于

另外
,
编制古典密码的基本方法对于

编
制近代密码仍然有效
.
编制近代密码仍然有效

一
,
古典密码

一
,
古典密码

C. D. Shannon:

采用混淆
,
扩散和乘积的方法来设计密码

混淆
:
使密文和明文
,
密钥之
间的关系复杂化

扩散
:
将每一位明文和密钥的影响扩大到尽可

能多的
密文位中
.
乘积和迭代
:
多种加密方法混合使用

对一个加密函数多次
迭代

古典密码编码方法
:
置换
,
代替
,
加法

一
,
古典密码

一
,
古典密码

1,
置换密码

把明文中的字母重新排列
,
字母本身不变
,
但其位置改变了
,
这样编成
的密码称为置

换密码
.

最简单的置换密码是把明文中的字母顺序倒过来
,
最简单的置换密码
是把明文中的字母顺序倒过来
,
然后截成固定长度的
字母组
作为密文
.
然后截成固定长度的
字母组
作为密文
.
明文
:
明晨
5
点发动反攻
.
明文
:
明晨
5
点发动反攻
. MING CHEN WU DIAN FA DONG FAN GONG
密文
:GNOGN
密文
:GNOGN AFGNO DAFNA IDUWN EHCGN IM

一
,
古典密码

一
,
古典密码

把明文按某一顺序排成一个矩阵
,
然后按另一顺

序选出矩阵中的字母
以形成密文
,
最后截成固定长

度的
字母组
作为密文
.

例如
:
明文
:MING
明文
:MING CHEN WU DIAN FA DONG FAN GONG
矩
阵
:MINGCH
矩阵
:MINGCH
选出顺序
:
按列
ENWUDI
ANFADO
改变矩阵大小
和取出序列
NGFANG
可得到不同的密码
ONG
密文
:MEANO
密文
:MEANO
INNGN NWFFG GUAA CDDN HIOG

一
,
古典密码

一
,
古典密码

理论上: ① , 置换密码的加密钥是置换矩阵
p ,
解密钥是置换矩阵

p-1 .

P= 1 2 3 a1 a2 a3 … … n an

② , 置换密码经不起已知明文攻击
.

一
,
古典密码

一
,
古典密码

2,
代替密码

首先构造一个或多个密文字母表
,
首先构造一个或多个密文字母表
,
然后用

密文字母表中的字母或
字母组
来代替明文字母
< br>或
字母组
,
各字
母或
字母组
的相对位置不变
,
或
字母组
,
各字母或
字母组
的相对位置不
变< br> ,
但其本身改变了
.
但其本身改变了
.
这样编成的密码称为代替密

码
.

①单表代替密码

②多表代替密码

③多名代替密码

一
,
古典密码

一
,
古典密码

⑴ . 单表代替密码

只使用一个密文字母表
,
只使用一个密文字母表
,
并且用密文字母表中
的一

个字母来代替明文字母表中的一个字母
.
个字母来代替明文字母
表中的一个字母
.
明文字母表
:A = { a 0 , a 1 , ... , a n - 1 } ...,
密文字母表
:B
密文字母表
:B = { b 0 , b 1 , ... , b n - 1 } ...,
定义一个由
A
定义一个由
A
到
B
的映射: f:A→B 的映射
:f f(a i )=
b i
设明文
:M
设明文
: M = ( m 0 , m 1 , ... , m n - 1 ) , ...,
则密文
:
C
=(f(m0
),f(m1
),
...,f(mn-1
))
.
则密文
:C
),...,f(m
)).
简单代替密码的密钥就是映射函数
f
简单代替密码的密钥就是映射函
数
f
或密文字母表
B.

一
,
古典密码

一
,
古典密码

⑴ 单表代替密码

①,加法密码
A
和
B
是有
n
个字母的字母表
.
定义一个由
A
到
B
的映
射: f:A→B 定义一个由
A
的映射:f:A→B

f(a i )= b i =a j j=i+k mod n
加法密码是用明文字母在字母表中后
面第
k
个字母

来代替
. K=3
时是著名的凯撒密码
.

一
,
古典密码

一
,
古典密码

⑴ 单表代替密码

②,乘法密码
A
和
B
是有
n
个字母的字母表
.
定义一个由
A
到
B
的映
射: f:A→B 定义一个由
A
的映射:f:A→B

f(a i )= b i = a j j=ik mod n
其中
,( n,k)=1.
其中
, ( n,k)=1.
注意
:
只有
(n,k)=1 ,
才能正确解密
.
只有
(n,k)=1,

一
,
古典密码

一
,
古典密码

⑴ 单表代替密码

③ 密钥词
组代替密码
:

随机选一个词语
,
去掉其中的重复字母
,
写到矩阵的第一行
,
从明文字
母表中去掉这第

一行的字母
,
其余字母顺序写入矩阵
.
然后按

列取出
字母构成密文字母表
.

一
,
古典密码

一
,
古典密码

举例
:

密钥
: HONG YE
选出顺序
:
按列

矩阵
: HONGYE
选出顺序
:
按列
ABCDFI
JKLMPQ
改变密钥
,
矩阵大小
RSTUVW
和取出序列
,
得到不同的
XZ
密文
字母表
.
密文字母表
: B={ HAJRXOBKSZNCLTGDMUYFPVEIQW }

一
,
古典密码

一
,
古典密码

⑵,多表代替密码

单表代替密码的安全性不高
,
一个原因是

一个明文字母只由一个密文字母代替
.

构造多个密文字母表
,
在密钥的控制下用相应密文字母表中的一个字

母来代替明文字母表中的一个字母
.
一个明文

母来代替明文字母表中
的一个字母
.
一个明文

字母有多种代替
.

Vigenere
密码
:
著名的多表代替密码

密码
:
著名的多表代替密码

一
,
古典密码

一
,
古典密码

Vigenre
方阵
Vigenre
方阵

A B
密
C
文
H
明文字母
AB C D E F G H I J K LM N O P Q R S TU V
WX YZ

AB C D E F G H I J K LM N O PQ R S T UV WX YZ BCDE FG HIJ KLMNO
PQ RSTUVWXYZA CDE FG HIJ KLMNO PQ RSTUVWXYZAB H I J K LM N O P
Q R S TU V WXY ZAB C D EF G

字
X X YZAB C D E F G H I J K LM N O P Q R S TU V W
母
Y YZAB
CDEFGHIJKLMNOPQRSTUVW X Z ZAB C D E F G H I J K LM N O PQ R S
TU VWX Y

一
,
古典密码

一
,
古典密码

Vigenre
密码的代替规则是用明文字母在
Vigenre
方阵中的列和密钥
字母在
Vigenre
方阵中的行的交

点处的字母来代替该明文字母
.
例如
,
点处的字母来代替该明文字母
.
例如
,
设明文字

母为
P,
密钥字母为
Y ,
则用字母
N
来代替明文字

母
P.

明文
:
明文
:
MING
CHEN
WU
DIAN
FA
DONG
FAN
GONG
密钥
:
密钥
:
XING
CHUI PING YE KUO YUE YONG DA JIANG LIU
密文
:
密文
: JQAME OYVLC
QOYRP URMHK DOAMR NP

解密就是利用
Vigenre
方阵进行反代替
.
方阵进行反代替
.

一
,
古典密码

一
,
古典密码

3,
代数密码
:

① Vernam
密码
Vernam
密码

明文
,
密文
,
密钥都表示为
二
进制位
:

M=m1,m2,…
,mn
K
=k1,k2,…
,kn
C
=c1,c2,…
,cn
② 加密

:
c1=
mi⊕
ki ,i=1,2,… ,n 解密

: m1= ci⊕ ki ,i=1,2,… ,n ③ 因为加解密
算法是模
2
加
,
所以称为代数密码
.
因为加解密算法是模
2 ④ 对合运
算
:f=f-1,
模
2
加运算是对合运算
.
对合运算
:

密码算法是对和运算
,
则加密算法
=
解密算法
,
工程实

现工作量减半
.

⑤
Vernam
密码经不起已知明文攻击
.
Vernam
密码经不起已知明文攻击
.

一
,
古典密码

一
,
古典密码

⑥ 如果密钥序列有重复
,
则
Vernam
密码是不安全

如果密钥序列有重复
,
则
Vernam
密码是不安全

的
.
一种极端情况
:
一次一密

⑦ 一种极端情
况
:
一次一密

密钥是随机序列
.
密钥至少和明文一样长
.
一个密钥只
用一次. ⑧ 一次一密是绝对不可破译的
,
但它是不实用的. ⑨ 一次一
密给密码设计指出一个方向
,
人们用序

列密码逼近一次一密
.

二
,
古典密码的穷举分析

1 ,
单表代替密码分析

① 加法密码

因为
f(ai )= b i =aj
因为
f(a
j=i+k mod n

所以
k=1,2,... ,n - 1,
共
n- 1
种可能
,
密钥空

所以
k=1,2, ,n- 1,
共

间太小
.
以英文为例
,
只有
25
种密钥
.
间太小
.
以英文为例
,
只有
25
种
密钥
.
经不起穷举攻击
.

二
,
古典密码的穷举分析

1 ,
单表代替密码分析

② 乘法密码

因为
f(ai )= b i =aj
因为
f(a
j=ik
mod
n
,
且
(
k,n)=1
.
n,
且
(k,n)=1.
所以
k
共有
φ
(n)
种可能
,
密钥空间更小
.
所以
k
对于英文字母表
,n=26,
对于英文字母表
,n=26 ,
k=1,3,5,7,9,11,15,17,19,21,23,25
取掉
1
,
共
11
种
,
比加法密码更弱
.
取掉
1 ,
共
11
种
,
比加法密码更弱
.
经不起穷举攻击
.

二
,
古典密码的穷举分析

1 ,
单表代替密码分析

③ 密钥词语代替密码

因为

密钥词语的选取是
随机的
,
所以密文字母

因为密钥词语的选取是随机的
,
所以密文字母

表完全可能穷尽明文字母表的全排列
.

以英文字母表为例
,n=26,
所以共有
26!
种可

以英文字母表为例
,n=26,
所以共有
26 !
种可

能的密文字母表. 26! ≈4× 26 ! ≈4 ×1026 用
计算机也不可能穷举攻击
.
注意
:
穷举不是攻击密钥词语代替密码的
唯一

注意
:
穷举不是攻击密钥词语代替密码的唯一

方法
.

三
,
古典密码的统计分析

2
,
密钥词组单表代替密码的统计分析

任何自然语言都有自己的统计规
律
.
如果

密文中保留了明文的统计特征
,
就可用

如果密文中保留了明
文的统计特征
,
就可用

统计方法攻击密码
.
由于单表代替密码只使用
一个密文字母表
,
一个明文字母固定的用一个密文字母来代替
,
一个
明文字母固定的用一个密文字母来代替
,
所以密文的统计规律与明文
相同
.
所以

密文的统计规律与明文相同
.

因此
,
单表代替密码可用统计分析

攻破
.

三
,
古典密码的统计分析

英语的统计规律

每个单字母出现的频率稳定
.
最高频率字母
E
次高
频率字母
T A O I N S H R
中高频率字母
D L
低频率字母
C U M W F
G Y P B
最低频率字母
V K J X Q Z

三
,
古典密码的统计分析

英语的统计规律

频率最高的双
字母组
: TH HE IN ER AN RE ED ON ES