（高职）西华大学：密码学：2

2012-3-19 1
第一章 概论
一、信息安全与密码技术
二、密码系统模型和密码体制
三、几种简单的密码体制
四、初等密码分析
五、密码学的信息论基础
六、密码学的复杂性理论基础
2012-3-19 2
一,信息安全与密码技术
2012-3-19 3
信息安全面临的威胁
? 政府宏观调控决策
? 商业经济信息
? 银行资金转账
? 股票证券
? 经济医疗记录
? 科研数据等
信息安全有广泛的应用
2012-3-19 4
信息安全面临的威胁
? 可能的攻击者,
– 黑客
– 竞争对手
– 间谍
– 媒体
– 政府机构
2012-3-19 5
信息安全面临的威胁
信息安全所面临的威胁来自很多
方面，并且随着时间的变化而变化。
这些威胁可以宏观地分为,
? 自然威胁
– 自然灾害
– 恶劣的场地环境
– 电磁辐射和电磁干扰
– 网络设备自然老化等。
2012-3-19 6
? 人为威胁 (对信息的人为攻击。这些攻击手段
都是通过寻找系统的弱点，以便达到破坏、
欺骗、窃取数据等目的，造成经济上和政治
上不可估量的损失。 )
2012-3-19 7
被动攻击
消息内容
获取
监听
(保密性）
业务流量
分析
2012-3-19 8
主动攻击
伪造
(真实性 )
中断
(可用性 )
篡改
(完整性 )
2012-3-19 9
1.被动攻击
被动攻击即窃听 (Interception),
是对系统的保密性进行攻击，如搭线窃
听、对文件或程序的非法拷贝等，以获
取他人的信息。被动攻击因不对消息做
任何修改，因而是难以检测的，所以抗
击这种攻击的重点在于预防而非检测 。
2012-3-19 10
被动攻击 又分为两类，一类是获取消息的
内容，很容易理解；第二类是进行业务
流分析，假如我们通过某种手段，比如
加密，使得敌手从截获的消息无法得到
消息的真实内容，然而敌手却有可能获
得消息的格式、确定通信双方的位臵和
身份以及通信的次数和消息的长度，这
些信息可能对通信双方来说是敏感的。
2012-3-19 11
主动攻击 又可分为以下三个子类 (如图
1.2所示 ),
中断（ Interruption),是对系统的可
用性进行攻击，如破坏计算机硬件、
网络或文件管理系统。
2012-3-19 12
篡改 (Modification),是对系统的完整性
进行攻击，如修改数据文件中的数据、
替换某一程序使其执行不同的功能、修
改网络中传送的消息内容等。
伪造 (Fabication),是对系统的真实性进
行攻击。如在网络中插入伪造的消息或
在文件中插入伪造的记录。
2012-3-19 13
中断 （ Interruption）
Alice
Bob
图 1.2
2012-3-19 14
窃听 (Interception)
Eve
Bob Alice
2012-3-19 15
篡改 (Modification)
Alice Bob
Eve
2012-3-19 16
Bob Alice
Eve
伪造 (Fabication)
2012-3-19 17
信息安全的要求
保密性 Confidentiality
完整性 Integrity
不可否认性 Non-reputiation
可鉴别性 Authentication
可用性 Availability
2012-3-19 18
信息安全的要求
2012-3-19 19
图 1.3 信息安全的基本模型
信息系统安全模型和密码技术
可信赖的第三方
(如仲裁者、秘密信息分布者
用户 用户
攻击者
消息
秘密
信息
消息
秘密
信息
信道
2012-3-19 20
安全的网络通信必须考虑以下几个方面,
? 加密算法。
? 用于加密算法的秘密信息。
? 秘密信息的分布和共享。
? 使用加密算法和秘密信息以获得安全服
务所需的协议。
2012-3-19 21
信息安全可分为,
? 系统安全 （ 包括操作系统安全, 数据库系
统安全等 ）
? 数据安全 （ 包括数据的安全存储, 安全传
输 ）
? 内容安全 （ 包括病毒的防护, 不良内容的
过滤等 ）
2012-3-19 22
这 3个层次, 是一个综合, 交叉的学科领
域, 要利用数学, 电子, 信息, 通信,
计算机等诸多学科的长期知识积累和最
新发展成果 。
信息安全研究的内容很多, 它涉及安全体
系结构, 安全协议, 密码理论, 信息分
析, 安全监控, 应急处理等, 其中密码
技术是保障数据安全的关键技术 。
2012-3-19 23
?密码学是信息安全的核心部分
?密码学就是研究与信息安全相关的
方面如机密性、完整性、实体鉴别、
抗否认等的综合技术。
?密码并不是提供安全的单一的手段，
而是一组技术 。
2012-3-19 24
二、密码系统模型和密码体制
2012-3-19 25
一、密码学的基本概念
密码学 (Cryptology)：研究信息系统
安全保密的科学。它包含两个分支,
? 密码编码学 (Cryptography),对信
息进行编码实现隐蔽信息的一门学
问
? 密码分析学 (Cryptanalytics)，研
究分析破译密码的学问。
2012-3-19 26
?明文 (消息 )(Plaintext), 被隐蔽消息。
?密文 (Ciphertext)或密报 (Cryptogram)：
明文经密码变换成的一种隐蔽形式。
?加密 (Encryption),将明文变换为密文的
过程。
一、密码学的基本概念
2012-3-19 27
? 解密 (Decryption),加密的逆过程，即
由密文恢复出原明文的过程。
? 加密员或密码员 (Cryptographer),对
明文进行加密操作的人员。
一、密码学的基本概念
2012-3-19 28
? 加密算法 (Encryption algorithm),密码
员对明文进行加密时所采用的一组规则。
?接收者 (Receiver),传送消息的预定对象。
?解密算法,接收者对密文进行解密时所采用
的一组规则。
一、密码学的基本概念
2012-3-19 29
? 密钥 (Key),控制加密和解密算法操作
的数据处理，分别称作加密密钥和解密
密钥。
? 截收者 (Eavesdropper),在信息传输和
处理系统中的非受权者，通过搭线窃听
、电磁窃听、声音窃听等来窃取机密信
息。
一、密码学的基本概念
2012-3-19 30
密码分析 (Cryptanalysis),截收者试图通过
分析从截获的密文推断出原来的明文或密钥
。
密码分析员 (Cryptanalyst),从事密码分析
的人。
被动攻击 (Passive attack),对一个保密系
统采取截获密文进行分析的攻击。
一、密码学的基本概念
2012-3-19 31
主动攻击 (Active attack),非法入
侵者 (Tamper),攻击者 (Attcker)
或黑客 (Hacker)主动向系统窜扰，
采用删除、增添、重放、伪造等窜
改手段向系统注入假消息，达到利
已害人的目的。
一、密码学的基本概念
2012-3-19 32
图 1.4
密码系统模型
非法接
入者 密码分析员 (窃听者 )
信源
M 接收者
密钥源
K1
加密器
c=EK1(m)
密钥源
K2
解密器
m=EK2(c)
密钥信道
m m
c
c’
搭线信道
(主动攻击 )
K1
K2
搭线信道
(被动攻击 ) m’
2012-3-19 33
?明文空间
?密文空间
?密码方案
?密钥空间
四个部分组成
一个密码系统由,
2012-3-19 34
密码体制
密码体制有两类,
单钥体制（ One-key system)加密密钥
和解密密钥相同
双钥体制（ Two-key system)加密密钥
和解密密钥不同
2012-3-19 35
单钥体制的系统的保密性：主要取决于密钥
的保密性（与算法的保密性无关）
单钥体制研究的主要课题,
? 密钥的产生 (Key generation)。
? 密钥的管理 (Key management)。
单钥体制
2012-3-19 36
单钥体制
分类,
? 序列密码 (Stream cipher)按字符逐位
加密。
? 分组密码 (Block cipher)按分组加密。
单钥体制不仅可用于数据加密，也可用于
消息的认证。
2012-3-19 37
公钥体制
双钥体制（ Diffie 和 Hellman1976年引入）
每个用户都有一对选定的密钥（公钥,K1，
私钥 K2） K1是可以公开的，可以像电话号
码一样进行注册公布； K2则是秘密的。
2012-3-19 38
公钥体制的主要特点,
? 将加密和解密能力分开
? 多个用户加密的消息只能由一个用户解读（
秘密通信）
? 一个用户加密的消息而使多个用户可以解读
（认证）
? 不用事先分配秘钥
2012-3-19 39
对密码体制的一般要求,
?系 统 即 使 达 不 到 理 论 上 是 不 可 破 的, 即
pr{m’=m}=0,也应当为实际上不可破的 。 就是
说, 从截获的密文或某些已知明文密文对, 要
决定密钥或任意明文在计算上是不可行的 。
2012-3-19 40
对密码体制的一般要求,
? 系统的保密性不依赖于对加密体制或
算法的保密, 而依赖于密钥 。 这是著
名的 Kerckhoff原则 。
? 加密和解密算法适用于所有密钥空间
中的元素 。
? 系统便于实现和使用 。
2012-3-19 41
三,几种简单密码体制
2012-3-19 42
几种简单密码体制
1.换位密码
2.仿射密码
3.密钥短语密码
4.多名代换密码
5.多表代换密码
2012-3-19 43
换位密码
例：给定明文消息 the simplest
possible transposition ciphers （ 不
计空格符），将它分成长度的段，最后
一段长度不足 5添加一个字符 x,成为 8个
完整的明文组
thesi | mples | tposs | iblet | ransp
| ositi | oncip | hersx
2012-3-19 44
换位密码
加密方法,
得到密文,
01234
14302
k
E
??
? ??
??
STIEH EMSLP STSOP EITLB SRPNA TOIIS
IOPCN SHXRE
2012-3-19 45
换位密码
解密方法,
密钥量,
01234
30421
k
D
??
? ??
??
!L?K
2012-3-19 46
换位密码
缺点,
当明（密）文字母表内字符数不大时，
一味增加分段长度（比如使），可能
导致若干对很多明文组的加密结果重
合，甚至在局部明文空间上与恒等变
换等价，即密文消息等于明文消息，
达不到加密的效果。
2012-3-19 47
仿射密码
上的仿射密码的加密变换记为,
按
计算密文，其中密钥,
并且要求 gcd
以保证加密变换是可逆的。
? ?,kE i i j?qZ
? ? 1 0 0 1( ) m o d,kqj E i k i k q k k Z? ? ? ?
01(,)k k k?
? ?1,1kq ?
2012-3-19 48
仿射密码
当 时密钥量,
26q ?
2 6 ( ) 1 2 6 1 2 1 3 1 1q?? ? ? ? ? ?
注意,
其中 是整数 的欧拉函数 。 这里不取,
即不选
()q?
q ( 0,1)k ?
kEI?
2012-3-19 49
仿射密码
仿射密码就是 乘数密码
仿射密码就是 移位代换密码
或加法密码
其全部 26个加密变换的代换表
整合在一起构成一个密文形如 26阶对称矩
阵的表（该矩阵的第一行、第一列是从 A到
Z顺序排列的字母），称为 维吉尼亚表
0 0k ?
1 1k ?
26q ?
2012-3-19 50
仿射密码
针对 个英文字母,的加
法密码则称为 凯撒密码
仿射密码又是 多项式代换密码 的特
例 。
26q ? 0 3k ?
2012-3-19 51
仿射密码
构造 上的仿射密码
式中, +” 为矢量相加,是 上的 阶
满秩矩阵，即存在 使得
上 的仿射密码,
则称为 Hill密码
L
qZ ? ?,kE ?m m c
? ? ( + ) m o d,L L Lk q qE q Z Z?? ? ? ?c m m T b T b
T
qZ LL?
LLqZ ??-1T m o d q??-1T T I
26
LZ ?b0
2012-3-19 52
密钥短语密码
密钥短语密码
实际上是 26个英文字母或 上的一
种臵换 。
密钥量,
26Z
262 6 ! 4 1 0? ? ?K
2012-3-19 53
密钥短语密码
加密举例：选择一个英文短语作为密钥字
或称密钥短语, 如 HAPPY NEW YEAR,去掉
重复的字母得到 HAPYNEWR。 将它依次写在
明文字母表的下面, 而后再将字母表中未
在短语中出现过的字母依次写在这个短语
后面, 就可以构造一个代换表, 如下所示,
:
':
A
A
abcdefghijklmnopqrstuvwxyz
HAPYNEWRBCDFGIJKLMOQSTUVXZ
2012-3-19 54
多名代换 密码
也称为同音代换密码。
多名代换是一对多变换，它将明文字
母表中的每个字母映射为较大的密文
字母表中相应字母分组中的某个字母
（一般等概率地选定），各字母分组
的大小与相应原明文字母的概率成比
例。
2012-3-19 55
多名代换 密码
例如，字母 a,i,e,n,o,p,t的多名集可作
如下选择,
明文
字母
出现
频度 %
密文（多名集）
a 8.167 17,19,34,41,56,60,67,83
c 2.782 03,44,76
h 6.094 08,22,53,65,88,90
i 6.966 02,09,15,27,32,40,59
p 1.929 33,91
r 5.987 00,11,23,42,54,70
t 9.056 05,10,20,29,45,58,64,78,99
2012-3-19 56
多名代换 密码
个字母的明文字母表上的二阶多名代换
密码的构造方法：将 个整数随机地填入
一个, 二阶多名代换密表, 矩阵
中, 方阵中的行和列都对应于明文字母表
的 个字母 。
q
2q
{ (,) }qqW W w i j???
A q
2012-3-19 57
多名代换 密码
给定要加密的明文字母序列 01
...mm?m
，随机地选择
一 个 等 长 的 哑 明 文 字 母 序 列 01
...xx?x
,则 由
m
和
x
各 相 应 字 母 对
(,)
ll
mx
,可 以 在 矩 阵
W
中 确 定 密 文
字母序列 01
....cc?c
，其中
(,) 0 1,.,,
l l l
c w m x l??,
2012-3-19 58
多表代换密码
多表代换密码是以两个以上代换表依
次对明文消息的字母进行代换的加密方
法 。 令明文字母表为, 为
代换序列 。 明文字母序列为,
则相应的密文字母序列为
qZ
? ?01,,.,,? ? ??
01,..mm?m
? ? ? ? ? ? ? ?0 0 1 1,..kE m m? ? ?? ? ?c m m
2012-3-19 59
多表代换密码
若 是非周期的无限序列，则相
应的密码为非周期多表代换密码。
这类密码对每个明文字母都采用不
同的代换表（或密钥）进行加密，
称作一次一密钥密码
?
2012-3-19 60
多表代换密码
几种历史上较著名的多表代换密码,
维吉尼亚密码（ Vigenere Cipher）
博福特密码（ Beaufort Cipher）
滚动密钥密码（ running-key Cipher）
弗纳姆密码（ Vernam Cipher）
转轮密码（ rotor Cipher）
2012-3-19 61
四,初等密码分析
2012-3-19 62
基本概念
试图获得加密体制细节, 解密密钥和
明文等机密信息的过程, 通常包括,
分析统计截获的密文材料, 假设, 推
断和证实等步骤 。
2012-3-19 63
基本概念
密码分析方法有传统破译方法和物
理破译方法两大类 。
传统破译方法包括穷举破译法和数
学分析法两类 。
数学分析法又分为确定性分析法的
和统计分析法 。
2012-3-19 64
基本概念
四种破译类型,
（ 1） 唯密文破译 （ ciphertext only
attacks）, 分析者仅知道有限数量的密
文 。
（ 2） 已知明文破译 （ know plaintext
attacks）, 分析者除了拥有有限数量的
密文外, 还有数量限定的一些已知
,明文 —密文, 对 。
2012-3-19 65
基本概念
（ 3） 选择明文破译 （ chosen plaintext
attacks）, 分析者除了拥有有限数量的密文
外, 还有机会使用注入了未知密钥的加密机,
通过自由选择明文来获取所希望的, 明文 —密
文, 对 （ 集合 ） 。
（ 4） 选择密文破译 （ chosen ciphertext
attacks）, 分析者除了拥有有限数量的密文
外, 还有机会使用注入了未知密钥的解密机,
通过自由选择密文来获取所希望的, 密文 —明
文, 对 （ 集合 ） 。
2012-3-19 66
单表代换密码分析
能对密码分析者提供很大帮助的英文统
计特性,
（ 1） 冠词 the对统计特性影响极大, 它
使 t,h,th,he和 the在单, 双和三字母统
计中都为高频度元素 。
（ 2） 英文中大约有一半的字以 e,s,d
和 t作为字的结尾字母 。
（ 3） 英文中大约有一半的字以 t,a,s
或 w作为字的开头字母 。
2012-3-19 67
多表代换密码分析
定义 1, 4, 1 设 0 1 1
...
n
x x x
?
?x
是取自某字
母表的 n 个 字 母 的 一 个 串,
x
的 重合指
数 （ i n d e x o f c o i n c i d e n c e ）定 义 为 自
x
中随
机 选 取 的 两 个 字 母 为 相 同 字 母 的 概 率,
记为
cI ( )x
。
2012-3-19 68
多表代换密码分析
对于字母数为 26 的英文字母表,
? ?
? ?
C
2 5 2 5
0
1
I ( ) =
1
i
2
f i i
i = 0 i
2
n
C f f
C n n
?
?
?
?
??
x
其中，
? ?0,1,2,.,,,2 5
i
fi ?
分别表示
x
中字母
A,B,C,…,Z 出现的频数。
2012-3-19 69
多表代换密码分析
定义 1, 4, 2 设 0 1 1
...
n
x x x
?
?x
和 0 1 ' 1
...
n
y y y
?
?y
分
别是长为
n
和 n' 的 字 母 串 。
x
和
y
的 重合
互指数 定义为分别自
x
和
y
中 随 机 选 取
一 个 字 母 为 相 同 字 母 的 概 率, 记 为
cM I ( )x,y
。
2012-3-19 70
多表代换密码分析
如果用
? ?0,1,2,.,,,2 5
i
fi ?
与
? ?0,1,2,.,,,2 5
i
fi ?
'
分
别表示
x
和 y 中字母 A,B,C,…,Z 出 现 的 频 数,则
C
25
0
M I ( ) =
''
ii25
ii i
i = 0
ff
ff
n n n n
?
??
?
?
'
'
x,y
2012-3-19 71
多表代换密码分析
步骤一,
从密文中找出大于等于 3的重复图样，对
于每种重复图样，列出其间的距离。
步骤二,
确定具体的密钥 。
2012-3-19 72
五,密码学的信息论基础
2012-3-19 73
5.1 信息量和熵
5.2 完善保密性
5.3 唯一解距离、理论保密性与
实际保密性
2012-3-19 74
信息量和熵
将集 X 中 事 件 出 现 的 信 息 量 统 计
的平均值
? ? ? ? ? ?
2
l o g 0
ii
i
H X p x p x? ? ??
定义为集 X 的 熵 ( e n t r o p y ), 它表示
X
中 出 现 一 个 事 件 平 均 给 出 的 信 息
量, 或者集 X 中 事 件 的 平均不确定
性 （ a v e r a g e u n c e r t a i n t y ） 。
2012-3-19 75
信息量和熵
定理 1, 5, 1 对任意有
n
个 事 件 的 集
合，有
? ?
2
0 l o gH X n??
这个定理表明,
均匀分布下集 X 的不确定性为最大。
2012-3-19 76
信息量和熵
设有两个事件集
? ?,0,1,.,,,1
i
X x i n? ? ?
和
? ?,0,1,.,,,1
i
Y y i m? ? ?
。令联合事件
ij
xy
的概率为
? ?
ij
p x y
，则有
? ? ? ? ? ?
2
l o g
ii
i
H X p x p x??
?
? ? ? ? ? ?
2
l o g
jj
j
H Y p y p y??
?
? ? ? ? ? ?
2
,
l o g
i j i j
ij
H X Y p x y p x y??
?
称
? ?H X Y
为集
X
和
Y
的联合熵
2012-3-19 77
信息量和熵
? ? ? ? ? ?
2
,
l o g
i j i j
ij
H X Y p x y p x y?? ?
? ? ? ? ? ?
2
,
l o g
i j i j
ij
H Y X p x y p y x?? ?
为条件熵。
2012-3-19 78
信息量和熵
将 X 看 作 是 一 个 系 统 的 输 入 空 间, 将 Y 看作
是 系 统 的 输 出 空 间, 当 输 入 为 i
xX ?
,输 出
j
yY ?
，将 由 j
y
得到的关于 i
x
出 现 的 信 息 量 定
义为
? ?
? ?
? ?
2; l o g
ij
ij
i
p x y
I x y
px
?
?
2012-3-19 79
信息量和熵
若 将 系 统 看 作 是 一 个 传 信 通 道, 则 可
以定义
? ?
? ?
{}
m a x ;a
px
C I X Y?
为 信道容量 （ c h a n n e l c a p a c i t y ）
2012-3-19 80
完善保密性
基本术语,
密码源
解密空间
解密变换
2012-3-19 81
完善保密性
定理 1, 5, 2 对于任意密码系统
? ? ? ? ? ?
';
L L L
I M C H M H?? K
如果密文与明文之间的互信息量满足
? ?
';0
LL
I M C ?
则该密码系统为 完 善 保 密 的 （ p e r f e c t s e c u r e ）,或 具
有 无条件安全性 （ u n c o n d i t i o n a l s e c u r i t y ） 。
2012-3-19 82
完善保密性
定理 1, 5, 3 完 善 保 密 密 码 系 统 存 在 的
必要条件是
? ? ? ?
L
H H M?K
2012-3-19 83
唯一解距离、理论保密性与实际保密性
由条件熵性质知
? ? ? ?HH ???+1CCKK
若,
就可以唯一地确定密钥, 从而实现破译 。
? ? 0vHC ?K
2012-3-19 84
唯一解距离、理论保密性与实际保密性
对于给定的密码系统, 我们称
为唯密文破译下的唯一解距离
（ unicity distance）,式中 是正
整数集。
? ?? ?0 m i n 0vv v N H C? ? ?K
N
2012-3-19 85
唯一解距离、理论保密性与实际保密性
理论保密性是假定密码分析者有无限的时
间、设备和资金条件下，研究唯密文攻击
时密码系统的安全性。
实际的密码分析者所具有的资金、设备和
时间总是有限的。在这种条件下来研究密
码体制的安全保密性，就是研究系统的实
际保密性。
2012-3-19 86
六、密码学的复杂性理论基础
2012-3-19 87
?所谓问题，是指一个要求给出解释的一般性
提问，通常含有若干未定参数或自由变量。
两个要素,
? 描述所有的参数
? 解答必须满足的性质
问题与算法
2012-3-19 88
?所谓算法,是由明确指出操作的规
定所组成的若干语句的集合。只要
安规则一步一步执行一定数目的语
句,便可求出问题的解答 。
问题与算法
2012-3-19 89
算法的复杂性
算法的复杂性表征了算法在执行时所
需要计算的能力方面的信息, 通常由
该算法的所要求的最大时间与存取空
间来确定 。
用, 大 O”符号来衡量算法 的复杂程度
,
2012-3-19 90
按时间 (或空间 )复杂性对算法分类
? 多项式时间算法
? 指数时间算法
? 超多项式算法等
算法的复杂性
2012-3-19 91
问题按复杂性分类
问题的复杂性由在图灵机上解最难实
例所需的最小时间与空间所决定 。 问
题的复杂性可以用理解为由解该问题
的最胡效的算法 所需时间与空间来
度量 。
2012-3-19 92
P类：在确定图灵机上可用多项式时
间求解的问题,称为易处理的问题,
易处理的问题的全体称为确定性多
项式时间可解类 。 记为 P类 。
问题按复杂性分类
2012-3-19 93
问题按复杂性分类
NP类：在非确定图灵机上可用多项式
时间求解的问题,称为非确定性多
项式时间可解问题,记为 NP问题 。
2012-3-19 94
? NPC类,NP完全类记为 NPC,属于 NP类中
困难程度最难的一类问题。已经证明,
所有的 NP问题都可以在多项式时间内转
换为 NPC的问题,NPC具有如下性质：若
其中的任何一问题属于 P,则所有的 NP
问题都属于 P,且 P=NP。
问题按复杂性分类