2010-5-14 1
第二章,密码学基础
一、密码学的基本概念
二、密码体制分类
三、密码分析
2010-5-14 2
一、密码学的基本概念
密码学 (Cryptology)：研究信息系统安全
保密的科学。它包含两个分支，
? 密码编码学 (Cryptography),对信息进行
编码实现隐蔽信息的一门学问
? 密码分析学 (Cryptanalytics)，研究分析
破译密码的学问。
2010-5-14 3
几个概念（一）
。
明文 (消息 )(Plaintext), 被隐蔽消息。
密文 (Ciphertext)或 密报 (Cryptogram),明文经密
码变换成的一种隐蔽形式。
加密 (Encryption),将明文变换为密文的过程。
解密 (Decryption),加密的逆过程，即由密文恢复出
原明文的过程。
加密员 或 密码员 (Cryptographer),对明文进行加密
操作的人员。
2010-5-14 4
几个概念（二）
。
加密算法 (Encryption algorithm),密码员对明文进
行加密时所采用的一组规则。
接收者 (Receiver),传送消息的预定对象。
解密算法,接收者对密文进行解密时所采用的一组规
则。
密钥 (Key),控制加密和解密算法操作的数据处理，分
别称作 加密密钥 和 解密密钥 。
截收者 (Eavesdropper),在信息传输和处理系统中的
非受权者, 通过搭线窃听, 电磁窃听, 声音窃听等来窃
取机密信息 。
2010-5-14 5
几个概念（三）
密码分析 (Cryptanalysis),截收者试图通过分析从
截获的密文推断出原来的明文或密钥。
密码分析员 (Cryptanalyst),从事密码分析的人 。
被动攻击 (Passive attack),对一个保密系统采取截
获密文进行分析的攻击 。
主动攻击 (Active attack),非法 入侵者 (Tamper)、
攻击者 (Attcker)或 黑客 (Hacker)主动向系统窜扰, 采用
删除, 增添, 重放, 伪造等窜改手段向系统注入假消息
,达到利已害人的目的 。
2010-5-14 6
保密系统模型
信源
M
m 加密器
)(1 mEc k?
解密器
)(2 cDm k?
接收者
m
非法接入者
搭线信道
（主动攻击）
C ’
搭线信道
（被动攻击） 密码分析员 m‘
密钥源
K1
k1
密钥源
K2
k2
密钥信道
2010-5-14 7
保密系统应当满足的要求
? 系统即使达不到理论上是不可破的, 即 pr{m’=m}=0，
也应当为实际上不可破的 。 就是说, 从截获的密文
或某些已知明文密文对, 要决定密钥或任意明文在
计算上是不可行的 。
? 系统的保密性不依赖于对加密体制或算法的保密,
而依赖于密钥 。 这是著名的 Kerckhoff原则 。
? 加密和解密算法适用于所有密钥空间中的元素 。
? 系统便于实现和使用 。
2010-5-14 8
认证与认证系统
认证系统 (Authentication system)
防止消息被窜改, 删除, 重放和伪造的一种有效方法,
使发送的消息具有被验证的能力, 使接收者或第三者能够
识别和确认消息的真伪 。 实现这类功能的密码系统称作认
证系统
保密性
保密性是使截获者在不知密钥条件下不能解读密文的
内容 。
认证性
使任何不知密钥的人不能构造一个密报, 使意定的接
收者解密成一个可理解的消息 (合法的 消息 )。
2010-5-14 9
安全认证系统应满足下述条件
意定的接收者能够检验和证实消息的合法性和真实性 。
消息的发送者对所发送的消息不能抵赖 。
除了合法消息发送者外, 其它人不能伪造合法的消息 。
而且在已知合法密文 c和相应消息 m下, 要确定加密密钥
或系统地伪造合法密文在计算上是不可行的 。
必要时可由第三者作出仲裁 。
2010-5-14 10
完整性 (integrity)
在有自然和人为干扰条件下, 系统
保持检测错误和恢复消息和原来发送消
息一致性的能力 。 实际中常常借助于纠,
检错技术和杂凑技术来保证消息的完整
性 。
2010-5-14 11
二、密码体制分类
? 密码体制有 2大类：
? 单钥体制 (One-key system)：
加密密钥和解密密钥相同。
? 双钥体制 (Two key system)：
加密密钥和解密密钥不同。
2010-5-14 12
密码体制分类 单钥体制
加密器
EK
解密器
DK
密文明文 明文
K
密钥产生器
K
2010-5-14 13
密码体制分类 单钥体制
? 单钥体制主要研究问题：
? 密钥产生 (Key generation)，
? 密钥管理 (Key management)。
? 分类：
? 流密码 (Stream cipher)
? 分组密码 (Block cipher)
? 单钥体制不仅可用于数据加密，也可用
于消息的认证 。
2010-5-14 14
密码体制分类 双钥体制
双钥体制 或 公钥体制 (Public key system)
(Diffie和 Hellman,1976)
每个用户都有一对选定的密钥 (公钥 k1； 私钥
k2),公开的密钥 k1可以像电话号码一样进行注
册公布 。
2010-5-14 15
公钥体制的主要特点
? 加密和解密能力分开
? 可以实现多个用户加密的消息只能由一个用户
解读 （ 用于公共网络中实现保密通信 ）
? 只能由一个用户加密消息而使多个用户可以解
读 （ 可用于认证系统中对消息进行数字签字 ） 。
? 无需事先分配密钥 。
2010-5-14 16
三、密码分析
截收者在不知道解密密钥及通信者所采用的加
密体制的细节条件下，对密文进行分析，试图
获取机密信息。研究分析解密规律的科学称作
密码分析学 。
密码分析在外交、军事、公安、商业等方面都
具有重要作用，也是研究历史、考古、古语言
学和古乐理论的重要手段之一。
2010-5-14 17
密码分析
密码设计和密码分析是共生的、又是互逆的，两
者密切有关但追求的目标相反。两者解决问题的
途径有很大差别
密码设计是利用数学来构造密码
密码分析除了依靠数学、工程背景、语言学等知识外，
还要靠经验、统计、测试、眼力、直觉判断能力 ……,有
时还靠点运气。
2010-5-14 18
密码分析方法 --穷举破译法
对截收的密报依次用各种可解的密钥试译，直到得到
有意义的明文；
或在不变密钥下，对所有可能的明文加密直到得到与
截获密报一致为止，此法又称为 完全试凑法 (Complete
trial-and-error Method)。
只要有足够多的计算时间和存储容量，原则上穷举法
总是可以成功的。但实际中，任何一种能保障安全要求的
实用密码都会设计得使这一方法在实际上是不可行的。
2010-5-14 19
密码分析方法 — 分析法
确定性分析法
利用一个或几个已知量 (比如，已知密文或明文 -密文对
)用数学关系式表示出所求未知量 (如密钥等 )。已知量和未
知量的关系视加密和解密算法而定，寻求这种关系是确定
性分析法的关键步骤。
统计分析法
利用明文的已知统计规律进行破译的方法。密码破译者
对截收的密文进行统计分析，总结出其间的统计规律，并
与明文的统计规律进行对照比较，从中提取出明文和密文
之间的对应或变换信息。
2010-5-14 20
密码可能经受的攻击
攻击类型 攻击者拥有的资源
惟密文攻击 ?加密算法
?截获的部分密文
已知明文攻
击
?加密算法，
?截获的部分密文和相应的明文
选择明文攻
击
?加密算法
?加密黑盒子，可加密任意明文得到相应的密文
选择密文攻
击
?加密算法
?解密黑盒子，可解密任意密文得到相应的明文
2010-5-14 21
无条件安全和计算安全
无条件安全
如果算法产生的密文不能给出唯一决定相应明文的
足够信息，无论截获多少密文，花费所少时间都不能解
密密文。
Shannon指出，仅当密钥至少和明文一样长时达到无
条件安全（即一次一密）
计算安全
破译密文的代价超过被加密信息的价值
破译密文所花时间超过信息的有效期
2010-5-14 22
第三章 流密码
一、流密码的基本概念
二、线性反馈移位寄存器序列
三, B-M综合算法
四,非线性序列
2010-5-14 23
一、流密码的基本概念
2010-5-14 24
流密码的基本概念
? 流密码是将明文划分成字符 (如单个字母 )，或其编码
的基本单元 (如 0,1数字 )，字符分别与密钥流作用进
行加密，解密时以同步产生的同样的密钥流实现。
? 流密码强度完全依赖于密钥序列的随机性 (Randomness)
和不可预测性 (Unpredictability)。
? 核心问题是密钥流生成器的设计 。
? 保持收发两端密钥流的精确同步是实现可靠解密的关
键技术 。
2010-5-14 25
流密码的框图
kI 安 全 信 道 kI
··· ···
KG KG
ki ki
mi ci ci mi
Eki(mi) ··· Eki(mi)
2010-5-14 26
流密码的框图
? 消息流,m=m1m2… mi,其中 mi?M。
? 密文流,c=c1c2… ci… =Ek1(m1)Ek2(m2)… Eki(mi)…,
ci?C。
? 密钥流,{ki},i?0。
一个完全随机的非周期序列, 可以实现一次一密体制 。 但
需要无限存储单元和复杂的输出逻辑函数 f。 ?i是第 i时刻
密钥流生成器的内部状态, 以存储单元的存数矢量描述 。
? 加法流密码,ci=Eki(mi)=mi ?ki
2010-5-14 27
有限状态自动机 FA
(Finite state Automation)
? 具有离散输入和输出（输入集和输出集均
有限）的一种数学模型
? 有限状态集 S={si|i=1,2,…,l}
? 有限输入字符集 X={ Xi|i=1,2,…,m}
? 有限输出字符集 Y={ Yk|k=1,2,…,n}
? 转移函数
? Yj＝ f 1(sj,Xj)
? Sj+1＝ f 2(sj,Xj) 第 j时刻输入 Xj X, 输出 Yj
Y
? ?
2010-5-14 28
例 2-1
? S={s1,s2,s3},X={x1,x2,x3},Y=(y1,y2,y3)
? 转移函数
f1 x1 x2 X3
s1
s2
s3
y1
y2
y3
y3
y1
y2
y2
y3
y1
f2 x1 x2 X3
s1
s2
s3
s2
s3
s1
s1
s2
s3
s3
s1
s2
2010-5-14 29
FA的状态图表示
若输入为
x1x2x1x3x3x1
初始状态 s1
输出为
y1y1y2y1y3y1
2010-5-14 30
作为 FA的密钥流产生器
? 同步流密码的密钥流产生器可
看为一个参数为 k的 FA
? 输出集 Z，状态集 Σ,状态转移
函数 φ 和输出函数 ψ,初态 ?0
? 设计的关键是 φ 和 ψ
φ
?i ψ
k
k
k
zi
2010-5-14 31
作为 FA的密钥流产生器
? 具有非线性的 φ的 FA理论很不完善，通
常采用线性 φ以及非线性的 ψ
? 可将此类产生器分为驱动部分和非线性
组合部分。
? 驱动部分控制状态转移
? 非线性组合部分提供统计特性良好的序
列
2010-5-14 32
两种常见的密钥流产生器
LFSR
非线性组合函数
zi
LFSR
LFSR
LFSR
非
线
性
组
合
函
数
zi
第二章,密码学基础
一、密码学的基本概念
二、密码体制分类
三、密码分析
2010-5-14 2
一、密码学的基本概念
密码学 (Cryptology)：研究信息系统安全
保密的科学。它包含两个分支，
? 密码编码学 (Cryptography),对信息进行
编码实现隐蔽信息的一门学问
? 密码分析学 (Cryptanalytics)，研究分析
破译密码的学问。
2010-5-14 3
几个概念（一）
。
明文 (消息 )(Plaintext), 被隐蔽消息。
密文 (Ciphertext)或 密报 (Cryptogram),明文经密
码变换成的一种隐蔽形式。
加密 (Encryption),将明文变换为密文的过程。
解密 (Decryption),加密的逆过程，即由密文恢复出
原明文的过程。
加密员 或 密码员 (Cryptographer),对明文进行加密
操作的人员。
2010-5-14 4
几个概念（二）
。
加密算法 (Encryption algorithm),密码员对明文进
行加密时所采用的一组规则。
接收者 (Receiver),传送消息的预定对象。
解密算法,接收者对密文进行解密时所采用的一组规
则。
密钥 (Key),控制加密和解密算法操作的数据处理，分
别称作 加密密钥 和 解密密钥 。
截收者 (Eavesdropper),在信息传输和处理系统中的
非受权者, 通过搭线窃听, 电磁窃听, 声音窃听等来窃
取机密信息 。
2010-5-14 5
几个概念（三）
密码分析 (Cryptanalysis),截收者试图通过分析从
截获的密文推断出原来的明文或密钥。
密码分析员 (Cryptanalyst),从事密码分析的人 。
被动攻击 (Passive attack),对一个保密系统采取截
获密文进行分析的攻击 。
主动攻击 (Active attack),非法 入侵者 (Tamper)、
攻击者 (Attcker)或 黑客 (Hacker)主动向系统窜扰, 采用
删除, 增添, 重放, 伪造等窜改手段向系统注入假消息
,达到利已害人的目的 。
2010-5-14 6
保密系统模型
信源
M
m 加密器
)(1 mEc k?
解密器
)(2 cDm k?
接收者
m
非法接入者
搭线信道
（主动攻击）
C ’
搭线信道
（被动攻击） 密码分析员 m‘
密钥源
K1
k1
密钥源
K2
k2
密钥信道
2010-5-14 7
保密系统应当满足的要求
? 系统即使达不到理论上是不可破的, 即 pr{m’=m}=0，
也应当为实际上不可破的 。 就是说, 从截获的密文
或某些已知明文密文对, 要决定密钥或任意明文在
计算上是不可行的 。
? 系统的保密性不依赖于对加密体制或算法的保密,
而依赖于密钥 。 这是著名的 Kerckhoff原则 。
? 加密和解密算法适用于所有密钥空间中的元素 。
? 系统便于实现和使用 。
2010-5-14 8
认证与认证系统
认证系统 (Authentication system)
防止消息被窜改, 删除, 重放和伪造的一种有效方法,
使发送的消息具有被验证的能力, 使接收者或第三者能够
识别和确认消息的真伪 。 实现这类功能的密码系统称作认
证系统
保密性
保密性是使截获者在不知密钥条件下不能解读密文的
内容 。
认证性
使任何不知密钥的人不能构造一个密报, 使意定的接
收者解密成一个可理解的消息 (合法的 消息 )。
2010-5-14 9
安全认证系统应满足下述条件
意定的接收者能够检验和证实消息的合法性和真实性 。
消息的发送者对所发送的消息不能抵赖 。
除了合法消息发送者外, 其它人不能伪造合法的消息 。
而且在已知合法密文 c和相应消息 m下, 要确定加密密钥
或系统地伪造合法密文在计算上是不可行的 。
必要时可由第三者作出仲裁 。
2010-5-14 10
完整性 (integrity)
在有自然和人为干扰条件下, 系统
保持检测错误和恢复消息和原来发送消
息一致性的能力 。 实际中常常借助于纠,
检错技术和杂凑技术来保证消息的完整
性 。
2010-5-14 11
二、密码体制分类
? 密码体制有 2大类：
? 单钥体制 (One-key system)：
加密密钥和解密密钥相同。
? 双钥体制 (Two key system)：
加密密钥和解密密钥不同。
2010-5-14 12
密码体制分类 单钥体制
加密器
EK
解密器
DK
密文明文 明文
K
密钥产生器
K
2010-5-14 13
密码体制分类 单钥体制
? 单钥体制主要研究问题：
? 密钥产生 (Key generation)，
? 密钥管理 (Key management)。
? 分类：
? 流密码 (Stream cipher)
? 分组密码 (Block cipher)
? 单钥体制不仅可用于数据加密，也可用
于消息的认证 。
2010-5-14 14
密码体制分类 双钥体制
双钥体制 或 公钥体制 (Public key system)
(Diffie和 Hellman,1976)
每个用户都有一对选定的密钥 (公钥 k1； 私钥
k2),公开的密钥 k1可以像电话号码一样进行注
册公布 。
2010-5-14 15
公钥体制的主要特点
? 加密和解密能力分开
? 可以实现多个用户加密的消息只能由一个用户
解读 （ 用于公共网络中实现保密通信 ）
? 只能由一个用户加密消息而使多个用户可以解
读 （ 可用于认证系统中对消息进行数字签字 ） 。
? 无需事先分配密钥 。
2010-5-14 16
三、密码分析
截收者在不知道解密密钥及通信者所采用的加
密体制的细节条件下，对密文进行分析，试图
获取机密信息。研究分析解密规律的科学称作
密码分析学 。
密码分析在外交、军事、公安、商业等方面都
具有重要作用，也是研究历史、考古、古语言
学和古乐理论的重要手段之一。
2010-5-14 17
密码分析
密码设计和密码分析是共生的、又是互逆的，两
者密切有关但追求的目标相反。两者解决问题的
途径有很大差别
密码设计是利用数学来构造密码
密码分析除了依靠数学、工程背景、语言学等知识外，
还要靠经验、统计、测试、眼力、直觉判断能力 ……,有
时还靠点运气。
2010-5-14 18
密码分析方法 --穷举破译法
对截收的密报依次用各种可解的密钥试译，直到得到
有意义的明文；
或在不变密钥下，对所有可能的明文加密直到得到与
截获密报一致为止，此法又称为 完全试凑法 (Complete
trial-and-error Method)。
只要有足够多的计算时间和存储容量，原则上穷举法
总是可以成功的。但实际中，任何一种能保障安全要求的
实用密码都会设计得使这一方法在实际上是不可行的。
2010-5-14 19
密码分析方法 — 分析法
确定性分析法
利用一个或几个已知量 (比如，已知密文或明文 -密文对
)用数学关系式表示出所求未知量 (如密钥等 )。已知量和未
知量的关系视加密和解密算法而定，寻求这种关系是确定
性分析法的关键步骤。
统计分析法
利用明文的已知统计规律进行破译的方法。密码破译者
对截收的密文进行统计分析，总结出其间的统计规律，并
与明文的统计规律进行对照比较，从中提取出明文和密文
之间的对应或变换信息。
2010-5-14 20
密码可能经受的攻击
攻击类型 攻击者拥有的资源
惟密文攻击 ?加密算法
?截获的部分密文
已知明文攻
击
?加密算法，
?截获的部分密文和相应的明文
选择明文攻
击
?加密算法
?加密黑盒子，可加密任意明文得到相应的密文
选择密文攻
击
?加密算法
?解密黑盒子，可解密任意密文得到相应的明文
2010-5-14 21
无条件安全和计算安全
无条件安全
如果算法产生的密文不能给出唯一决定相应明文的
足够信息，无论截获多少密文，花费所少时间都不能解
密密文。
Shannon指出，仅当密钥至少和明文一样长时达到无
条件安全（即一次一密）
计算安全
破译密文的代价超过被加密信息的价值
破译密文所花时间超过信息的有效期
2010-5-14 22
第三章 流密码
一、流密码的基本概念
二、线性反馈移位寄存器序列
三, B-M综合算法
四,非线性序列
2010-5-14 23
一、流密码的基本概念
2010-5-14 24
流密码的基本概念
? 流密码是将明文划分成字符 (如单个字母 )，或其编码
的基本单元 (如 0,1数字 )，字符分别与密钥流作用进
行加密，解密时以同步产生的同样的密钥流实现。
? 流密码强度完全依赖于密钥序列的随机性 (Randomness)
和不可预测性 (Unpredictability)。
? 核心问题是密钥流生成器的设计 。
? 保持收发两端密钥流的精确同步是实现可靠解密的关
键技术 。
2010-5-14 25
流密码的框图
kI 安 全 信 道 kI
··· ···
KG KG
ki ki
mi ci ci mi
Eki(mi) ··· Eki(mi)
2010-5-14 26
流密码的框图
? 消息流,m=m1m2… mi,其中 mi?M。
? 密文流,c=c1c2… ci… =Ek1(m1)Ek2(m2)… Eki(mi)…,
ci?C。
? 密钥流,{ki},i?0。
一个完全随机的非周期序列, 可以实现一次一密体制 。 但
需要无限存储单元和复杂的输出逻辑函数 f。 ?i是第 i时刻
密钥流生成器的内部状态, 以存储单元的存数矢量描述 。
? 加法流密码,ci=Eki(mi)=mi ?ki
2010-5-14 27
有限状态自动机 FA
(Finite state Automation)
? 具有离散输入和输出（输入集和输出集均
有限）的一种数学模型
? 有限状态集 S={si|i=1,2,…,l}
? 有限输入字符集 X={ Xi|i=1,2,…,m}
? 有限输出字符集 Y={ Yk|k=1,2,…,n}
? 转移函数
? Yj＝ f 1(sj,Xj)
? Sj+1＝ f 2(sj,Xj) 第 j时刻输入 Xj X, 输出 Yj
Y
? ?
2010-5-14 28
例 2-1
? S={s1,s2,s3},X={x1,x2,x3},Y=(y1,y2,y3)
? 转移函数
f1 x1 x2 X3
s1
s2
s3
y1
y2
y3
y3
y1
y2
y2
y3
y1
f2 x1 x2 X3
s1
s2
s3
s2
s3
s1
s1
s2
s3
s3
s1
s2
2010-5-14 29
FA的状态图表示
若输入为
x1x2x1x3x3x1
初始状态 s1
输出为
y1y1y2y1y3y1
2010-5-14 30
作为 FA的密钥流产生器
? 同步流密码的密钥流产生器可
看为一个参数为 k的 FA
? 输出集 Z，状态集 Σ,状态转移
函数 φ 和输出函数 ψ,初态 ?0
? 设计的关键是 φ 和 ψ
φ
?i ψ
k
k
k
zi
2010-5-14 31
作为 FA的密钥流产生器
? 具有非线性的 φ的 FA理论很不完善，通
常采用线性 φ以及非线性的 ψ
? 可将此类产生器分为驱动部分和非线性
组合部分。
? 驱动部分控制状态转移
? 非线性组合部分提供统计特性良好的序
列
2010-5-14 32
两种常见的密钥流产生器
LFSR
非线性组合函数
zi
LFSR
LFSR
LFSR
非
线
性
组
合
函
数
zi
