2
主要内容
一、密码简介
二、分组密码
三、公钥密码
四、消息认证
3
一、密码简介
4
信息为什么不安全
?信息需要共享...
?信息需要使用...
?信息需要交换...
?信息需要传输...
5
为什么需要密码
信息的存储:在公开的地方
信息的交换:使用非隐秘介质
信息的传输:通过不安全信道
6
基本概念
密码学(Cryptology):是研究信息系统
安全保密的科学.
?密码编码学(Cryptography):主要研究
对信息进行编码,实现对信息的隐蔽.
?密码分析学(Cryptanalytics):主要研究
加密消息的破译或消息的伪造.
7
基本术语
消息被称为明文(Plaintext)。用某种方法伪装消息
以隐藏它的内容的过程称为加密(Encrtption)，被
加密的消息称为密文(Ciphertext)，而把密文转变
为明文的过程称为解密(Decryption)。
密码算法(CryptographyAlgorithm):是用于加密和
解密的数学函数。
密钥（key），加密或解密所需要的除密码算法之外
的关键信息.
密码员对明文进行加密操作时所采用的一组规则称
作加密算法(EncryptionAlgorithm).
所传送消息的预定对象称为接收者(Receiver).
接收者对密文解密所采用的一组规则称为解密算法
(DecryptionAlgorithm).
8
加密与解密
明文
明文
密文
加密算法
解密算法
密钥
密钥
加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称
为加密密钥(EncryptionKey)和解密密钥(DecryptionKey).
9
加密通信模型
发方
加密机
解密机
收方
安全信道
密钥源
攻击者
x
y
x
k
密码学的目的：发方和收方两个人在不安全的
信道上进行通信，而敌方（攻击者）不能理解
他们通信的内容。
10
密码体制
密码体制：它是一个五元组（P,C,K,E,D)满足条件：
（1）P是可能明文的有限集；（明文空间）
（2）C是可能密文的有限集；（密文空间）
（3）K是一切可能密钥构成的有限集；（密钥空
间）
（4）任意k∈K,有一个加密算法和相应的
解密算法，使得和
分别为加密解密函数，满足d
k
(e
k
(x))=x,这里x∈P。
Ee
k
∈Dd
k
∈
CPe
k
→:
PCd
k
→:
11
密码算法分类
基于密钥的算法，按照密钥的特点分类：
?对称密码算法（symmetriccipher)：又称传统密
码算法（conventionalcipher)，就是加密密钥和
解密密钥相同，或实质上等同，即从一个易于
推出另一个。又称秘密密钥算法或单密钥算法。
?非对称密钥算法（asymmetriccipher):加密密钥
和解密密钥不相同。如果从一个很难推出另一
个。又称公开密钥算法（public-keycipher)。
公开密钥算法用一个密钥进行加密,而用另一
个进行解密.其中的加密密钥可以公开,又称公
开密钥（publickey)，简称公钥.解密密钥必须
保密,又称私人密钥（privatekey)私钥.简称私钥。
12
对称密钥密码又可分为
?分组密码（也称块密码）
每次对一块数据加密
多数网络加密应用
DES,IDEA,RC6,Rijndael
?流密码（序列密码）
每次对一位或一字节加密
13
密码学的起源和发展
三个阶段：
?1949年之前
密码学是一门艺术
?1949～1975年
密码学成为科学
?1976年以后
密码学的新方向——公钥密码学
14
密码学的起源
隐写术(steganography):
通过隐藏消息的存在来保护消息.
a.隐形墨水
b.字符格式的变化
c.图形图像
15
古典密码
代替密码（substitutioncipher)
置换密码(permutationcipher)，又称换位
密码（transpositioncipher)
16
古典密码
?单表替换密码的破译
?通过字母的使用频率破译
17
古典密码
移位密码
移12位：
移3位，即Caesar密码
18
古典密码
移位密码分析
给定加密的消息:
PHHWPHDIWHUWKHWRJDSDUWB
如果移1位得：QIIXQI….
如果移2位得：RJJYRJ….
…
如果移23位得：meetmeafterthetogaparty
可能尝试的密钥只有２6个,而事实上，还有一个
是不变，因此，最多尝试25次即可得到明文！
19
古典密码
仿射密码
加密函数取形式为
y=e(x)=ax+b(mod26),a,b,x,y∈Z/(26)，
要求唯一解的充要条件是gcd(a,26)=1
加密函数取形式为：
x=d
k
(y)=a
-1
(y-b)(mod26)
可能的密钥是2612=311个
20
二、分组密码
21
密码的设计原则
信息的保密取决于密钥的保密：
一切秘密寓于密钥之中。加密算法可以公开
（Kerckhoff假设）
22
分组密码设计要求
◆Diffusion(扩散)
密文没有统计特征，明文一位影响密文
的多位，密钥的一位也影响密文的多位
◆Confusion(混淆)
明文与密文、密钥与密文的依赖关系充
分复杂
?结构简单、易于分析
23
实现方面的设计原则
软件实现的要求：使用子块和简单的运算。密码运算
在子块上进行，要求子块的长度能自然地适应软件编
程，如8、16、32比特等。应尽量避免按比特置换，在
子块上所进行的密码运算尽量采用易于软件实现的运
算。最好是用处理器的基本运算，如加法、乘法、移
位等。
硬件实现的要求：加密和解密的相似性，即加密和解
密过程的不同应仅仅在密钥使用方式上，以便采用同
样的器件来实现加密和解密，以节省费用和体积。尽
量采用标准的组件结构，以便能适应于在超大规模集
成电路中实现。
24
分组密码的操作模式
电子密码本ECB(electroniccodebook
mode)
密码分组链接CBC(cipherblockchaining)
密码反馈CFB(cipherfeedback)
输出反馈OFB(outputfeedback)
25
电子密码本（ECB）
C
i
=E
K
(P
i
)?P
i
=D
K
(C
i
)
26
密码分组链接CBC
?C
i
=E
K
(C
i-1
⊕P
i
)?P
i
=E
K
(C
i
)⊕C
i-1
27
CBC特点
?没有已知的并行实现算法
?能隐藏明文的模式信息
–需要共同的初始化向量IV
–相同明文?不同密文
–初始化向量IV可以用来改变第一块
?对明文的主动攻击是不容易的
–信息块不容易被替换、重排、删除、重放
–误差传递：密文块损坏?两明文块损坏
安全性好于ECB
适合于传输长度大于64位的报文，还可以进行用户鉴
别,是大多系统的标准如SSL、IPSec采用的模式
28
密文反馈CFB模式
?CFB:分组密码?流密码
S
i
为移位寄存器,j为流单元宽度
加密:C
i
=P
i
⊕(E
K
(S
i
)的高j位)
S
i+1
=(S
i
<
i
解密:P
i
=C
i
⊕(E
K
(S
i
)的高j位)
S
i+1
=(S
i
<
i
29
密文反馈CFB
30
输出反馈模式（OFB）
31
分组密码的分析方法
根据攻击者所掌握的信息,可将分组密码的攻击分为以
下几类:
–唯密文攻击
–已知明文攻击
–选择明文攻击
?攻击的复杂度
–数据复杂度:实施该攻击所需输入的数据量
–处理复杂度:处理这些数据所需要的计算量
32
三、公钥密码
33
基本思想
加密与解密由不同的密钥完成
(KP,KS)
加密:X?Y:Y=E
KP
(X)
解密:Y?X:X=D
KS
(Y)=D
KS
(E
KP
(X))
从解密密钥得到加密密钥在计算上是不可行的
34
公钥密码学的历史
76年Diffie和Hellman发表了“密码学的新方
向”，奠定了公钥密码学的基础
公钥技术是二十世纪最伟大的思想之一
改变了密钥分发的方式
可以广泛用于数字签名和身份认证服务
78年，RSA算法
PKI
35
公钥算法的条件
公钥算法的条件：
产生一对密钥是计算可行的
已知公钥和明文，产生密文是计算可行的
接收方利用私钥来解密密文是计算可行的
对于攻击者，利用公钥来推断私钥是计算不可行的
已知公钥和密文，恢复明文是计算不可行的
(可选)加密和解密的顺序可交换
36
如何设计一个公钥算法
公钥和私钥必须相关，而且从公钥到私钥
不可推断
必须要找到一个难题，从一个方向走是容易的，
从另一个方向走是困难的
如何把这个难题跟加解密结合起来
计算可行和不可行的界
37
公钥密码学的研究情况
与计算复杂性理论密切相关
计算复杂性理论可以提供指导
但是需求不尽相同
?计算复杂性通常针对一个孤立的问题进行研究
?而公钥密码学往往需要考虑一些相关的问题
比如，密码分析还需要考虑已知明文、选择明文等相关
的情形
讨论的情形不同
?计算复杂性考虑最坏的情形
?而对于公钥密码学则是不够的
一个困难问题必然会导致一个保密性很好的
密码系统吗？
不一定，还需要有好的构造
38
背包(knapsack)问题
0-1背包问题：
给定一个正整数S和一个背包向量A=(a
1
,…,a
n
)，其中
a
i
是正整数，求满足方程
S=∑a
i
x
i
的二进制向量X=(x
1
,…,x
n
)。
这是一个NP完全问题，解决这个问题所需要的时间
与n呈指数增长
背包问题用于公钥密码学
奥妙在于有两类背包，一类可以在线性时间内求解，
另一类则不能
把易解的背包问题修改成难解的背包问题
?公开密钥使用难解的背包问题
?私钥使用易解的背包问题
39
易解的背包问题——超递增背包
满足下列条件的背包
a
i
>∑a
j
(j=1,…,i-1)
这样的背包也被称为简单背包
求解
从最大的a
i
开始，如果S大于这个数，则减去a
i
,记x
i
为1，
否则记x
i
为0
如此下去，直到最小的a
i
例如背包序列{2,3,6,13,27,52}
求解70的背包
?结果为{2,3,13,52}
?所以，密文70对应的明文为110101
40
转换背包
简单背包用作私钥
如何产生相应的公钥——转换
做法：
选择一个整数m>∑a
i
(i=1,…,n)
然后选择一个与m互素的整数w，然后
a
i
’=wa
i
(modm)(i=1,…,n)
这里的a
i
’是伪随机分布的
这样得到的背包是非超递增背包
41
基于背包问题的公钥密码系统
——MH公钥算法
加密
将明文分为长度为n的块X=(x
1
,…,x
n
)
然后用公钥A’=(a
1
’,…,a
n
’)，将明文变为密文
S
S=E(X)=∑a
i
’
x
i
解密
先计算S’=w
-1
Smodm
再求解简单背包问题
S’=∑a
i
x
i
42
背包密码系统的意义
是第一个公钥密码系统
有较好的理论价值
在实践过程中，大多数的背包方案都已
被破解，或者证明存在缺陷
43
RSA算法
1977年由RonRivest、AdiShamir和Len
Adleman发明，1978年公布
是一种分组加密算法。
明文和密文在0~n-1之间,n是一个正整数
应用最广泛的公钥密码算法
只在美国申请专利，且已于2000年9月到期
44
RSA算法描述
分组大小为k,2
k
k+1
加密:C=M
e
modn
解密:M=C
d
modn=M
ed
modn
公钥:KP={e,n},私钥:KS={d,n}
上述算法需要满足以下条件:
能够找到e,d,n,使得M
ed
modn=M,对所有M
计算M
e
和C
d
相对容易
从e和n得到d是在计算上不可行的
45
公钥密码与私钥密码
公钥密码由于速度慢，直接用于加密效率低
当单向通信的时候，可以采用公钥和私钥结合
的办法。如设B的公开密钥为Pb，A要向B发送
消息m。则A可以用私钥k加密m，再用Pb加密k，
同时把E（k，m）和E（Pb，k）发给B.
当双向通信时，A、B可以利用公钥协商一个
私钥密码的密钥。
46
四、消息认证
47
消息认证
在网络通信中，有一些针对消息内容的攻击方法
伪造消息
窜改消息内容
改变消息顺序
消息重放或者延迟
消息认证：对收到的消息进行验证，证明确实是
来自声称的发送方，并且没有被修改过。
如果在消息中加入时间及顺序信息，则可以完成对时
间和顺序的认证
48
消息认证的四种方式
Messageencryption：用整个消息的密文作为认证
标识
接收方必须能够识别错误
MAC：一个公开函数，加上一个密钥产生一个固
定长度的值作为认证标识
Hashfunction：一个公开函数将任意长度的消息映
射到一个固定长度的散列值，作为认证标识
数字签名
49
Hash函数
Hash是一种直接产生认证码的方法
Hash函数:h=H(x),要求:
可作用于任何尺寸数据且均产生定长输出
H(x)能够快速计算
单向性:给定h，找到x使h=H(x)在计算上不可行
WeakCollisionResistence(WCR)，有时也叫Collision
free：给定x，找到y≠x使H(x)=H(y)在计算上不可行
StrongCollisionResistence(SCR):找到y≠x使H(x)=H(y)
在计算上不可行
50
MD5算法
作者：RonRivest
算法
输入：任意长度的消息
输出：128位消息摘要
处理：以512位输入数据块为单位
51
MD5步骤
第一步：padding
消息最后64位添加消息长度的低64位
在消息及其长度之间填充k长的字符串100…0，k为1~512，使
得最后的总长度是512的倍数！
第二步
把结果分割为512位的块：Y
0
,Y
1
,…Y
L-1
第三步
初始化MDbuffer，128位常量(4个字)，进入循环迭代，共L次
每次：一个输入128位，另一个输入512位，结果输出128位，
用于下一轮输入
第四步
最后一步的输出128位即为hash结果
52
SecureHashAlgorithm简介
1992年NIST制定了SHA(128位)
1993年SHA成为标准
1994年修改产生SHA-1(160位)
1995年SHA-1成为新的标准
SHA-1要求输入消息长度<2
64
SHA-1的摘要长度为160位
基础是MD4
53
SHA-1算法
结构与MD5类似
第一步：pading
与MD5相同，补齐到512的倍数
第二步
分块
第三步
初始化MDbuffer，160位常量(5个字)
进入循环，160输入+512输入-〉160输出
第四步
最后的输出为SHA-1的结果
54
SHA-1算法结论
SHA-1使用big-endian
抵抗生日攻击:160位hash值
没有发现两个不同的512-bit块,它们在
SHA-1计算下产生相同的“hash”
速度慢于MD5
安全性优于MD5
55
MAC(MessageAuthenticationCode)
MAC是一个带密钥的hash函数，也称密码校验
和(cryptographicchecksum)
用户A和用户B，共享密钥K，对于消息M，
MAC=C
K
(M)
如果接收方计算的MAC与收到的MAC匹配，则
接收者可以确信消息M未被改变
接收者可以确信消息来自所声称的发送者
如果消息中含有序列号，则可以保证正确的消息顺序
MAC函数类似于加密函数，但不需要可逆性。
因此在数学上比加密算法被攻击的弱点要少
56
MAC应用方式
M
C
||C
K
C
k
(M)
M
Compare
K
57
HMAC简介
MAC可用块加密算法产生
MAC算法速度慢
加密算法出口受限制
hash函数可用来构造MAC:HMAC为其中
之一
58
HMAC示意图
59
HMAC的定义与特征
对密钥K左边补0以产生一个hash块K+
K
+
每个字节与ipad(00110110)作XOR以产生S
i
对(S
i
||M)进行hash
K
+
每个字节与opad(01011010)作XOR以产生S
0
HMAC=f[IV,S
0
||f(IV,S
i
||M)]
HMAC特征:
可直接使用各种hash算法
可使用将来的更加安全和更加快速的hash算法
保持原始hash算法的性能
密钥的使用简单
与hash函数有同等的安全性
60
hash函数小结
hash函数把变长信息映射到定长信息
hash函数不具备可逆性
hash函数速度较快
hash函数与对称密钥加密算法有某种相似性
对hash函数的密码分析比对称密钥密码更困难
hash函数可用于消息摘要
hash函数可用于数字签名
61
数字签名
传统签名的基本特点:
能与被签的文件在物理上不可分割
签名者不能否认自己的签名
签名不能被伪造
容易被验证
数字签名是传统签名的数字化,基本要求:
能与所签文件“绑定”
签名者不能否认自己的签名
签名不能被伪造
容易被验证
62
数字签名方案
签名
1)A拟向B发送消息m
2)A计算hash（m）
3)A计算s=K
A保密（用于签名）
[hash（m）]
4)A?B:m,s
验证
1)B得到一个m’，s’
2)B计算hash（m’），K
A公开
（s’）；
3)B判断hash（m’）＝K
A公开
（s’）？
63
关于数字签名应该注意的
公钥的解密密钥要与签名密钥分开
假设二者相同
1)K
B公开
(m):A?B
2)C没有K
B保密
，C不能解密K
B公开
(m)
3)C伪造一个消息x=K
B公开
(m)，请B签名，B对x
签名得到:
K
B保密
(x)=K
B公开
[K
B公开
(m)]
=m
!!!
64
关于数字签名应该注意的
先hash，再对hash签名，好处是：
直接签名，速度慢，而hash的速度快，
用hash得到较短的消息摘要，对摘要签
名，速度快。
在通信和签名采用同一对密钥的时候，
可以避免无意地向第3方泄漏你的秘密
65
谢谢！
|
|
